코딩테스트 연습 레포

DP(다이나믹 프로그래밍)

• 반복되는 작은 문제부터 시작
• 답을 저장해가며 재귀적으로 사용
• 점화식 작성
• 연습문제

그래프 탐색 (BFS, DFS)

• 넓이 우선 탐색, 깊이 우선 탐색
• 하나의 정점에서 시작하여 한번씩 방문
• BFS: 큐를 이용하여 구현 (최단거리에 유리)
• DFS: 스택 또는 재귀로 구현 (검색 그래프가 클 경우)
• 연습문제

이분탐색

• 양단에서 시작하여 중간지점 찾기
• 연습문제

분할정복

• 해결할 수 없을 정도로 거대한 문제를 조금씩 나눠가며 풀이
• 테이블에 캐시하지 않는 점이 DP와 다름
• 재귀를 이용하여 구현
• 연습문제

그리디

• 현 단계에서 가장 최선의 선택
• 예시) 최소값이 최대가 되도록 분배
• 연습문제

완전탐색

위상정렬

• 순서가 정해져있는 작업
• prev와 next를 노드로 연결
• 큐나 스택을 이용하여 구현
• 연습문제