Minjun Kim

PS

[PS] BOJ 6603 / 로또

문제 링크: https://www.acmicpc.net/problem/6603 백트래킹의 기본적인 구조만 이해한다면 쉽게 풀 수 있습니다. 풀이 $K$개의 원소를 가지는 집합 $S$에서, 6개의 숫자를 오름차순으로 고르는 모든 경우를 출력하는 문제입니다. ($6 < K < 13$으로 크지 않습니다.) 입력에서 집합 $S$의 원소는 항상 오름차순으로 주어지기 때문에, 항상

PS

[PS] BOJ 8905 / 리트

문제 링크: https://www.acmicpc.net/problem/8905 재밌게 풀었던 백트래킹 문제입니다. 풀이 리트 변환 규칙 문제에서 언급한 리트 표기의 규칙은 다음과 같습니다. * 각 알파벳을 리트로 나타낼 때, 최대 $K$개의 문자로 나타낼 수 있습니다. * 한 문자를 리트로 바꾸는 방법은 한 가지입니다. * d를 앞서 [)로 바꿨다면, 다른 d를 |>로

PS

[PS] BOJ 25711 / 인경산

문제 링크: https://www.acmicpc.net/problem/25711 누적 합을 어떻게 활용할 지 잘 생각해야 합니다. 풀이 누적 합 계산하기 문제에서는 $Q$개의 질문이 주어지고, 각 질문마다 $i$번 산장에서 출발해 $j$번 산장에 도달하기 위해 소모되는 체력을 계산해야 합니다. 매 질문마다 거리를 직접 계산하는 방식으로는 질문을 처리하는 과정의 시간

PS

[PS] BOJ 17383 / 옥토끼는 통신교육을 풀어라!!

문제 링크: https://www.acmicpc.net/problem/17383 아이디어만 떠올리면 구현은 어렵지 않은 문제입니다. 풀이 최적화 문제 생각해보기 문제를 처음 보면 각 문제를 어떻게 배치해 풀어야 하는지 고민이 되지만, 문제가 아닌 시간 간격에 초점을 둬봅시다. tncks0121는 항상 각 문제가 풀리는 시간의 차이에만 신경을 씁니다. 문제를 어떻게 푸는지는 상관 없이, 한

PS

[PS] BOJ 2512 / 예산

문제 링크: https://www.acmicpc.net/problem/2512 오랜만에 푸는 매개변수 탐색 문제입니다. 풀이 이분탐색과 매개변수 탐색 돌아보기 1) 이분 탐색은 무엇인가? 이분 탐색은 정렬된 배열 안에서 $O(\log N)$의 시간 복잡도로 배열 안에서 값을 찾는 방법입니다. 2) 결정 문제와 최적화 문제 이분 탐색을 이용해 풀 수 있는 문제

PS

[PS] BOJ 21772 / 가희의 고구마 먹방

문제 링크: https://www.acmicpc.net/problem/21772 백트래킹으로 고구마를 최대한 많이 먹어봅시다. 풀이 백트래킹 가희는 1개의 시작점에서 시작해, 주어진 격자 그래프를 탐색하며 $T$초 이내 ($1 \leq T \leq 10$)에 고구마를 최대한 많이 먹으려고 합니다. $T$가 작은 수 이므로, 백트래킹을 통해 가능한 경우를 모두 찾아서 최댓값을 구하면

PS

[PS] BOJ 1613 / 역사

문제 링크: https://www.acmicpc.net/problem/1613 플로이드-워셜을 통해 모든 정점들 사이의 연결 관계를 파악하는 문제입니다. 풀이 플로이드-워셜 오랜만에 푸는 플로이드-워셜 문제인 만큼, 개념을 다시 정리해 봅시다. 플로이드-워셜은 모든 정점에서 다른 모든 정점으로의 최단 경로를 계산하는 알고리즘입니다. 3중 반복문으로 동작하기 때문에, $V$개의 정점에 대해, 시간 복잡도는 $O(V^

PS

[PS] BOJ 14938 / 서강그라운드

문제 링크: https://www.acmicpc.net/problem/14938 다익스트라 문제입니다. 풀이 다익스트라 오랜만에 푸는 다익스트라 문제인 만큼, 다익스트라 알고리즘의 개념을 다시 정리해 봅시다. 다익스트라 알고리즘은 정점을 기준으로 최단 경로를 찾는 알고리즘이며, 한 개의 정점에서 다른 모든 정점으로의 최단 경로를 계산합니다. 아래는 우선순위 큐 기반의 다익스트라 구현입니다. from heapq import heappop,

PS

[PS] BOJ / N과 M

