[헷갈리는 알고리즘 다시 정리 + 노션 백업용]
1. 이진탐색
복잡도
O(logN)
이진탐색 특징
- 초기 설정시 왼/오 끝, 중간 인덱스 초기화 필요
- 반복문 탈출 조건
- mid가 양 끝값 중 하나와 만날 때
- left ≤ right를 벗어날 때
- 이미 정렬된 배열에서 특정 원소를 찾을 때 효과적
예외사항
- 배열의 요소가 1개일 때 → mid와 target 같은지 검사
반복문 이후 상태
- 예외사항을 제외하면 무조건 left = mid, right 상태
- target은 left보다 작거나, right와 같거나, right보다 큼
- 무조건 일치하는 값을 찾는 경우라면 left보다 작거나 right보다 큰 경우를 고려할 필요 없이 left나 right중에 같은 게 있는지만 확인
예제
- 예제1 mid로 계속 범위를 반씩 쪼개면서 탐색하다가, mid가 right이나 left와 만나는 순간 쪼개나가기 탈출 둘 중 하나가 target이면 탐색 성공, target이 아니면 찾는 값 없음(탐색 실패)
class Solution: def search(self, nums: List[int], target: int) -> int: #초기설정 left = 0 right = len(nums)-1 mid = (left+right)//2 #mid가 left나 right중 하나라도 만날 때까지 돌림 while mid != left and mid != right: if target > nums[mid]: left = mid mid = (left+right)//2 else: right = mid mid = (left+right)//2 #left와 right중에 target이 존재하면 해당 인덱스 리턴, 없으면 탐색 실패(-1) if nums[left] == target: return left elif nums[right] == target: return right else: return -1 - 예제2 https://leetcode.com/problems/sqrtx/description/ x의 제곱근수보다 작으면서 가장 가까운 정수 구하기
class Solution: def mySqrt(self, x: int) -> int: left = 0 right = x while right>=left: # 종료 조건 mid = (left + right)//2 if mid*mid<=x: left = mid+1 else: right = mid-1 # 이미 mid를 검사했으므로 범위에서 제외 return right # 끝나고도 남아있다면 right이 반환값(마지막 m값)
2. DFS (깊이 우선 탐색)
- 스택 또는 재귀 함수로 구현
- 탐색 시간
O(N) - 경로의 특징을 저장해야 할 경우 유리하다
1) 구현 방법 [스택]
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리
- 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드 꺼내기
- 더 이상 수행할 수 없을 때까지 반복
특징
- 초기화 - 루트 노드 스택에 삽입
- 반복문 탈출 조건 - 스택이 비는 순간
2) 구현 방법 [재귀]
DFS-1. 중위 순회
특징
-
왼-중앙-오 순으로 방문
-
왼쪽 SubTree를 이루는 모든 노드는 부모 노드보다 작거나 같음
-
오른쪽 SubTree를 이루는 모든 노드는 부모 노드보다 크거나 같음
-
가장 왼쪽 아래 노드로부터 시작하여 가장 오른쪽 아래 노드로 끝남
-
중위 순회 예제 - subtree validation
https://leetcode.com/problems/validate-binary-search-tree/description/
class Solution: def isValidBST(self, root: Optional[TreeNode]) -> bool: # 중위순회 문제 - 중위순회하여 노드의 값을 나열했을 때 오름차순 보장해야 함 arr = [] def inorder(v): if not v: return None inorder(v.left) arr.append(v.val) inorder(v.right) inorder(root) return arr == sorted(list(set(arr))) # 숫자가 겹치면 요구사항을 만족하지 않으므로 Setleft is None and right is None 일 때 동작하도록 (X)
노드 자체가 None일때 동작을 하지 않게 해서 깔끔하게 구현 (O)
DFS-2. 전위 순회
특징
- 왼쪽 아래로 최대한 쭉 내려가고, 다 거치면 오른쪽 지남
- 루트 노드를 시작으로 하고, 마지막으로 오른쪽 아래 노드를 거침
- 왼쪽 뿌리부터 순회
DFS-3. 후위 순회
특징
- 하위 트리 다 방문한 후에 부모 노드 방문
3. BFS (너비 우선 탐색)
- 큐를 이용하여 구현 (deque)
- 탐색 시간
O(N) - 인접한 노드부터 너비 우선 탐색
- 먼저 가로로 이동한 뒤, 더 지나갈 노드가 없을 때 depth 내려감
- 일반적으로 수행 시간은 DFS보다 좋은 편 → 둘 다 써도 된다면 BFS가 유리
- 너비 우선 탐색은 가까운 곳에서부터 찾기. 때문에 먼저 찾아지는 해답이 최단거리
구현 방법 [큐 deque] → append + popleft
- 탐색 시작 노드를 스택에 삽입하고 방문 처리
- 방문하지 않은 인접 노드가 있으면 그. 노드들을
모두 큐에 삽입하고 visited 처리 - 방문하지 않은 인접 노드가 더 이상 없다면 visited스택에서 최상단 노드를 꺼냄
- 두 번째 과정을 더 이상 수행할 수 없을 때까지 반복
특징
-
초기화 - 루트 노드 큐에 삽입
-
반복 탈출 조건 - 큐가 비는 순간
-
각 자식 노드가 visited에 이미 추가되어 있는지를 확인할 필요가 없음 - null이 아니라면 무조건 추가
- 예) if v.left not in visited: 와 같은 조건이 필요 없음
-
예제1. 노드 개수 세기
방법1) BFS + 큐 사용
from collections import deque # DFS, deque class Solution: def countNodes(self, root: Optional[TreeNode]) -> int: # 예외 if not root: return 0 count = 0 visited = deque([root]) while visited: v = visited.popleft() count += 1 if v.left: visited.append(v.left) if v.right: visited.append(v.right) return count
BFS vs DFS, 큐? 스택?
- 스택과 큐의 차이
- BFS는 바로 이전 노드로 돌아가서 탐색해야 하므로 스택 사용
- DFS는 인접한 노드들을 한 번에 넣고, 아까 넣은 것들을 먼저 방문해야 하므로 큐 사용
❗️ DFS vs BFS 문제 유형
- 모든 정점을 방문하는 것이 중요한 경우 →
DFS, BFS 상관 없음 - 경로의 특징을 저장해야 하는 문제 →
DFS- a - b간 경로를 구할 때 같은 숫자가 있으면 안 된다 등
- BFS는 경로의 특징을 가지지 못함
- 최단거리 →
BFS- 깊이 우선 탐색의 경우 처음으로 발견되는 해답이 최단거리가 아닐 수도 있음
- 너비 우선 탐색은 가까운 곳에서부터 찾기 때문에 먼저 찾아지는 해답이 최단거리
- 검색 대상 그래프의 크기가 클 때 →
DFS - 검색 대항 그래프가 크지 않고, 시작 지점부터 원하는 대상이 멀지 않다면
BFS
