나의 개발일지

문제 : 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)

문제 : https://www.acmicpc.net/problem/1927 🔑 최소 힙 from heapq import heappop, heappush import sys input = sys.stdin.readline n = int(input()) heap = [] for _ in range(n): x = int(input()) if not heap and x == 0: print(0) elif x > 0: heappush(heap, x) else: print(heappop(heap))

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/77885 🔑 2진수로 변환해서 자리 바꾸기 짝수라면 그 숫자에 +1을 해서 정답에 추가한다. 홀수라면 숫자를 2진수로 바꾸고 50자리까지 남는 자리에 0을 채워준다. (10^15를 2진수로 바꾸면 50자리까지 나와서) 변환된 2진수를 역순으로 순회하면서 처음 0을 만나면 1로 바꿔주고, 바로 오른쪽 값은 0으로 바꿔준다. 7 일 때 2진수로 바꾸면 000...0111 처음 0으로 만났을 때 값을 바꿔주면 000...1011 이렇게 자리를 바꾼 2진수를 다시 10진수로 변환해서 정답에 추가하면 끝 ✨ def solution(numbers): answer = [] for n in numbers:..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/42884 🔑 그리디, 정렬 나간 지점을 기준으로 오름차순 정렬 [[-20, -15], [-14, -5], [-18, -13], [-5, -3]] → [[-20, -15], [-18, -13], [-14, -5], [-5, -3]] 초기값(camera)을 -30000보다 작은 값으로 초기화한다. 현재 차량의 진입 지점이 카메라가 설치된 지점(camera) 보다 크면 나간 지점에 카메라 설치 밑에 그림으로 봤을 때 카메라를 설치한 지점과 겹치지 않는 경우에 해당 그림을 보면 이해하기 쉽다. 빨간 막대가 카메라가 설치된 자리 파란 막대는 차량이 이동한 거리 def solution(routes): ..

문제 : https://school.programmers.co.kr/learn/courses/30/lessons/12987 🔑 정렬 A의 순서가 어떻든 간에 B의 순서를 내 마음대로 배치할 수 있으니까 둘 다 오름차순으로 정렬을 한다. (A의 순서가 주어진 대로 사용할 필요 없음) A보다 B[i]가 더 크면 정답 올리고 A의 다음 순서를 불러온다. 반복 한 번만 하면 끝 ✨ def solution(A, B): answer = 0 A.sort() B.sort() p = 0 for i in range(len(A)): if A[p] < B[i]: answer += 1 p += 1 return answer

문제 : https://www.acmicpc.net/problem/16496 🔑 숫자를 모두 10자리로 맞추기 3 = 3333333333 30 = 3030303030 34 = 3434343434 5 = 5555555555 9 = 9999999999 정렬하면 9999999999, 5555555555, 3434343434, 3333333333, 3030303030 이렇게 10자리로 맞추고 내림차순 정렬을 한 후 원래 숫자들을 출력하면 끝 ✨ n = int(input()) nums = input().split() sort_list = [] for n in nums: new_num = n * 10 # 문자열 10번 반복해서 최소 10자리 이상으로 만들기 sort_list.append((int(new_num[:1..