N과 M 문제 시리즈의 풀이를 모아왔습니다. N과 M (6) / BOJ 15655 * N개의 자연수 중에서 M개를 고른 수열 * 고른 수열은 오름차순 * 주어지는 $N$개의 자연수는 모두 서로 다른 수 * 같은 수 중복 사용 X 고른 수열이 오름차순으로 나오기 위해서는 입력 받은 수를 정렬한 뒤 순차적으로 백트래킹을 통해 수열을 구성하면 된다. 또,

PS

[PS] BOJ 1759 / 암호

문제 링크: https://www.acmicpc.net/problem/1759 백트래킹 문제입니다. 백트래킹을 거쳐 완성한 암호가 답이 될지 안될지를 잘 판단해야 합니다. 풀이 올바른 암호의 조건 문제에서 요구하는 올바른 암호의 조건은 다음과 같습니다. * 암호의 길이는 $L$입니다. * 암호는 미리 주어진 $C$개의 알파벳으로만 구성됩니다. * 암호는 반드시 사전순으로 증가하는 순서로 구성되어야 합니다. * abc는

PS

[PS] BOJ 4485 / 녹색 옷 입은 애가 젤다지?

문제 링크: https://www.acmicpc.net/problem/4485 그래프 탐색 문제입니다. 풀이 우선순위 큐 기반의 BFS 문제 내용을 요약하면, 결국 최소 비용으로 $(0, 0)$에서 $(N-1, N-1)$까지 갈 수 있는 경로를 찾는 문제입니다. 지도의 크기는 최대 $125 \times 125$이고, 격자 그래프 상의 문제이므로, 굳이 간선 정보를 만들어 다익스트라로

PS

[PS] BOJ 1865 / 웜홀

문제 링크: https://www.acmicpc.net/problem/1865 벨만-포드 알고리즘을 활용하는 문제입니다. 풀이 벨만-포드 이해하기 벨만-포드 알고리즘의 기본적인 설명은 이전 글을 참고해주세요. 벨만-포드 알고리즘은 다익스트라 알고리즘과 같이 한 개의 정점에서 다른 모든 정점으로의 최단 경로를 계산합니다. 따라서, 출발점에서 도달할 수 없는 정점들에 대해선 경로가 계산되지 않으며, 이러한 정점들을 거치는 음의

PS

[PS] BOJ 10216 / Count Circle Groups

문제 링크: https://www.acmicpc.net/problem/10216 분리 집합을 활용하는 문제입니다. 풀이 분리 집합 활용해 그룹 합치기 각 부대의 연결 관계를 파악하며, 만약 두 부대의 통신 영역이 닿거나 겹칠 경우 분리 집합을 사용해 같은 집합으로 합쳐주면 됩니다. 두 부대가 연결되는 경우 각 부대는 중심 좌표 $(x, y)$와 통신

PS

[PS] BOJ 1393 / 음하철도 구구팔

문제 링크: https://www.acmicpc.net/problem/1393 옛날 학생 시절에 배운 "수선의 발" 개념을 사용하면 어렵지 않게 계산할 수 있습니다. 풀이 수선의 발? 어느 한 직선과 직선 위에 있지 않은 점 P가 있을 때, 점 P에서 직선 위에 수직이 되도록 내린 점을 수선의 발이라고 합니다. 여러 방법으로

PS

[PS] BOJ 30508 / 고인물이싫어

문제 링크: https://www.acmicpc.net/problem/30508 그래프 탐색과 누적합을 모두 활용하는 문제입니다. 풀이를 떠올리면 구현은 어렵지 않습니다. 풀이 단계별로 생각하기 1. 하수구에서부터 BFS 진행해서 전체 타일에 물이 빠진 칸 파악하기 2. 누적합 계산해서 (r, c) 지점까지 물이 빠진 칸의 수 세기 3. H x M 크기로 모두 물이

PS

[PS] BOJ 4195 / 친구 네트워크

문제 링크: https://www.acmicpc.net/problem/4195 분리 집합을 활용해 풀 수 있는 문제입니다. 단, 두 문자열 간의 연결 관계가 주어지므로 맵을 활용해야 합니다. 풀이 분리 집합 기반의 Union-Find 알고리즘 분리 집합은 흔히 다익스트라 구현에서 사이클 여부를 판단하기 위해 사용하는 자료구조로, 여러 원소들을 단일 집합으로 합치고, 임의의 두 원소가

PS

[PS] BOJ 7562 / 나이트의 이동

