PS

Problem Solving (알고리즘, 자료구조 문제풀이)

PS Featured

[PS] BOJ 1300 / K번째 수

문제 링크: https://www.acmicpc.net/problem/1300 풀이 N x N 크기의 2차원 배열의 $i$번째 행, $j$ 번째 열의 원소는 $i \times j$입니다. 이 2차원 배열을 1차원 배열로 펼치고 정렬한 뒤, 오름차순으로 $K$번째 수를 찾는 문제입니다. 정렬된 배열에서의 $K$번째 수라는 것은, 이 수와 같거나 작은

PS Featured

[PS] BOJ 24508 / 나도리팡

문제 링크: https://www.acmicpc.net/problem/24508 풀이 한 바구니에서 다른 바구니로 나도리 1마리를 올기는 행동을 최대 $T$회 반복했을 때 모든 나도리를 터뜨릴 수 있는지 파악해야 합니다. 나도리는 한 바구니에 $K$마리가 모이면 터지며 사라집니다. 한 바구니에 나도리를 $K$마리 채우려 할 때, 수가 적은 바구니에서 많은 바구니

PS Featured

[PS] BOJ 2141 / 우체국

문제 링크: https://www.acmicpc.net/problem/2141 풀이 예제 입력을 보며 풀이를 찾아봅시다. # 예제 데이터 3 1 3 2 5 3 3 먼저, 각 마을의 인구 수가 동일하다고 가정해 단순화한 문제를 풀어 봅시다. 이 경우, [1, 2, 3]에서 중간 값을 찾으면 되는 문제가 되고 답은 2임을 알 수

PS Featured

[PS] BOJ 34955 / 낚시 (Hard)

문제 링크: https://www.acmicpc.net/problem/34955 풀이 같은 내용에 출력 양식이 다른 문제 (낚시 (Easy))도 존재합니다. 풀이 또한 동일하니, 이 글에서는 Hard 버전의 풀이를 작성합니다. 낚시 조건 살펴보기 처음에 $N$개의 미끼와 $M$마리의 물고기가 있습니다. 문제에서, 우리는 미끼를 사용해 낚시를 하거나 기존에 잡은 물고기를 미끼로 바꾸는

PS Featured

[PS] BOJ 1167 / 트리의 지름

문제 링크: https://www.acmicpc.net/problem/1167 풀이 동일한 내용의 다른 문제가 있습니다. [PS] BOJ 1967 / 트리의 지름그래프 탐색 문제인 BOJ 1967을 풀어봤습니다.Tech.itMinjun Kim 트리의 지름? 트리의 지름이란, 트리의 임의의 두 정점 간의 거리 중 가장 긴 것을 말합니다. 문제에서는 100,000개 이하의 정점이 주어지고, 각 간선의

PS Featured

[PS] BOJ 2696 / 중앙값 구하기

문제 링크: https://www.acmicpc.net/problem/2696 풀이 중앙값 찾기 어떤 수열에서 중앙값을 찾는 방법은 수 전체를 정렬하는 것입니다. 하지만, 수열에 원소를 계속 추가하면서 중앙값을 구해야 합니다. 매번 수를 추가할 때 마다 다시 정렬하는 방법은 분명 시간 초과를 받을 것이니, 더 빠른 방법을 찾아야 합니다. 매번 수를 추가할 때

PS Featured

[PS] BOJ 2075 / N번째 큰 수

문제 링크: https://www.acmicpc.net/problem/2075 풀이 정렬로 풀기엔 적은 메모리 전체 $N^{2}$개의 수 중에서 $N$번째로 큰 수를 찾아야 합니다. 그런데, $1 \leq N \leq 1,500$이므로 우리가 비교해야 하는 수의 최대치는 2,250,000 개임을 알 수 있습니다. 단순히 수를 다 입력 받아

PS Featured

[PS] BOJ 2023 / 신기한 소수

문제 링크: https://www.acmicpc.net/problem/2023 풀이 신기한 소수? 길이가 $N$인 수 중 신기한 소수란, 왼쪽부터 1자리, 2자리, $\cdots$, $N$자리의 숫자가 모두 소수인 수를 말합니다. 우리는 $N$자리의 모든 신기한 소수를 사전 순으로 찾아 출력해야 합니다. 먼저, $N$자리의 신기한 소수를 만드는 방법부터 생각해봅시다. $N$자리의

