알고리즘

코테를 위한 알고리즘 유형별 정리 1위~20

king-koopa 2025. 4. 4. 15:26

✅ 알고리즘 유형별 정리 (1위 ~ 20위)

1. 그래프 탐색 (DFS / BFS)

✅ 핵심 개념 요약

그래프에서 모든 정점을 빠짐없이 방문하는 방식
DFS: 깊이 우선 탐색 → 스택 or 재귀
BFS: 너비 우선 탐색 → 큐 사용 (deque)

🧩 자주 쓰는 함수들 요약

함수명 설명

visited = [False] * n	노드 방문 여부 표시
graph = [[] for _ in range(n)]	인접 리스트 방식 그래프 초기화
deque()	BFS에서 큐 자료구조 사용
sys.setrecursionlimit()	깊은 DFS를 위해 재귀 한도 증가

💻 예제 코드

# DFS
def dfs(node):
    visited[node] = True
    for neighbor in graph[node]:
        if not visited[neighbor]:
            dfs(neighbor)

# BFS
from collections import deque
def bfs(start):
    queue = deque([start])
    visited[start] = True
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if not visited[neighbor]:
                visited[neighbor] = True
                queue.append(neighbor)

📝 단계별 연습 문제

BOJ 1260: DFS와 BFS
BOJ 11724: 연결 요소
BOJ 2606: 바이러스
BOJ 2146: 다리 만들기

2. 그리디 (Greedy)

✅ 핵심 개념 요약

매 순간 가장 최적이라고 생각되는 선택을 하는 방식
“항상 지역적 최적이 전체 최적”이어야 성립

🧩 자주 쓰는 함수들 요약

함수명 설명

sorted(arr)	기본 오름차순 정렬
sorted(arr, key=lambda x: ...)	조건 기반 정렬
reverse=True	내림차순 정렬
if 잔여 >= 현재 항목:	조건 판단 시 자주 사용

💻 예제 코드

coins = [500, 100, 50, 10]
amount = 1260
count = 0
for coin in coins:
    count += amount // coin
    amount %= coin

📝 단계별 연습 문제

BOJ 11047: 동전 0
BOJ 11399: ATM
BOJ 1931: 회의실 배정
BOJ 2839: 설탕 배달

3. 정렬

✅ 핵심 개념 요약

내장 정렬 or 조건에 따른 사용자 정의 정렬 사용
정렬 기준이 중요 → lambda 활용

🧩 자주 쓰는 함수들 요약

함수명 설명

sorted(list)	리스트 정렬 (새 리스트 반환)
list.sort()	리스트 자체를 정렬
sorted(arr, key=lambda x: (x[0], -x[1]))	복합 조건 정렬
from operator import itemgetter	빠른 키 추출 정렬 (튜플 등에서 활용)

💻 예제 코드

arr = [(1, 'A'), (3, 'C'), (2, 'B')]
arr.sort(key=lambda x: x[0])

📝 단계별 연습 문제

BOJ 10814: 나이순 정렬
BOJ 11650: 좌표 정렬
BOJ 1181: 단어 정렬
프로그래머스: K번째 수

4. 해시

✅ 핵심 개념 요약

딕셔너리, set 등을 이용한 빠른 탐색/삽입
중복 확인, 개수 세기, 매핑에 유리

🧩 자주 쓰는 함수들 요약

함수명 설명

dict()	기본 해시맵 구조
set()	중복 제거용 집합
collections.Counter()	빈도수 자동 계산
'key' in dict	포함 여부 확인

💻 예제 코드

from collections import Counter
arr = ['a', 'b', 'a', 'c']
counter = Counter(arr)

📝 단계별 연습 문제

프로그래머스: 완주하지 못한 선수
프로그래머스: 베스트앨범
BOJ 1620: 나는야 포켓몬 마스터
BOJ 17219: 비밀번호 찾기

5. 완전탐색 / 백트래킹

✅ 핵심 개념 요약

가능한 모든 경우를 탐색
조건에 따라 가지치기를 하여 시간 단축 (백트래킹)

🧩 자주 쓰는 함수들 요약

함수명 설명

