코딩테스트를 위한 필수 핵심 알고리즘 Best 10

🥇 1. 완전 탐색 (Brute Force)

• 개요: 가능한 모든 경우의 수를 무식하게 다 찾아보는 방법입니다.
• 핵심 기법: for/while 반복문, 순열/조합(itertools), 재귀함수, 백트래킹(Backtracking).
• 자주 나오는 문제: N-Queen, 비밀번호 찾기, 특정 조건을 만족하는 부분 수열 구하기.

🥇 2.DFS / BFS (그래프 탐색)

• 개요: 코딩 테스트 최고 빈출 유형입니다. 지도나 네트워크에서 특정 목적지까지 가는 길을 찾거나 연결된 덩어리를 찾을 때 씁니다.
• DFS(깊이 우선 탐색): 재귀함수나 스택을 이용. 주로 백트래킹이나 연결된 영역(Connected Component)의 개수를 셀 때 사용.
• BFS(너비 우선 탐색): 큐(Queue)를 이용. 가중치가 동일한 그래프에서 최단 거리/최소 시간을 구할 때 무조건 사용.
• 자주 나오는 문제: 미로 탐색, 바이러스 전파, 섬의 개수 구하기.

🥈 3. 정렬(Sorting) & 해시 (Hash)

• 개요: 데이터를 순서대로 나열하거나, 딕셔너리를 이용해 데이터를 빠르게 매핑하는 기본기입니다.
• 핵심 기법: 파이썬 내장 함수(sort(), sorted()), 딕셔너리(dict), set 활용. 커스텀 정렬 기준(lambda) 작성법 숙지 필수.
• 자주 나오는 문제: 점수 순 정렬 후 조건 계산, K번째 수 찾기, 중복 제거.

🥈 4. 이진 탐색 (Binary Search)

• 개요: 정렬된 데이터 안에서 특정 값을 $O(\log N)$이라는 엄청난 속도로 찾아내는 알고리즘입니다.
• 핵심 기법: start, end, mid 포인터를 이용해 탐색 범위를 반씩 줄여나갑니다. 파이썬의 bisect 라이브러리 활용.
• 자주 나오는 문제: 파라메트릭 서치(최적화 문제를 결정 문제로 바꾸어 풀기 - 예: 예산 분배, 랜선 자르기).

🥈 5. 그리디 알고리즘 (Greedy)

• 개요: 현재 상황에서 당장 가장 좋아 보이는 것만 선택하는 방법입니다.
• 핵심 기법: 정렬이나 우선순위 큐(Heap)를 사용하여 가장 큰 값이나 작은 값을 반복적으로 뽑아냅니다.
• 자주 나오는 문제: 거스름돈 최소 동전 개수, 회의실 배정 (시간표 짜기).

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

• 개요: 큰 문제를 작은 문제로 쪼개고, 한 번 계산한 결과는 배열에 저장해두고 재활용(Memoization)하는 기법입니다.
• 핵심 기법: 1차원/2차원 배열 초기화, 점화식 세우기.
• 자주 나오는 문제: 피보나치 수열, 0-1 배낭 문제(Knapsack), 계단 오르기 최댓값 구하기.

🥉 7. 다익스트라 (Dijkstra)

• 개요: 한 지점에서 다른 모든 지점까지의 최단 경로를 구하는 알고리즘입니다. (단, 간선 가중치가 다를 때 사용)
• 핵심 기법: 우선순위 큐(heapq)를 이용해 가장 비용이 적은 노드부터 방문.
• 자주 나오는 문제: 도시 간 최단 이동 비용, 내비게이션 경로 탐색.

🥉 8. 시뮬레이션 / 구현

• 개요: 특별한 알고리즘적 지식보다는, 문제에서 제시한 복잡한 규칙을 코드로 빠짐없이 정확하게 구현하는 능력을 봅니다.
• 자주 나오는 문제: 삼성 SW 역량테스트 기출(주사위 굴리기, 뱀 이동하기 등 2차원 배열 다루기).

🎖 9. 투 포인터 (Two Pointers) / 슬라이딩 윈도우

• 개요: 1차원 배열에서 두 개의 포인터 위치를 조작하면서 원하는 결과를 얻어내는 방법입니다.
• 자주 나오는 문제: 연속된 부분 배열의 합 구하기, 두 수의 합(2-Sum) 구하기.

🎖 10. 크루스칼 (Kruskal) / 유니온 파인드 (Union-Find)

• 개요: 노드들을 하나로 합치거나(Union), 같은 그룹인지 확인(Find)할 때 사용하며, 이를 응용해 최소 신장 트리(MST)를 만듭니다.
• 자주 나오는 문제: 모든 섬(노드)을 가장 적은 비용으로 연결하기 (네트워크 연결).