PS Featured

[PS] BOJ 2812 / 크게 만들기

문제 링크: https://www.acmicpc.net/problem/2812 풀이 초안 처음에는 0~9의 각 숫자별로 어느 위치(인덱스)에 있었는지 기록한 뒤, 0부터 차례대로 제거해 나가는 방식으로 구현했습니다. 그러나, 이 방식은 $K$개의 숫자를 제거한 뒤의 숫자를 다시 구성하는 과정에 어려움이 있어 다른 방식을 생각해보게 되었습니다. 큰 수가 앞에 오게

PS Featured

[PS] BOJ 33915 / 불꽃놀이의 아름다움 2

문제 링크: https://www.acmicpc.net/problem/33915 풀이 그래프 색칠하기 인접한 두 정점끼리 서로 다른 색으로 칠하는 규칙을 따라 전체 그래프를 칠하는 문제입니다. 이는 이분 그래프의 개념을 활용해 접근할 수 있습니다. 다만, 이분 그래프처럼 그래프의 정점이 온전히 2개의 그룹으로만 분리되지는 않습니다. 따라서 그래프 탐색 과정에서 적절히 색의 개수를 늘려가며

PS Featured

[PS] BOJ 5052 / 전화번호 목록

문제 링크: https://www.acmicpc.net/problem/5052 풀이 트라이 활용하기 트라이에 관한 자세한 설명은 이전 글을 참고해주세요. 이번 문제는 전화번호를 하나의 단어로 생각해 트라이에 저장하는 방법으로 해결할 수 있습니다. 전화번호의 숫자를 한 자리 씩 트라이의 노드로 저장하고, 마지막 자리에 해당하는 노드에는 전체 전화번호를 값으로 저장합니다. 한 전화번호부의 모든 전화번호를

PS Featured

[PS] BOJ 2206 / 벽 부수고 이동하기

문제 링크: https://www.acmicpc.net/problem/2206 풀이 우선순위 큐 기반의 BFS 최단 경로의 길이만 구하면 되므로, 거리를 우선순위로 하는 큐를 활용해 BFS(너비 우선 탐색)를 진행했습니다. 기본적인 틀은 벽을 부수지 못하는 경우의 BFS와 동일합니다. from heapq import heappop, heappush maze = [list(map(int, list(input().rstrip()))) for

PS Featured

[PS] BOJ 24524 / 아름다운 문자열

문제 링크: https://www.acmicpc.net/problem/24524 풀이 단계 별로 생각하기 문자열 $S$에 포함된 알파벳들을 기존 순서를 유지한 채 골라서 문자열 $T$를 구성해야 합니다. 이때, $S$의 각 문자는 최대 한 번만 사용할 수 있습니다. $T$를 구성하기 위해 임의의 문자 $x$가 필요할 때, $S$에서

PS Featured

[PS] BOJ 15686 / 치킨 배달

문제 링크: https://www.acmicpc.net/problem/15686 치킨이 먹고 싶습니다. 풀이 단계 별로 생각하기 $N \times N$ 크기의 도시에 현재 $L$개의 치킨집이 있습니다. 이 중 $M$개만 남기고 나머지를 모두 없앨 때, 도시의 치킨 거리의 최솟값을 구하는 문제입니다. 풀이를 단계 별로 나눠서 생각해봅시다. 1. 치킨집을 $M$개만 남기기

PS Featured

[PS] BOJ 14725 / 개미굴

문제 링크: https://www.acmicpc.net/problem/14725 트라이(Trie)의 개념을 이해하기에 좋은 문제입니다. 풀이 Trie? Trie란, 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다. 문자열 자동 완성, 사전 검색 등의 기능을 구현하는데 자주 사용됩니다. Radix Tree, Prefix Tree, Retrieval Tree라고도 부릅니다. * 문자열 탐색이 빠릅니다. 전체 문자열을 하나하나 비교하면서

PS Featured

[PS] BOJ 23083 / 꿀벌 승연이

