PS

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

PS

[PS] BOJ 29756 / DDR 체력 관리

문제 링크: https://www.acmicpc.net/problem/29756 Thumbnail: Photo by George Dagerotip (Unsplash) 조금만 생각해보면, 배낭 문제의 점화식을 응용해 풀이할 수 있습니다. 풀이 0-1 배낭 문제 풀이에 앞서, 0-1 배낭 문제의 아이디어를 다시 복습해봅시다. $N$개의 물건에 대해, $i$번째 물건의 무게를 $W_i$, 가치를 $V_i$라고 하고

PS

[PS] BOJ 20303 / 할로윈의 양아치

문제 링크: https://www.acmicpc.net/problem/20303 Thumbnail: Photo by Frames For Your Heart (Unsplash) 분리 집합 + 배낭 문제의 환상의 콜라보! 풀이 아이디어 아이들 사이의 친구 관계는 그래프로 나타낼 수 있습니다. 이 때, 간선에는 가중치가 없으며 무방향 그래프로 생각할 수 있습니다. 또한, 스브러스는 매우 공평한 사람이기 때문에 한 아이의

PS

[PS] BOJ 1202 / 보석 도둑

문제 링크: https://www.acmicpc.net/problem/1202 Thumbnail: Photo by Bùi Hoàng Long (Unsplash) 정렬과 우선순위 큐를 활용해 배낭을 채우는 문제입니다. 풀이 아이디어 이 문제는 가방과 보석 모두 정렬한 뒤 풀어야 합니다. 가방은 가방의 용량(담을 수 있는 최대 무게)에 따라 오름차순으로, 보석은 보석의 무게에 따라 내림차순으로 정렬합니다.

PS

[PS] BOJ 8913 / 문자열 뽑기

문제 링크: https://www.acmicpc.net/problem/8913 Thumbnail: Photo by Finn (Unsplash) 백트래킹으로 가능한 모든 경우를 찾는 문제입니다! 풀이 백트래킹 (DFS) 백트래킹으로 가능한 모든 경우를 탐색해, 한 가지 경우라도 전체 문자열을 빈 문자열로 바꿀 수 있는지 찾아내면 됩니다. 전체 문자열의 길이는 최대 25자에 시간 제한은 2초(언어마다 조금씩 다릅니다.

PS

[PS] BOJ 9328 / 열쇠

문제 링크: https://www.acmicpc.net/problem/9328 Thumbnail: Photo by Susan Q Yin (Unsplash) 격자 그래프 상에서 그래프 탐색을 하는 문제입니다! 풀이 BFS 기본적인 풀이는 BFS로, 벽과 길을 구분해 갈 수 있는 곳을 모두 탐색하면 됩니다. 다만, 격자 그래프 상의 타일(각 칸)이 벽과 길만 있는 것이 아니라

PS

[PS] BOJ 1644 / 소수의 연속합

문제 링크: https://www.acmicpc.net/problem/1644 Thumbnail: Photo by Ryunosuke Kikuno (Unsplash) 풀이 에라토스테네스의 체를 사용해 $N$까지의 소수를 미리 구하고, 소수들의 배열을 가지고 투 포인터 탐색을 활용해 연속 합을 구하면 됩니다. 에라토스테네스의 체 에라토스테네스의 체는 잘 알려진 소수 판별법으로, 1부터 $N$까지의 범위 안에서 소수를 일괄적으로 구할

PS

[PS] BOJ 4056 / 스-스-스도쿠

문제 링크: https://www.acmicpc.net/problem/4056 Thumbnail: Photo by Luna Lee (Unsplash) 스도쿠를 풀어봅시다. 백트래킹으로요. 풀이 스도쿠의 규칙은 다음과 같습니다. * 같은 행에는 1~9까지의 수가 1개씩만 포함됩니다. * 같은 열에는 1~9까지의 수가 1개씩만 포함됩니다. * 같은 칸(3x3)에는 1~9까지의 수가 1개씩만 포함됩니다. 이 규칙을 기반으로, 백트래킹을 진행하면서

PS

[PS] BOJ 9466 / 텀 프로젝트

문제 링크: https://www.acmicpc.net/problem/9466 Thumbnail: Photo by Vitaly Gariev (Unsplash) 풀이 학생들이 팀을 이룰 수 있는 조건은 다음과 같습니다. 학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한

PS

[PS] BOJ 2239 / 스도쿠

문제 링크: https://www.acmicpc.net/problem/2239 Thumbnail: Photo by Richard Bell (Unsplash) 스도쿠를 풀어봅시다. 백트래킹으로요. 풀이 스도쿠의 규칙은 다음과 같습니다. * 같은 행에는 1~9까지의 수가 1개씩만 포함됩니다. * 같은 열에는 1~9까지의 수가 1개씩만 포함됩니다. * 같은 칸(3x3)에는 1~9까지의 수가 1개씩만 포함됩니다. 입력으로 주어지는 스도쿠는 빈칸이 굉장히

