Algorithm

[백준] 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..

[백준] 11659. 구간 합 구하기 4 - 파이썬

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 풀이 1 Brute-Force로 풀어봤으나 시간초과 N, M = map(int, input().split()) nums = list(map(int, input().split())) totals = [] for _ in range(M): total = 0 i, j = map(int, input().split()) for k in range(i-1, j): total += nu..

[백준] 1697. 숨바꼭질 - 파이썬

https://www.acmicpc.net/problem/1697 1697번: 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 난이도에 맞지 않게 굉장히 애를 먹었던 문제. 시간초과 메모리초과 틀렸습니다의 늪에서 허우적거린...^ㅁ^ 풀고 보니 결국 하나를 잘못 생각했다. 풀이 1 [백준] 1463. 1로 만들기 와 비슷하게, DP로 풀 수 있을 것이라 생각했으나, 오답. 아무래도 +1, -1이 둘 다 존재하기 때문에, 수가 계속 커지기만 하는 것은 아니라서, 이런 방식으로 풀이하는 것은 불가능..