본문 바로가기

코딩 테스트/do it! 알고리즘 코딩테스트100

064 최소 스패닝 트리 첫번째 코드 최소 신장 트리 알고리즘을 이용한 문제이다.코드는 책을 참고했다. 유니온 파인드와 최단 거리가 섞인 문제로 유니온 파인드에 대한 명확한 이해가 필요하다.부모노드와 최단 거리를 함께 생각하는 문제로개념을 이해하면 원리는 이해가 되지만코드 작성하려고 손을 올리면 멈추게 되는 문제이다. 다음에 다시 풀어보아야 하는 문제이다.혼자 모두 이해하고 적을 수 있다면 최소 신장 트리와 유니온 파인드를 모두 이해했다는 것이 아닐까 import sys input = sys.stdin.readline from queue import PriorityQueue n, m = map(int, input().split()) queue = PriorityQueue() parent = [0] * (n+1) for i in .. 2024. 7. 18.
063 케빈 베이컨의 6단계 법칙 첫번째 코드 그래프에서 최단 거리를 표현하는 방법들을 정리한 후플로이드-워셜을 이용해야 하는 문제를 풀었다. 그래서 코드를 적으면서 비교적 이해가 쉬웠다.플로이드-워셜 개념을 알고 있다면 문제에 적용하는 방법만 잘 생각하면 쭉쭉 적을 수 있을 것 같다.(수학적 원리는 아는데 문제에 적용이 걱정 되는 느낌) 코드는 책을 참고했다!코드와 익숙해지자!! import sys input = sys.stdin.readline n, m = map(int, input().split()) distance = [[sys.maxsize for j in range(n+1)] for i in range(n+1)] for i in range(1, n+1):     distance[i][i] = 0      for i in ran.. 2024. 7. 18.
061 플로이드 첫번째 코드 플로이드-워셜 방법을 처음 써보았다.코드는 책을 참고했다. 앞서 작성한 다양한 방법의 그래프 문제들의 알고리즘들을 빨리 정리해야할 필요성이 느껴진댜....복잡하다.. 어렵당; import sys input = sys.stdin.readline n = int(input()) m = int(input()) distance = [[sys.maxsize for j in range(n+1)] for i in range(n+1)] for i in range(1, n+1):     distance[i][i] = 0 for i in range(m):     s, e, v = map(int, input().split())     if distance[s][e] > v:         distance[s][e.. 2024. 7. 16.
062 경로 찾기 첫번째 코드 3개의 for문이 반복되는 코드이므로 차차 생각하면서 정리해야겠다는 생각이 든다.하지만 앞의 그래프 풀이법보다는 조금 더 생각하기 편한 것 같다.정작 혼자 하나하나 따지면 머리가 깨지겠지만! 우울하지말고 다음에 다시 풀어보자!코드는 책을 참고했다! n = int(input()) distance = [[0 for j in range(n)] for i in range(n)] for i in range(n):     distance[i] = list(map(int, input().split())) for k in range(n):     for i in range(n):         for j in range(n):             if distance[i][k] == 1 and dista.. 2024. 7. 16.
059 타임머신 첫번째 코드 벨만-포드는 음수가 가능하고사이클이 있는 경우 확인이 가능하다. 뭔가 다익스트라와 비슷한 유형의 문제라고 느꼈는데위의 경우를 제외하고 언제 사용하는게 더 효율적인지는 잘 모르겠다! 코드는 책을 참고했는데여전히 어렵고 다음에 꼭 다시 풀어야겠다...문제가 어려워서 그런가 점점 그냥 따라쓰는 기분... import sys from collections import deque input = sys.stdin.readline n, m = map(int, input().split()) A = [] distance = [sys.maxsize] * (n+1) for i in range(m):     s, e, t = map(int, input().split())     A.append((s, e, t)).. 2024. 7. 11.
060 오민식의 고민 첫번째 코드 벨만-포드 알고리즘을 반대로 생각하는 문제이다.벨만-포드 자체에 익숙하지 않지만 반대로 하라고 하니 더 정신이 없다... 코드는 책을 참고했다!그래도 전반적인 개념에 대한 코드와 적응하고 있다!꼭 다시 풀어봐야하는 문제이다!! import sys input = sys.stdin.readline n, scity, ecity, m = map(int, input().split()) A = [] distance = [-sys.maxsize] * n for i in range(m):     s, e, p = map(int, input().split())     A.append((s, e, p)) money = list(map(int, input().split())) distance[scity] = m.. 2024. 7. 11.
728x90

티스토리툴바