[파이썬 알고리즘 인터뷰] 그래프

CS/algorithm & data structure

hjkim0502 2022. 3. 12. 01:31

그래프: 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조
오일러 경로: 모든 간선(edge)을 한 번씩 방문하는 유한 그래프 경로(= 한붓그리기)
- 모든 정점(vertex)이 짝수 개의 차수(degree)를 갖는다면 오일러 경로
해밀턴 경로: 각 정점을 한 번씩 방문하는 무향 또는 유향 그래프 경로
- 최적 알고리즘이 없는 대표적인 NP-완전 문제 (NP문제 중 NP-난해 문제)
- 해밀턴 순환: 원래의 출발점으로 돌아오는 경로
  - 외판원 문제: 최단거리인 해밀턴 순환을 찾는 문제 -> 다이나믹 프로그래밍으로 최적화
그래프 순회 (그래프 탐색): 그래프의 각 정점을 방문하는 과정
- 깊이 우선 탐색(DFS)이 너비 우선 남색(BFS)에 비해 더 널리 쓰임
- DFS는 주로 스택이나 재귀로 구현(재귀 선호), BFS는 주로 큐로 구현하며 그래프의 최단 경로 문제에 쓰임
- 그래프 표현: 인접 행렬, 인접 리스트
백트래킹: 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 알고리즘 -> 제약 충족 문제에 유용
- DFS와 같은 방식으로 탐색하는 모든 방법, 주로 재귀로 구현
- 제약 충족 문제: 수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제 ex)스도쿠, 십자말 풀이

200. number of islands

- DFS (사방)

* 클래스 내에서 멤버변수 사용시: 클래스명.변수명, 인스턴스 변수 사용시: self.인스턴스명, 메소드 사용시: self.메소드명

- 중첩함수 -> 부모 변수를 자유롭게 쓸 수 있으므로 grid 불러올 필요 없고, self. 필요없음

※ 부모 함수에서 선언한 객체를 중첩 함수에서 조작하면 부모에 동일하게 적용, 재할당하면 부모에는 반영되지 않는다

17. letter combination of a phone number

- DFS로 탐색, 백트래킹으로 결과 조합

46. permutations

- DFS

- itertools.permutations(nums)

※ 객체 복사: [:], list.copy(), 중첩 리스트일때: import copy -> copy.deepcopy(list)

- 내 풀이: 바로 직전 문제처럼 답을 저장하는 prev_nums를 dfs의 인자로 담아서 append, pop 부분 간결화

77. combinations

- DFS -> 조합 결과가 오름차순으로 정렬되게끔 탐색 범위를 설정하여 순서만 다른 중복된 결과를 걸러낸다

- itertools.combinations(nums, k)

- 내 풀이: 마찬가지로 nums를 dfs의 인자로 담음

dfs 생성 시, 문제 input의 인덱스를 인자로 설정해 재귀적으로 인덱스+1을 넘기는 방식이 보통 코드가 더 간결하고, 아니면 input 자체를 담아 for문 안에서 일일히 조작하여 재귀적으로 넘겨준다(복사에 유의)

39. combination sum

- DFS: 중복 조합 (인자로 target을 넘겨줌) -> int 뺄셈 값으로 탐색 종료 결정

- 내 풀이: 인자로 candidates를 넘겨줌 -> list sum 값으로 탐색 종료 결정

- 책의 풀이가 약간 시간복잡도가 더 낮다

78. subsets

- DFS: input의 각 단계별로 탐색하여 나오는 모든 결과들의 집합

332. reconstruct itinerary

- DFS 재귀

- DFS 반복

- 중복경로 배제하며 어휘순으로 탐색

- 경로가 안 끊길 때까지 계속 탐색하다가 막히면 그때까지 탐색 경로 역순으로 담기

207. course schedule

- DFS -> 순환구조 유무 탐색

- 가지치기로 최적화 -> 이미 방문한 노드 탐색 X