반응형 분류 전체보기103 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. [백준] 1236번 : 성 지키기 유형 : 탐색 [예제] 5 8 ....XXXX ........ XX.X.XX. ........ ........ [출력] 3 1. 내 풀이 우선 예시를 통해 문제를 이해해보자. (아래그림 참고) import sys N, M = map(int,sys.stdin.readline().split()) _list = [] result1 = 0 for i in range(N): tmp = sys.stdin.readline().strip() _list.append(tmp) if 'X' not in tmp: result1 += 1 result2 = 0 for i in range(M): cnt2 = 0 for j in range(N): if _list[j][i] == 'X': break else: cnt2 += 1 if .. 2022. 1. 4. [백준] 1668번 : 트로피 진열 유형 : 탐색 [예제] 7 1 4 2 5 3 7 1 [출력] 4 2 1. 내 풀이 예제를 우선 살펴보면, 위의 그림처럼 중간중간 변하는 max를 기준으로 보이는 개수가 달라지는 것을 알 수 있다. 그래서 max값을 기준으로 값을 비교하는 식으로 코드를 짜면 되겠다고 생각했다. import sys N = int(sys.stdin.readline()) _list = [] for _ in range(N): num = int(sys.stdin.readline()) _list.append(num) def count_trophy(_list,N): cnt = 1 _max = _list[0] for i in range(N): if _max < _list[i]: cnt += 1 _max = _list[i] return .. 2022. 1. 3. [백준] 1302번 : 베스트셀러 ☆ 유형 : 탐색 [예제] 5 top top top top kimtop [출력] top 1. 내 풀이 import sys N = int(sys.stdin.readline()) _list = [] for _ in range(N): book = sys.stdin.readline().strip() _list.append(book) _list = sorted(_list) _set = set(_list) _list2 = list(_set) _list2 = sorted(_list2) max = 0 max_book = 0 for i in range(len(_list2)): cnt = _list.count(_list2[i]) if cnt > max: max = cnt max_book = _list2[i] print(max.. 2022. 1. 3. 이전 1 2 3 4 5 6 7 8 ··· 18 다음 반응형
