2021/03/08

[Python] 백준 1208

구글링이 잘 안돼서...직접 쓰는 리뷰 😅 1182번 부분수열의 합과 같은 유형의 문제이지만 범위와 시간제한 등으로 다른 풀이 방법을 적용해야한다. n개의 원소를 가진 수열의 부분 수열을 구하는 방법은 2**n 이라고 한다. 이 문제의 최대 범위는 n==40이므로 최악의 경우 2**40의 복잡도를 가지게된다. 그래서 이 문제는 리스트를 반으로 나눠 반에 해당하는 부분 수열을 구할 것이다. 그럼 최악의 경우 (2**20)*2이다. (2**20)*2 = 2097152 VS 2**40 = 1099511627776 효율 ㅇㅈ? 나는 딕셔너리를 사용해서 부분 수열을 구했다. (이유는 뒤에) key : 부분 수열의 합 value : 해당 부분 수열의 합이 나온 횟수 예제를 예로 들어 코드 설명을 하자면 우선 l=[..

[Python] 백준 1167, 1967

입력값의 차이 외에는 똑같은 문제이다. 먼저 트리의 지름을 찾는데에는 rule이 있다. ✔ 트리에서 임의의 노드(A)를 선택해 가장 먼 노드를 찾는다. -> B ✔ B에서 가장 먼 노드를 찾는다. -> C ✔ 그러면 B와 C사이의 거리가 가장 멀다. (==지름) 이 규칙을 알면 쉽게 쉽게 풀 수 있겠다. 모르면 ㅠㅠ 삽질 하니까 알고있자... Answer 1167 import sys from collections import defaultdict from collections import deque n=int(sys.stdin.readline()) dic=defaultdict(list) for i in range(n): l=list(map(int,sys.stdin.readline().split())) a..