정의 1. 환, 체, 분배법칙 집합 $R$에 덧셈 $+$과 곱셈 $\cdot$이라는 두 이항연산이 주어졌을 때, 다음 조건을 만족하면 $R$을 환이라고 한다. $(R,+)$는 아벨군이다. 곱셈은 결합법칙을 만족한다. 즉, 모든 $x,y,z\in R$에 대해 $(xy)z=x(yz)$이다. 곱셈은 덧셈에 대해 양쪽으로 분배된다. 즉, 모...

집합론, 대수학, 해석학에서 사용하는 기본 정의를 정리한다. 1. 집합 집합은 서로 구별되는 대상들의 모임이며, 각 대상을 원소라고 한다. $x\in X$는 $x$가 집합 $X$의 원소라는 뜻이다. 2. 외연적 정의와 내포적 정의 집합은 원소를 나열하는 외연적 정의 또는 원소가 만족해야 할 성질을 제시하는 내포적 정의로 나타낼 수 있다. 예를 ...

정리 서로 다른 시작점 $s$와 도착점 $t$를 가진 유한 유향 네트워크 $G=(V,E)$를 생각하자. 각 유향 간선 $e$에는 유한한 음이 아닌 용량 $c_e$가 주어진다. 실현 가능한 유량은 각 간선에 값 $f_e$를 할당하여 [0\leq f_e\leq c_e] 를 만족하고, $s,t$ 이외의 모든 정점에서 유입량과...

플로우 네트워크와 실현 가능한 유량 플로우 네트워크는 서로 다른 시작점(source) $s$와 싱크(sink) $t$를 지정한 유한 유향 그래프 $G=(V,E)$이다. 각 간선 $e$에는 유한한 음이 아닌 용량 $c_e$가 주어진다. 끝점이 같더라도 간선은 서로 구별되는 객체로 취급한다. 이는 평행 간선이나 서로 반대 방향인 간선이 있을 때 중요하다...

축소구간 정리 실수 집합 $\mathbb{R}$의 공집합이 아닌 닫힌구간들로 이루어진 열 $(I_n)_{n\in\mathbb{N}}$을 생각하자. 각 구간을 $I_n=[a_n,b_n]$이라 하고, 그 길이를 $|I_n|=b_n-a_n$으로 나타내자. 다음 두 조건을 가정한다. 모든 $n\in\mathbb{N}$에 대해 $I_{n+1}\sub...

정리 $(a_n)$을 실수 수열이라고 하자. $(a_n)$이 단조 증가하고 위로 유계이면, 수열은 $\sup{a_n:n\in\mathbb{N}}$로 수렴한다. $(a_n)$이 단조 감소하고 아래로 유계이면, 수열은 $\inf{a_n:n\in\mathbb{N}}$로 수렴한다. 따라서 실수 단조 수열이 유한한 실수 극한을 가지는 것과 유계...

