[WIL] 2주차
·
크래프톤 정글/마이 정글(WIL, 에세이)
03.20알고리즘 문제 풀이 (BOJ 1629 1655 1715 1920 2110 2164 2470 2493 2504 2630 2805 2812 8983 9012 10773 10828 11053 11279 11866 17608 18258)  03.21키워드 정리: 이분 탐색https://just-live.tistory.com/entry/CS%EA%B8%B0%EC%B4%88-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89Binary-Search [CS기초] 이분 탐색(Binary Search)이분 탐색 (Binary Search) 개요이분 탐색은 정렬된 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법인데요. 이분 탐..
[중간정리] 1주차 - 재귀 함수, 피보나치 수열, 퀵 정렬, CPU의 PC/ALU
·
크래프톤 정글/CS기초(키워드, 개념정리)
재귀 함수재귀 함수의 장단점장점코드가 직관적이고 간결해 이해하기 쉽다.단점호출 시 추가적으로 메모리를 사용해 메모리 소비가 많고, 과도한 호출 시 스택 오버플로우가 발생할 수 있다.반복문에 비해 실행 속도가 느리다. 피보나치 수열 반환 함수1항부터 n항까지의 피보나치 수열 반환 함수를 반복문/재귀문으로 각각 만들어보기. n이 0~2에 대한 처리는 두 방식 모두 같았다. 다만 n이 3이상일 때 원래 수열을 가지고 계속 덧붙여가느냐(반복문), 직전 n-1에 대한 피보나치 수열을 새롭게 불러와 덧붙여 반환하느냐(재귀문)의 차이가 있었다.반복문으로 구현한 피보나치 수열 반환 함수def pivo(n): if n == 0: return [] elif n == 1: return [..
[알고리즘] 백트래킹 기본 예제 코드(순열, 조합)
·
크래프톤 정글/CS기초(키워드, 개념정리)
백트래킹으로 순열, 조합 구하기백트래킹은 탐색 과정에서 불필요한 경로를 미리 차단하여 효율적으로 해를 찾는 기법인데요. 이를 활용하면 순열과 조합을 생성할 때, 가능한 모든 경우를 탐색하면서도 불필요한 연산을 줄일 수 있습니다.  순열 (같은 수 중복 X)n, m = map(int, input().split())arr = [x for x in range(1, n+1)]result = [0] * mvisited = [False] * ndef func(k): if k == m: print(*result) return for i in range(n): if not visited[i]: visited[i] = True res..
[CS기초] 정수론(Number Theory)
·
크래프톤 정글/CS기초(키워드, 개념정리)
정수론 개요정수론은 정수의 성질 또는 정수가 등장하는 경우들을 연구하는 학문으로, 수학 체계에서 원점이자 정점 그 자체라고 할 수 있는데요. 기초 수준에서는 정수 그 자체보다는 자연수, 그 중에서도 소수를 중점적으로 다룹니다. 소수 (Prime Number)1과 자기 자신으로만 나눠지는 수. 즉, 약수가 2개이며 2부터 N-1까지의 수로 나눠지지 않는 수를 말합니다.소수 판정법합성수(소수가 아닌 수)  N에서 1을 제외한 가장 작은 약수는 √N 이하라는. 그렇기 때문에 2부터 √N 이하의 자연수로 해당 수를 나눠보면 됩니다. 만약 도중에 나누어 떨어지게 되면 합성수, 아니라면 소수가 됩니다.# 소수 판별 함수def is_prime(number): if number == 1: return..
[CS기초] 완전 탐색(Brute Force)
·
크래프톤 정글/CS기초(키워드, 개념정리)
완전 탐색 (Brute Force) 개요완전 탐색은 가능한 모든 경우의 수를 탐색하여 정답을 찾아내는 알고리즘인데요. 직관적이고 단순하지만, 경우의 수가 많아지면 시간 효율이 나빠질 수 있습니다. 완전 탐색의 종류단순 브루트 포스 (Brute Force)가능한 모든 방법을 단순하게 시도하는 기법반복문과 조건문을 활용해 모든 경우를 하나씩 검사ex) 비밀번호를 0000~9999까지 하나씩 대입하여 찾는 방식백트래킹 (Backtracking)되돌아가면서 모든 경로를 탐색하는 기법.탐색 중 해당 경로가 조건에 맞지 않으면 탐색을 중단하고 되돌아가 다른 경로를 탐색한다.불필요한 탐색을 줄이기 때문에 단순 브루트 포스보다 효율적ex) N-Queen 문제, 미로 찾기순열 (Permutation)서로 다른 n개의 원..
[CS기초] 정렬(Sort)
·
크래프톤 정글/CS기초(키워드, 개념정리)
정렬 알고리즘 개요정렬 알고리즘은 데이터를 특정 기준에 따라 순서대로 정렬하는 방법을 의미합니다. 정렬 알고리즘에는 다양한 정렬 방식이 존재하는데요. 시간 복잡도와 공간 복잡도, 사용 목적에 따라 각각의 알고리즘을 적절히 선택해야 합니다. 기본 정렬 알고리즘기본적인 정렬 알고리즘에는 대표적으로 버블 정렬, 선택 정렬, 삽입 정렬이 있는데요. 비교적 단순한 로직을 사용하며, 주로 작은 데이터 집합에서 사용됩니다. 세 방식 모두 시간 복잡도가 O(N2)인 정렬 방법입니다.버블 정렬 (Bubble Sort)인접한 두 요소를 비교해 더 큰 값을 오른쪽으로 이동시키며 정렬데이터가 거의 정렬된 경우 비교적 빠르게 동작하지만, 최악의 경우 O(N2)의 시간 복잡도를 가짐선택 정렬 (Selection Sort)주어진 ..
[CS기초] 알고리즘 복잡도(Big-O Notation)
·
크래프톤 정글/CS기초(키워드, 개념정리)
Big-O 표기법알고리즘의 성능을 분석할 때에는 시간 복잡도와 공간 복잡도를 고려해야 하는데요. 이를 표현하는 대표적인 방법이 Big-O 표기법입니다.알고리즘의 실행 시간 또는 메모리 사용량이 입력 크기(n)에 따라 어떻게 변하는지 나타내는 표기법보통 최악의 경우(Worst Case)를 기준으로 성능을 분석가장 큰 차수만 나타내고, 계수는 무시 ( 예) O(3N + 5) → O(N) ) 시간 복잡도 (Time Complexity)알고리즘이 실행되는 데 걸리는 연산 횟수의 증가율을 나타냅니다.주요 시간 복잡도 유형시간 복잡도설명예제O(1)상수 시간. 입력 크기에 관계없이 실행 시간이 일정배열 인덱싱, 스택 push / popO(logN)로그 시간. 입력 크기가 2배가 되어도 실행 시간은 조금만 증가이진 탐..
[CS기초] 반복문(Loop), 재귀 함수(Recursion Function)
·
크래프톤 정글/CS기초(키워드, 개념정리)
반복문 (Loop)일정한 코드를 특정 횟수만큼 또는 특정 조건을 달성할 때까지 반복하는 구문특정 횟수만큼 반복 → for 문특정 조건을 만족할 때까지 반복 → while 문, do-while 문 재귀 함수 (Recursion Function)하나의 함수가 자기 자신을 다시 호출하여 작업을 수행하는 함수재귀 함수의 특징직관적이고 코드가 간결하다호출 연산이 추가적으로 필요하므로 메모리나 실행 시간을 더 잡아먹는다한 함수가 자기 자신을 여러 번 호출하면 비효율적일 수 있다. (피보나치 수열 등)재귀 호출이 많아지는 경우 스택 메모리가 부족할 수 있다.단, 예외적으로 재귀 호출 이후에 추가 연산이 없는(결과를 그대로 반환하는) 꼬리 재귀의 경우 스택을 추가로 사용하지 않음.귀납적 사고경험적 사실을 바탕으로 원리..