코딩 테스트 준비 - 기초
코딩 테스트에 주로 나오는 4개의 알고리즘 위주로 강의가 구성되어 있습니다.
- 시뮬레이션과 구현
- 브루트 포스
- 그래프와 BFS
- 다이나믹 프로그래밍
강의는 총 3개로 이루어져 있습니다.
- 코딩 테스트 준비 - 기초: 브루트 포스, 그래프와 BFS, 다이나믹 프로그래밍에 대한 기본 이론 설명과 기초 문제들을 풀어봅니다.
- 코딩 테스트 준비 - 연습: 기초에서 설명한 알고리즘의 연습 문제를 풀어봅니다.
- 코딩 테스트 준비 - 문제: 다양한 문제 풀이를 통해서 위의 4개 알고리즘을 연습해봅니다.
강의에 사용하는 언어는 C++, Java, Python3이며, 강의에서 이 3가지 언어에 대해서 모두 설명합니다. 슬라이드에는 C++, Java, Python3 코드가 모두 첨부되어 있습니다.
이 강의는 다음과 같이 구성되어 있습니다.
1. 시간 복잡도와 언어별 유의사항
알고리즘 문제를 해결할 때 가장 중요한 시간 복잡도에 대해서 먼저 알아봅니다. 언어별로 자주 하기 쉬운 실수 몇 가지도 함께 알아봅니다.
2. 수학
주로 사용하는 수학 관련 알고리즘인 소수 판별, 최대 공약수에 대해서 알아봅니다.
- 10430번 - 나머지
- 4375번 - 1
- 1037번 - 약수
- 17427번 - 약수의 합 2
- 17425번 - 약수의 합
- 2609번 - 최대공약수와 최소공배수
- 1978번 - 소수 찾기
- 1929번 - 소수 구하기
- 6588번 - 골드바흐의 추측
3. 브루트 포스
모든 경우의 수를 다 해보는 브루트 포스 알고리즘에 대해서 알아봅니다.
브루트 포스의 개념을 먼저 알아보고, 모든 방법을 만드는 방법인 재귀, 순열, 비트마스크에 대해서 알아봅니다. 재귀가 브루트 포스에서 가장 중요하니 재귀를 위주로 설명을 진행합니다.
다음 문제가 포함되어 있습니다.
브루트 포스
- 2309번 - 일곱 난쟁이
- 3085번 - 사탕 게임
- 1476번 - 날짜 계산
- 1107번 - 리모컨
- 14500번 - 테트로미노
- 6064번 - 카잉 달력
- 1748번 - 수 이어 쓰기 1
- 9095번 - 1, 2, 3 더하기
브루트 포스 - N과 M
- 15649번 - N과 M (1)
- 15650번 - N과 M (2)
- 15651번 - N과 M (3)
- 15652번 - N과 M (4)
- 15654번 - N과 M (5)
- 15655번 - N과 M (6)
- 15656번 - N과 M (7)
- 15657번 - N과 M (8)
- 18290번 - NM과 K (1)
브루트 포스 - 재귀
- 9095번 - 1, 2, 3 더하기
- 1759번 - 암호 만들기
- 14501번 - 퇴사
- 14889번 - 스타트와 링크
- 15661번 - 링크와 스타트
- 2529번 - 부등호
- 1248번 - 맞춰봐
브루트 포스 - 순열
브루트 포스 - 비트마스크
4. 다이나믹 프로그래밍
다이나믹 프로그래밍의 개념과 점화식을 세우는 방법을 자세하게 알아봅니다.
다이나믹 프로그래밍 Part 1
- 1463번 - 1로 만들기
- 11726번 - 2×n 타일링
- 11727번 - 2×n 타일링 2
- 9095번 - 1, 2, 3 더하기
- 11052번 - 카드 구매하기
- 16194번 - 카드 구매하기 2
- 15990번 - 1, 2, 3 더하기 5
- 10844번 - 쉬운 계단 수
- 2193번 - 이친수
- 11053번 - 가장 긴 증가하는 부분 수열
- 14002번 - 가장 긴 증가하는 부분 수열 4
- 1912번 - 연속합
- 1699번 - 제곱수의 합
- 14501번 - 퇴사
- 2225번 - 합분해
다이나믹 프로그래밍 Part 2
- 15988번 - 1, 2, 3 더하기 3
- 1149번 - RGB거리
- 1309번 - 동물원
- 11057번 - 오르막 수
- 2156번 - 포도주 시식
- 1932번 - 정수 삼각형
- 11055번 - 가장 큰 증가 부분 수열
- 11722번 - 가장 긴 감소하는 부분 수열
- 11054번 - 가장 긴 바이토닉 부분 수열
- 13398번 - 연속합 2
- 2133번 - 타일 채우기
5. 그래프와 BFS
가장 중요한 자료구조인 큐에 대해서 알아보고, 그래프와 DFS, 그리고 BFS를 알아봅니다. 이후 BFS를 이용해서 풀 수 있는 문제들을 연습해봅니다.
큐와 그래프
- 10845번 - 큐
- 10866번 - 덱
- 13023번 - ABCDE
- 1260번 - DFS와 BFS
- 11724번 - 연결 요소의 개수
- 1707번 - 이분 그래프
- 2667번 - 단지번호붙이기
- 2178번 - 미로 탐색
- 7576번 - 토마토
- 7562번 - 나이트의 이동
BFS
6. 시뮬레이션과 구현
시뮬레이션과 다양한 구현 문제에 대해서 알아봅니다.
시간 복잡도와 언어별 유의사항
시간 복잡도와 언어별 유의사항00:39:00
수학
나머지 연산00:19:13
약수00:31:27
최대공약수, 소수00:26:36
브루트 포스
브루트 포스00:26:37
일곱 난쟁이 (설명 수정)
날짜 계산, 리모컨, 테트로미노00:39:31
건너 뛰며 해보기00:12:36
브루트 포스 - N과 M
N과 M00:31:05
NM과 K00:12:12
브루트 포스 - 재귀
브루트 포스 - 재귀00:34:48
백트래킹00:34:24
브루트 포스 - 순열
순열00:22:57
순열을 이용한 브루트 포스 문제00:20:07
브루트 포스 - 비트마스크
브루트 포스 - 비트마스크00:41:17
다이나믹 프로그래밍 1
다이나믹 프로그래밍00:18:34
1로 만들기00:17:02
1차원 다이나믹00:28:18
연속과 관련된 다이나믹00:23:01
가장 긴 증가하는 부분 수열00:34:24
제곱수의 합부터 퇴사까지00:12:28
다이나믹 프로그래밍 2
오르막 수까지00:17:57
포도주 시식부터00:34:24
큐와 그래프
큐00:11:01
그래프00:07:13
그래프의 표현00:25:07
그래프의 탐색00:40:36
BFS
BFS - 100:19:37
BFS - 200:24:16
시뮬레이션
배열 돌리기 300:11:06
배열 돌리기 100:09:54
주사위 굴리기부터 톱니바퀴까지00:14:50
로봇 청소기부터 드래곤 커브까지00:22:25
LCD Test부터 컨베이어 벨트 위의 로봇까지00:24:03
참고자료
1 - 시간 복잡도와 언어별 유의사항.pdf
1a - 시간 복잡도와 언어별 유의사항.pdf
1s - 시간 복잡도와 언어별 유의사항.pdf
2 - 수학.pdf
2a - 수학.pdf
2s - 수학.pdf
3-1 - 브루트 포스.pdf
3-1a - 브루트 포스.pdf
3-1s - 브루트 포스.pdf
3-1 - 일곱 난쟁이 (설명 수정).pdf
3-2 - 브루트 포스 - N과 M.pdf
3-2a - 브루트 포스 - N과 M.pdf
3-2s - 브루트 포스 - N과 M.pdf
3-3 - 브루트 포스 - 재귀.pdf
3-3a - 브루트 포스 - 재귀.pdf
3-3s - 브루트 포스 - 재귀.pdf
3-4 - 브루트 포스 - 순열.pdf
3-4a - 브루트 포스 - 순열.pdf
3-4s - 브루트 포스 - 순열.pdf
3-5 - 브루트 포스 - 비트마스크.pdf
3-5a - 브루트 포스 - 비트마스크.pdf
3-5s - 브루트 포스 - 비트마스크.pdf
4-1 - 다이나믹 프로그래밍 1.pdf
4-1a - 다이나믹 프로그래밍 1.pdf
4-1s - 다이나믹 프로그래밍 1.pdf
4-2 - 다이나믹 프로그래밍 2.pdf
4-2a - 다이나믹 프로그래밍 2.pdf
4-2s - 다이나믹 프로그래밍 2.pdf
5-1 - 큐와 그래프.pdf
5-1a - 큐와 그래프.pdf
5-1s - 큐와 그래프.pdf
5-2 - BFS.pdf
5-2a - BFS.pdf
5-2s - BFS.pdf
6 - 시뮬레이션과 구현.pdf
6a - 시뮬레이션과 구현.pdf
6s - 시뮬레이션과 구현.pdf