1️⃣ 구현(Implementation) & 탐색(Search)
1-1. 구현(Implementation)
✅ 특징
- 문제의 조건을 그대로 코드로 옮기는 유형
- 자료구조, 알고리즘보다는 코드 작성 능력이 중요
- 문제를 읽고 그대로 따라 쓰면 되는 유형이 대다수
🔑 키워드
- 문자열 처리, 배열 조작, 조건문 & 반복문
📌 대표 예시:
- 문자열 압축
- 좌표 이동
- 숫자 뒤집기
💡 TIP
- 문제 조건을 안 빼먹도록 잘 체크하는 것이 중요
1-2. 시뮬레이션(Simulation)
✅ 특징
- 특정한 동작을 여러 단계에 걸쳐서 직접 구현하는 유형
- 시간에 따른 상태 변화, 이동, 규칙 적용이 많음
🔑 키워드
- 2차원 배열 조작, 움직임 처리, 게임 구현
📌 대표 예시:
- 로봇 이동 시뮬레이션 (방향에 따라 이동 후 최종 좌표 출력)
- 달팽이 배열 (숫자가 시계 방향으로 증가하는 형태의 2차원 배열)
- 테트리스 블록 회전 (2차원 배열을 90도 회전시키기)
💡 TIP
- dx, dy 배열을 활용하여 방향을 쉽게 처리 가능 (3.13 이게 뭔 소리지)
- 문제를 작은 단위로 나누어 처리하면 좋음
1-3. 완전 탐색 (Brute Force)
✅ 특징
- 가능한 모든 경우의 수를 하나하나 다 확인하는 방식
- 최적화 없이 풀기 때문에 O(N!)에 걸릴 수도 있음
🔑 키워드
- 백 트래킹, 순열, 조합, DFS
📌 대표 예시:
- N개의 숫자 중에서 K개를 골라 합이 특정 값이 되는 경우 찾기
- 모든 경로를 다 탐색하는 문제 (예: 미로 탈출)
💡 TIP
- “모든 경우의 수를 따져야 한다”고 생각되면 완전 탐색을 고려
- 백트래킹을 활용해서 불필요한 경우의 수는 미리 제거하면 효율성 증가
1-4. 깊이 우선 탐색(DFS, Depth-First Search)
✅ 특징
- 한 방향으로 탐색을 계속 진행하다가 더 이상 갈 곳이 없으면 되돌아옴
🔑 키워드
- 스택(Stack), 재귀(Recursion), 백트래킹
📌 대표 예시:
- 미로 탐색 (한 경로를 끝까지 가보고 안되면 백트래킹)
- 그래프 연결 요소 개수 찾기
💡 TIP
- 재귀 호출을 사용하면 직관적으로 구현 가능
1-5. 너비 우선 탐색(BFS, Depth-First Search)
✅ 특징
- 한 단계씩 넓게 탐색하며 최단 경로를 찾음
- 최단 거리 문제에 자주 사용됨
🔑 키워드
- 큐(Queue), 최단 경로
📌 대표 예시:
- 미로에서 최단 거리 찾기
- 특정 위치에서 가까운 노드 찾기
💡 TIP
collections.deque를 활용해 큐를 구현하면 빠름(Python)- 방문 체크를 미리 해두면 불필요한 연산을 줄일 수 있음
1-6. 백트래킹 (Backtracking)
✅ 특징
- 완전 탐색의 한 종류지만, 불필요한 탐색을 줄이는 기법
- 가능성이 없는 경우는 더 탐색하지 않고 중단(가지치기, Pruning)
- DFS 기반으로 동작, 재귀 호출 사용
🔑 키워드
- 가지치기(Pruning), DFS, 순열(Permutation), 조합(Combination)
📌 대표 예시:
- N-Queen 문제 (서로 공격하지 않게 N개의 퀸 배치)
- 부분 수열의 합 (주어진 수열에서 부분 집합을 골라 합이 특정 값이 되는 경우 찾기)
- 모든 경우의 수 중 최적해 찾기 (예: 최적의 숫자 조합)
💡 TIP
- 가능성이 없는 경우를 미리 제거하면 연산량이 크게 줄어듦
- DFS와 같이 재귀를 이용하여 구현하는 경우가 많음
2️⃣ 탐색 최적화
2-1. 이진 탐색(Binary Search)
✅ 특징
- 정렬된 배열에서 빠르게 원하는 값을 찾는 알고리즘
- O(log N)
🔑 키워드
- O(log N), 결정 문제, 매개변수 탐색
📌 대표 예시:
- 특정 숫자가 리스트에 있는지 찾기
- 범위를 좁혀가며 특정 조건을 만족하는 값 찾기
💡 TIP
- 정렬된 상태인지 확인하고 사용해야 함
- lower_bound, upper_bound를 알면 좋음
2-1. 투 포인터 (Two Pointers)
✅ 특징
- 두 개의 포인터를 조작하여 효율적으로 문제를 해결하는 방식
- O(N)
🔑 키워드
- O(N), 정렬, 부분 배열
📌 대표 예시:
- 배열에서 특정한 합을 만족하는 두 수 찾기
- 중복 제거하면서 리스트 탐색
💡 TIP
- 정렬된 리스트에서 많이 사용됨
- 정렬되지 않았다면, 먼저 정렬 후 적용
2-3. 슬라이딩 윈도우 (Sliding Window)
✅ 특징
- 일정한 크기의 윈도우를 이동시키면서 최적해를 찾음
🔑 키워드
- 부분 합, 연속된 부분 배열
📌 대표 예시:
- 가장 긴 연속된 부분 수열 찾기
- 특정 합을 가지는 부분 배열 찾기
💡 TIP
- 투 포인터와 비슷하지만, 윈도우 크기가 고정/가변적일 수 있음
- 리스트에서 연속된 부분을 다룰 때 유용
3️⃣ 최적해 찾기
3-1. 그리디 (Greedy)
✅ 특징
- 매 순간 최적의 선택을 하여 최종 해답을 구하는 방식
- 항상 지역적으로 최선의 선택을 하면, 전체적으로도 최선인가? 고민해야 함
🔑 키워드
- 최적해
📌 대표 예시:
- 거스름돈 최소 개수 문제
- 회의실 배정 문제 (빨리 끝나는 회의를 먼저 배정)
- 배낭 문제
💡 TIP
- 정렬과 함께 사용하는 경우가 많음
- 반례가 없는지 항상 체크 (지역적 최적해 ≠ 전체 최적해인 경우가 있음)
3-2. 동적 계획법 (DP, Dynamic Programming)
✅ 특징
- 이전에 계산한 결과를 저장하여 중복 계산을 줄이는 기법
- 작은 문제를 해결한 결과를 저장해서 큰 문제를 해결
- 점화식(Recurrence Relation)을 세우는 것이 핵심
- O(2^N)의 완전 탐색을 O(N)으로 최적화 할 수 있음
🔑 키워드
- 메모이제이션, 최적 부분 구조, 점화식
📌 대표 예시:
- 피보나치 수열
- 배낭 문제
- 최장 증가 부분 수열(LIS, Longest Increasing Subsequence)
💡 TIP
- Top-Down(재귀 + 메모이제이션) vs Bottom-UP(반복문 + DP 테이블) 방식을 구별할 것
- 점화식을 먼저 세우고 코드로 옮기는 연습이 중요
4️⃣ 그래프 & 트리
4-1. 유니온 파인드(Union-Find)
✅ 특징
- 그래프에서 노드들의 연결 여부를 빠르게 확인하는 알고리즘
- 서로소 집합(Disjoint Set) 알고리즘의 핵심
🔑 키워드
- 서로소 집합, 경로 압축
📌 대표 예시:
- 네트워크 연결 여부 확인
- 사이클 판별 (MST에서 사용됨)
💡 TIP
- 경로 압축 최적화를 적용하면 빠름
4-2. 최소 신장 트리 (MST, Minimum Spanning Tree)
✅ 특징
- 그래프에서 모든 노드를 연결하는 최소 비용 트리를 찾는 문제
- 사이클이 없고, V-1개의 간선을 가짐
- 대표적인 알고리즘: 크루스칼(Kruskal) & 프림(Prim)
🔑 키워드
- 최소 비용 연결, 유니온 파인드, 그리디 알고리즘
📌 대표 예시:
- 도시 간 도로 건설 시 최소 비용 찾기
- 네트워크 연결 문제
💡 TIP
- 크루스칼(Kruskal) → 간선을 정렬 + 유니온 파인드 활용
- 프림(Prim) → 우선순위 큐(Heap) 활용
4-3 최단 경로 알고리즘
✅ 특징
- 두 노드 간의 최소 거리를 찾는 문제
- 가중치가 있는 그래프에서 경로 최적화
- 대표적인 알고리즘: 다익스트라, 벨만-포드, 플로이드-워셜
🔑 키워드
- 가중치 그래프, 최단 경로, 우선순위 큐
📌 대표 예시:
- 한 도시에서 다른 도시까지의 최단 거리 찾기
- 물류 배송 비용 최소화 문제
💡 TIP
- 단일 출발점 → 다익스트라 / 벨만-포드
- 모든 노드 간 거리 → 플로이드-워셜
cf)
📍 다익스트라 (Dijkstra)
• 특징: 음수 가중치 X, 우선순위 큐(O((V+E) log V))
• 방법: 현재 가장 짧은 거리의 노드부터 탐색
📍 벨만-포드 (Bellman-Ford)
• 특징: 음수 가중치 O, O(VE)
• 방법: 모든 간선을 V-1번 반복하며 최단 경로 갱신
📍 플로이드-워셜 (Floyd-Warshall)
• 특징: 모든 노드 간 최단 경로, O(V^3)
• 방법: 모든 쌍을 확인하면서 최단 거리 갱신
4-4. 위상 정렬 (Topological Sort)
✅ 특징
- 순서를 정해야 하는 문제에서 등장
- 사이클이 없는 방향 그래프(DAG)에서 노드의 순서를 정하는 알고리즘
- 대표적인 알고리즘: 다익스트라, 벨만-포드, 플로이드-워셜
🔑 키워드
- 방향 그래프(DAG), 선행 관계, 진입 차수
📌 대표 예시:
- 과목 순서 정하기 (선수 과목이 있는 경우)
- 작업 스케쥴링 (Task Scheduling)
💡 TIP
- 진입 차수가 0인 노드부터 큐에 넣고 진행
- BFS 기반(O(V+E)) or DFS 기반(O(V+E))
5️⃣ 비트 연산 & 최적화
5-1. 비트 마스킹 (Bit Masking)
✅ 특징
- 정수를 이진수(Binary)로 변환하여 비트 단위 연산을 수행하는 기법
- 부분 집합 구하기, 상태 저장, 빠른 연산 최적화에 자주 사용됨
🔑 키워드
- & (AND), | (OR), ^ (XOR), << (왼쪽 시프트), >> (오른쪽 시프트)
📌 대표 예시:
- 부분 집합 구하기
- 비트 DP (TSP, 외판원 문제 최적화)
💡 TIP
- 부분 집합을 다룰 때 비트마스크를 사용하면 O(2^N)을 O(N * 2^N)으로 최적화 가능
개발자 지망생