나의 개발일지

문제 : https://www.acmicpc.net/problem/1043 🔑 union, find [유니온 파인드] 진실을 아는 사람들을 모두 같은 번호로 묶어준다. union 각 파티마다 오는 사람들을 모두 같은 번호로 묶어준다. union 진실을 아는 사람들이 오는 파티면 1번 과정에서의 그룹에 포함된다. 진실을 아는 사람들의 그룹과, 각 파티의 그룹이 겹치지 않으면 거짓말을 한다. find 거짓말할 수 있는 파티의 개수를 세면 끝 ✨ 예외로 진실을 아는 사람이 없으면 파티의 횟수를 출력하고 종료했다. import sys input = sys.stdin.readline n, m = map(int, input().split()) parent = [i for i in range(n+1)] true = ..

문제 : https://www.acmicpc.net/problem/1541🔑 더하기 먼저더하기 먼저 모두 하고 나서 빼기를 진행'-'를 기준으로 split을 한다.55-50+40 → ['55', '50+40']요소가 숫자로만 구성된 문자열이면 정수로 형변환요소에 '+'가 있으면 '+'를 기준으로 split을 하고 더함 → [55, 90] 만들어진 리스트 요소들을 전부 빼면 정답 ✨ n = input()s = n.split('-')for i in range(len(s)): if '+' in s[i]: tmp = map(int, s[i].split('+')) s[i] = sum(tmp) else: s[i] = int(s[i]) answer = s[0]f..

문제 : https://www.acmicpc.net/problem/1202 🔑 힙, 우선순위 큐 1. 입력받은 보석들을 무게 기준 오름차순 정렬 2. 가방도 오름차순 정렬 3. 가장 작은 가방부터 시작해서 이 가방에 담을 수 있는 보석이면 힙에 보석 가격을 담는다. (음수로 담는다. 최대힙) 4. 담긴 보석이 있으면 가장 비싼 보석을 선택한다. 3, 4번 과정을 가방 개수만큼 반복한다. 크기가 작은 가방부터 담기 때문에 보석을 모두 담고 뽑아내는 게 가능하게 된다. 크기가 2인 가방에 담을 수 있는 보석이면 크기가 3인 가방에도 담을 수 있다. 가방 크기 = [2, 10] 보석 = [(1, 65), (2, 99), (5, 23)] 가방 크기 2일 때 힙 = [-99, -65] -99를 뽑아서 정답으로 올..

문제 : https://www.acmicpc.net/problem/1874 🔑 스택 나열해야 하는 수 보다 현재 숫자가 같거나 작으면 스택에 넣어놓는다. + 스택 제일 위의 수가 나열해야 하는 수와 같으면 스택에서 꺼낸다. - +, - 를 바로 출력하지 않고 저장해 놓고 수열을 만들 수 있으면 출력을 한다. 끝 ✨ import sys input = sys.stdin.readline n = int(input()) numbers = [int(input()) for _ in range(n)] stack = [] idx = 1 answer = [] for i in numbers: while idx

문제 : https://www.acmicpc.net/problem/1414 🔑 최소 비용 신장 트리, 프림 알고리즘 입력되는 문자열을 문제 형식에 맞게 숫자로 변환해서 그래프를 생성한다. ord() 함수 사용 변환한 랜선 길이의 총 합도 구해놓는다. 그리고 프림 알고리즘을 사용해 최소 비용을 구할 때마다 전체 랜선의 길이에서 빼준다. 남은 랜선의 길이가 정답인데 방문을 못한 노드가 있으면 -1을 출력한다. 더 쉬운 프림 알고리즘 문제 : https://study-yoon.tistory.com/235 import sys from heapq import heappop, heappush from collections import defaultdict input = sys.stdin.readline n = in..

문제 : https://www.acmicpc.net/problem/1922 🔑 최소 비용 신장 트리, 프림 알고리즘 양방향으로 그래프를 생성 힙 (비용, 출발 노드)로 초기화, 출발 노드는 어떤 노드라도 상관없음 그래프를 탐색하면서 방문 안 한 노드면 방문 처리하고 정답에 비용을 더한다. 그다음 현재 노드와 연결된 노드들을 힙에 넣는다. 이렇게 해서 최소 비용이 구해지는 이유는 힙으로 구현했기 때문에 현재 노드와 연결된 노드 중 최소 비용인 노드가 먼저 뽑히게 되고 이 노드는 방문처리가 되기 때문에 최소 비용이 아닌 길로는 가지 않는다. import sys from heapq import heappop, heappush from collections import defaultdict n = int(inp..

문제 : https://www.acmicpc.net/problem/1747 🔑 에라토스테네스의 체 에라토스테네스의 체를 사용해 소수를 미리 구해둔다. 최대 입력값인 1000000이 들어오면 1003001이 정답이므로 넉넉한 크기까지 구함 구한 소수들을 n번부터 시작해서 순회하면서 팰린드롬인 소수를 찾는다. 문자열[::-1]을 하면 문자열을 뒤집을 수 있음 n = int(input()) prime = [True] * (1_030_001) prime[1] = False for i in range(2, int(1_030_000 ** 0.5) + 1): if prime[i]: for j in range(i*2, 1_030_000 + 1, i): prime[j] = False for i in range(n, le..

문제 : https://www.acmicpc.net/problem/1715 🔑 최소 힙 힙에서 가장 작은 수 두 개를 뽑는다. heappop 두 번 뽑아낸 두 수를 더해서 힙에 다시 넣고 합한 값만큼 정답을 올려준다. from heapq import heappop, heappush import sys input = sys.stdin.readline n = int(input()) heap = [] for _ in range(n): heappush(heap, int(input())) answer = 0 while len(heap) >= 2: x = heappop(heap) + heappop(heap) heappush(heap, x) answer += x print(answer)