수열에 대한 정리 $d\geq 1$인 유한 차원 유클리드 공간 $\mathbb{R}^d$의 유계 수열 $(x_n)$은 수렴하는 부분수열을 갖는다. 그 극한은 $\mathbb{R}^d$에 속하지만, 수열의 항일 필요는 없다. 수열에 필요한 가정은 유계성뿐이다. 특히 수열이 취하는 값들의 집합이 닫혀 있을 필요는 없다. 증명 $x_n=(x_n^{(...

플로이드-워셜 알고리즘 플로이드-워셜 알고리즘은 가중치가 있는 방향 그래프의 모든 순서쌍 정점 사이 최단 거리를 계산한다. 음수 간선 가중치도 처리할 수 있지만, 해당 정점 쌍의 경로에 영향을 주는 음수 사이클이 없어야 유한한 최단 거리가 존재한다. 이 알고리즘은 정해진 순서로 중간 정점 후보를 하나씩 허용하는 동적 계획법이다. 동적 계획법 점화식...

유클리드 알고리즘은 공약수를 보존하는 더 작은 쌍으로 두 비음수 정수를 반복해서 바꾸어 가며 최대공약수(gcd)를 구하는 방법이다. 핵심 항등식 $b>0$인 비음수 정수 $a,b$를 생각하자. 유클리드 나눗셈에 따라 다음을 만족하는 정수 $q,r$가 유일하게 존재한다. [a=bq+r,\qquad 0\le r<b.] 핵심은 다음 항등식...

백준 3653번: 영화 수집 영화 번호가 아니라 위치를 관리하기 영화를 요청할 때마다 DVD의 위치가 바뀌므로, 영화 번호만 인덱스로 삼으면 특정 영화 위에 DVD가 몇 장 있는지 바로 표현하기 어렵다. 대신 각 위치의 점유 여부를 관리한다. DVD가 있는 위치는 1, 비어 있는 위치는 0으로 두고, 이 값의 구간 합을 펜윅 트리로 계산한다. 테...

백준 19565번 - 수열 만들기 방향 그래프로 모델링하기 수열의 각 원소는 $1,\dots,N$ 중 하나이며, 첫 원소와 마지막 원소는 모두 1이어야 한다. 또한 같은 순서쌍이 인접한 원소로 두 번 이상 나타나면 안 된다. 순서쌍 $(x,y)$와 $(y,x)$는 서로 다르며, $(x,x)$처럼 같은 값으로 이루어진 쌍도 허용된다. 값마다 정점 ...

백준 1395번 - 스위치 문제와 구간 트리 스위치 $N$개가 있으며 처음에는 모두 꺼져 있다. 각 명령은 $1\le S\le T\le N$인 구간에 대해 주어진다. 명령 0 S T는 양 끝을 포함하는 $[S,T]$ 구간의 모든 스위치를 반전하고, 1 S T는 그 구간에서 켜진 스위치의 개수를 출력한다. 구간의 모든 스위치를 하나씩 바꾸면 한 명...

백준 1035번: 조각 움직이기 풀이: 배치 상태를 정점으로 하는 BFS 보드는 25칸이고 조각은 최대 5개입니다. 한 상태는 조각 전체의 위치를 나타내야 합니다. 각 칸의 점유 여부를 25비트 정수로 표현하고, (r, c) 칸에 조각이 있으면 r * 5 + c번째 비트를 1로 둡니다. 조각은 서로 구별되지 않으므로 순서를 따로 정할 필요가 없습니...

문제 링크 문제 모델 적이 배치된 2행 N열의 원형 격자가 있다. 소대 하나는 한 칸을 맡거나, 적의 수 합이 W 이하인 인접한 두 칸을 함께 맡을 수 있다. 모든 칸을 맡는 데 필요한 소대의 최소 수를 구한다. 인접한 두 칸은 같은 열의 위아래 칸이거나, 같은 행의 이웃 열 칸이다. 같은 행에서는 N열과 1열도 이웃한다. 원형으로 이어지는 두 ...

정수에 대한 베주 항등식 $a,b\in\mathbb Z$가 동시에 0은 아니라고 하고, [g=\gcd( a , b )>0] 로 놓자. 그러면 다음을 만족하는 정수 $x,y$가 존재한다. [ax+by=g.] 더 나아가 $a,b$의 모든 정수 선형결합은 정...

백준 5373번: 큐빙 모델과 회전 방향 각 스티커를 큐브 조각의 위치 $(x,y,z)$와 바깥쪽 법선 벡터로 표현합니다. 축은 큐브에 고정하며 $+x$는 오른쪽, $+y$는 위쪽, $+z$는 앞쪽을 가리킵니다. 위치 좌표는 ${-1,0,1}$ 중 하나이고 법선은 여섯 방향의 부호 있는 축 벡터 중 하나입니다. 색은 스티커에 붙어 있으므로 층을 돌...

문제 링크 기존 접근이 느린 이유 (값, 인덱스) 쌍을 한 번 정렬하는 데는 O(N log N) 시간이 걸리지만, 이후 각 구간 질의마다 전체 N개 원소를 훑으므로 최악의 경우 질의 처리에 O(NM) 시간이 걸립니다. 변수를 전역으로 선언하는 것은 저장 기간을 바꿀 뿐 수행해야 하는 연산량을 바꾸지 않으므로 점근적 시간 복잡도는 달라지지 않습니다....

백준 1520번: 내리막 길 풀이: DAG에서의 동적 계획법 각 칸을 정점으로 생각합니다. 한 칸에서 상하좌우로 인접한 칸 중 높이가 더 낮은 곳으로 향하는 방향 간선을 둡니다. 모든 간선은 높이를 낮추므로 방향 사이클은 존재하지 않으며, 이 그래프는 DAG입니다. 높이가 같은 인접 칸 사이에는 간선이 없습니다. 왼쪽 위에서 오른쪽 아래까지 가는...

문제 링크 다이얼 조작 규칙과 동적 계획법 다이얼은 왼쪽부터 번호를 매깁니다. 다이얼 i를 양수만큼 돌리면 i번 다이얼과 그 아래의 모든 다이얼이 함께 왼쪽으로 회전합니다. 음수만큼 돌리면 i번 다이얼만 오른쪽으로 회전합니다. 출력하는 회전량은 부호가 있는 정수이며 양수는 왼쪽, 음수는 오른쪽 회전입니다. 왼쪽부터 다이얼을 처리합니다. dp[i]...

문제 링크 모델링: 교차 그래프와 연결 요소 각 입력 선분을 그래프의 정점으로 두고, 두 닫힌 선분이 교차할 때 두 정점을 간선으로 연결합니다. 그룹은 이 그래프의 연결 요소입니다. 직접 교차하지 않더라도 교차하는 선분들의 사슬로 이어져 있으면 같은 그룹입니다. 따라서 모든 선분 쌍을 검사하고 교차하는 쌍을 서로소 집합(DSU) 자료구조에서 합칩니...

문제 링크 교집합 넓이 두 원의 중심을 $C_1=(x_1,y_1)$, $C_2=(x_2,y_2)$, 반지름을 $r_1,r_2$라 하고 중심 사이 거리를 $d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$라 하자. 원이 만나는 형태에 따라 교집합 넓이를 구한다. $d\ge r_1+r_2$이면 두 원은 서로 떨어져 있거나 외접하므로 ...

문제 링크 시작점에서 목표까지의 거리를 $D_0=\sqrt{x^2+y^2}$라 하자. 곧장 걸어가면 걸리는 시간은 $D_0$이다. 점프는 방향과 관계없이 항상 거리 $D$만큼 이동하며 시간 $T$가 걸리고, 남은 거리는 걸을 수 있다. $q=\lfloor D_0/D\rfloor$, $r=D_0-qD$로 두면 $0\le r<D$이다. 고려할 후...

문제 링크 방향 판정과 선분 교차 세 점 A, B, C의 방향 판정값을 다음과 같이 정의한다. cross(A, B, C) = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x) 값이 양수이면 C는 방향이 지정된 직선 AB의 반시계 방향에 있고, 음수이면 시계 방향에 있다. 0이면 세 점이 한 직선 위에 있다....

백준 17387번: 선분 교차 2 풀이: 방향 판정과 닫힌 선분의 경계 세 점 $P$, $Q$, $R$에 대해 외적 $(Q-P) \times (R-P)$의 부호로 점 $R$이 방향이 있는 직선 $PQ$의 어느 쪽에 있는지 알 수 있습니다. 값이 양수면 반시계 방향, 음수면 시계 방향이며, 0이면 세 점이 한 직선 위에 있습니다. 선분을 $AB$,...

문제 링크 문제 모델 N명의 직원과 M개의 일이 주어지고, 직원마다 맡을 수 있는 일의 목록이 주어진다. 각 직원은 기본적으로 최대 한 일을 맡을 수 있으며, 전체 추가 배정 횟수는 K 이하이다. 추가 배정은 직원 한 명당 최대 한 번만 가능하므로 직원은 최대 두 일을 맡는다. 각 일은 최대 한 직원에게만 배정한다. 이 조건을 만족하면서 배정된 일...

문제 링크 문제 모델 N명의 직원과 M개의 일이 있다. 각 직원에게는 맡을 수 있는 일의 목록이 주어진다. 각 일은 최대 한 명에게만 배정하고, 직원 한 명에게는 최대 두 개의 일을 배정하면서 배정한 일의 수를 최대화해야 한다. 이분 그래프에서 직원마다 매칭용 슬롯을 두 개 만들고, 두 슬롯 모두 해당 직원이 할 수 있는 모든 일과 연결한다. 매...

백준 11375번: 열혈강호 풀이: 이분 매칭 왼쪽 정점은 직원, 오른쪽 정점은 일이라고 생각합니다. 직원이 할 수 있는 일마다 직원에서 해당 일로 간선을 연결합니다. 유효한 배정은 매칭입니다. 선택된 간선에 직원이나 일이 두 번 이상 등장할 수 없습니다. 구할 값은 최대 매칭의 크기입니다. 직원을 하나씩 처리하면서 깊이 우선 탐색으로 증가 경로...

문제 링크 핵심 관찰 문자열 S의 부분 문자열 중 회문이 아닌 것의 최대 길이를 구한다. S 자체가 회문이 아니면 전체 문자열이 답이므로 N이다. S가 회문이지만 모든 문자가 같다면 모든 부분 문자열도 회문이므로 답은 -1이다. 남은 경우, 즉 회문이지만 문자가 모두 같지는 않다면 답은 N - 1이다. 증명 전체 문자열이 회문이 아니면 S가 길...

문제: BOJ 16235 — 나무 재테크 · English · 日本語 매년 봄, 여름, 가을, 겨울 순서로 진행합니다. 봄에는 각 칸의 나무를 나이가 어린 순으로 처리합니다. 나무는 나이만큼 양분을 소비한 뒤 나이가 1 증가합니다. 양분이 부족하면 그 나무와 같은 칸에서 아직 처리하지 않은 더 나이 많은 나무가 모두 죽으므로, 그 칸의 처리를 멈춥니...

문제: BOJ 1240 — 노드사이의 거리 · English · 日本語 입력 그래프는 트리이므로 임의의 두 정점 사이에는 경로가 정확히 하나만 존재합니다. 따라서 최단 거리는 그 경로에 있는 간선 가중치의 합이며, 일반적인 최단 경로 알고리즘은 필요하지 않습니다. 각 질의마다 시작 정점에서 명시적인 스택으로 탐색합니다. 스택의 각 원소에는 현재 정...

문제 풀이 매 시간 시작할 때 보드 바깥의 빈 테두리에서 BFS를 하여 외부 공기와 연결된 빈칸을 찾습니다. 외부 공기와 인접한 치즈 칸은 해당 시간에 녹습니다. 먼저 녹을 칸을 모두 모은 뒤 한꺼번에 제거하므로, 제거 후에야 새로 노출되는 치즈는 다음 시간까지 녹지 않습니다. 각 녹이기 직전의 전체 치즈 개수를 저장합니다. 한 시간 동안 마지막...

문제: BOJ 14890 — 경사로 · English · 日本語 각 행이나 열에서 인접한 칸의 높이 차이가 0 또는 1이고, 높이 차이가 1인 곳마다 길이 L의 경사로를 놓을 수 있으면 길을 만들 수 있습니다. 경사로 하나는 높이가 낮은 쪽의 L개 칸을 차지합니다. 해당 칸들은 모두 같은 높이여야 하고, 길의 범위를 벗어나면 안 되며, 다른 경사로가...

문제: BOJ 11437 — 최소 공통 조상 · English · 日本語 트리의 루트를 정점 1로 잡습니다. 재귀가 아닌 너비 우선 탐색으로 각 정점의 깊이와 바로 위 부모를 기록합니다. 루트의 부모는 0으로 두며, 이 센티널 정점의 조상도 모두 0입니다. 입력이 트리이므로 루트가 아닌 각 정점은 부모로부터 정확히 한 번 방문됩니다. 재귀 DFS 대...

문제: BOJ 5052 — 전화번호 목록 · English · 日本語 모든 전화번호를 사전순으로 정렬한 뒤, 서로 이웃한 번호만 비교합니다. 한 번호가 다른 번호의 접두사라면 짧은 번호가 긴 번호보다 사전순으로 먼저 옵니다. 짧은 번호가 끝난 다음 위치에서 긴 번호에는 숫자가 남아 있으므로 긴 번호가 뒤에 놓이기 때문입니다. 따라서 접두사 관계가 있...

문제: BOJ 17144 — 미세먼지 안녕! · English · 日本語 매초 미세먼지가 있는 각 칸은 floor(미세먼지 / 5)만큼의 먼지를 상하좌우 인접 칸 중 범위 안에 있고 공기청정기가 아닌 칸으로 확산시킵니다. 모든 칸은 동시에 확산하므로, 미세먼지 값을 갱신하기 전에 별도의 격자에 각 칸에서 이동하는 양을 누적해야 합니다. 확산한 뒤 원...

문제: BOJ 1339 — 단어 수학 · English · 日本語 각 알파벳은 그 글자가 나타나는 모든 위치에서 동일한 숫자를 나타냅니다. 단어의 일의 자리에 있는 글자는 해당 숫자를 한 번 더하고, 십의 자리에 있으면 숫자의 10배를 더하며, 그보다 왼쪽 자리도 같은 방식으로 계산합니다. 예를 들어 ABC의 값은 100 * value[A] + 10...

문제: BOJ 2169 — 로봇 조종하기 · English · 日本語 로봇은 N × M 격자의 왼쪽 위 칸에서 출발해 오른쪽 아래 칸에 도착해야 합니다. 방문한 각 칸의 값을 점수에 더합니다. 로봇은 왼쪽, 오른쪽, 아래쪽으로만 이동할 수 있고 위쪽으로는 이동할 수 없으며, 같은 칸을 두 번 방문할 수도 없습니다. 목표는 방문한 칸의 값 합을 최대로...

문제: BOJ 15683 — 감시 · English · 日本語 각 CCTV는 종류에 따라 정해진 방향을 감시하며, 90도씩 회전할 수 있습니다. 1번은 한 방향, 2번은 서로 반대인 두 방향, 3번은 인접한 두 방향, 4번은 세 방향, 5번은 네 방향을 모두 감시합니다. 서로 다른 회전 상태의 수는 각각 4, 2, 4, 4, 1개입니다. 감시 광선은...

문제: BOJ 16234 — 인구 이동 · English · 日本語 하루 동안 인접한 두 나라의 인구 차이가 L 이상 R 이하이면 국경을 엽니다. 열린 국경을 통해 서로 연결된 나라들이 연합을 이루며, 나라가 둘 이상인 각 연합의 모든 나라는 연합 인구의 평균을 소수점 아래를 버려 적용합니다. 그날의 모든 연합은 인구를 갱신하기 전 격자를 기준으로 ...

문제: BOJ 13460 — 구슬 탈출 2 · English · 日本語 보드에는 벽, 구멍, 빨간 구슬과 파란 구슬이 있습니다. 한 방향으로 기울이면 구슬은 벽에 막히거나 구멍에 빠질 때까지 움직입니다. 최대 10번 기울여 빨간 구슬을 구멍에 넣되 파란 구슬은 빠뜨리지 않는 것이 목표입니다. 상태는 두 구슬의 현재 칸 (빨간 구슬, 파란 구슬)입니...

문제: BOJ 14500 — 테트로미노 · English · 日本語 N × M 크기의 보드에서 변을 공유하며 연결된 네 칸을 덮는 테트로미노를 놓을 때, 덮인 칸의 합 중 최댓값을 구합니다. 다섯 가지 테트로미노의 모든 회전과 대칭 배치를 고려해야 합니다. 인접한 칸을 하나씩 추가하며 단순 경로를 깊이 우선 탐색하면 막대, L, S, Z 모양은 찾...

문제: BOJ 3190 — 뱀 · English · 日本語 뱀은 보드의 왼쪽 위 칸에서 오른쪽을 향해 출발합니다. 매 초 한 칸 앞으로 이동하며, 머리가 보드 밖으로 나가거나 몸이 차지하고 있는 칸으로 들어가면 그 초에 게임이 끝납니다. 이동할 칸에 사과가 있으면 뱀의 길이가 늘어납니다. 사과가 없으면 꼬리가 한 칸 이동합니다. 이동을 완료한 뒤 해...

문제: BOJ 14503 — 로봇 청소기 · English · 日本語 로봇은 현재 칸을 청소한 다음 왼쪽으로 90도 회전해 앞쪽을 확인합니다. 네 방향을 차례로 확인하며, 청소되지 않은 빈 칸을 찾으면 그쪽으로 한 칸 이동하고 다시 현재 칸 청소부터 시작합니다. 네 칸을 모두 확인했는데 이동할 곳이 없다면 방향을 유지한 채 뒤쪽으로 한 칸 물러납니다...

문제: BOJ 14499 — 주사위 굴리기 · English · 日本語 주사위의 여섯 면에 적힌 값을 고정된 방향 배열 TOP, BOTTOM, NORTH, SOUTH, EAST, WEST에 저장합니다. 불변식은 배열의 각 항목이 항상 해당 방향을 향하고 있는 면의 값을 나타낸다는 것입니다. 굴릴 때마다 회전축을 기준으로 네 면만 바뀌고, 나머지 두 ...

문제: BOJ 16236 — 아기 상어 · English · 日本語 아기 상어가 현재 위치에서 출발해 먹을 수 있는 물고기를 찾을 때마다 BFS를 실행합니다. 상어보다 큰 물고기가 있는 칸은 지나갈 수 없고, 빈칸과 상어보다 작거나 같은 물고기가 있는 칸은 지나갈 수 있습니다. 먹을 수 있는 물고기는 상어보다 크기가 엄격히 작아야 합니다. 따라서 크...

문제: BOJ 15686 — 치킨 배달 · English · 日本語 도시에는 집 H개와 치킨집 C개가 있습니다. 정확히 M개의 치킨집을 남길 때, 각 집의 치킨 거리는 남긴 치킨집 중 가장 가까운 곳까지의 맨해튼 거리입니다. 도시의 치킨 거리는 모든 집의 치킨 거리를 합한 값이며, 이 합을 최소화해야 합니다. 순열이 아니라 조합을 열거합니다. DF...

문제: BOJ 13275 — 가장 긴 팰린드롬 부분 문자열 · English · 日本語 마나커 알고리즘은 가능한 각 중심에서 팰린드롬의 반지름을 저장합니다. 홀수 길이 팰린드롬의 중심은 문자 하나입니다. radiusOdd[i]는 중심 문자까지 포함한 길이의 절반이므로 팰린드롬의 길이는 2 * radiusOdd[i] - 1입니다. 짝수 길이 팰린드롬의...

문제: BOJ 17131 — 여우가 정보섬에 올라온 이유 · English · 日本語 여우 트리플에서 가운데 점을 p라고 하면, 한 점은 p보다 엄격히 왼쪽에 있고 다른 한 점은 엄격히 오른쪽에 있어야 합니다. 두 점의 y 좌표는 모두 p보다 커야 합니다. 이 조건을 만족하며 왼쪽에 있는 점의 수를 L(p), 오른쪽에 있는 점의 수를 R(p)라 하면...

문제: BOJ 10999 — 구간 합 구하기 2 · English · 日本語 배열에는 N개의 값이 있습니다. 1번 연산은 1부터 시작하는 양 끝 포함 구간 [B, C]의 모든 원소에 D를 더하고, 2번 연산은 같은 형태의 구간 합을 출력합니다. 배열 크기는 최대 백만이고 구간 합은 32비트 정수 범위를 넘을 수 있으므로 세그먼트 트리와 모든 계산에 ...

문제: BOJ 1725 — 히스토그램 · English · 日本語 각 막대를 높이로 하는 직사각형 중 가장 넓은 것은 해당 막대가 가장 낮은 막대인 구간에서 찾을 수 있습니다. 이 구간의 양쪽 경계는 해당 막대보다 높이가 엄격히 낮은 가장 가까운 막대입니다. 왼쪽부터 단조 스택으로 훑으면 더 낮은 막대를 만나는 순간 경계를 확정할 수 있습니다. 스...

문제: BOJ 2268 — 수들의 합 7 · English · 日本語 배열의 원소는 N개이며 처음에는 모두 0입니다. 0 a b 명령은 1부터 시작하는 양 끝 포함 구간 [min(a, b), max(a, b)]의 합을 출력합니다. 1 a b 명령은 a번째 원소를 b로 대입하며, 기존 값은 새 값으로 교체됩니다. 문제에서 대입 값은 음수가 아니며 0일...

문제: BOJ 1275 — 커피숍2 · English · 日本語 배열은 계속 바뀝니다. 각 질의는 x부터 y까지의 합을 구한 뒤, 위치 a의 값을 b로 대입합니다. 반복형 세그먼트 트리는 배열의 각 값을 리프에 저장하고, 내부 노드에는 두 자식 노드 값의 합을 저장합니다. 트리에는 크기 2N인 배열을 사용합니다. 0부터 시작하는 인덱스 i의 리프는...

문제: BOJ 10868 — 최솟값 · English · 日本語 각 질의는 1부터 시작하는 양 끝 포함 구간 [a, b]를 주며, 그 구간의 최솟값을 구해야 합니다. 반복형 세그먼트 트리는 N개의 값을 tree[N..2N)에 저장합니다. 내부 노드는 두 자식의 최솟값으로 아래에서 위로 채웁니다. 이 간결한 배열 배치는 N이 2의 거듭제곱이 아니어도 ...

문제: BOJ 2836 — 수상 택시 · English · 日本語 택시는 위치 0에서 출발해 위치 M까지 이동해야 하며, 각 승객은 일직선 경로를 따라 어느 방향으로든 이동할 수 있습니다. 택시는 먼저 0에서 M 방향으로 이동합니다. 출발지보다 오른쪽에 목적지가 있는 승객은 택시가 지나갈 때 내려 줄 수 있으므로, 반드시 이동해야 하는 거리 M 외에...

문제: BOJ 5419 — 북서풍 · English · 日本語 각 테스트 케이스에서 x1 <= x2이고 y1 >= y2인 점의 쌍 (x1, y1), (x2, y2)의 개수를 셉니다. 왼쪽에서 오른쪽으로 스위핑하며 쌍을 한 번씩 셉니다. 따라서 x좌표가 같은 점은 y좌표가 큰 순서로 처리하며, 좌표가 완전히 같은 점도 입력에서 서로 다른 점...

문제: BOJ 2170 — 선 긋기 · English · 日本語 각 선분은 두 끝점 좌표 사이의 모든 점을 덮습니다. 적어도 하나의 선분이 덮는 전체 길이를 구합니다. 구간을 왼쪽 끝점 기준 오름차순으로 정렬한 뒤 왼쪽에서 오른쪽으로 순회하며 현재 합쳐진 구간의 가장 오른쪽 끝점을 유지합니다. 다음 구간의 시작점이 현재 끝점 이하라면 겹치거나 맞닿으...

문제: BOJ 4013 — ATM · English · 日本語 풀이 시작점에서 출발해 식당에 도착하는 경로 중 모을 수 있는 돈의 최댓값을 구합니다. 강한 연결 요소(SCC) 안에서는 모든 정점을 서로 오갈 수 있으므로 그 요소의 돈을 전부 모을 수 있습니다. 각 SCC를 구성 정점의 돈 합으로 가중치를 둔 정점 하나로 압축하면 방향 비순환 그래프...

문제: Codeforces 1638A — Reverse · English · 日本語 배열은 1..n의 순열입니다. 하나의 구간을 선택해 뒤집을 수 있을 때, 사전순으로 가장 작은 순열을 만들어야 합니다. 왼쪽부터 살펴보며 p[i] != i + 1인 첫 번째 위치 i를 찾습니다. 그보다 앞선 위치는 이미 가능한 가장 작은 값이므로 그대로 두어야 합니...

문제: BOJ 11281 — 2-SAT - 4 · English · 日本語 반복형 코사라주 알고리즘을 이용한 2-SAT 입력 절 (a ∨ b)는 함의 ¬a → b와 ¬b → a로 바꿀 수 있습니다. 부호가 있는 각 리터럴을 정점으로 표현합니다. 양수 리터럴 x의 인덱스는 x - 1, 음수 리터럴 ¬x의 인덱스는 N + x - 1입니다. 리터럴의 부...

문제: AtCoder ARC 135 C — XOR to All · English · 日本語 각 인덱스 i에 대해 sum_j (A[i] XOR A[j])를 계산하고, 모든 i 중 최댓값을 구합니다. 비트 위치 b 하나씩 살펴봅시다. A[i]의 b번째 비트가 0이면 XOR 결과의 해당 비트가 1인 원소는 그 비트가 1인 count[b]개입니다. 반대로 ...

문제: AtCoder ARC 135 B — Sum of Three Terms · English · 日本語 길이 N인 배열 A가 주어집니다. 길이 N + 2인 음이 아닌 정수 배열 B가 존재하여 모든 0 <= i < N에 대해 A[i] = B[i] + B[i + 1] + B[i + 2] 를 만족하는지 판정합니다. 존재하면 임의의 배열 하...

문제: AtCoder ARC 135 A — Floor, Ceil Decomposition English · 日本語 양의 정수 x에 대해 x <= 4이면 f(x) = x입니다. 그보다 큰 경우 x를 floor(x / 2)와 ceil(x / 2)로 나누고, 두 함수값의 곱을 998244353으로 나눈 나머지로 정의합니다. f(x) = f(floo...

문제: Codeforces 1637B — MEX and Array · English · 日本語 배열을 여러 개의 연속된 비어 있지 않은 구간으로 분할합니다. 분할의 비용은 구간 개수와 각 구간의 MEX 합이며, 배열의 값은 가능한 분할 중 최대 비용입니다. 주어진 배열의 모든 비어 있지 않은 부분 배열에 대해 그 값을 합산합니다. 공식 제약은 1 ...

문제: BOJ 3648 — 아이돌 · English · 日本語 각 테스트 케이스에서 모든 절을 만족시키고 변수 1을 참으로 만들어야 합니다. 절 (a OR b)는 함의 ¬a → b, ¬b → a라는 두 간선으로 바꿉니다. 변수 1을 참으로 만드는 조건은 단위 절 (1 OR 1)로 추가하며, 다른 절과 마찬가지로 ¬1 → 1 간선을 생성합니다. 입력...

문제: Codeforces 1637A — Sorting Parts · English · 日本語 각 테스트 케이스에서 1 <= k < n인 분할점 k를 하나 고릅니다. 접두 구간 a[1..k]와 접미 구간 a[k+1..n]을 각각 독립적으로 정렬합니다. 이 연산을 한 뒤 전체 배열이 비내림차순이 아니게 되는 유효한 분할이 존재하는지 묻습니다...

문제: Codeforces 1637C — Andrew and Stones · English · 日本語 한 번의 연산에서 i < j < k인 세 인덱스를 고르고, 가운데 더미 j에 돌이 두 개 이상 있으면 그 더미에서 돌 두 개를 꺼내 i와 k에 하나씩 놓습니다. 목표는 첫 번째와 마지막 더미에만 돌을 남기는 것입니다. 최소 연산 횟수 ...

문제: BOJ 11280 — 2-SAT - 3 · English · 日本語 각 절 (a OR b)는 ¬a → b와 ¬b → a라는 두 함의 간선으로 바꿀 수 있습니다. 부호가 있는 정수로 리터럴을 입력받으며, 변수 i의 양수 리터럴 i는 정점 i - 1, 음수 리터럴 -i는 정점 N + i - 1로 인코딩합니다. 따라서 부정을 취하는 정점 인덱스는 ...

문제: BOJ 4196 — 도미노 · English · 日本語 각 테스트 케이스에는 방향 그래프가 주어집니다. 도미노 u를 밀면 방향 간선을 따라 u에서 도달할 수 있는 모든 도미노가 쓰러집니다. 모든 정점을 쓰러뜨리는 데 필요한 최초의 밀기 횟수의 최솟값을 구합니다. 먼저 정점들을 강한 연결 요소(SCC)로 묶습니다. 한 SCC 안에서는 모든 정...

문제: BOJ 3977 — 축구 전술 · English · 日本語 그래프를 강한 연결 요소(SCC)로 나누면, 각 SCC를 정점으로 하고 서로 다른 SCC 사이의 간선을 유지한 축약 그래프를 얻습니다. 진입 간선이 없는 SCC는 다른 SCC에서 도달할 수 없는 시작 요소입니다. 이런 SCC가 하나뿐이면 그 안의 모든 정점이 답이고, 둘 이상이면 Co...

문제: BOJ 13511 — 트리와 쿼리 2 · English · 日本語 정점 1을 루트로 정하고 반복문으로 트리를 순회합니다. 각 정점의 깊이와 부모를 기록합니다. 루트의 부모는 루트 자신으로 두어 조상 테이블의 모든 값이 유효하도록 합니다. up[v][j]는 v에서 간선 2^j개를 올라간 조상이고, weight[v][j]는 그 간선들의 가중치 합...

문제: BOJ 1509 — 팰린드롬 분할 · English · 日本語 길이 N인 문자열 s를 연속된 팰린드롬 조각으로 나눌 때, 조각 수의 최솟값을 구합니다. 먼저 palindrome[l][r]를 계산합니다. 이는 양 끝 인덱스를 포함하는 부분 문자열 s[l..r]가 팰린드롬인지 나타냅니다. 부분 문자열 길이가 짧은 것부터 계산하면, 양 끝 문자가 ...

문제: BOJ 11003 — 최솟값 찾기 English · 日本語 풀이 각 위치 i에서 구해야 하는 구간은 [max(0, i - L + 1), i]입니다. 따라서 처음 L - 1개의 구간에는 지금까지 입력된 값만 들어가며, 존재하지 않는 값을 채워 넣지 않습니다. 덱에는 후보 인덱스를 오름차순으로 저장하고, 값은 별도의 기본형 배열에 보관합니다...

문제: BOJ 3176 — 도로 네트워크 · English · 日本語 정점 1을 루트로 삼고 명시적인 스택으로 트리를 순회하며 각 정점의 깊이, 바로 위 부모, 한 칸 위로 올라갈 때 지나는 간선의 최솟값과 최댓값을 기록합니다. 이후 2^j칸 점프를 두 개의 2^(j-1)칸 점프로 나누어 조상, 최솟값, 최댓값 테이블을 채웁니다. 루트의 조상은 루트...

문제: BOJ 11438 — LCA 2 · English · 日本語 정점 1을 루트로 잡고, 각 정점 v의 깊이와 up[v][j]를 저장합니다. up[v][j]는 v에서 간선을 2^j개 거슬러 올라간 조상입니다. 루트는 모든 단계에서 자기 자신의 조상으로 지정합니다. 이 규칙으로 조상 테이블의 모든 값이 유효해지고 루트에서의 점프도 안전해집니다. ...

문제: BOJ 17435 — 합성함수와 쿼리 English · 日本語 풀이 입력은 정수 1..M에서 정의된 함수 f를 주며, 각 쿼리는 시작값 x에 함수를 K번 적용한 값, 즉 f^K(x)를 묻습니다. 함수를 한 번씩 적용하면 쿼리마다 최대 500,000번의 연산이 필요할 수 있으므로, 이진 리프팅으로 함수의 거듭제곱을 미리 계산합니다. up[...

문제: BOJ 3584 — 가장 가까운 공통 조상 · English · 日本語 각 테스트 케이스에는 N개의 정점으로 이루어진 루트 트리와 가장 가까운 공통 조상(LCA)을 구할 정점 쌍이 주어집니다. 테스트 케이스마다 질의는 정확히 하나입니다. 입력 간선은 부모에서 자식 방향으로 주어지므로 각 자식의 부모를 parent 배열에 저장합니다. 부모가 없...

문제: BOJ 1086 — 박성원 · English · 日本語 부분집합 동적 계획법 입력에는 N개의 문자열이 있습니다. 순열은 문자열의 위치를 하나씩 고르는 순서입니다. 내용이 같은 문자열이 여러 개 있어도 서로 다른 위치이므로 각각 별개의 선택이며, 전체 순열 수는 N!입니다. dp[mask][r]를 mask에 포함된 문자열을 이어 붙였을 때 ...

문제: BOJ 2098 — 외판원 순회 English · 日本語 비트마스크 동적 계획법 출발 도시를 0으로 고정합니다. 어떤 순회 경로든 시작점을 회전해 도시 0에서 출발하도록 나타낼 수 있습니다. 상태 (current, visited)에서 visited는 지금까지 방문한 도시의 비트마스크이며, 출발 도시 0을 포함합니다. dp[current][...

문제: BOJ 17404 — RGB거리 2 English · 日本語 풀이 각 집은 빨강, 초록, 파랑 중 하나로 칠하며 이웃한 집의 색은 달라야 합니다. 집들이 원형으로 이어져 있으므로 첫 번째 집과 마지막 집도 이웃입니다. 따라서 두 집의 색도 서로 달라야 합니다. 첫 번째 집의 색을 하나로 고정한 뒤 선형 동적 계획법을 실행합니다. dp[c...

문제: BOJ 3665 — 최종 순위 · English · 日本語 작년 순위는 모든 팀 쌍의 순서를 알려 줍니다. 순위가 높은 팀에서 낮은 팀으로 방향 간선을 만들면 완전한 방향 그래프가 됩니다. 올해 순위가 바뀐 두 팀은 그 쌍의 간선 방향을 뒤집습니다. 인접 행렬과 도착 정점의 진입 차수를 함께 갱신하면 위상 정렬에 필요한 정보가 유지됩니다. ...

문제: BOJ 1766 — 문제집 · English · 日本語 방향 간선 A -> B는 문제 A를 문제 B보다 먼저 풀어야 한다는 뜻입니다. 따라서 모든 정점을 정확히 한 번씩 포함하고, 모든 간선의 시작 정점이 도착 정점보다 앞서는 위상 정렬 순서를 만들어야 합니다. 여러 문제를 다음에 풀 수 있다면 번호가 가장 작은 문제를 먼저 선택합니다....

문제: BOJ 1009 — 분산 처리 · English · 日本語 각 테스트 케이스에서 a^b의 일의 자리를 10으로 나눈 나머지에 대한 이진 거듭제곱으로 계산합니다. 반복 주기를 따로 찾을 필요가 없으며, 10으로 나누어떨어지는 밑도 처리할 수 있습니다. 계산한 나머지는 컴퓨터 번호를 나타냅니다. 단, 나머지가 0이면 컴퓨터 10번을 뜻합니다(컴퓨...

문제: AtCoder ABC 238 C — digitnum · English · 日本語 1부터 N까지의 모든 정수에 대해 십진수 자릿수를 더하고, 그 합을 998244353으로 나눈 나머지를 출력합니다. 정수들을 자릿수별로 묶습니다. 자릿수가 d인 정수의 범위는 [10^(d-1), min(N, 10^d - 1)]이므로, 그 범위에 포함되는 정수의 ...

문제: AtCoder ABC 238 B — Pizza · English · 日本語 처음 칼집의 위치를 0°로 둡니다. 지시를 하나씩 적용할 때마다 칼은 주어진 각도만큼 시계 방향으로 회전하므로, 새 칼집의 위치는 직전 위치에 회전 각도를 더한 뒤 360으로 나눈 나머지입니다. 이렇게 얻은 N개 위치와 0°를 배열에 저장합니다. 같은 위치가 여러 번 ...

문제: AtCoder ABC 238 A — Exponential or Quadratic English · [한국어] · 日本語 2^N > N^2인지 판정하는 문제입니다. 거듭제곱을 직접 계산할 필요는 없습니다. N = 1일 때 부등식은 참이고, N = 2, 3, 4일 때는 거짓입니다(2^4 = 4^2). N = 5부터는 항상 참입니다. 어떤 N...

문제: BOJ 2482 — 색상환 · English · 日本語 원형으로 놓인 N개 위치 중 서로 인접하지 않도록 K개를 고릅니다. 첫 위치와 마지막 위치도 인접한 것으로 취급합니다. 길이 L인 직선에서 서로 인접하지 않게 k개를 고르는 경우의 수를 line(L, k)라 하면, 선택 사이마다 최소 한 자리를 비워야 하므로 다음과 같습니다. line(...

문제: BOJ 1005 — ACM Craft · English · 日本語 각 규칙 A B는 건물 A를 완성한 뒤에 B를 지을 수 있다는 뜻입니다. 규칙을 방향 간선으로 표현하면 비순환 방향 그래프가 됩니다. 위상 순서로 처리하면 각 건물의 모든 선행 건물이 먼저 처리됩니다. finish[v]를 건물 v를 가장 빨리 완성하는 시각이라고 합시다. 점화...

문제: BOJ 1305 — 광고 · English · 日本語 길이 L인 광고 문구가 주어집니다. 이 문구 전체가 앞부분으로 나타나도록 무한히 반복할 수 있는 가장 짧은 문자열의 길이를 구합니다. KMP 접두사 함수 pi를 계산합니다. pi[i]는 s[0..i]의 proper prefix(문자열 전체가 아닌 접두사)이면서 suffix인 문자열 중 가장...

문제: BOJ 2213 — 트리의 독립집합 · English · 日本語 정점 1을 루트로 트리를 구성합니다. 각 정점 v에 대해 in[v]는 v를 포함하는 v의 서브트리 독립집합 중 최대 가중치이고, out[v]는 v를 제외했을 때의 최대 가중치입니다. 정점의 양수 가중치를 w[v]라고 하면 다음과 같습니다. in[v] = w[v] + sum...

문제: BOJ 1949 — 우수 마을 · English · 日本語 각 마을에는 인구수가 주어집니다. 서로 인접한 두 마을을 동시에 선택하지 않으면서 선택한 마을들의 인구수 합을 최대로 만드는 문제입니다. 입력은 N, 각 마을의 인구수 N개, 그리고 양방향 도로 N - 1개로 이루어집니다. 마을 1을 루트로 삼아 트리를 반복문으로 순회합니다. 방문 ...

문제: BOJ 5670 — 휴대폰 자판 · English · 日本語 단어를 입력할 때 첫 글자는 항상 입력합니다. 그다음 글자는 현재까지 입력한 접두사의 트라이 노드에 자식이 둘 이상 있거나, 그 접두사 자체가 완성된 단어일 때만 입력합니다. 어떤 단어가 다른 단어의 접두사라면 그 단어와 더 긴 단어를 구별해야 하므로 끝 글자 다음의 추가 입력이 필...

문제: BOJ 2533 — 사회망 서비스(SNS) English · 日本語 풀이 정점 0을 루트로 정하고 반복문으로 루트 우선 순서를 만듭니다. 이 순서를 역순으로 처리하면 모든 자식을 먼저 계산하므로 재귀 호출이 필요 없습니다. 따라서 정점이 최대 10^6개인 일자형 트리에서도 호출 스택이 넘치지 않습니다. 각 정점 u에 대해 notAdopt...

문제: BOJ 10266 — 시계 사진들 · English · 日本語 시계의 각도 위치는 0부터 359999까지 총 360000개이며, 각 위치 단위는 1/1000도입니다. 각 사진을 길이 360000인 불리언 배열로 나타내고, 시계 바늘이 있는 위치만 true로 표시합니다. 같은 위치에 바늘이 여러 개 있어도 이 표현과 매칭 방법은 그대로 사용할 ...

문제: AtCoder ABC 237 E — Skiing · English · 日本語 정점 1에서 정점 v까지 가는 경로에서 오른 총 높이를 U, 내려간 총 높이를 D라고 하겠습니다. 경로의 행복도 변화량은 D - 2U입니다. 1만큼 내려가면 행복도가 1 증가하고, 1만큼 오르면 2 감소하기 때문입니다. 전체 높이 변화는 H[v] - H[1] = U ...

문제: AtCoder ABC 237 D — LR insertion · English · 日本語 최대 500,000개의 노드를 재귀 중위 순회하면 호출 스택이 넘칠 수 있습니다. 대신 덱(deque)을 사용해 답을 직접 구성합니다. 먼저 N을 넣고, S를 오른쪽에서 왼쪽으로 처리합니다. 각 인덱스 i에 대해 S[i]가 L이면 i를 덱의 뒤에 추가하고,...

문제: AtCoder ABC 237 C — kasaka English · [한국어] · 日本語 문자열 앞에 a만 덧붙일 수 있으므로 문자열 끝의 문자는 바꿀 수 없습니다. 문자열 앞부분에 연속된 a가 몇 개인지(leadingA), 뒷부분에 연속된 a가 몇 개인지(trailingA) 셉니다. leadingA > trailingA라면 앞의 a들을 ...

문제: AtCoder ABC 237 B — 행렬 전치 · English · 日本語 H행 W열 행렬 A가 주어지면 전치 행렬 B를 출력합니다. 전치 행렬의 크기는 W행 H열이며, 원소의 행과 열 인덱스를 서로 바꿉니다. 즉 모든 0 <= i < H, 0 <= j < W에 대해 B[j][i] = A[i][j]입니다. 정사각형이 아닌...

문제: AtCoder ABC 237 A — Not Overflow English · [한국어] · 日本語 입력값은 32비트 부호 있는 정수의 범위보다 클 수 있으므로 long으로 읽어야 합니다. 32비트 부호 있는 정수의 범위는 Integer.MIN_VALUE(-2^31)부터 Integer.MAX_VALUE(2^31 - 1)까지이며 양 끝값도 포함됩...

문제: BOJ 1786 — 찾기 · English · 日本語 문자열 T에서 패턴 P가 나타나는 모든 위치를 찾아야 합니다. KMP는 불일치가 발생해도 T의 이미 비교한 부분을 다시 훑지 않습니다. 입력 조건상 패턴은 비어 있지 않지만, 아래 검색 함수도 빈 패턴이면 인덱싱하지 않고 결과가 없는 것으로 처리합니다. 접두사 함수와 검색 pi[i]는 ...

문제: BOJ 4354 — 문자열 제곱 English · 한국어 · 日本語 접두사 함수와 후보 주기 길이가 L인 각 입력 문자열 s에 대해 접두사 함수 pi를 계산합니다. pi[i]는 s[0..i]의 접미사이기도 한 가장 긴 진접두사의 길이입니다. 마지막 값 pi[L - 1]은 문자열 전체의 가장 긴 테두리(border)의 길이입니다. 이 테두리...

문제: BOJ 14725 — 개미굴 · English · 日本語 각 입력 줄은 개미굴의 루트에서 시작하는 하나의 경로입니다. 각 토큰을 트라이에 삽입하면 이미 존재하는 접두사는 합쳐집니다. 노드의 자식은 그 접두사 다음에 올 수 있는 먹이들입니다. TreeMap은 자식을 사전순으로 저장하므로, 깊이 우선 탐색은 자식을 먼저 정렬하거나 복사하지 않고도...

문제: BOJ 14425 — 문자열 집합 · English · 日本語 N개의 문자열을 저장하고 M개의 문자열을 확인합니다. 확인할 문자열 중 저장된 문자열에 포함된 것이 몇 개인지 셉니다. 모든 문자열은 영문 소문자로만 이루어집니다. 해시 집합 입력 문자열을 HashSet<String>에 저장합니다. 같은 문자열을 여러 번 삽입해도 집...

BOJ 2470: 두 용액 · English · 日本語 서로 다른 두 용액을 골라 합의 절댓값이 가장 작게 만드는 문제입니다. 용액 값을 정렬한 다음 양 끝에 두 포인터를 둡니다. 매 단계에서 두 포인터가 가리키는 서로 다른 원소의 합을 후보로 보고, 지금까지의 최소 절댓값보다 작으면 두 인덱스를 저장합니다. 합이 음수이면 합을 키우기 위해 왼쪽 포...

문제: BOJ 1450 — 냅색 문제 중간에서 만나기 N = 30일 때 모든 부분집합을 열거하면 O(2^N) 시간이 필요합니다. 대신 물건을 두 그룹으로 나누고 각 그룹의 부분집합 합을 구합니다. 각 목록의 크기는 최대 2^(N/2)입니다. 오른쪽 그룹의 합을 정렬한 다음, 모든 왼쪽 그룹 합 s에 대해 C - s보다 큰 첫 번째 오른쪽 합의 위치...

문제: BOJ 3273 — 두 수의 합 서로 다른 양의 정수 N개와 목표값 X가 주어집니다(1 ≤ N ≤ 100,000, 각 수는 최대 1,000,000). 합이 X인 서로 다른 두 입력 원소의 순서 없는 쌍의 개수를 구합니다. 정렬과 투 포인터 먼저 수를 정렬하고, 아직 살펴보지 않은 구간의 가장 왼쪽과 오른쪽에 포인터를 둡니다. 두 수의 합이...

문제: BOJ 1806 — 부분합 모든 수가 양수이므로 오른쪽 경계를 바깥으로 옮기면 구간의 합은 증가하고, 왼쪽 경계를 오른쪽으로 옮기면 합은 감소합니다. 배타적 오른쪽 경계를 하나씩 확장하고, 합이 S 이상이 되면 그 구간을 답 후보로 기록한 뒤 합이 계속 S 이상인 동안 왼쪽 경계를 이동합니다. 같은 끝점으로 끝나는 더 긴 구간은 답을 더 작게...

문제: BOJ 1094 — 막대기 English · 日本語 목표 길이는 1부터 64까지입니다. 처음 막대의 길이는 64이며, 막대를 절반씩 자르면 만들 수 있는 조각의 길이는 모두 64, 32, 16, 8, 4, 2, 1과 같은 2의 거듭제곱입니다. 목표 길이를 이진수로 나타내면, 켜진 비트에 해당하는 서로 다른 2의 거듭제곱의 합으로 표현됩니다....

문제: BOJ 2252 — 줄 세우기 입력된 각 쌍 A B는 학생 A가 학생 B보다 앞에 서야 한다는 뜻입니다. 이를 방향 간선 A -> B로 나타냅니다. 유효한 줄은 위상 정렬 순서이며, 모든 간선의 시작점이 도착점보다 앞에 있어야 합니다. 서로 순서 관계가 없는 학생은 어느 쪽이 먼저 와도 되므로, 답은 유일한 순서가 아니라 가능한 순서 하...

문제: BOJ 1311 — 할 일 정하기 1 N명의 사람에게 N개의 일을 하나씩 배정합니다. 각 일은 정확히 한 번만 사용하며, 배정 비용의 합을 최소화합니다. 비트마스크 동적 계획법 dp[mask]를 mask에서 비트가 켜진 일들을 처음 Integer.bitCount(mask)명의 사람에게 배정했을 때의 최소 비용이라고 정의합니다. 따라서 다음...

문제: BOJ 11049 — 행렬 곱셈 순서 · English · 日本語 구간 동적 계획법 dp[i][j]를 행렬 i부터 j까지 순서대로 곱하는 데 필요한 스칼라 곱셈 횟수의 최솟값이라고 정의합니다. 행렬 하나는 곱셈이 필요 없으므로 dp[i][i] = 0입니다. 여러 행렬로 이루어진 구간에서는 마지막으로 곱할 위치 k를 선택합니다. 먼저 왼쪽 구...

문제: BOJ 1644 — 소수의 연속합 에라토스테네스의 체와 슬라이딩 윈도우 먼저 에라토스테네스의 체로 N 이하의 모든 소수를 구합니다. 그런 다음 인덱스 left부터 right까지 연속한 소수들의 구간과 그 합을 유지합니다. 합이 N보다 작으면 오른쪽 끝을 늘립니다. 합이 N 이상이 되면 합이 같은 경우 정답에 더하고 가장 왼쪽 소수를 구간에서...

비트마스크 집합에는 1부터 20까지의 정수만 들어가므로 하나의 int에 원소의 포함 여부를 저장할 수 있습니다. 값 x를 비트 위치 x - 1에 대응시킵니다. 1 << (x - 1)은 해당 비트만 1인 마스크를 만듭니다. 시프트 위치는 0부터 시작하므로 값에서 1을 빼야 합니다. 전체 집합 마스크 (1 << 20) - 1은 하위...

문제: BOJ 2150 — Strongly Connected Component 반복형 코사라주 알고리즘 코사라주 알고리즘은 두 번의 깊이 우선 탐색으로 강한 연결 요소(SCC)를 찾습니다. 이 구현은 재귀 호출 대신 명시적인 정수 스택을 사용하므로 정점 10,000개로 이루어진 긴 경로에서도 Java 호출 스택이 넘치지 않습니다. 첫 번째 탐색은...

문제: BOJ 15681 — 트리와 쿼리 · English · 日本語 반복형 루트 설정과 역순 누적 무방향 트리를 R을 루트로 삼아 탐색합니다. 스택을 사용하는 순회에서 각 노드의 부모를 기록하고 방문 순서를 order 배열에 저장합니다. 노드는 부모에서 발견될 때만 스택에 추가하고, 현재 노드의 부모로 돌아가는 간선은 건너뜁니다. 따라서 각 노드...

문제: BOJ 17472 — 다리 만들기 2 English · 日本語 풀이 각각의 연결된 땅을 그래프의 정점으로 봅니다. 먼저 플러드 필로 섬마다 번호를 붙입니다. 그런 다음 모든 행과 열을 살펴봅니다. 각 섬 칸에서 한 방향으로 물을 따라가 다음 땅이나 지도의 경계까지 진행합니다. 서로 다른 섬에 도달하고 물 칸을 두 칸 이상 지났을 때만 다리...

문제: BOJ 2887 — 행성 터널 크루스칼을 위한 희소 후보 간선 행성 u, v를 잇는 터널의 비용은 min(|x[u] - x[v]|, |y[u] - y[v]|, |z[u] - z[v]|)입니다. 행성 쌍을 모두 간선으로 만들면 N(N - 1) / 2개가 되어 큰 입력에서 비효율적입니다. 대신 각 좌표축별로 행성을 정렬하고, 정렬 순서에서 이웃...

문제 링크 · English · 日本語 크루스칼 알고리즘 신장 트리는 모든 정점을 사이클 없이 연결하는 트리입니다. 최소 스패닝 트리(MST)는 가능한 신장 트리 중 간선 가중치 합이 가장 작은 트리입니다. 크루스칼 알고리즘은 간선을 가중치가 작은 순서로 정렬한 뒤, 양 끝점이 서로 다른 연결 요소에 속할 때만 간선을 선택합니다. 서로 연결되어 있...

문제 링크 · English · 日本語 DVD 순열을 위한 반복형 세그먼트 트리 배열은 처음에 0, 1, ..., N - 1 순열입니다. 0번 연산은 두 위치의 값을 교환하고, 1번 연산은 현재 구간 [A, B]에 번호가 A부터 B까지인 DVD만 들어 있는지 확인합니다. 배열이 순열이므로 이 조건은 min(A..B) == A이면서 max(A..B...

문제 링크: BOJ 1168 — 요세푸스 문제 2 1번부터 N번까지 번호가 매겨진 사람이 원형으로 서 있습니다. 다음 사람부터 세어 매 K번째 사람을 차례로 제거하고, 제거 순서를 <a, b, ...> 형식으로 출력합니다. 생존자 수를 저장하는 펜윅 트리 각 위치의 값은 해당 번호의 사람이 아직 원에 있으면 1, 제거되었으면 0인 펜윅...

고정된 값 범위 [1, 2_000_000]에서 삽입된 값들의 다중집합을 펜윅 트리로 관리합니다. tree[i]에는 최하위 비트 i & -i로 정해지는 구간의 빈도 합이 저장됩니다. 값을 삽입할 때 해당 빈도에 1을 더하고, 순위에 해당하는 값을 찾아 제거할 때는 1을 빼므로 같은 값도 서로 다른 원소로 셉니다. k번째로 작은 값을 찾을 때는 ...

BOJ 2618: 경찰차 두 경찰차의 마지막 사건을 이용한 동적 계획법 dp[a][b]를 경찰차 1이 마지막으로 처리한 사건 번호가 a, 경찰차 2가 마지막으로 처리한 사건 번호가 b일 때 남은 사건을 모두 처리하는 최소 이동 거리라고 정의합니다. 0은 아직 사건을 맡지 않았음을 뜻합니다. 따라서 a = 0일 때 경찰차 1의 위치는 (1, 1), ...

BOJ 16975: 수열과 쿼리 21 펜윅 트리와 차분 배열로 구간 더하기 처리하기 초기 값은 기본 배열에 보관하고 이후의 더하기 연산은 차분 배열로 표현합니다. 1-based 양 끝점 포함 구간 [left, right]의 모든 위치에 x를 더하면 차분 배열에서 바뀌는 곳은 두 군데뿐입니다. left에 x, right + 1에 -x를 더합니다. 따...

문제: AtCoder ABC 235 D — Multiply and Rotate · English · 日本語 정수 1에서 시작해 다음 두 연산 중 하나를 적용합니다. 현재 정수에 A를 곱하거나, 마지막 십진 숫자를 맨 앞으로 옮깁니다. 회전은 두 자리 이상이며 끝자리가 0이 아닐 때만 가능합니다. N에 도달하는 데 필요한 최소 연산 횟수를 구하고, 도...

문제: AtCoder ABC 235 C — The Kth Time Query · English · 日本語 각 질의 (x, k)에 대해 배열에서 x가 k번째로 등장하는 위치(1부터 세는 위치)를 구합니다. x의 등장 횟수가 k보다 적으면 -1을 출력합니다. 값마다 등장 위치를 저장하는 맵을 만듭니다. 배열을 왼쪽에서 오른쪽으로 순회하면서 해당 값의 ...

문제: AtCoder ABC 235 B — Climbing Takahashi English · 日本語 각 지점의 높이는 경로를 따라 주어집니다. 타카하시는 첫 번째 지점에서 출발해 다음 지점의 높이가 현재 지점보다 엄격히 높을 때만 계속 이동합니다. 높이가 같거나 낮은 지점을 처음 만나면 그 지점에는 도착하지 않고 멈춥니다. 따라서 답은 마지막으로 ...

문제: AtCoder ABC 235 A — Rotate · English · 日本語 세 자리 십진수 ABC가 주어집니다. 여기서 A, B, C는 각각 백의 자리, 십의 자리, 일의 자리 숫자입니다. 숫자를 왼쪽으로 한 칸씩 회전해 얻는 세 수 ABC, BCA, CAB의 합을 구하면 됩니다. 회전은 숫자 세 개의 순서를 바꾸는 것이므로, 숫자가 반복되...

문제: BOJ 11780 — 플로이드 2 양의 비용을 가진 방향 그래프에서 모든 순서쌍 도시 사이의 최소 비용과 그 최소 경로 하나를 구합니다. 같은 방향으로 여러 간선이 있을 수 있으므로 가장 싼 간선만 유지하면 됩니다. 대각선은 도시에서 자기 자신으로 가는 빈 경로를 나타내도록 0으로 초기화합니다. 다음 정점 행렬을 이용한 플로이드–워셜 di...

문제: BOJ 11779 — 최소비용 구하기 2 음수가 아닌 비용을 가진 방향 그래프에서 지정된 출발점부터 도착점까지의 최소 비용과 해당 경로 하나를 구합니다. 각 방향 간선을 인접 리스트에 저장합니다. 평행 간선도 유효하며 별도로 처리할 필요 없이 모두 보관하면 됩니다. 다익스트라 알고리즘 distance[v]에는 출발점에서 v까지 발견한 최소...

풀이 0부터 9999까지의 정수를 각각 그래프의 정점으로 봅니다. DSLR의 네 명령은 현재 값에서 해당 명령의 결과 값으로 향하는 간선입니다. 모든 명령의 비용이 1이므로 너비 우선 탐색(BFS)은 시작 상태로부터 명령 횟수가 적은 상태부터 탐색합니다. 각 상태의 다음 상태는 D, S, L, R 순서로 방문합니다. BFS는 최단 경로를 먼저 찾으...

문제 링크 수빈이가 있는 위치를 x라고 할 때, 범위 [0, 100000] 안에서 이동할 수 있는 위치는 x - 1, x + 1, 2 * x입니다. 각 이동의 비용은 1초이므로 너비 우선 탐색(BFS)은 시작점으로부터 이동 횟수가 적은 위치부터 방문합니다. 어떤 위치를 처음 발견한 순간의 거리는 최소이며, 그 위치를 발견한 직전 위치를 부모로 저장하...

문제 링크 dp[i][j]를 문자열 a의 앞 i개 문자와 문자열 b의 앞 j개 문자 사이 최장 공통 부분 수열의 길이라고 정의합니다. 빈 접두사의 LCS 길이는 0입니다. 두 접두사의 마지막 문자가 같으면 그 문자를 앞부분의 LCS에 추가할 수 있습니다. 다르면 마지막 문자 중 적어도 하나를 제외해야 합니다. dp[0][j] = dp[i][0] =...

BOJ 14003: 가장 긴 증가하는 부분 수열 5 풀이 각 입력 값에 대해 tails[length]에는 길이가 length + 1인 증가 부분 수열이 가질 수 있는 가장 작은 끝값을 저장하고, tailIndices[length]에는 그 끝값을 제공하는 입력 인덱스를 저장합니다. 현재 값 이상인 첫 번째 끝값을 이분 탐색(lower_bound)하여...

문제 링크 각 입력값에 대해 tails[length]에는 해당 길이의 증가 부분 수열이 가질 수 있는 가장 작은 끝값을 저장하고, 그 값을 만든 입력 인덱스도 함께 저장합니다. 현재 값 이상인 첫 번째 꼬리값(lower_bound)을 이 값으로 교체합니다. 꼬리값 배열 자체가 실제 부분 수열을 나타내는 것은 아닙니다. 실제 수열을 복원하기 위해 인덱...

풀이 dp[x]를 x를 1로 만드는 데 필요한 최소 연산 횟수라고 하겠습니다. x에서 마지막으로 할 수 있는 연산은 1을 빼거나, 2로 나누어떨어질 때 2로 나누거나, 3으로 나누어떨어질 때 3으로 나누는 것입니다. 따라서 2부터 N까지 각 x에 대해 가능한 이전 값들의 dp 중 최솟값에 1을 더하면 됩니다. 모든 이전 값은 x보다 작으므로 이미 계...

문제 링크 중위 순회에서는 노드가 왼쪽·오른쪽 서브트리 사이에 놓이고, 후위 순회에서는 각 서브트리의 마지막 값이 루트입니다. 따라서 현재 처리할 두 구간에서 후위 순회의 마지막 값이 해당 서브트리의 루트입니다. 값에서 중위 순회 인덱스로 가는 표를 사용하면 분할 위치를 상수 시간에 찾을 수 있습니다. 그 위치 왼쪽의 노드 수가 왼쪽 서브트리의 크기...

문제 링크 i < j이면서 A[i] > A[j]인 인덱스 쌍 (i, j)를 역전(inversion)이라고 합니다. 버블 정렬은 순서가 잘못된 인접 원소를 교환합니다. 한 번 교환된 쌍은 올바른 순서가 되어 다시 교환되지 않으며, 모든 역전이 하나씩 제거됩니다. 따라서 버블 정렬의 전체 교환 횟수는 역전의 수와 같습니다. 병합 정렬로 실제...

문제 링크 각 입력 줄은 노드 하나와 왼쪽·오른쪽 자식을 나타냅니다. 노드 이름은 대문자 한 글자이므로 label - 'A'를 인덱스로 하는 배열에 두 자식을 저장합니다. 자식이 없으면 .이 입력되며, 배열에 그대로 보존한 뒤 순회할 때 이 값을 만나면 해당 가지를 건너뜁니다. A에서 시작해 전위 순회는 노드-왼쪽-오른쪽, 중위 순회는 왼쪽-노드-오...

BOJ 1967: 트리의 지름 입력에는 무방향 간선이 한 번씩만 주어집니다. 어느 방향으로든 탐색할 수 있도록 각 간선을 양쪽 정점의 인접 리스트에 한 번씩 추가합니다. 각 방향을 중복해서 추가하지 않습니다. 트리에서는 두 정점 사이의 단순 경로가 유일하며, 그 경로의 길이가 두 정점 사이의 거리입니다. 임의의 정점 s에서 트리 전체를 순회해 각 ...

문제 링크 가중치가 음이 아닌 트리에서 임의의 정점으로부터 가장 먼 정점 a를 찾고, 이어서 a에서 가장 먼 정점을 찾으면 두 번째 탐색에서 얻은 거리가 트리의 지름입니다. 임의의 시작점에서 가장 먼 정점은 지름의 한 끝점입니다. 지름 경로와 시작점에서 뻗는 경로를 함께 살펴보면, 트리의 유일한 경로와 음이 아닌 가중치의 성질에 따라 지름의 양 끝점...

BOJ 5639: 이진 검색 트리 전위 순회로 BST 구성하기 입력은 서로 다른 키를 가진 이진 검색 트리의 전위 순회 결과입니다. 전위 순회에서는 노드가 모든 자손보다 먼저 등장합니다. 루트에서 가장 최근에 방문한 노드까지의 경로를 스택에 유지합니다. 스택의 맨 위는 현재 삽입 위치입니다. 다음 키가 맨 위 키보다 작으면 그 노드의 왼쪽 자식입니...

BOJ 2357: 최솟값과 최댓값 반복형 세그먼트 트리 입력 값은 두 개의 평면 배열에서 각각 리프 n + i에 저장합니다. 각 내부 노드는 자식 두 개를 병합합니다. 최솟값 트리에는 min(left, right), 최댓값 트리에는 max(left, right)를 저장합니다. 이 병합 연산은 결합법칙을 만족하므로 구간을 서로 겹치지 않는 트리 구간...

BOJ 11725: 트리의 부모 찾기 순회로 트리에 루트 지정하기 입력으로 주어진 무방향 간선을 인접 리스트에 저장하고 1번 노드를 루트로 둡니다. 너비 우선 탐색 큐에 1번 노드를 넣고 탐색하면, 현재 노드에서 처음 발견한 이웃은 현재 노드의 자식입니다. 이 관계는 이웃을 큐에서 꺼낼 때가 아니라 큐에 넣을 때 기록합니다. 발견 즉시 방문 상태를...

문제 링크 간선을 입력 순서대로 처리합니다. 간선 (a, b)를 추가하기 전에, 앞서 처리한 간선으로 이루어진 그래프에서 두 정점의 연결 요소 대표를 찾습니다. 대표가 같다면 이미 a와 b를 잇는 경로가 있으므로 이 간선을 추가할 때 사이클이 생깁니다. 따라서 그 차례를 1부터 세어 즉시 출력합니다. 대표가 다르면 두 연결 요소를 합칩니다. 경로로 ...

문제 링크 팰린드롬 표를 미리 계산한 뒤 백트래킹 palindrome[left][right]를 양 끝 인덱스를 포함하는 부분 문자열 s[left..right]가 팰린드롬인지 나타내는 값으로 둔다. 양 끝 문자가 같고, 길이가 2 이하이거나 그 내부 부분 문자열도 팰린드롬이면 해당 부분 문자열은 팰린드롬이다. palindrome[left][ri...

풀이 각 사람의 이름을 부모 이름에 대응시키고, 각 루트에는 컴포넌트 크기를 저장합니다. 처음 등장한 이름은 자기 자신을 루트로 하며 크기는 1입니다. 친구 관계를 입력받으면 두 사람의 루트를 찾아 작은 컴포넌트를 큰 컴포넌트 아래에 연결하고, 살아남은 루트의 크기를 합칩니다. 이미 루트가 같으면 구조를 변경하지 않고 기존 크기를 출력합니다. 테스트...

문제 링크 도시를 정점, 도로를 무방향 간선으로 생각합니다. 여행 계획에 포함된 모든 도시가 같은 연결 요소에 속할 때, 그리고 그때만 여행이 가능합니다. 그러면 계획에서 연속한 두 도시 사이에 경로가 존재하고, 그 경로들을 이어 여행할 수 있습니다. 따라서 도시 하나만 있는 계획은 항상 가능합니다. 분리 집합(DSU) 자료구조를 사용합니다. 처음...

문제 링크 인접한 두 파일을 합치는 비용은 두 파일 크기의 합입니다. 파일의 순서는 유지되므로, 마지막으로 합치는 시점을 기준으로 최적의 과정을 나눌 수 있습니다. [i, k] 구간을 먼저 하나로 합치고 [k + 1, j] 구간도 하나로 합친 다음, 두 결과를 합치는 비용은 [i, j] 전체 크기입니다. dp[i][j]를 0부터 시작하는 인덱스에서...

문제 링크 dist[u][v]를 정점 u에서 정점 v까지 가는 방향 최단 거리라고 하겠습니다. 모든 값을 무한대로 초기화하고 dist[i][i]는 0으로 둡니다. 직접 간선이 여러 개 있으면 그중 가장 작은 가중치를 저장합니다. 대각선의 0은 플로이드–워셜에서 빈 경로를 나타내며, 직접 자기 자신으로 향하는 간선은 사이클 후보 계산을 위해 별도의 간...

풀이 best[v][c]는 총비용을 c 이하로 사용해 공항 v에 도착하는 최소 시간을 나타냅니다. 시작점은 비용을 쓰지 않고 도달 가능하므로 모든 비용 한도에서 best[0][c] = 0으로 두고, 나머지는 무한대로 초기화합니다. 각 티켓의 새 비용이 M 이하일 때만 완화합니다. 어떤 비용 한도에서 경로가 더 좋은 시간을 만들면 더 큰 비용 한도의 ...

문제 링크 dist[i][j]를 도시 i에서 도시 j로 가는 현재까지 알려진 최단 비용이라고 하겠습니다. 처음에는 같은 도시에 머무르는 비용 0과 직접 연결된 버스 노선만 알려져 있습니다. 출발 도시와 도착 도시가 같은 노선이 여러 개라면 그중 비용이 가장 작은 노선만 저장합니다. 각 도시 k를 중간 경유지로 차례대로 고려합니다. k를 처리하기 전...

문제 링크 차수로 판별하기 신뢰 관계 [a, b]를 사람 a에서 사람 b로 향하는 방향 간선으로 보자. 마을 판사는 누구도 신뢰하지 않으므로 진출 차수가 0이다. 또한 나머지 모든 사람이 판사를 신뢰하므로 진입 차수는 n - 1이다. 두 조건을 모두 확인해야 한다. 진입 차수만으로 판별하면 다른 사람을 신뢰하는 사람을 판사로 잘못 고를 수 있다...

풀이 이 문제는 방향 그래프이며 음수 가중치 간선이 있으므로 다익스트라 알고리즘을 사용할 수 없습니다. 벨만–포드는 1번 정점에서 각 정점까지 알려진 최단 거리를 저장하고, 모든 간선을 최대 V - 1회 완화합니다. 음수 사이클을 포함하지 않는 최단 경로는 최대 V - 1개의 간선으로 이루어지므로, 한 번의 순회에서 거리가 바뀌지 않으면 조기에 종료...

문제 링크 풀이 각 테스트 케이스에서 출발점 s와 지정 간선의 양 끝점 g, h를 시작점으로 다익스트라를 실행합니다. 도착 후보 x는 s에서 x로 가는 최단 경로 중 지정된 간선 g-h를 지나는 경로가 있을 때 정답입니다. 따라서 최단 거리가 다음 두 경로 길이 중 하나와 같아야 합니다. dist(s, g) + w(g, h) + dist(h...

문제 링크 구간 동적 계획법 배열 양 끝에 값이 1인 가상 풍선을 추가한다. dp[l][r]를 양쪽 경계 풍선 l, r은 터뜨리지 않은 채 그 사이에 있는 풍선을 모두 터뜨려 얻을 수 있는 최대 코인 수라고 하자. 열린 구간에서 마지막으로 터뜨릴 풍선 k를 고른다. 그 시점에는 구간 안의 다른 풍선이 이미 모두 사라졌으므로 k의 양옆에는 정확...

문제 링크 풀이 양의 가중치를 갖는 무방향 그래프에서 정점 v1, v2를 모두 방문하는 최단 경로를 구합니다. 두 필수 정점을 방문하는 순서는 1 → v1 → v2 → N 또는 1 → v2 → v1 → N뿐입니다. 각 구간의 최단 거리를 더한 두 후보 중 작은 값을 선택하고, 후보 경로가 모두 도달 불가능하면 -1을 출력합니다. 시작점 1, v1...

문제 링크 배열의 한 원소를 갱신하면서 임의의 닫힌 구간 곱을 1,000,000,007로 나눈 나머지로 구합니다. 갱신 때 한 위치만 바뀌므로 반복형 세그먼트 트리에서 해당 리프와 그 조상만 다시 계산하면 됩니다. 각 내부 노드는 두 자식 값의 곱을 MOD로 나눈 값입니다. 트리의 n개 리프는 [n, 2n)에 둡니다. 인덱스 p를 갱신할 때 리프 ...

풀이 방향 그래프이므로 각 간선은 출발 정점의 인접 리스트에만 저장합니다. 모든 간선의 가중치가 음수가 아니므로 다익스트라 알고리즘을 사용할 수 있습니다. 거리 배열에는 시작점에서 각 정점까지 알려진 최솟값을 저장합니다. 우선순위 큐에서 현재 임시 거리가 가장 작은 항목을 꺼내 해당 정점의 간선을 완화하면 이웃 정점의 거리를 더 짧게 만들 수 있습니...

문제 링크 풀이 컴퓨터들을 정점, 컴퓨터 사이의 직접 연결을 간선으로 보면 무방향 그래프가 됩니다. computers[i][j] === 1은 i번 컴퓨터와 j번 컴퓨터가 직접 연결되어 있다는 뜻입니다. 문제에서 구하는 네트워크 수는 이 그래프의 연결 요소 개수입니다. 모든 컴퓨터를 순서대로 확인하면서 아직 방문하지 않은 컴퓨터를 발견할 때마다 네...

각 테스트 그래프의 정점에 두 가지 색을 칠합니다. 모든 간선이 서로 다른 색의 정점을 연결할 때, 그리고 그때에만 그래프는 이분 그래프입니다. 그래프가 비연결일 수 있으므로 아직 색칠하지 않은 모든 정점에서 너비 우선 탐색을 시작합니다. 탐색 중 새로 발견한 이웃에는 현재 정점과 반대 색을 지정합니다. 이미 같은 색인 두 정점을 잇는 간선을 발견하면...

문제 링크 각 테스트 케이스에서 L × L 체스판의 시작 칸에서 목표 칸까지 이동하는 나이트의 최소 이동 횟수를 구합니다. 한 번 이동할 때 한 좌표는 1, 다른 좌표는 2만큼 변하며, 두 좌표의 부호는 각각 달라질 수 있습니다. 나이트는 체스판 밖으로 나갈 수 없습니다. 체스판의 각 칸을 그래프의 정점으로, 가능한 나이트 이동을 간선으로 봅니다....

문제 링크 풀이 후보를 정렬한 뒤 인덱스를 기준으로 깊이 우선 탐색을 합니다. 각 재귀 호출은 현재 인덱스보다 뒤에 있는 인덱스(i + 1)만 선택하므로 배열의 각 원소는 최대 한 번만 사용할 수 있습니다. 서로 다른 인덱스에 있는 같은 값은 각각 별도의 원소로 사용할 수 있습니다. 같은 탐색 깊이에서 바로 앞 후보와 값이 같으면 건너뜁니다....

문제 링크 r = L / 2라고 하겠습니다. 경과 시간 E에서 관람차의 회전각은 주기 T를 이용해 theta = 2π * (E mod T) / T 라디안으로 나타낼 수 있습니다. E가 T보다 커도 E mod T를 사용하면 각도를 한 바퀴 범위 안으로 되돌릴 수 있습니다. 관람차의 최하점 높이를 0으로 두면, 회전하는 수직면에서 탑승자의 좌표는 y ...

문제 링크 dp[x]를 합계 x를 만드는 데 필요한 동전의 최소 개수라고 정의합니다. dp[0] = 0으로 두고, 양의 금액마다 마지막에 사용한 동전은 세 가지 액면 A, B, C 중 하나입니다. 따라서 다음 점화식을 얻습니다. dp[x] = min(dp[x - coin] + 1) (각 액면 coin <= x에 대해) 금액을 작은 순서대로 ...

문제 링크 일렬로 놓인 N개의 위치 중에서 서로 인접하지 않도록 k개를 고르는 방법의 수를 k = 1부터 N까지 각각 구합니다. 각 답은 1,000,000,007로 나눈 나머지로 출력합니다. 선택한 위치를 x_1 < x_2 < ... < x_k라고 합시다. 연속해서 선택된 두 위치는 인접할 수 없으므로 x_(i+1) >= x_...

문제 링크 정수 N개가 들어 있는 두 배열이 주어집니다. 첫 번째 배열의 각 원소를 두 번째 배열의 원소 하나와 짝지어, 모든 절댓값 차이의 합을 최소화해야 합니다. 두 배열을 각각 오름차순으로 정렬한 뒤 같은 인덱스의 원소끼리 짝지으면 최솟값을 얻습니다. 이를 위해 x <= y, u <= v인 두 원소를 생각해 봅시다. 같은 순서로 짝...

문제 링크 각 정점 i의 답은 정점 1에서 i까지의 최단 거리와 i에서 정점 N까지의 최단 거리를 더한 값입니다. 그래프는 무방향이므로 두 번째 거리는 N에서 i까지의 최단 거리와 같습니다. 정점 1에서 한 번, 정점 N에서 한 번 다익스트라 알고리즘을 실행한 뒤 각 정점에서 두 거리를 더합니다. 각 간선은 인접 리스트에 저장합니다. 모든 간선의 ...

문제 링크 처음에는 모든 칸이 흰색입니다. 칸을 빨간색으로 칠하거나 두 칸을 지정하는 질의가 주어집니다. 두 칸이 모두 빨간색이고 빨간 칸만 상하좌우로 이동하여 서로 도달할 수 있으면 Yes, 그렇지 않으면 No를 출력합니다. 각 격자 칸을 분리 집합 자료구조(DSU)의 원소로 취급하고, 빨간 칸을 나타내는 red 배열을 따로 관리합니다. 칸을 칠...

문제 링크 각 작업에는 마감 시각 D, 소요 시간 C, 보상 S가 주어집니다. 작업을 마감 시각의 오름차순으로 정렬해 차례로 처리합니다. dp[t]를 시각 t까지 끝나는 일정에서 얻을 수 있는 최대 보상이라고 정의합니다. 각 작업을 선택하는 경우를 고려해 t를 D부터 C까지 내림차순으로 순회하며 dp[t] = max(dp[t], dp[t - C] ...

문제 링크 학생 N명의 점수와 반 번호가 주어집니다. 각 질문에서 지정한 포함 구간 [L, R]에 대해 1반과 2반의 점수 합을 각각 출력합니다. 반별 누적 합 배열 두 개를 만듭니다. classOne[i]는 1번부터 i번 학생까지의 1반 점수 합이고, classTwo[i]는 같은 구간의 2반 점수 합입니다. 학생 i의 반에 해당하는 배열에만 점수...

문제 링크 각 점을 기준점으로 삼고, 그 점에서 다른 모든 점을 향하는 방향을 살펴봅니다. 두 방향을 선택하면 기준점에서 하나의 각이 만들어지므로, 모든 방향 쌍 중 작은 쪽의 각을 최대로 하면 됩니다. 방향각을 도 단위의 [0, 360) 범위로 정렬한 뒤, 정렬된 배열을 복제하여 복사본의 각도에 360을 더합니다. m = N - 1이라 할 때 각...

문자열 S가 주어졌을 때 atcoder와 같은 부분 수열의 개수를 셉니다. 부분 수열은 문자의 순서를 바꾸지 않고 0개 이상의 문자를 삭제해 만들며, 선택한 위치가 다르면 서로 다른 부분 수열로 셉니다. dp[j]를 지금까지 처리한 문자들로 atcoder의 처음 j개 문자를 만드는 방법의 수라고 합니다. 초기 상태의 dp[0] = 1은 빈 접두사를 ...

문제 링크 각 클래스의 평가 점수가 주어지고, 각 질문 점수와 가장 가까운 클래스 점수까지의 절대 차이를 출력합니다. 클래스 점수를 오름차순으로 한 번 정렬한 뒤, 각 질문에 대해 이분 탐색으로 삽입 위치를 찾습니다. 삽입 위치의 바로 앞과 바로 뒤에 있는 점수만 비교하면 충분합니다. 삽입 위치보다 앞의 모든 점수는 앞의 이웃보다 작거나 같으므로 ...

문제 링크 문자열 S에서 문자의 순서를 바꾸지 않고 정확히 K개를 골라 사전순으로 가장 작은 부분 수열을 만듭니다. 정확히 N - K개의 문자를 버릴 수 있습니다. S를 왼쪽부터 훑으면서 선택한 문자를 스택에 저장합니다. 현재 문자가 스택의 마지막 문자보다 작고 아직 버릴 수 있는 문자가 남아 있다면 마지막 문자를 제거합니다. 이는 사전순에 대한 ...

문제 링크 허용된 숫자만 사용해 값이 B로 나누어떨어지는 길이 N의 숫자 문자열 개수를 구합니다. 첫 자리는 0이어도 됩니다. 상태는 B로 나눈 나머지이며, 나머지가 r일 때 숫자 d를 뒤에 붙이면 나머지는 (10r + d) % B가 됩니다. T[next][current]를 나머지 current에서 next로 이동시키는 허용 숫자의 개수로 정의합니...

문제 링크 각 칸에 대해 해당 행과 열에 있는 모든 값의 합을 출력합니다. 각 행의 합과 각 열의 합을 한 번씩 구한 뒤, 모든 칸의 답을 계산합니다. 해당 칸의 값은 행의 합과 열의 합에 모두 포함되므로, 한 번 빼서 중복 계산을 바로잡습니다. rowSum[i] + colSum[j] - grid[i][j] 큰 합이 int 범위를 넘지 않도록 값...

문제 링크 이 문제는 트리에서 경로에 포함될 수 있는 마을 수의 최댓값을 구합니다. 트리에서는 임의의 두 정점 사이의 경로가 유일하며, 가장 긴 경로를 트리의 지름이라고 합니다. 두 번 탐색하는 방법으로 지름을 구합니다. 임의의 정점에서 시작해 트리를 탐색하고 가장 멀리 있는 끝점 u를 찾은 다음, u에서 다시 탐색합니다. u에서 가장 멀리 있는 ...

괄호 문자열을 왼쪽부터 하나씩 만듭니다. 어떤 접두사에서도 닫는 괄호 수가 여는 괄호 수보다 많아서는 안 됩니다. 그렇지 않으면 뒤에 어떤 문자열을 붙여도 균형 잡힌 문자열이 될 수 없습니다. 길이 N인 완전한 균형 괄호 문자열에는 여는 괄호가 정확히 N/2개 있습니다. 따라서 재귀에서는 여는 괄호를 N/2개보다 적게 사용했을 때 (를 추가하고, c...

길이 L인 막대와 N개의 가능한 절단 위치가 주어집니다. 가능한 위치 중 정확히 K개를 선택해 막대를 K + 1개의 조각으로 나누고, 가장 짧은 조각의 길이를 최대화합니다. 최솟값 후보 d에 대해 가능한 절단 위치를 왼쪽부터 확인합니다. 마지막 절단 위치(처음에는 0)로부터 거리가 d 이상이 되는 즉시 절단하고, K번 절단하면 탐색을 멈춥니다. 각 ...

서로소 집합 합집합(DSU) 자료구조는 0부터 n까지의 정수 집합을 여러 부분집합으로 관리합니다. 각 집합은 루트로 표현하며, find(x)는 원소 x가 속한 집합의 대표 원소를 반환합니다. 합집합 연산은 두 집합을 하나로 합치고, 연결 여부 질의는 두 원소의 대표 원소가 같은지 확인합니다. parent 배열은 포리스트를 이룹니다. 자기 자신을 부모...

문제 링크 서로 다른 양의 정수 candidates와 목표값이 주어질 때, 합이 목표값이 되는 모든 고유한 조합을 반환한다. 각 후보 숫자는 횟수 제한 없이 사용할 수 있다. 후보를 정렬한 뒤 깊이 우선 백트래킹을 수행한다. 헬퍼 함수는 시작 인덱스와 남은 합을 전달받는다. 재귀 호출에서 선택한 후보의 인덱스부터 다시 선택하므로 같은 후보를 재...

문제 링크 미로는 N × M 격자이며, 0은 빈 칸이고 1은 벽입니다. 왼쪽 위 칸에서 출발해 오른쪽 아래 칸까지 가는 경로에 포함되는 칸의 최솟값을 구합니다. 벽은 최대 한 개까지 부술 수 있습니다. 시작 칸과 도착 칸도 경로의 칸 수에 포함하며, 경로가 없으면 -1을 출력합니다. 위치만으로는 BFS 상태를 충분히 나타낼 수 없습니다. 벽을 아직...

펜윅 트리(이진 인덱스 트리)는 부분 합을 저장하여 한 원소의 변경과 구간의 접두 합 조회를 각각 O(log N) 시간에 처리합니다. 원본 값은 별도로 보관합니다. 1-based 인덱스 i의 값이 old에서 new로 바뀌면 차이 new - old를 트리의 인덱스 i에 더합니다. 1-based 인덱스 i에서 i & -i는 가장 낮은 비트 하나를...

풀이 0부터 100000까지의 정수를 각각 하나의 상태로 봅니다. 상태 x에서는 결과가 허용 범위 안에 있을 때 x - 1, x + 1, 2 * x로 한 번에 이동할 수 있습니다. 모든 간선의 비용이 1이므로 너비 우선 탐색(BFS)은 시작점으로부터의 거리가 작은 상태부터 방문합니다. 따라서 목표를 처음 발견했을 때의 이동 횟수가 최단 거리입니다. ...

문제 링크 풀이 각 숫자를 십진수 문자열로 바꾼 다음, a + b > b + a일 때 a가 b보다 앞에 오도록 정렬합니다. 예를 들어, "330" > "303"이므로 "3"은 "30"보다 앞에 옵니다. 정렬된 순서대로 이어 붙이면 만들 수 있는 가장 큰 수가 됩니다. 비교 규칙은 교환 논증으로 설명할 수 있습니다. 이어 붙인 결과에서 ...

문제 링크 풀이 첫 번째 항인 "1"에서 시작합니다. 다음 항을 만들 때는 현재 항을 왼쪽에서 오른쪽으로 훑으며 같은 숫자가 연속되는 최대 구간을 찾고, 그 구간의 길이와 숫자를 차례로 추가합니다. 구간 전체를 처리한 뒤 다음 위치로 이동하므로 각 숫자는 정확히 한 번씩 인코딩됩니다. 이 변환을 n - 1회 반복하면 원하는 항을 얻습니다. 각...

문제 링크 토마토 상자는 3차원 격자입니다. 익은 토마토는 축을 따라 인접한 여섯 방향의 익지 않은 토마토를 익게 하며, 모든 변화는 하루 단위로 동시에 일어납니다. 익지 않은 토마토가 모두 익을 때까지 걸리는 날짜를 구하고, 끝내 익지 못하는 토마토가 있으면 -1을 출력합니다. 다중 시작점 너비 우선 탐색(BFS)을 사용합니다. 탐색을 시작하기 ...

유효한 스도쿠 보드에는 해가 하나만 있습니다. 각 행, 열, 3 × 3 박스에 1부터 9까지의 숫자가 정확히 한 번씩 들어가도록 빈 칸을 제자리에서 채웁니다. 문제 링크 접근 방법 각 행, 열, 박스마다 이미 사용 중인 숫자를 9비트 마스크로 기록합니다. 비트 d는 숫자 d + 1을 나타내며, 비트가 설정되어 있으면 해당 칸에 그 숫자를 놓을...

문제 링크 9×9 스도쿠 보드가 유효한지 확인한다. 채워진 칸만 검사하면 된다. 빈칸(.)은 무시하며, 현재 부분 보드가 스도쿠를 완성할 수 있는지는 확인하지 않는다. 각 행, 열, 3×3 박스에서 이미 사용된 숫자를 각각 9개의 정수 마스크에 기록한다. 숫자 d는 1 << (d - '1') 비트로 나타낸다. 칸 (r, c)의 박스 인덱...

백준 1655번: 가운데를 말해요 지금까지 입력된 수를 두 개의 우선순위 큐에 나누어 저장한다. lower는 작은 절반을 담는 최대 힙이고, upper는 큰 절반을 담는 최소 힙이다. 다음 두 불변식을 유지한다. lower의 모든 값은 upper의 모든 값보다 작거나 같다. lower의 원소 수는 upper와 같거나, 정확히 하나 더 많다...

문제 링크 배열이 정렬되어 있으므로 이진 탐색 두 번으로 경계를 찾을 수 있다. 첫 번째 탐색은 값이 target 이상인 첫 인덱스를 찾고, 두 번째 탐색은 값이 target보다 큰 첫 인덱스를 찾는다. 첫 번째 경계가 배열 끝이거나 해당 위치의 값이 target이 아니면 목표값은 없다. 그렇지 않으면 첫 번째 경계와 두 번째 경계보다 1 작...

문제 링크 풀이 오름차순으로 정렬된 배열을 회전한 입력이 주어지며, 모든 값은 서로 다릅니다. 각 이진 탐색 단계에서 현재 구간의 절반 중 적어도 한쪽은 정렬되어 있습니다. 정렬된 절반의 값 범위 안에 target이 있는지 확인합니다. 그 범위에 있으면 반대쪽 절반을 버리고, 없으면 정렬된 절반을 버립니다. 따라서 target이 배열에 존재한다...

문제 링크 풀이 문자열을 왼쪽에서 오른쪽으로 순회하면서 각 문자의 인덱스를 ArrayDeque<Integer>에 저장합니다. 스택은 현재 유효한 부분 문자열 바로 앞의 경계를 나타내는 센티널 인덱스 -1로 시작합니다. 여는 괄호를 만나면 그 인덱스를 스택에 넣습니다. 닫는 괄호를 만나면 가장 최근의 짝이 없는 여는 괄호 위치(또는 ...

BOJ 11279: 최대 힙 최대 힙에서는 모든 부모 노드의 값이 자식 노드의 값보다 크거나 같으므로, 가장 큰 값이 항상 루트에 있다. 값을 삽입할 때는 배열 끝에 추가한 뒤 부모보다 큰 동안 위로 올린다. 최댓값을 삭제할 때는 루트에 마지막 값을 옮기고, 더 큰 자식과 교환하며 아래로 내린다. 각 연산은 루트에서 리프까지의 경로를 최대 한 번 따...

문제 링크 배열의 역전 쌍 개수는 i < j이면서 A[i] > A[j]인 인덱스 쌍의 수다. 값이 같은 쌍은 역전 쌍이 아니다. 정렬된 ArrayList에 각 값을 삽입하면 이진 탐색으로 위치를 찾을 수 있지만, 삽입 과정에서 원소를 이동하는 데 한 번에 O(N)이 걸리므로 전체 시간 복잡도는 O(N²)이다. 병합 정렬을 이용하면 O(N...

문제 링크 풀이 이진 탐색으로 하한(lower bound), 즉 target보다 크거나 같은 첫 번째 값의 인덱스를 찾습니다. 반열린 탐색 구간 [left, right)을 유지하며, 처음에는 모든 유효한 배열 인덱스를 포함합니다. 매 단계에서 left보다 앞에 있는 모든 값은 target보다 작고, right부터 뒤에 있는 모든 값은 targe...

문제 링크 풀이 현재 순열보다 크면서 가능한 한 가장 작은 순열을 만들려면, 오른쪽에서부터 증가시킬 수 있는 가장 오른쪽 위치를 바꿔야 합니다. 오른쪽에서 왼쪽으로 탐색해 nums[i] < nums[i + 1]을 만족하는 첫 인덱스 i를 찾습니다. i 뒤의 접미부는 비증가 순서입니다. 그러한 인덱스가 없다면 배열 전체가 비증가 순서이므로 ...

문제 링크 풀이 모든 단어의 길이가 같고 0이 아니므로, 문자열을 단어 길이 L만큼 이동하는 여러 슬라이딩 윈도로 나눌 수 있습니다. 시작 오프셋을 0부터 L - 1까지 각각 처리합니다. target은 words에 포함된 각 단어의 요구 개수를 저장하고, window는 현재 윈도에 포함된 단어 개수를 저장합니다. 이렇게 하면 중복 단어도 정확히...

문제 링크 곱셈, 나눗셈, 나머지 연산자를 사용하지 않고 두 정수를 나누는 문제다. 몫은 0을 향해 버림한다. 문제의 제약 조건에서 제수는 0이 아니다. 두 피연산자의 절댓값을 long으로 구한다. 절댓값을 구하기 전에 long으로 변환해야 한다. Integer.MIN_VALUE의 양의 절댓값은 int에 담을 수 없지만 long에는 담을 수 있기 ...

[문제 링크] https://leetcode.com/problems/implement-strstr/ 접두사 함수(“접두사이면서 접미사인 가장 긴 proper prefix”를 저장하므로 LPS 배열이라고도 합니다)는 needle의 각 위치에서 끝나는 부분 문자열에 대해, 동시에 접미사이기도 한 가장 긴 proper prefix의 길이를 기록합니다....

문제 풀이 nums를 왼쪽에서 오른쪽으로 순회하면서 남길 다음 값을 기록할 쓰기 인덱스를 유지합니다. 현재 값이 val과 다르면 nums[write]에 복사하고 write를 증가시킵니다. val과 같은 값은 건너뜁니다. 각 원소를 처리하기 전, 앞의 write개 위치에는 지금까지 만난 값 중 val과 다른 값만 원래 순서대로 정확히 들어 있습니다...

문제 링크 풀이 입력이 정렬되어 있으므로 같은 값은 서로 인접해 있습니다. 읽기 인덱스로 배열을 왼쪽부터 순회하고, 쓰기 인덱스로 새로운 고유 값이 들어갈 다음 위치를 추적합니다. 현재 값이 마지막으로 쓴 값과 다르면 현재 값을 쓰기 위치에 복사한 다음 쓰기 인덱스를 증가시킵니다. 각 읽기 단계에서 nums[0..write) 접두부에는 이미 ...

문제 풀이 리스트를 한 그룹씩 처리합니다. 각 그룹의 첫 노드부터 k - 1개의 링크를 따라가 k번째 노드를 찾습니다. 남은 노드가 k개보다 적으면 그 접미 리스트는 원래 순서를 유지해야 하므로 처리를 멈춥니다. 그룹을 완성할 수 있으면 그룹 다음 노드를 groupNext에 저장한 뒤, 그룹 안의 링크를 groupNext 방향으로 뒤집습니다. ...

[문제 링크] https://leetcode.com/problems/swap-nodes-in-pairs/ 각 인접한 두 노드의 위치를 서로 바꿉니다. 노드의 값만 바꾸는 것이 아니라 next 참조를 다시 연결하므로, 원래 리스트의 노드를 그대로 재사용합니다. 더미 노드는 첫 번째 쌍 앞에도 이전 노드가 있는 것처럼 다룰 수 있게 해 줍니다. b...

문제 풀이 비어 있지 않은 각 입력 리스트의 현재 헤드를 최소 힙에 넣습니다. 각 단계에서 힙에는 아직 노드가 남아 있는 각 리스트의 가장 앞선 미병합 노드가 하나씩 들어 있습니다. 따라서 힙의 최솟값은 모든 리스트에 남은 노드 중 가장 작으므로 결과에 추가할 수 있습니다. 해당 노드를 꺼낸 뒤 결과에 연결하기 전에 그 노드의 다음 노드를 힙에...

문제 풀이 더미 헤드를 두면 결과 리스트를 간단하게 만들 수 있습니다. tail 포인터는 마지막에 추가한 노드를 가리킵니다. 두 입력 리스트가 모두 비어 있지 않은 동안 현재 노드 중 더 작은 노드를 결과에 연결하고, 그 노드가 속한 입력 리스트만 한 칸 전진시킵니다. 이 과정에서 결과는 항상 정렬된 상태이며, 입력에서 처리한 노드가 순서대로 ...

문제 동적 계획법 이 문제에서 사용하는 패턴 연산자는 두 가지뿐입니다. .은 임의의 문자 하나와 일치하고, *는 바로 앞에 있는 원자를 0회 이상 반복한 것과 일치합니다. 따라서 *는 바로 앞의 원자와 함께 처리하며, 단독으로 쓰이거나 패턴의 더 앞부분에 적용되지 않습니다. 문제에서 모든 패턴은 유효하다고 보장하므로 각 * 앞에는 원자가 있습니다....

문제 풀이 문자열을 왼쪽에서 오른쪽으로 순회하면서 아직 짝을 찾지 못한 여는 괄호를 스택에 저장합니다. 각 문자를 처리하기 직전에 스택에는 지금까지 확인한 여는 괄호 중 아직 닫히지 않은 것만 원래 순서대로 들어 있습니다. 따라서 닫는 괄호가 나오면 가장 최근에 나온 여는 괄호와 짝이 맞아야 합니다. 스택이 비어 있거나 괄호 종류가 맞지 않으면 ...

문제 백트래킹 입력에는 2부터 9까지의 숫자가 주어집니다. 각 숫자는 전화 키패드의 문자에 직접 대응합니다. 입력이 비어 있으면 만들 수 있는 조합도 없으므로 빈 리스트를 반환합니다. 재귀는 숫자를 한 자리씩 처리합니다. 인덱스가 i인 호출에 진입할 때 StringBuilder에는 앞의 i개 숫자에 대해 각각 하나씩 선택한 문자가 입력 순서대...

문제 링크 이 문제는 서로에게 도달할 수 있는 서로 다른 두 정점으로 이루어진 순서 없는 쌍의 개수를 구합니다. 두 정점이 서로에게 도달할 수 있는 것은 두 정점이 같은 강한 연결 요소(SCC)에 속할 때, 그리고 그때뿐입니다. SCC 안에서는 모든 정점에서 다른 모든 정점으로 향하는 방향 경로가 존재합니다. 크기가 s인 각 SCC에서는 s * (...

강한 연결 요소 방향 그래프에서 강한 연결 요소(SCC)는 모든 정점이 서로 도달 가능한 정점들의 최대 집합입니다. 서로 도달 가능하다는 것은 양방향 도달을 뜻합니다. 같은 SCC에 속한 임의의 두 정점 u와 v에 대해 u에서 v로 가는 방향 경로와 v에서 u로 가는 방향 경로가 모두 존재합니다. 한쪽 방향으로만 경로가 있다고 해서 두 정점이 같은 ...

[문제 링크] https://leetcode.com/problems/remove-nth-node-from-end-of-list/ 단일 연결 리스트의 시작 노드 head가 주어지면 뒤에서 n번째 노드를 삭제하고 리스트의 시작 노드를 반환합니다. 입력의 n은 유효하다고 보장됩니다. 값을 복사하는 대신 기존 노드의 연결을 다시 설정합니다. head ...

공식 복소수의 극형식을 다음과 같이 쓰겠습니다. [z=r(\cos\theta+i\sin\theta),] 여기서 $r\ge 0$은 복소수의 절댓값이고, $\theta$는 라디안 단위로 측정한 편각입니다. 정수 $n$에 대해 드무아브르 공식은 다음과 같습니다. [z^n=r^n\bigl(\cos(n\theta)+i\sin(n\theta)\bigr)....

문제 풀이 배열을 왼쪽에서 오른쪽으로 한 번 순회합니다. nums[i]를 처리하기 전에 맵에는 더 앞에서 확인한 값과 해당 인덱스만 저장되어 있습니다. 현재 값에 대해 보수 target - nums[i]를 맵에서 찾습니다. 보수가 있으면 저장된 인덱스와 i가 정답입니다. 찾지 못하면 현재 값과 인덱스를 저장해 이후 원소에서 사용할 수 있게 합니다....

문제 링크 풀이 중위 순회는 각 노드를 왼쪽-노드-오른쪽 순서로 방문합니다. 명시적인 스택에는 왼쪽 서브트리를 아직 모두 처리하지 않은 노드를 저장합니다. 루트에서 시작해 왼쪽으로 내려갈 수 있는 만큼 내려가며 각 노드를 스택에 넣습니다. 그런 다음 다음 노드를 꺼내 값을 결과에 추가하고 오른쪽 자식으로 이동합니다. 현재 노드와 스택이 모두 비...

[문제 링크] https://leetcode.com/problems/single-element-in-a-sorted-array/ 정렬된 배열에서 단일 원소를 제외한 모든 값은 정확히 두 번씩 나타납니다. 단일 원소 앞에서는 각 쌍이 짝수 인덱스에서 시작하고, 단일 원소 뒤에서는 쌍의 정렬이 어긋나 각 쌍이 홀수 인덱스에서 시작합니다. 각 반복에...

[문제 링크] https://leetcode.com/problems/hamming-distance/ XOR 연산은 x와 y의 같은 위치 비트가 서로 다를 때 해당 위치를 1로 만듭니다. 따라서 x ^ y는 서로 다른 모든 비트 위치를 표시하고, Integer.bitCount는 그 1 비트의 개수, 즉 해밍 거리를 셉니다. Java 정수의 너비는...

BOJ 11659: 구간 합 구하기 4 배열의 누적 합 배열을 만든다. prefix[0] = 0으로 두고 prefix[i + 1] = prefix[i] + value[i]로 정의한다. 1부터 시작하는 인덱스를 사용하는 입력에서 양 끝이 포함되는 구간 [a, b]의 합은 prefix[b] - prefix[a - 1]이다. 이 식에서 누적 합 배열의 인...

문제 링크 풀이 입력 배열은 비어 있지 않다고 보장됩니다. 배열을 한 번 순회하면서 현재 인덱스에서 끝나야 하는 부분 배열의 최대 합(ending)과 지금까지 확인한 전체 최대 합(best)을 추적합니다. 각 원소에서 이전 부분 배열을 이어 가거나 현재 원소부터 새로 시작합니다. ending = max(nums[i], ending + nums...

문제 링크 왼쪽에서 오른쪽으로 순회하기 표준 로마 숫자에서 기호는 바로 다음에 더 큰 값의 기호가 올 때만 뺍니다. 따라서 IV는 -1 + 5 = 4이며, 뺄셈 표기에 속하지 않는 기호는 원래 값을 더합니다. 각 기호와 바로 다음 기호를 비교하면 이 규칙을 그대로 적용할 수 있습니다. 반복문 불변식은 각 반복이 끝날 때까지 처리한 모든 기호의 ...

문제 링크 풀이 리스트가 정렬되어 있으므로 같은 값은 반드시 서로 인접해 있습니다. 포인터 하나를 사용해 현재까지 유지한 마지막 노드를 가리킵니다. 다음 노드의 값이 현재 노드와 같으면 다음 노드를 건너뛰고, 다르면 포인터를 다음 노드로 이동합니다. 각 단계에서 head부터 포인터까지는 지금까지 처리한 서로 다른 값마다 노드 하나씩만 정렬된 순...

문제 링크 접근 방법 첫 번째 문자열을 왼쪽에서 오른쪽으로 순회합니다. 각 위치에서 첫 번째 문자열의 문자와 나머지 모든 문자열의 같은 위치에 있는 문자를 비교합니다. 처음으로 문자가 다르면 그 위치부터 공통 접두사가 끝나므로, 첫 번째 문자열에서 해당 위치 직전까지를 반환합니다. 비교하기 전에 각 문자열이 해당 위치의 문자를 포함할 만큼 충...

문제 풀이 음수는 부호 -가 왼쪽에만 있으므로 회문이 될 수 없습니다. 또한 0이 아닌 수가 0으로 끝나면 회문이 아닙니다. 뒤집었을 때 앞자리가 0이 되지만, 원래 정수에는 맨 앞의 0이 표현되지 않기 때문입니다. 수를 문자열로 변환하거나 모든 자릿수를 뒤집는 대신, 마지막 절반의 자릿수만 뒤집습니다. 반복할 때마다 x에서 마지막 자릿수를 제거...

문제 풀이 입력의 숫자를 하나씩 꺼내 역순으로 만든 값에 붙입니다. Java의 정수 나눗셈은 0 방향으로 버림하고 % 연산 결과는 피제수의 부호를 따릅니다. 따라서 양수와 음수 모두 x % 10은 부호를 포함한 마지막 숫자이며, 반복해서 나누면 그 숫자가 제거됩니다. 그러므로 0이나 끝에 0이 있는 경우도 별도의 처리가 필요하지 않습니다. 누적값...

문제 풀이 문자열을 한 글자씩 순회하며 현재 행의 빌더에 문자를 추가합니다. 행 인덱스는 아래쪽이나 위쪽으로 한 칸씩 이동하고, 첫 번째 행이나 마지막 행에 도달하면 이동 방향을 반대로 바꿉니다. 모든 문자를 배치한 뒤 행 빌더를 위에서 아래 순서로 이어 붙이면 변환된 문자열이 됩니다. 행이 하나뿐이거나 행 수가 문자 수 이상이면 대각선 이동이 없...

문제 풀이 모든 회문은 중심이 문자 하나인 홀수 길이 회문이거나, 인접한 두 문자 사이의 간격을 중심으로 하는 짝수 길이 회문입니다. 각 인덱스에서 두 종류의 중심을 모두 잡고, 양쪽 문자가 같은 동안 바깥쪽으로 확장합니다. 이 과정을 통해 해당 중심을 갖는 모든 회문을 확인할 수 있습니다. 가장 긴 답은 반열린 구간 [bestStart, bes...

문제 이진 탐색으로 분할하기 두 배열이 모두 정렬되어 있으므로 병합하지 않고도 각 배열을 왼쪽과 오른쪽 절반으로 나눌 수 있습니다. 왼쪽 절반에는 전체 원소 수의 절반(올림)에 해당하는 원소가 있어야 하며, 왼쪽의 모든 값은 오른쪽의 모든 값보다 작거나 같아야 합니다. 더 짧은 배열인 nums1에서 분할 위치를 이진 탐색합니다. nums1의 ...

문제: Longest Substring Without Repeating Characters 슬라이딩 윈도우 문자열의 s[left..right] 구간을 윈도우로 유지하고, 그 안의 문자를 집합에 저장합니다. 활성 윈도우에 같은 UTF-16 char가 중복되지 않는다는 것이 불변 조건입니다. right 위치의 문자가 이미 집합에 있다면 중복 문자가 사...

문제 링크 정수 배열 nums와 정수 target이 주어질 때, 서로 다른 세 원소의 합 중 target에 가장 가까운 값을 반환합니다. 같은 거리의 합이 여러 개라면 어느 것이든 반환할 수 있습니다. 배열을 오름차순으로 정렬하고 각 원소를 차례로 첫 번째 원소로 고정합니다. 나머지 범위의 양 끝에 두 포인터를 두고 세 수의 합을 탐색합니다. 합이...

문제 풀이 배열을 정렬한 뒤 각 인덱스 i를 차례로 고정하고, 나머지 구간에서 두 포인터 left = i + 1, right = nums.length - 1로 탐색합니다. 정렬되어 있으므로 포인터를 한 방향으로만 이동할 수 있습니다. 세 수의 합이 0보다 작다면 현재 left와 더 작은 오른쪽 값으로 만드는 합도 더 작으므로 left를 증가시켜...

문제 링크 그리디한 액면가 선택 로마 숫자는 큰 자리 기호부터 작은 자리 기호 순으로 씁니다. 뺄셈 표기 여섯 가지인 IV와 IX는 각각 4와 9, XL과 XC는 40과 90, CD와 CM은 400과 900을 나타냅니다. 남은 값 이하인 액면가 중 가장 큰 것을 선택해 기호를 결과에 붙이고, 그 액면가만큼 남은 값에서 뺍니다. 남은 값이 0이 ...

문제: Container With Most Water 투 포인터 l < r인 두 인덱스를 고르면 두 선 중 더 낮은 선까지만 물을 담을 수 있습니다. 컨테이너의 너비는 r - l, 높이는 min(height[l], height[r])이며 넓이는 다음과 같습니다. [(r-l)\times\min(\text{height}[l],\text{he...

풀이 트리는 연결되어 있고 사이클이 없는 무방향 그래프입니다. 방문하지 않은 정점마다 너비 우선 탐색을 시작해 해당 연결 요소 전체를 방문합니다. 정점은 큐에 넣는 순간 방문 표시를 하므로 같은 정점이 큐에 중복해서 들어가지 않습니다. 간선을 따라 이웃을 확인할 때 이미 방문한 이웃이 현재 정점의 부모가 아니라면 사이클의 증거입니다. 무방향 그래프에...