PS

[PS] BOJ 2263 / 트리의 순회

문제 링크: https://www.acmicpc.net/problem/2263 Thumbnail: Photo by Antoine PERIER (Unsplash) 풀이 트리의 inorder 순회 결과와 postorder 순회 결과가 주어질 때, preorder 순회의 결과를 구하는 문제입니다. 트리의 순회? 트리를 순회하는 방식 4가지를 먼저 이해해야 합니다. * preorder (전위 순회) * 루트 노드 -> 왼쪽 자식 노드 ->

PS

[PS] BOJ 26123 / 외계 침략자 윤이

문제 링크: https://www.acmicpc.net/problem/26123 Thumbnail: Photo by Danie Franco (Unsplash) 풀이 윤이가 레이저를 발사하는 방식을 그대로 구현해주면 됩니다. 맵을 사용해, 각 높이별로 건물의 개수를 기록해두고 $D$일동안 반복하면 됩니다. 전체 코드 input = open(0).readline N, D = map(int, input().split()) heights = {} max_height = 0 for

PS

[PS] BOJ 1417 / 국회의원 선거

문제 링크: https://www.acmicpc.net/problem/1417 Thumbnail: Photo by Arnaud Jaegers (Unsplash) 풀이 먼저, 각 후보자를 투표 수를 기준으로 맵에 저장합니다. 이후, 투표 수를 기준으로 우선 순위 큐에 추가해주고, 다솜이보다 더 많은 표가 예상되는 후보들의 표를 1씩 줄여가며 계산합니다. 전체 코드 from heapq import heappush, heappop input = open(

PS

[PS] BOJ 10275 / 골드 러시

문제 링크: https://www.acmicpc.net/problem/10725 Thumbnail: Photo by Jingming Pan (Unsplash) 이진수로 생각해보면 금방 풀 수 있었는데, 직관적으로 풀이가 떠오르지 않았어서 정리해봅니다. 풀이 문제의 번역에 살짝 오역이 있어, 마법을 사용한 횟수를 출력한다고 생각하면 됩니다. 기본적으로는, $A$ 또는 $B$ 둘 중에 아무거나 기준으로 잡고 금을 쪼개가며 해당 수를

PS

[PS] BOJ 1238 / 파티

문제 링크: https://www.acmicpc.net/problem/1238 Thumbnail: Photo by Adi Goldstein (Unsplash) 파티를 즐기기 위해서는 최단 거리를 구해야 합니다! 풀이 다익스트라(Dijkstra)! 다익스트라 알고리즘을 활용하는 문제입니다. 한가지 유의할 점은, 유향 그래프이기 때문에 각 학생이 사는 마을에서 파티가 열리는 $X$번 마을로 가는 거리와, $X$번 마을에서 다시 집으로

PS

[PS] BOJ 11404 / 플로이드

문제 링크: https://www.acmicpc.net/problem/11404 Thumbnail: Photo by Gerson Repreza (Unsplash) 플로이드-워셜(Floyd-Warshall) 알고리즘을 활용하는 정석적인 문제입니다. 풀이 플로이드-워셜(Floyd-Warshall)! 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로 가는 최단 거리를 탐색하는 방법입니다. 다익스트라 알고리즘이 한 정점에서 다른 모든 정점으로의 최단 거리를 계산하는 점에서 차이가 있습니다. 모든 정점에서 모든

PS

[PS] BOJ 18769 / 그리드 네트워크

문제 링크: https://www.acmicpc.net/problem/18769 Thumbnail: Photo by Nastya Dulhiier (Unsplash) 격자 그래프에서 최소 신장 트리(MST)를 구하는 문제입니다. 풀이 기본적인 풀이 요령은 MST를 구하는 다른 문제들과 동일합니다. 다만, 정점이 번호로 주어지지 않고 격자 그래프의 형태로 주어지니, 간단한 전처리를 통해 일반적인 그래프의 형태로 저장해봅시다. 1) 간선

PS

[PS] BOJ 1799 / 비숍

문제 링크: https://www.acmicpc.net/problem/1799 Thumbnail: Photo by Omar Lopez-Rincon (Unsplash) N-Queen으로 변환해 풀 수 있는 백트래킹 문제입니다. 풀이 기본적인 풀이는 N-Queen과 동일합니다. 하지만, 비숍을 어떻게 N-Queen 문제의 형태로 변환할지는 충분한 고민이 필요합니다. 아이디어 기본적인 아이디어는 아래 2가지입니다. * 체스판을 45도 회전시켜 보면, 비숍 대신 룩을 배치하는 문제로