itertools.permutations()	순열 생성
itertools.combinations()	조합 생성
dfs(path) + visited	직접 구현형 완전탐색
if 조건: return	가지치기 로직

💻 예제 코드

def backtrack(path):
    if len(path) == n:
        print(path)
        return
    for i in range(1, n+1):
        if i not in path:
            backtrack(path + [i])

📝 단계별 연습 문제

프로그래머스: 모의고사
BOJ 15649: N과 M
BOJ 9663: N-Queen
BOJ 14888: 연산자 끼워넣기

6. 우선순위 큐 (Heap)

✅ 핵심 개념 요약

항상 가장 작은 값(또는 큰 값)을 빠르게 꺼내기 위한 자료구조
Python의 heapq는 min-heap이 기본이므로, 최대 힙은 값 사용

🧩 자주 쓰는 함수들 요약

함수명 설명

heapq.heapify(list)	리스트를 힙 구조로 바꿈
heapq.heappush(heap, item)	힙에 새로운 값 추가
heapq.heappop(heap)	힙에서 가장 작은 값 꺼냄
heapq.heappushpop(heap, item)	아이템을 넣고 가장 작은 값 바로 꺼냄
heapq.nlargest(n, iterable)	가장 큰 값 n개 반환
heapq.nsmallest(n, iterable)	가장 작은 값 n개 반환

💻 예제 코드

import heapq
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
print(heapq.heappop(heap))  # 1

📝 단계별 연습 문제

BOJ 1927: 최소 힙
BOJ 11279: 최대 힙
BOJ 1715: 카드 정렬
프로그래머스: 더 맵게

7. 이분 탐색

✅ 핵심 개념 요약

정렬된 범위에서 원하는 값을 빠르게 찾는 알고리즘
보통 탐색 대상이 정답이 될 수 있는 값일 때 사용 (parametric search)

🧩 자주 쓰는 함수들 요약

함수명 설명

bisect_left(arr, x)	x 이상의 첫 위치
bisect_right(arr, x)	x 초과의 첫 위치
while left <= right:	이분 탐색 루프 구조
mid = (left + right) // 2	중간 지점 계산

💻 예제 코드

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

📝 단계별 연습 문제

BOJ 1920: 수 찾기
BOJ 1654: 랜선 자르기
BOJ 2805: 나무 자르기
프로그래머스: 입국 심사

8. 투 포인터 / 슬라이딩 윈도우

✅ 핵심 개념 요약

두 개의 포인터를 사용해 연속된 구간을 탐색
투 포인터는 정렬된 배열에서 조건 만족하는 범위를 찾고, 슬라이딩 윈도우는 고정된 크기의 연속 구간 활용

🧩 자주 쓰는 함수들 요약

함수명 설명

left, right	양쪽 포인터 선언
sum += arr[right], sum -= arr[left]	범위 값 조절
while sum > target:	조건 만족 구간 축소
max_len = max(max_len, right - left + 1)	최대 길이 갱신 등 응용

💻 예제 코드

arr = [1, 2, 3, 4, 5]
left = right = 0
sum_ = 0
while right < len(arr):
    sum_ += arr[right]
    while sum_ > target:
        sum_ -= arr[left]
        left += 1
    right += 1

📝 단계별 연습 문제

BOJ 2003: 수들의 합 2
BOJ 1806: 부분합
프로그래머스: 연속 부분 수열

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

✅ 핵심 개념 요약

작은 문제의 결과를 저장하고 이를 바탕으로 큰 문제를 해결
점화식을 세우고, 메모이제이션 또는 탑다운/바텀업 방식 사용

🧩 자주 쓰는 함수들 요약

함수명 설명

dp = [0] * n	1차원 DP 테이블 초기화
dp[i] = dp[i-1] + dp[i-2]	점화식 기본 형태
@lru_cache(None)	재귀 메모이제이션
dp = [[0]*m for _ in range(n)]	2차원 DP 테이블

💻 예제 코드

dp = [0] * (n + 1)
dp[1], dp[2] = 1, 1
for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

📝 단계별 연습 문제

BOJ 9095: 1, 2, 3 더하기
BOJ 1149: RGB 거리
BOJ 2156: 포도주 시식
프로그래머스: 정수 삼각형

10. Union-Find (Disjoint Set)

