본문 바로가기

코딩 테스트291

최소 신장 트리 최소 신장 트리 minimum spanning tree 모든 노드를 연결할 때 사용된 에지의 가중치의 합을 최소로 하는 트리사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음n개의 노드가 있으면 최소 신장 트리 구성 에지 개수는 n-1이다.1. 에지 리스트로 그래프 구현, 유니온 파인드 리스트 초기화2. 그래프 데이터를 가중치 기준 정렬3. 가중치가 낮은 에지부터 연결 시도사이클 형성 여부 find로 확인 후사이클이 아닌 경우에만 union 연산으로 두 노드 연결 4. 연결 에지 개수 n-1만큼 반복 5. 에지 개수 n-1인 경우 종료완성된 최소 신장 트리의 총 에지 비용 출력 2024. 8. 10.
이어 붙인 수 첫번째 코드 하나하나 숫자를 확인한 후 홀수/짝수인지 확인확인한 후 해당 숫자를 문자열로 바꾸어 더하는 과정을 통해 숫자를 이어붙임모든 숫자를 이어붙인 후 문자열인 값을 숫자로 바꾸어 더하는 방법을 통해 정답을 구한다. def solution(num_list):     answer = 0     num1 = ''     num2 = ''          for i in num_list:         if i % 2 == 0:             num2 += str(i)         else:             num1 += str(i)          answer = int(num1) + int(num2)              return answer 통과!오랜만에 문제를 풀어서 걱정이 많았.. 2024. 8. 9.
075 LCA2 (미해결) 첫번째 코드 코드는 책을 보고 참고하는 중 이해가 되지 않은 부분이 있어 아직 작성을 하지 않는다.이해 후에 코드를 다시 작성할 예정이다.링크 2024. 8. 8.
076 이항 계수 1 첫번째 코드 코딩 테스트 문제를 풀면서 맨날 dp, dp 이야기는 들었는데 드디어 나왔다.오히려 반가운 마음도 들었다. 처음 풀어보는 dp문제이므로 방법을 알기 위해 코드는 책을 참고했다.이해가 비교적 쉬웠으나 암기할 내용들이 있고, 응용될 방법이 정말 많다는 생각이 들었다. import sys input = sys.stdin.readline n, k = map(int, input().split()) dp = [[0 for _ in range(n+1)] for _ in range(n+1)] for i in range(0, n+1):     dp[i][1] = i     dp[i][0] = 1     dp[i][i] = 1 for i in range(2, n+1):     for j in range(1, .. 2024. 8. 8.
074 LCA (미해결) 첫번째 코드 최소 공통 조상 관련된 문제로 코드는 책을 참고했다.개념이나 그림으로 이해하면 이해는 편한데 사실 코드상에서 이해가 너무 어려웠다...사실 지금도 제대로 이해하고 있는지는 의문이다... ㅋㅋ; 그치만 개념은 이해가 되었기 때문에 차근차근 다음에도 풀어보면 이해할 수 있을 것이다. import sys from collections import deque input = sys.stdin.readline print = sys.stdout.write n = int(input()) tree = [[] for _ in range(n+1)] for _ in range(0, n-1):     s, e = map(int, input().split())     tree[s].append(e)     tree[.. 2024. 8. 6.
073 구간 곱 구하기 첫번째 코드 구간 합 구하기를 세그먼트로 풀어보았다면 아래 코드 이해는 어렵지 않을 것이다.하지만 곱하기를 이용하므로 MOD를 이용한다는 부분 정도를 생각한다면금방 변형해서 풀 수 있는 문제이다. import sys input = sys.stdin.readline n, m, k = map(int, input().split()) treeHeight = 0 length = n MOD = 1000000007 while length != 0:     length //= 2     treeHeight += 1 treeSize = 2 ** (treeHeight + 1) leftNodeStartIndex = treeSize//2 - 1 tree = [1] * (treeSize + 1) for i in range(le.. 2024. 8. 6.
728x90

티스토리툴바