문제 (링크) https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline def get_dist(loc1, loc2): x1, y1, x2, y2 = loc1[0], loc1[1], loc2[0], loc2[1] return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** 0.5 def find(parent, x): if x != p..
알고리즘
문제 (링크) https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 나의 코드 import sys input = sys.stdin.readline def find(parent, x): if x != parent[x]: parent[x] = find(parent, parent[x]) return parent[x] # 사실을 아는 사람과 Union시, 해당 사람이 부모노드가 되도록 def union(parent, a, b, know_truth): a = find(..
카운팅 정렬, 혹은 계수 정렬은 O(n + k)의 시간복잡도를 가진 정렬이다. 여기서 다소 낯선 k는 정렬을 수행할 배열의 가장 큰 값을 의미한다. k가 단순히 상수로 취급되어 생략되지 않고 남아있는 것은 그만큼 k에 따라 수행시간에 영향을 미치기 때문이다. 만약 k가 n보다 작다면 정렬의 수행시간은 O(n)이 되겠지만, 무한대로 크다면 정렬의 수행시간도 무한대가 된다. 작동 방식 1. 배열을 이용한 방식 계수 정렬은 counting이라는 말 답게 배열에 존재하는 수의 개수를 세어주고, 이 정보를 바탕으로 정렬을 수행한다. 그리고 여기서 수와 수의 개수는 배열 혹은 딕셔너리의 인덱스와 해당 값을 통해서 기록할 수 있다. 먼저 배열을 통한 계수 정렬은 누적합의 개념을 적용하여 구현할 수 있다. 배열을 이용..
문제 (링크) https://www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n = int(input()) arr = list(map(int, input().split())) arr.sort() target = 1 for num in arr: if target < num: break target += num print(target) 코드 설명 및 풀이법 처음엔 1원부터 모든 무게의 합까지 확..
문제 (링크) https://www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline n = int(input()) tops = list(map(int, input().split())) stack = [] # 인덱스와 탑의 높이 stack.append([1, tops[0]]) # 맨 왼쪽 탑은 수신되지 않음 ans = [0] for i in range(1, n): while stack: ..
문제 (링크) https://www.acmicpc.net/problem/19237 19237번: 어른 상어 첫 줄에는 N, M, k가 주어진다. (2 ≤ N ≤ 20, 2 ≤ M ≤ N2, 1 ≤ k ≤ 1,000) 그 다음 줄부터 N개의 줄에 걸쳐 격자의 모습이 주어진다. 0은 빈칸이고, 0이 아닌 수 x는 x번 상어가 들어있는 칸을 의미 www.acmicpc.net 나의 풀이 import sys input = sys.stdin.readline # 1번 상어는 모두 쫓아낼 수 있음 # N * N 그래프에 M 마리의 상어, k = 냄새 지속시간 n, m, k = map(int, input().split()) graph = [] sharks = [[] for _ in range(m + 1)] # 위, 아래..
문제 (링크) https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 나의 풀이 import sys import heapq input = sys.stdin.readline n, m = map(int, input().split()) in_degree = [0] * (n + 1) graph = [[] for _ in range(n + 1)] for _ in range(m): a, b = map(int, input().spli..
시간 제한 메모리 1 초 256 MB 문제 (링크) https://www.acmicpc.net/problem/11000 11000번: 강의실 배정 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 109) www.acmicpc.net 나의 풀이 (Python) import sys import heapq input = sys.stdin.readline n = int(input()) arr = [] for _ in range(n): arr.append(list(map(int, input().split()))) arr.sort() queue = [] heapq.heappush(queue, arr[0][1]) for i in ra..