✅ 핵심 개념 요약

서로소 집합(Disjoint Set)을 관리
두 원소가 같은 집합인지 확인하거나, 합치기 위해 사용
경로 압축으로 시간 최적화

🧩 자주 쓰는 함수들 요약

함수명 설명

find(x)	루트 노드 찾기
union(a, b)	두 집합 합치기
parent = [i for i in range(n)]	초기 부모 배열 설정
if find(a) == find(b):	같은 집합인지 확인

💻 예제 코드

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(a, b):
    a, b = find(a), find(b)
    if a != b:
        parent[b] = a

📝 단계별 연습 문제

BOJ 1717: 집합의 표현
BOJ 1976: 여행 가자
BOJ 4195: 친구 네트워크
프로그래머스: 네트워크

11. 비트마스킹

✅ 핵심 개념 요약

정수의 이진 표현을 이용해 상태, 집합 등을 표현하는 방식
보통 집합의 포함 여부나 부분집합을 순회할 때 사용

🧩 자주 사용하는 함수 / 메서드

함수명 설명

1 << i	i번째 비트 값 생성 (2ⁱ)
x & (1 << i)	i번째 비트가 1인지 확인
x & ~(1 << i)	i번째 비트를 0으로 설정
bin(x).count('1')	1의 개수 (집합 원소 수 등)

💻 예제 코드

n = 3
for i in range(1 << n):
    for j in range(n):
        if i & (1 << j):
            print(j, end=' ')
    print()

📝 단계별 연습 문제

BOJ 11723: 집합
BOJ 1285: 동전 뒤집기
BOJ 2098: 외판원 순회

12. 누적합 / 구간합

✅ 핵심 개념 요약

누적합 배열을 미리 만들어놓고 구간합을 빠르게 계산
2차원 누적합, 나머지 합, 차이 배열 등으로 확장 가능

🧩 자주 사용하는 함수 / 메서드

함수명 설명

prefix[i] = prefix[i-1] + arr[i]	누적합 배열 생성
prefix[b] - prefix[a-1]	[a, b] 구간합
sum(arr[a:b+1])	슬라이싱으로 구간합 (비효율적)

💻 예제 코드

arr = [1, 2, 3, 4, 5]
prefix_sum = [0]
for num in arr:
    prefix_sum.append(prefix_sum[-1] + num)

# 구간합 (2~4 구간)
print(prefix_sum[4] - prefix_sum[1])

📝 단계별 연습 문제

BOJ 11659: 구간 합 구하기 4
BOJ 2559: 수열
BOJ 10986: 나머지 합

13. 문자열 처리

✅ 핵심 개념 요약

문자열 슬라이싱, 파싱, 비교, 패턴 매칭 등
투포인터, 해시, DP 등과 함께 쓰이는 경우 많음

🧩 자주 사용하는 함수 / 메서드

함수명 설명

s[::-1]	문자열 뒤집기
s.find('a'), s.count('a')	탐색, 개수 세기
ord(char), chr(num)	아스키 변환
'substr' in s	부분 문자열 여부
s.split(), s.strip()	문자열 분리 및 정리

💻 예제 코드

s = "racecar"
print(s == s[::-1])  # 팰린드롬 판별

📝 단계별 연습 문제

BOJ 1543: 문서 검색
BOJ 5582: 공통 부분 문자열
프로그래머스: 가장 긴 팰린드롬

14. 최단 경로 (다익스트라, 플로이드)

✅ 핵심 개념 요약

그래프에서 최단 거리 계산
단일 시작점 → 다익스트라, 모든 쌍 → 플로이드

🧩 자주 사용하는 함수 / 메서드

함수명 설명

heapq.heappush / heappop	우선순위 큐로 다익스트라 구현
dist = [inf] * n	거리 배열 초기화
dist[start] = 0	시작점 초기화
3중 for문	플로이드 워셜

💻 예제 코드

import heapq
def dijkstra(start):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    hq = [(0, start)]
    while hq:
        cost, now = heapq.heappop(hq)
        if dist[now] < cost:
            continue
        for next, weight in graph[now]:
            if cost + weight < dist[next]:
                dist[next] = cost + weight
                heapq.heappush(hq, (dist[next], next))

