알고리즘

문제 (링크) 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(..

문제 (링크) 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..

문제 (링크) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 나의 코드 import sys from collections import deque 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 =..

문제 (링크) https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 나의 풀이 from collections import deque import sys def get_prime_nums(): prime = [True] * 10000 prime[0], prime[1] = False, False for i in range(2, 10000): if prime[i] == True: j = 2 while i * j < 10000: prime[i * j] = False..