Programming/Algorithm
-
[백준] 2293번 동전 1 (by Python)Programming/Algorithm 2021. 3. 31. 20:15
문제 https://www.acmicpc.net/problem/2293 2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 DP가 늘 그렇듯, 아이디어가 중요한 문제이다. n, k = map(int, input().split()) arr = sorted([int(input()) for _ in range(n)]) ans = [0 for i in range(k + 1)] ans[0] = 1 for i in range(1, k + 1): for j in arr: if i >= j: ans[i] += ans[i -..
-
[백준] 14719번 빗물 (by Python)Programming/Algorithm 2021. 3. 26. 01:32
문제 https://www.acmicpc.net/problem/14719 14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 풀이 h, w = map(int, input().split()) block = [[False] * w for _ in range(h)] height = list(map(int, input().split())) for i, ht in enumerate(height): for j in range(ht): block[j][i] = True i, count = 0, 0 ans = ..
-
[백준] 1786번 찾기 (by Python)Programming/Algorithm 2021. 3. 24. 17:57
문제 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 풀이 parent string에 pattern string이 포함되어 있는지 찾을 수 있는 KMP 알고리즘에 대한 문제이다. KMP 알고리즘은 다음과 같다. 먼저, pattern과 같은 길이의 table array를 만들어준다. 이 때 pattern에서 prefix와 같은 내용의 postfix가 있다고 가정할 때, table의 원소는 같은 index를 가진 character가 postf..
-
[백준] 1062번 가르침 (by Python)Programming/Algorithm 2021. 3. 24. 17:13
문제 https://www.acmicpc.net/problem/1062 1062번: 가르침 첫째 줄에 단어의 개수 N과 K가 주어진다. N은 50보다 작거나 같은 자연수이고, K는 26보다 작거나 같은 자연수 또는 0이다. 둘째 줄부터 N개의 줄에 남극 언어의 단어가 주어진다. 단어는 영어 소문 www.acmicpc.net 풀이 브루트 포스 방식으로 푸는 비트마스킹 문제이다. 처음에는 비트마스킹 방식이 익숙하지 않아서 set으로 시도해봤으나 시간 초과의 벽에 막혀 비트마스킹 방법으로 풀게 되었다. import sys from itertools import combinations input = sys.stdin.readline def convert(x): return ord(x) - ord('a') def..
-
[백준] 18404번 현명한 나이트 (by Python)Programming/Algorithm 2021. 3. 14. 15:33
문제 https://www.acmicpc.net/problem/18404 18404번: 현명한 나이트 첫째 줄에 N과 M이 공백을 기준으로 구분되어 자연수로 주어진다. (1 ≤ N ≤ 500, 1 ≤ M ≤ 1,000) 둘째 줄에 나이트의 위치 (X, Y)를 의미하는 X와 Y가 공백을 기준으로 구분되어 자연수로 주어진다. ( www.acmicpc.net 풀이 움직이는 방식이 일반적인 상하좌우가 아니라 체스의 나이트가 움직이는 방식이라는 점에서 차별화되는 BFS 문제이다. 이에 맞추어 step 리스트를 다르게 바꾸어주었다. 또한, 목적지가 하나가 아님에 따라 하나를 찾을 때마다 체크하고 다 찾은 경우에는 while loop을 탈출하도록 코드를 짜주었다. from collections import deque..
-
[백준] 18310번 안테나 (by Python)Programming/Algorithm 2021. 3. 14. 15:28
문제 https://www.acmicpc.net/problem/18310 18310번: 안테나 첫째 줄에 집의 수 N이 자연수로 주어진다. (1≤N≤200,000) 둘째 줄에 N채의 집에 위치가 공백을 기준으로 구분되어 1이상 100,000이하의 자연수로 주어진다. www.acmicpc.net 풀이 무척 쉬워보이고, 코드 또한 4줄로 매우 간단하게 풀 수 있는 문제이지만 개인적으로 해답을 떠올렸음에도 확신하지 못해 많이 애먹은 문제이다. 결론적으로 답은 주어진 숫자들을 오름차순으로 정렬한 후의 가운뎃값이다. 어떻게 이 결론이 성립하는지 예시를 통해 알아보도록 하자. 오름차순으로 정렬된 숫자 5개 (a, b, c, d, e)가 있고 a, b / b, c / c, d / d, e 의 거리를 각각 x_1, x..
-
[백준] 3665번 최종 순위 (by Python)Programming/Algorithm 2021. 3. 14. 02:25
문제 www.acmicpc.net/problem/3665 3665번: 최종 순위 올해 ACM-ICPC 대전 인터넷 예선에는 총 n개의 팀이 참가했다. 팀은 1번부터 n번까지 번호가 매겨져 있다. 놀랍게도 올해 참가하는 팀은 작년에 참가했던 팀과 동일하다. 올해는 인터넷 예선 본부에 www.acmicpc.net 풀이 위상 정렬(Topology Sort)를 사용하는 문제이다. 주어진 올해 순위를 순위가 낮은 팀이 높은 팀을 가리키는 유향 그래프로 나타내었다. 원래는 위상 정렬에 쓰이는 그래프는 인접 리스트로 구현하였는데, 이번에는 방향성이 유동적이므로 이를 잘 다루기 위해 인접 행렬로 구현했다. 바뀐 순위들에 대해서 edge의 방향을 바꾸어주고 이에 대해 위상 정렬을 시행해주면 된다. 다만 주어지는 정보에 ..