반응형 Python51 [백준] 1927번 : 최소 힙 유형 : 힙, 자료구조 [예제 입력] 9 0 12345678 1 2 0 0 0 0 32 [예제 출력] 0 1 2 12345678 0 1. 내 풀이 1) 첫 번째 풀이 import sys n = int(sys.stdin.readline()) list = [] for i in range(n): x = int(sys.stdin.readline()) if x == 0: # 가장 작은 값 출력 if len(list) == 0: print(0) else: print(min(list)) list.remove(min(list)) # min 제거 else: list.append(x) ▷ 시간초과가 발생하길래, sys.stdin.readline()을 이용하였다. ▷ heapq라는 라이브러리를 몰라서 못 썼는데, 내가 알고.. 2022. 1. 24. [백준] 2250번 : 트리의 높이와 너비☆ 유형 : 트리, 구현 난이도 : 중(상) [예제 입력] 19 1 2 3 2 4 5 3 6 7 4 8 -1 5 9 10 6 11 12 7 13 -1 8 -1 -1 9 14 15 10 -1 -1 11 16 -1 12 -1 -1 13 17 -1 14 -1 -1 15 18 -1 16 -1 -1 17 -1 19 18 -1 -1 19 -1 -1 [예제 출력] 3 18 1. 내 풀이(미완성) class Node: def __init__(self, data, left_node, right_node): self.data = data self.left_node = left_node self.right_node = right_node self.col = 0 self.level = 0 array = [] def in_orde.. 2022. 1. 10. [백준] 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. BFS(Breadth-First Search), DFS(Depth-First Search) 1. 그래프 탐색 알고리즘 1) 대표적인 알고리즘 ① 너비우선탐색(BFS; Breadth First Search) : 정점들과 같은 레벨에 있는 노드들을 먼저 탐색하는 방식 ② 깊이우선탐색(DFS; Depth First Search) : 정점의 자식들을 먼저 탐색하는 방식 2) 예제 - 그래프가 아래 그림처럼 있을 경우, 그래프를 BFS와 DFS로 탐색하는 순서를 알아보자. ① BFS : A → B → C → D → E → F ② DFS : A → B → D → C → E → F 2. 그래프 표현 - 파이썬에서 제공하는 딕셔너리와 리스트 자료 구조를 활용해 그래프를 표현할 수 있다. - 노드들을 key로 만들어주고, 해당 노드에 간선으로 연결된 인접 정점을 values에 추가한다. key values A.. 2022. 1. 5. [백준] 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 3 4 5 6 ··· 9 다음 반응형