문제 링크: https://www.acmicpc.net/problem/23083 벌집을 2차원 배열로 표현해봅시다. 풀이 벌집을 2차원 배열료 표현하기 벌집 모양을 컴퓨터 상에서 동일하게 표현할 수는 없으니, 2차원 배열로 바꿔서 표현해야 합니다. 벌집에서는 항상 오른쪽 위 / 오른쪽 아래 / 아래쪽의 3방향으로 이동하지만, 2차원 배열로 표현할 경우 조금 달라집니다. 기존 좌표를 $(r, c)$ ($r$

PS

[PS] BOJ 29719 / 브실이의 불침번 근무

문제 링크: https://www.acmicpc.net/problem/29719 큰 수의 제곱 연산을 빠르게 하려면 어떻게 해야 할까요? 풀이 문제 이해하기 $M$명의 군인들이 $N$일동안 불침번 근무를 서야 합니다. 하루에는 1명의 군인만 불침번을 서며, 한 명이 여러 번 근무를 설 수 있습니다. 이는 $M$개의 원소 중에 중복을 허용한 채로

PS Featured

[PS] BOJ 2110 / 공유기 설치

문제 링크: https://www.acmicpc.net/problem/2110 결정 문제를 잘 정의하면 어렵지 않게 풀 수 있습니다. 풀이 매개변수 탐색 문제의 내용을 요약해보면, $N$개의 집 중에서 최소 $C$개의 공유기를 놓을 수 있도록 하는 인접한 두 공유기 사이의 거리의 최대값을 구하면 됩니다. 구해야 하는 것은 '인접한 두 공유기

PS Featured

[PS] BOJ 1948 / 임계 경로

문제 링크: https://www.acmicpc.net/problem/1948 주어진 방향 그래프에서의 최장 경로를 찾고, 그 경로를 구성하는 간선의 개수를 세는 문제입니다. 풀이 최장 경로 찾기 보통의 그래프 탐색 문제는 최단 경로를 찾지만, 이번 문제에서는 가중치의 합이 가장 큰 경로를 찾아야 합니다. 이를 최장 경로라고 부르겠습니다. 먼저 입력 데이터로 그래프를 구성해야

PS Featured

[PS] BOJ 27297 / 맨해튼에서의 모임

문제 링크: https://www.acmicpc.net/problem/27297 정렬을 활용해 중앙값을 찾는 문제입니다. 풀이 맨해튼 거리 N차원의 두 점 $A = (A_1, A_2, \cdots, A_N)$와 $B = (B_1, B_2, \cdots, B_N)$ 사이의 맨해튼 거리 $d_AB$는 다음과 같습니다. $d_{AB} = \sum_{i = 1}^{N}

PS Featured

[PS] BOJ 13911 / 집 구하기

문제 링크: https://www.acmicpc.net/problem/13911 다익스트라 알고리즘을 활용해 최단 거리를 구하는 문제입니다. 다만, 약간의 테크닉을 요구합니다. 풀이 다익스트라 알고리즘 다익스트라는 주어진 그래프에서 두 정점 사이의 최단 거리를 구하는 알고리즘입니다. 임의의 한 정점에서 시작해, 가장 거리가 가까운 정점을 찾아가며 전체 정점의 최단 거리를 갱신하는 방식으로 동작합니다. 자세한 설명은

PS Featured

[PS] BOJ 1953 / 팀배분

문제 링크: https://www.acmicpc.net/problem/1953 이분 그래프를 활용하는 문제입니다. 풀이 이분 그래프란? 서로 인접한 두 정점을 다른 색상으로 칠할 때, 전체 그래프의 모든 정점이 두 가지 색으로 표현되는 그래프를 말합니다. 그래프 탐색을 통해 그래프의 각 정점을 2가지 색상으로 칠해 주어진 그래프가 이분 그래프인지 아닌지를 알 수 있습니다.

PS

[PS] BOJ 1707 / 이분 그래프

문제 링크: https://www.acmicpc.net/problem/1707 주어진 그래프가 이분 그래프인지 아닌지를 판단하는 문제입니다. 이분 그래프의 개념에 대해 이해하기에 좋은 문제입니다. 풀이 이분 그래프란? 서로 인접한 두 정점을 다른 색상으로 칠할 때, 전체 그래프의 모든 정점이 두 가지 색으로 표현되는 그래프를 말합니다. 주어진 그래프가 이분 그래프인지 판단하기 이 그래프가

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를 |>로