Google DSC Sookmyung

목차 1. 개념 정리 (1) 수학 (2) 이분탐색, 투포인터 (3) 해시 2. 5주차 필수 문제 풀이 (1) A - 베르트랑 공준 (백준 4948번) (2) B - 게으른 백곰 (백준 10025번) (3) C - 랜선 자르기 (백준 1654번) (4) D - 어깨동무 (백준 27932번) (5) E - 콰트로치즈피자 (백준 27964번) 1. 개념 정리 (1) 수학 1. 소수 판정법 합성수 N에서 1을 제외한 가장 작은 약수는 ${\sqrt N}$ ex) N = 18 → 2 ≤ $\sqrt 18$ ex) N = 25 → 5 ≤ $\sqrt 25$ ex) N = 21 → 3 ≤ $\sqrt 21$ 즉, 2부터 $\sqrt N$까지의 수로 나누어지지 않으면 소수임을 알 수 있음. 시간 복잡도 $O(\sqrt..

목차 1. 개념 정리 (1) 정렬 (2) 다이나믹 프로그래밍 (3) 그리디 2. 4주 차 필수 문제 풀이 (1) A - 단어 정렬 (백준 1181번) (2) B - 팔찌 만들기 (백준 25707번) (3) C - 개발자 지망생 구름이의 취업 뽀개기 (백준 29155번) (4) D - 피보나치 비스무리한 수열 (백준 14495번) (5) E - 연속합 (백준 1912번) 1. 개념 정리 (1) 정렬 1 -1. Merge Sort 재귀적으로 수열을 나눠 정렬한 후 합치는 정렬법이다. 시간복잡도 O(NlogN)에 동작한다. 길이 N과 길이 M 인 리스트가 만나 길이 N + M의 정렬된 리스트를 만든다. 길이 N과 길이 M의 나머지 중 가장 앞에 있는 원소를 비교해 채워넣는다. O(N+M) 수행 가능 분할하는 ..

목차 1. 개념 정리 (1) 재귀 (2) 백트래킹 2. 3주 차 필수 문제 풀이 (1) A - 눈덩이 굴리기 (백준 21735번) (2) B - 222-풀링 (백준 2164번) (3) C - 하노이 탑 이동 순서 (백준 11729번) (4) D - N과 M(7) (백준 15656번) (5) E - 스도쿠(백준 2239번) 1. 개념 정리 (1) 재귀 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘이다. 어떤 문제를 재귀로 푼다는 것은 곧 귀납적인 방식으로 문제를 해결하겠다는 것이다. 이때 재귀 함수의 조건은 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 하며(Base condition), 모든 입력은 base condition으로 수렴해야 한다. [ 재귀의 특징 ] - 함수..

목차 1. 개념 정리 (1) 스택 (2) 큐 (3) 덱 (4) BFS (5) DFS 2. 2주차 필수 문제 풀이 (1) A - 괄호 (백준 9012번) (2) B - 카드2 (백준 2164번) (3) C - 알파벳 블록 (백준 27497번) (4) D - 바닥 장식 (백준 1388번) (5) E - W키가 빠진 성원이 (백준 28471번) 1. 개념 정리 (1) 스택 한쪽 끝에서만 원소를 넣거나 뺄 수 있는 자료구조이다. (FIrst In Last Out) 따라서 특정 위치에서만 원소가 변경될 수 있는 특성상 원소의 추가와 제거의 시간 복잡도가 모두 O(1)이다. 또한 스택에서는 제일 상단이 아닌 나머지 원소들의 확인/변경 기능이 제공되지 않는다. (2) 큐 한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를..

목차 1. 복잡도 2. 자료형 3. C++ 표준 입출력 4. 배열 5. 1주차 필수 문제 풀이 1. 복잡도 시간복잡도 : 입력의 크기와 문제를 해결하는데 걸리는 시간의 상관관계 - 주로 O 표기법(가장 큰 대표항으로 시간복잡도를 나타내는 방법)을 이용하여 표기한다. - O(1) < O(log N) < O(N) < O(N log N) < O(N^2) < O(2^N) < O(N!) 공간복잡도 : 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계 - 배열의 차원과 관련되어있다. 2. 자료형 정수 자료형 : char(1 byte), short(2 byte), int(4 byte), long long(8 byte) *1 byte = 8 bit - 할당된 메모리 범위를 넘어서는 경우 overflow 및 und..