📝 단계별 연습 문제

BOJ 1753: 최단 경로
BOJ 1504: 특정한 최단 경로
BOJ 1238: 파티

15. 트리 탐색 (DFS 기반)

✅ 핵심 개념 요약

트리는 사이클이 없는 연결 그래프
부모/자식 관계, 서브트리 탐색 등에 DFS 사용

🧩 자주 사용하는 함수 / 메서드

함수명 설명

tree = [[] for _ in range(n)]	트리 구조 생성
dfs(node, parent)	재귀 DFS
preorder / postorder	순회 방식
if child != parent:	역방향 방지

💻 예제 코드

def dfs(node, parent):
    for child in tree[node]:
        if child != parent:
            dfs(child, node)

📝 단계별 연습 문제

BOJ 11725: 트리의 부모 찾기
BOJ 1991: 트리 순회
BOJ 1240: 노드 사이의 거리

16. 시뮬레이션

✅ 핵심 개념 요약

문제에서 주어진 조건과 과정을 그대로 구현
방향 이동, 시간 흐름, 상태 변화 등을 반복적으로 시뮬레이션

🧩 자주 사용하는 함수 / 메서드

함수명 설명

dx, dy	방향 벡터 정의 (상하좌우 등)
while, for	시간 흐름 또는 반복 조건
if 조건:	상태 변화 조건
rotate(arr)	회전 구현 필요시

💻 예제 코드

dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
x, y, d = 0, 0, 0
for _ in range(k):
    nx, ny = x + dx[d], y + dy[d]
    if valid(nx, ny):
        x, y = nx, ny

📝 단계별 연습 문제

BOJ 14503: 로봇 청소기
BOJ 14891: 톱니바퀴
BOJ 3190: 뱀

17. 위상 정렬 (Topological Sort)

✅ 핵심 개념 요약

사이클이 없는 방향 그래프(DAG)에서 선후 관계를 고려한 순서 정렬
진입 차수가 0인 노드부터 차례대로 처리

🧩 자주 사용하는 함수 / 메서드

함수명 설명

indegree = [0] * n	진입차수 배열
deque()	위상 정렬 큐
if indegree[i] == 0:	진입차수 0이면 큐에 삽입
indegree[next] -= 1	간선 제거

💻 예제 코드

from collections import deque
indegree = [0] * (n + 1)
queue = deque()

for i in range(1, n + 1):
    if indegree[i] == 0:
        queue.append(i)

while queue:
    now = queue.popleft()
    for next in graph[now]:
        indegree[next] -= 1
        if indegree[next] == 0:
            queue.append(next)

📝 단계별 연습 문제

BOJ 2252: 줄 세우기
BOJ 1005: ACM Craft
BOJ 1516: 게임 개발

18. 세그먼트 트리 (Segment Tree)

✅ 핵심 개념 요약

구간 합, 구간 최솟값/최댓값 등을 빠르게 구할 수 있는 트리
크기가 고정된 배열을 트리 구조로 변형

🧩 자주 사용하는 함수 / 메서드

함수명 설명

build(node, start, end)	트리 생성
update(node, start, end, index, diff)	값 갱신
query(node, start, end, l, r)	구간 질의
tree = [0] * (4 * n)	트리 배열 초기화

💻 예제 코드

def build(node, start, end):
    if start == end:
        tree[node] = arr[start]
    else:
        mid = (start + end) // 2
        build(node*2, start, mid)
        build(node*2+1, mid+1, end)
        tree[node] = tree[node*2] + tree[node*2+1]

📝 단계별 연습 문제

BOJ 2042: 구간 합 구하기
BOJ 11505: 구간 곱 구하기
BOJ 12844: XOR 구간 갱신

19. 펜윅 트리 (Fenwick Tree / Binary Indexed Tree)

✅ 핵심 개념 요약

세그먼트 트리보다 구현이 쉬우며, 누적합 구간 질의에 효과적
1-based 인덱스로 구성됨

🧩 자주 사용하는 함수 / 메서드

함수명 설명

update(i, diff)	i번째 값을 diff만큼 갱신
prefix_sum(i)	1~i 누적합 계산
i += i & -i	다음 노드
i -= i & -i	부모 노드

