// fullstack developer

Gunmo's Dev Life

personal · algorithm

BAEKJOON Online Judge

코딩 테스트 대비 알고리즘 풀이 기록 — 유형별로 대표 문제와 핵심 아이디어를 정리

2016.06 –GitHub ↗백준 프로필 ↗

109

레포 풀이

25

분류

C++

주 언어 (+Java, Python)

2016

시작

01유형 분포

DP

20

자료구조

10

그리디

8

브루트포스

8

이분 탐색

8

최단 경로

8

분할 정복

7

정수론

6

BFS

5

분리 집합

4

최단 경로 = 다익스트라 + 플로이드 와샬, 자료구조 = 스택 · 큐/덱 · 우선순위 큐 · 맵

02대표 문제 요점 정리

DP

2098외판원 순회dp[현재 도시][방문 집합] 비트마스크 DP
1006습격자 초라기2×N 원형 구조를 처음·끝 열 연결 여부로 나눠, 열마다 윗칸/아랫칸/둘 다 채운 3가지 상태로 DP
11049행렬 곱셈 순서구간 [i, j]를 나누는 지점 k를 고르는 구간 DP
7579앱메모리 대신 비용을 축으로 둔 0/1 배낭 DP
9252LCS 2LCS 길이 DP 후 테이블을 역추적해 문자열 복원

이분 탐색 · 매개변수 탐색

12015가장 긴 증가하는 부분 수열 2길이별 최소 끝값 배열을 이분 탐색으로 갱신해 O(N log N)
1300K번째 수값 x에 대해 행마다 min(x / i, N)개를 세는 매개변수 탐색
2110공유기 설치최소 거리를 정해두고 설치 가능 여부를 판정하는 매개변수 탐색

분할 정복 · 정수론

11401이항 계수 3페르마 소정리로 분모의 모듈러 역원을 구하고 분할 정복 거듭제곱
11444피보나치 수 6피보나치 행렬의 분할 정복 거듭제곱으로 O(log N)
6549히스토그램에서 가장 큰 직사각형높이가 증가하는 단조 스택으로 O(N)

자료구조 · 그리디

1655가운데를 말해요최대 힙·최소 힙 두 개로 중앙값을 실시간 유지
17298오큰수아직 답을 못 찾은 인덱스를 단조 스택으로 관리
1202보석 도둑가방·보석 정렬 후 담을 수 있는 보석을 우선순위 큐에 넣고 최댓값 선택

그래프

1647도시 분할 계획크루스칼로 MST를 만든 뒤 가장 비싼 간선 하나를 제거
2162선분 그룹CCW로 선분 교차를 판정하고 유니온 파인드로 그룹화
1504특정한 최단 경로다익스트라로 경유지 순서 두 가지 경로를 각각 계산해 비교
16236아기 상어매 단계 BFS로 가장 가깝고 위·왼쪽 우선인 먹이를 찾는 시뮬레이션

비트마스킹 · 완전 탐색 · 구현

14939불 끄기첫 줄 누름 조합 2¹⁰가지를 고정하면 나머지 줄은 윗줄 상태로 결정
1029그림 교환(현재 사람, 소유 이력 비트마스크, 가격) 상태 공간 탐색
2580스도쿠빈칸마다 행·열·3×3 제약을 확인하는 백트래킹
3190뱀 · 경사로 · 톱니바퀴삼성 SW 역량테스트 기출 구현·시뮬레이션 (3190, 14890, 14891)

Gunmo Lee

010-6385-4676
rjsah5676@gmail.com