문제 링크: https://www.acmicpc.net/problem/7562 격자 그래프 상에서의 그래프 탐색 문제입니다. 풀이 격자 그래프 상의 그래프 탐색 이제는 익숙한 문제 유형입니다. DFS 또는 BFS를 사용해, 2차원 배열 내의 각 좌표의 방문 여부를 기록하며 목적지를 찾아가면 됩니다. 다만, 상하좌우로의 단순한 이동이 아닌 나이트의 이동이므로 다음 좌표를 적절히 계산해주면

PS

[PS] BOJ 11657 / 타임머신

문제 링크: https://www.acmicpc.net/problem/11657 최단 경로를 찾는 문제입니다. 단, 간선의 가중치가 음수로도 주어집니다. 풀이 최단 경로? 1개의 정점에서 다른 모든 정점으로의 최단 거리를 계산해야 합니다. 다익스트라를 먼저 떠올렸지만, 다익스트라 알고리즘은 음의 간선을 포함하는 경우 최단 경로를 찾을 수 없습니다. 음의 간선을 포함하는 그래프에서 최단 경로를 구하기

PS

[PS] BOJ 31963 / 두 배

문제 링크: https://www.acmicpc.net/problem/31963 그리디한 접근으로 풀 수 있는 문제입니다. 단, 수의 크기가 굉장히 크기 때문에 시간 초과를 피하기 위해서는 요령이 필요합니다. 풀이 간단한 구현 수열을 오름차순으로 만들기 위해서, $A$의 $i$번 원소 A[$i$] (단, $1 \leq i \leq N$)를 2배로 만드는 연산을

PS

[PS] BOJ 2580 / 스도쿠

문제 링크: https://www.acmicpc.net/problem/2580 백트래킹으로 가능한 모든 경우를 찾아보는 문제입니다. 풀이 스도쿠 규칙 간단하게, 한 개의 행/열/칸(굵은 선으로 구분된 3x3 격자)에는 1~9까지의 수가 한 개 씩 등장해야 합니다. 따라서, 백트래킹에서 분기의 유망성을 판단할 때 현재 분기에서 채우려는 수 $i$가 같은

PS

[PS] BOJ 13909 / 창문 닫기

문제 링크: https://www.acmicpc.net/problem/10986 작은 수에 대해서 직접 풀어보면 규칙이 보입니다. 풀이 규칙 찾기 $N$개의 창문이 있을 때, $i$번째 사람은 $i$의 배수에 해당하는 창문의 상태를 뒤집습니다 (창문이 열려 있다면 닫고, 닫혀 있다면 엽니다.) 모든 창문은 처음에 닫혀 있습니다. 단순히 위 조건만 봐서는 감이

Life

[월말정산] 25년 8~9월의 이야기

Thumbnail: Photo by Pauline Bernard (Unsplash) 8월~9월 회고입니다. 무엇을 했나요? 0) 훈련이 있었습니다. 8월 한 달 간은 훈련으로 인해 바쁜 하루를 보냈습니다. 그래도 간단한 문제라도 풀면서 스트릭은 꾸준히 유지했습니다 😄 1) 1일 1백준을 실천하고 있습니다. 이제는 매 월말 정산마다 반복해서 적고 있는 내용입니다. 어느덧 스트릭이 122일이 되었네요! (9월 30일 기준

PS

[PS] BOJ 10986 / 나머지 합

문제 링크: https://www.acmicpc.net/problem/10986 누적 합을 활용하는데, 최적화를 위한 테크닉이 필요합니다. 풀이 문제 변환하기 먼저, 구간 $[1, i]$ $(1 \leq i \leq N)$에 대해, 구간 합을 $P_i$라고 정의합니다. $P_i = \sum_{i=1}^N A[i]$ 또, 구간 $[1, i]$에 대해 구간

PS

[PS] BOJ 14889 / 스타트와 링크

문제 링크: https://www.acmicpc.net/problem/14889 백트래킹을 활용하는 문제입니다. 풀이 고찰 $N$은 언제나 짝수로 주어지고, $N / 2$명씩 두 팀으로 나눠 두 팀의 능력치 차가 최소가 되는 경우를 찾아야 합니다. $4 \leq N \leq 20$이므로, 백트래킹으로 충분히 모든 경우를 탐색해볼 수 있습니다. 구현 백트래킹으로 가능한 모든

PS

[PS] BOJ 3015 / 오아시스 재결합

문제 링크: https://www.acmicpc.net/problem/3015 스택을 활용해 풀 수 있는 문제입니다. 풀이 고찰 두 사람 A와 B가 서로 볼 수 있으려면, 두 사람 사이에 A 또는 B보다 키가 큰 사람이 없어야 한다. 다시 말해, 두 사람 A와 B 사이에 있는 사람들의 키가 min(A의 키, B의 키)