PS

[PS] BOJ 2253 / 점프

문제 링크: https://www.acmicpc.net/problem/2253 Thumbnail: Photo by Jackson Blackhurst (Unsplash) 처음 봤을 때는 DP로 풀 수 있는 계단 문제를 생각했는데, 오를 수 있는 속도를 변화시킬 수 있어 조금 더 풀이가 까다로웠습니다. 풀이 Bottom-Up 방식의 DP로 접근했습니다. DP 배열 구상 DP배열은 다음과 같이 정의했습니다. 💡 DP[돌 번호]

PS

[PS] BOJ 1806 / 부분합

문제 링크: https://www.acmicpc.net/problem/1806 Thumbnail: Photo by Thibault Penin (Unsplash) 전체 수열의 부분 수열 중, 전체 원소의 합이 $S$보다 크거나 같으면서 길이가 최소가 되는 수열을 찾아, 그 길이를 구하는 문제입니다. 풀이 0.5초라는 짧은 시간 제한 때문에, 모든 부분 수열을 탐색할 수 없습니다. 따라서, 투

PS

[PS] BOJ 10942 / 팰린드롬?

문제 링크: https://www.acmicpc.net/problem/10942 Thumbnail: Photo by Josh Nezon (Unsplash) 문자열이 회문인지 아닌지 판단하는 문제입니다. 그러나, 전체 문자열의 임의의 부분에 대해서 회문인지 아닌지를 여러 번 판단해줘야 합니다. 풀이 이 문제를 푸시는 분들은 회문이 무엇인지 모두 아실거라고 생각합니다! 간단히 이야기하면, 문자열을 반으로 잘랐을 때 대칭인 경우 회문입니다.

PS

[PS] BOJ 2887 / 행성 터널

문제 링크: https://www.acmicpc.net/problem/2887 Thumbnail: Photo by Louis Reed (Unsplash) 최소 신장 트리(MST)를 구하는 문제입니다. 하지만, 이번엔 간선도 직접 찾아야 합니다. 풀이 모든 행성을 터널로 연결하는데 필요한 최소 비용을 찾아야 합니다. 즉, 최소 신장 트리(MST)를 구하는 문제입니다. 하지만, 문제 입력에는 간선이 주어지는

PS

[PS] BOJ 2166 / 다각형의 면적

문제 링크: https://www.acmicpc.net/problem/2166 Thumbnail: Photo by Joel Filipe (Unsplash) CCW를 응용해 다각형의 면적을 계산하는 문제입니다. 풀이 다각형의 면적? 다각형을 이루는 각 점의 좌표가 순서대로 주어질 때, 그렇게 만들어진 다각형의 면적을 구하는 문제입니다. 이전에 CCW 문제에서, CCW 알고리즘을 통해 유도된 식은 사선 공식과 동일하며, 이를 활용해

PS

[PS] BOJ 11758 / CCW

문제 링크: https://www.acmicpc.net/problem/11758 Thumbnail: Photo by 愚木混株 Yumu (Unsplash) 세 점에 대한 방향 관계를 구하는, CCW 알고리즘 풀이의 정석적인 문제입니다. 풀이 CCW? CCW는 Counter Clockwise의 약자로, 임의의 세 점 A, B, C를 순서대로 볼 때, 세 점의 연결 방향이 시계 방향인지 반시계 방향인지 판단하는 알고리즘입니다.

PS

[PS] BOJ 1717 / 집합의 표현

문제 링크: https://www.acmicpc.net/problem/1717 Thumbnail: Photo by Orevaoghene Ahia (Unsplash) 분리 집합을 구현하는 방법인 Union-Find 알고리즘을 구현하는 문제입니다. 풀이 분리 집합(Disjoint Set)? 분리 집합의 수학적 정의는 다음과 같습니다: 전체 집합 \(U\)에 대해, 서로 겹치는 원소를 가지지 않는 둘 이상의 부분 집합 \(A, B\)를

PS

[PS] BOJ 1197 / 최소 스패닝 트리

문제 링크: https://www.acmicpc.net/problem/1197 Thumbnail: Photo by Marjan Blan (Unsplash) 정석적인 최소 신장 트리(MST; Minimum Spanning Tree)를 구하는 문제입니다. 풀이 크루스칼(Kruskal) 알고리즘 MST를 구하는 알고리즘은 대표적으로 크루스칼 알고리즘과 프림 알고리즘이 존재합니다. 보통 희소 그래프의 경우 크루스칼이, 밀집 그래프의 경우 프림 알고리즘이 더 유리합니다.