전체 글

[백준] 27939. 가지 교배 - 파이썬

[백준 2023 가지컵 A번] [Bronze I] https://www.acmicpc.net/contest/problem/27939 풀이 '''P를 1, W를 0이라 한다면, P-우선 교배는 or 연산, W-우선 교배는 and 연산''' '''결국 조수들이 교배한 결과에서 W-가지가 하나라도 존재하면, 키위 교수가 교배할 때는 무조건 W-가지가 탄생.''' '''[교배해서 나온 품종을 포함하여 자신이 교배한 적 없는 품종이 하나만 남을 때까지 현재 가지고 있는 교배하지 않은 품종들을 모두 교배한다.]''' '''이 말인 즉슨, 교배의 결과물은 무조건 한 종..

[백준] 2056. 작업 - 파이썬

[Gold IV] https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net [백준] 1005. ACM Craft - 파이썬 과 매우 유사했던 문제. 풀이 [백준] 1005. ACM Craft - 파이썬 과 매우 유사해서 비슷하게 어려움 없이 풀었던 문제. DP와 위상 정렬(Topological Sort) 을 이용해서 풀이했다. from collections import deque N = int(input()) times = [] graph_in..

[백준] 2239. 스도쿠 - 파이썬

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 풀이 1, 풀이 2 모두 PyPy3 기준 AC 가능(통과 가능) 풀이 1 Backtracking을 이용해 풀 수 있는 문제. 스도쿠를 이차원 배열에 저장하고, 0이 있는 좌표들을 리스트에 저장. 백트래킹을 이용해 모든 0이 있는 칸에 가능한 숫자를 채워준다. recursion의 depth는 9x9 스도쿠이기 때문에 최대 81. recursion error를 걱정할 만한 깊이가 아니니 안심하고..

[백준] 1806. 부분합 - 파이썬

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 1 문제 이름과 같이, Prefix Sum (부분합)을 이용하여 풀이하면 되는 문제. 설명은 다른 곳에 더 잘 설명되어 있을 테니 생략. line 13 ~ 16에서 Time Complexity가 O(N^2)이라 TLE. 1부터 N까지의 공차가 1인 등차수열의 합은 n(n+1)/2 이므로.. O(N^2) import sys input = sys.stdin.readline N, S..

[백준] 1202. 보석 도둑 - 파이썬

[Gold II] https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 1 담을 수 있는 보석의 value를 최대로 해야 하므로, 일단은 우선순위 큐 (최대 힙)을 이용할 것이라 생각했음. 우선 생각나는 대로 먼저 구현해 보았고, line 18 ~ line 33 쪽에서 가방에 들어갈 수 있는 지 Brute-Force로 반복해가며 검사했기 때문에, 아마 TLE(시간초과)가 나올 것이라고..

[백준] 2166. 다각형의 면적 - 파이썬

https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 풀이 vector의 외적(Cross Product)을 통한 삼각형의 넓이를 구하는 방법을 이용해 풀었다. 첫 번째 입력되는 점을 기준으로 잡고, [dot1, dot2, dot3 triangle] => (dot2-dot1) vector, (dot3-dot1) vector's cross product [dot1, dot3, dot4 triangle] => (dot3-dot1) vector, (dot4-dot1) vector's..

[백준] 1005. ACM Craft - 파이썬

[Gold III] https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net [위상 정렬(Topological Sort)] 참고. https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html 풀이 1 위상 정렬(Topological Sort)을 이용하여 풀이. 오답이 나왔는데, 잘 생각해보니 각 턴마다 건설 시간이 가장 긴 것을 더하는 것이 총 건설 시간의 합이 최소가 되도록 하지..

[백준] 1197. 최소 스패닝 트리 - 파이썬

https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net [참고] 이 블로그.. 알고리즘 설명 맛집이다! 깔끔하고 최고. MST(Minimum Spanning Tree) MST(Minimum Spanning Tree) - Kruskal 알고리즘 Union-Find 알고리즘 풀이 MST(Minimum Spanning Tree, 최소 스패닝 트리, 최소 신장 트리)의 기본 문제. MST를 구현하는 방법에는 Kr..