💻 예제 코드

def update(i, diff):
    while i <= n:
        tree[i] += diff
        i += i & -i

def prefix_sum(i):
    result = 0
    while i > 0:
        result += tree[i]
        i -= i & -i
    return result

📝 단계별 연습 문제

BOJ 2042 (Fenwick 버전으로 풀기)
BOJ 11658: 구간 합 구하기 2

20. 트라이 (Trie)

✅ 핵심 개념 요약

문자열의 공통 접두사를 저장하는 트리 자료구조
문자열 탐색, 자동완성 등에 사용

🧩 자주 사용하는 함수 / 메서드

함수명 설명

TrieNode	자식 노드 딕셔너리 + end 표시
insert(word)	단어 삽입
search(word)	단어 존재 여부 확인
startsWith(prefix)	접두사 확인

💻 예제 코드

class TrieNode:
    def __init__(self):
        self.children = dict()
        self.end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        cur = self.root
        for ch in word:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
        cur.end = True

📝 단계별 연습 문제

BOJ 14425: 문자열 집합
BOJ 5052: 전화번호 목록
프로그래머스: 자동완성

'알고리즘' 카테고리의 다른 글

프로그래머스 - 보석 쇼핑 with.Python (1)	2025.06.16
PCCP 모의고사 2회 3번 문제 - 카페 확장 (0)	2025.05.09
석유 시추 (0)	2025.04.14

현재글코테를 위한 알고리즘 유형별 정리 1위~20

눈뜨고 코딩해라

min 님의 개발블로그 입니다.

ssafy, 옵저버 패턴, 팩토리 패턴, MVP 패턴, 프록시 패턴, 프로그래머스, MVC 패턴, 전략 패턴, 이터레이터 패턴, 2024, PCCP, BFS, 싱글톤 패턴, 해시맵, 삼성 청년 SW 아카데미, 슬라이딩 윈도우, programmers, mvvm 패턴, 비전공, pccp 모의고사,

Today :
Yesterday :

눈뜨고 코딩해라

코테를 위한 알고리즘 유형별 정리 1위~20

✅ 알고리즘 유형별 정리 (1위 ~ 20위)

📌 목차

1. 그래프 탐색 (DFS / BFS)

2. 그리디 (Greedy)

3. 정렬

4. 해시

5. 완전탐색 / 백트래킹

6. 우선순위 큐 (Heap)

7. 이분 탐색

8. 투 포인터 / 슬라이딩 윈도우

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

10. Union-Find (Disjoint Set)

11. 비트마스킹

12. 누적합 / 구간합

13. 문자열 처리

14. 최단 경로 (다익스트라, 플로이드)

15. 트리 탐색 (DFS 기반)

16. 시뮬레이션

17. 위상 정렬 (Topological Sort)

18. 세그먼트 트리 (Segment Tree)

19. 펜윅 트리 (Fenwick Tree / Binary Indexed Tree)

20. 트라이 (Trie)

'알고리즘' 카테고리의 다른 글

'알고리즘'의 다른글

티스토리툴바

« 2026/03 »
일	월	화	수	목	금	토
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

코테를 위한 알고리즘 유형별 정리 1위~20

✅ 알고리즘 유형별 정리 (1위 ~ 20위)

📌 목차

1. 그래프 탐색 (DFS / BFS)

2. 그리디 (Greedy)

3. 정렬

4. 해시

5. 완전탐색 / 백트래킹

6. 우선순위 큐 (Heap)

7. 이분 탐색

8. 투 포인터 / 슬라이딩 윈도우

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

10. Union-Find (Disjoint Set)

11. 비트마스킹

12. 누적합 / 구간합

13. 문자열 처리

14. 최단 경로 (다익스트라, 플로이드)

15. 트리 탐색 (DFS 기반)

16. 시뮬레이션

17. 위상 정렬 (Topological Sort)

18. 세그먼트 트리 (Segment Tree)

19. 펜윅 트리 (Fenwick Tree / Binary Indexed Tree)

20. 트라이 (Trie)

'알고리즘' 카테고리의 다른 글

'알고리즘'의 다른글

관련글

티스토리툴바