반응형 ☆9 [백준] 1991번 : 트리 순회 ☆ 유형 : 트리, 구현 [예시 입력] 7 A B C B D . C E F E . . F . G D . . G . . [예시 출력] ABDCEFG DBAECFG DBEGFCA 1. 내 풀이 더보기 N = int(input()) value_list = [] key_list = [] for _ in range(N): tmp = input().split(' ') key_list.append(tmp[0]) value_list.append(tmp[1:]) graph = dict(zip(key_list,value_list)) start_node = 'A' visited, need_visit = list(), list() need_visit.append(start_node) # 전위 순회 while need_visit:.. 2022. 1. 9. [백준] 1939번 : 중량제한 ☆ 유형 : 이진탐색, BFS [예제] 3 3 1 2 2 3 1 3 2 3 2 1 3 [출력] 3 1. 풀이 출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online ** 핵심 아이디어 1. 다리의 개수 M은 최대 100,000이며, 중량 제한 C는 최대 1,000,000,000이다. - 중량 제한이 값이 크기 때문에 이진 탐색으로 풀 수 있을 것이라 의심 - log나 √로 풀 수 있을 것 같은 생각 - 중량 제한 c를 찾고자 하기 때문에, 찾고자 하는 값을 이진 탐색을 수행 - BFS 이용 : 그래프 간선, 노드가 주어졌을 때 특정 노드에서 다른 노드로 이동이 가능한지 판단 - BFS는 다리(간선)의 개수만큼 수행하기 때문에 시간복잡도는 O(M)이다. → 이진탐색 시간복잡도 : .. 2022. 1. 5. [백준] 2110번 : 공유기 설치 ☆ 유형 : 이진탐색 [예제] 5 3 1 2 8 4 9 [출력] 3 1. 풀이 출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패키지 Online ** 핵심 아이디어 1. 집의 개수 N은 최대 200,000이며, 집의 좌표 X는 최대 1,000,000,000이다. - 값이 10억이상으로 설정된 경우 이진탐색을 고려해보아야 한다. → logX나 √X의 시간복잡도를 가진다고 생각하고 방법을 생각해야 한다. 2. 이진 탐색으로 O(N*logX)에 문제를 해결할 수 있다. - 20만 * 30 = 600만 3. 가장 인접한 두 공유기 사이의 최대 Gap을 이진 탐색으로 찾는다. - 이진탐색을 재귀적 방법이나 반복적 방법으로 풀 수 있는데, 여기서는 반복적 방법으로 하는 게 편하다. ex. 1 2 4 .. 2022. 1. 4. 이전 1 2 다음 반응형
