320x100 전체 글108 백준 1520번 - 내리막 길 원문(한국어): https://0archlinux0.github.io/ko/posts/boj-1520-downhill-paths/ 이 글은 이전 아카이브에서 보존했습니다. 기존 URL과 언어 간 연결 관계를 유지하며 새 출판 구조로 이전했습니다. 백준 1520번: 내리막 길 풀이: DAG에서의 동적 계획법 각 칸을 정점으로 생각합니다. 한 칸에서 상하좌우로 인접한 칸 중 높이가 더 낮은 곳으로 향하는 방향 간선을 둡니다. 모든 간선은 높이를 낮추므로 방향 사이클은 존재하지 않으며, 이 그래프는 DAG입니다. 높이가 같은 인접 칸 사이에는 간선이 없습니다. 왼쪽 위에서 오른쪽 아래까지 가는 방향 경로의 수를 구해야 합니다. 메모이제이션을 사용하는 재귀 DFS로 점화식을 바로 표현할 수 있지만, 경로에는 최.. 2026. 10. 29. BOJ 1517 — 버블 소트 원문(한국어): https://0archlinux0.github.io/ko/posts/boj-1517-bubble-sort-inversions/ 문제: BOJ 1517 — 버블 소트 (https://www.acmicpc.net/problem/1517) i A[j]인 인덱스 쌍 (i, j)를 역전(inversion)이라고 합니다. 버블 정렬은 순서가 잘못된 인접 원소를 교환합니다. 한 번 교환된 쌍은 올바른 순서가 되어 다시 교환되지 않으며, 모든 역전이 하나씩 제거됩니다. 따라서 버블 정렬의 전체 교환 횟수는 역전의 수와 같습니다. 병합 정렬로 실제 교환을 수행하지 않고 역전을 셉니다. 두 구간을 각각 정렬한 뒤 병합할 때, 오른쪽 원소가 현재 왼쪽 원소보다 작다면 그 오른쪽 원소는 왼쪽 구간에 남은 .. 2026. 10. 28. BOJ 1509 - 팰린드롬 분할 원문(한국어): https://0archlinux0.github.io/ko/posts/boj-1509-palindrome-partitioning/ 문제: BOJ 1509 — 팰린드롬 분할 (https://www.acmicpc.net/problem/1509) · English · 日本語 길이 N인 문자열 s를 연속된 팰린드롬 조각으로 나눌 때, 조각 수의 최솟값을 구합니다. 먼저 palindrome[l][r]를 계산합니다. 이는 양 끝 인덱스를 포함하는 부분 문자열 s[l..r]가 팰린드롬인지 나타냅니다. 부분 문자열 길이가 짧은 것부터 계산하면, 양 끝 문자가 같아야 하고 길이가 2 이하이거나 안쪽 부분 문자열도 이미 팰린드롬이어야 합니다. 따라서 O(N²)개의 부분 문자열을 각각 한 번씩 처리합니다. .. 2026. 10. 28. BOJ. 특정한 최단 경로 (1504) 원문(한국어): https://0archlinux0.github.io/ko/posts/boj-1504-required-path/ 이 글의 목차• 풀이 • Java 문제 링크 (https://www.acmicpc.net/problem/1504) 풀이 양의 가중치를 갖는 무방향 그래프에서 정점 v1, v2를 모두 방문하는 최단 경로를 구합니다. 두 필수 정점을 방문하는 순서는 1 → v1 → v2 → N 또는 1 → v2 → v1 → N뿐입니다. 각 구간의 최단 거리를 더한 두 후보 중 작은 값을 선택하고, 후보 경로가 모두 도달 불가능하면 -1을 출력합니다. 시작점 1, v1, v2에서 각각 다익스트라를 실행합니다. 그러면 첫 번째 순서의 길이는 d(1,v1) + d(v1,v2) + d(v2,N), 두 번.. 2026. 10. 28. BOJ 14890 — 경사로 원문(한국어): https://0archlinux0.github.io/ko/posts/boj-14890-runway/ 문제: BOJ 14890 — 경사로 (https://www.acmicpc.net/problem/14890) · English · 日本語 각 행이나 열에서 인접한 칸의 높이 차이가 0 또는 1이고, 높이 차이가 1인 곳마다 길이 L의 경사로를 놓을 수 있으면 길을 만들 수 있습니다. 경사로 하나는 높이가 낮은 쪽의 L개 칸을 차지합니다. 해당 칸들은 모두 같은 높이여야 하고, 길의 범위를 벗어나면 안 되며, 다른 경사로가 이미 사용한 칸이어서도 안 됩니다. 한 줄을 왼쪽에서 오른쪽으로 검사하면서 경사로가 놓인 칸을 기록합니다. 높이가 같은 이웃 칸은 그대로 넘어갑니다. 오르막에서는 경계 바.. 2026. 10. 28. BOJ. 개미굴 (14725) 원문(한국어): https://0archlinux0.github.io/ko/posts/boj-14725-ant-tunnel/ 문제: BOJ 14725 — 개미굴 (https://www.acmicpc.net/problem/14725) · English · 日本語 각 입력 줄은 개미굴의 루트에서 시작하는 하나의 경로입니다. 각 토큰을 트라이에 삽입하면 이미 존재하는 접두사는 합쳐집니다. 노드의 자식은 그 접두사 다음에 올 수 있는 먹이들입니다. TreeMap은 자식을 사전순으로 저장하므로, 깊이 우선 탐색은 자식을 먼저 정렬하거나 복사하지 않고도 형제 노드를 요구되는 순서대로 방문합니다. 탐색 중에는 루트에서 현재 노드까지의 간선 수만큼 --를 한 번씩 출력한 뒤, 현재 토큰과 줄바꿈을 붙입니다. 따라서 루.. 2026. 10. 28. 이전 1 2 3 4 ··· 18 다음 반응형
