백트래킹

백트래킹

완전탐색을 가지치기 하는 것

가능성이 없는(볼 필요 없는) 경우의 수를 제거하는 기법

중복된 순열 등 풀때 필수

재귀함수 ⇒ 특정 시점으로 돌아오는 게 핵심

재귀 함수 팁

파라미터 : 바로 작성 X

구조를 먼저 잡으면 자연스럽게 필요한 변수들이 보임

def dfs(level):
    # 기저 조건
    # 이 문제에서는 3개를 뽑아을 때 까지 반복
    if level == 3:
        return

    # 들어가기 전 다음 재귀 호출 갔다와서 할 로직
    # 기본 코드
    '''
    path[level] = arr[0]
    dfs(level + 1)

    path[level] = arr[2]
    dfs(level + 1)
    '''
    # 기본 코드를 반복문으로 변경
    # 갈 수 있는 후보군
    for i in range(len(arr)):
        # 여기는 못가 ! (가지치기)
        # 갈 수 없을 때 조건을 거는 것이 조건이 까다로울 수록 좋음

        # 조건 1~~~
        if arr[i] in path:
            continue
        if 조건 2:
            continue

        path[level] = arr[i]
        dfs(level+1)
        # 갔다와서 할 로직
        # 기존 방문을 초기화
        path[level] = 0

dfs(0)

1. 완전 탐색 경우의 수를 계산해본다.
2. 가지치기를 했을 때 대략적인 감소 예측
3. 시간 초과가 발생하네? 기저조건, 가지치기를 더 고민하자

트리

싸이클이 없는 무향 연결 그래프

1. 싸이클
   • 방문했던 노드로 다시 돌아오는 다른 경로가 있는 경우
2. 무향
   • 간선에 방향이 없다(양방향)
3. 연결 그래프
   • 모든 꼭지점이 서로 갈 수 있는 경로가 있다.

형제 노드끼리는 연결 되지 않는다 ⇒ 싸이클이 발생하기 때문

노드의 차수 = 후보군의 수

높이는 왜 계산해야될까? 시간복잡도 계산 때문에

⇒ 최악의 경우 차수와 높이가 어떻게 될까 생각해봐야 된다.

이진트리

자식 노드(서브 트리)가 0,1,2인 특별한 형태의 트리

가장 많이 쓰이는 형태

노드의 개수가 N개 일때,
최악의 경우 : 높이 h = N
최선의 경우 : 높이 h = logN

N = $2^{k+1} -1$

완전 이진 트리

높이가 h이고 노드 수가 n개일 때 (단, $2^h <= n <= 2^{h+1}$)

이진 탐색 트리 BST

• 탐색작업을 효율적으로 하기 위한 자료구조
• 모든 원소는 서로 다른 유일한 키를 갖는다.
• key (왼쪽 서브 트리) < key(루트 노드) < key(오른쪽 서브 트리)
• 왼쪽 서브 트리와 오른쪽 서브 트리도 이진 탐색 트리다.
• 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.

탐색 연산

• 루트에서 탐색 시작
• 탐색할 키 값 x를 루트 노드의 키 값 k와 비교
  • x=k: 탐색 성공
  • x<k : 루트 노드의 왼쪽 서브 트리에 대해서 탐색 연산 수행
  • x>k : 루트 노드의 오른쪽 서브 트리에 대해서 탐색 연산 수행
• 서브 트리에 대해서 순환적으로 탐색 연산을 반복한다.
• 탐색 수행할 서브 트리가 없으면 탐색 실패

삽입 연산

1. 먼저 탐색 연산을 수행
   • 삽입할 원소와 같은 원소가 트리에 있으면 삽입할 수 없으므로, 같은 원소가 트리에 있는지 탐색하여 확인한다.
   • 탐색에서 탐색 실패가 결정되는 위치가 삽입 위치가 된다.
2. 탐색 실패한 위치에 원소를 삽입한다.

삭제 연산 - 까다로움

1. 삭제할 노드가 차수가 0인 리프 노드 : 그냥 찾아서 지운다.
2. 리프 노드가 아니고 차수가 1인 경우 : 탐색을 해서 해당 노드를 지워주고, 지운 노드의 자식을 부모에다가 연결시킨다.
3. 리프노드가 아니고 차수가 2인 경우 : 왼 쪽 서브 트리 (작은 것들) 중에서 가장 큰 것을 바꾼다.

성능

• 탐색, 삽입, 삭제 시간은 트리의 높이만큼 시간이 걸림 O(h)
• 평균적으로 O(logN)
• 최악의 경우(편향 이진 트리) O(n)
  • 순차탐색과 시간복잡도 같음

힙트리 Heap

우선순위큐에 많이 활용된다

형제 끼리는 정렬 보장 되지 않는다.

최대 힙

• 키 값이 가장 큰 노드를 찾기 위한 완전 이진 트리
• 부모 노드의 키 값 > 자식 노드의 키 값
• 루트 노드 : 키 값이 가장 큰 노드

최소 힙

• 키 값이 가장 작은 노드 찾기
• 부모 노드 < 자식 나도
• 루트 노드 : 키 값이 가장 낮은 노드

삽입 $logN 또는 O(n)$

일단 마지막에 넣는다. → 순서 변경하면서 자리 찾아간다

삭제

• 힙에서는 루트 노드의 원소만을 삭제 할 수 있다.
• 루트 노드의 원소를 삭제해서 반환한다. ⇒ 하지만 루트 노드를 갑자기 삭제하면 서브 트리가 두 개가 나와버림 = 리스트 두 개를 합치는 형식 = 자료구조 관리 어려움
• 일단 루트 노드와 마지막 노드를 바꾸고, 그리고 마지막 노드를 삭제 시킨다. = pop() + 위치 찾기
• 힙의 종류에 따라 최대 값 or 최소 값을 구할 수 있다.

힙의 활용

• 힙을 활용하는 대표적인 2가지 예는 특별한 큐의 구현과 정렬
• 우선순위 큐를 구현하는 가장 효율적인 방법이 힙을 사용하는 것이다.
  • 노드 하나의 추가 / 삭제가 시간 복잡도가 $O(logN)$ 이고 최대값/최소값을 O(1)에 구할 수 있다.
  • 완전 정렬보다 관리 빙용이 적다.

힙 트리를 다룰 때 조심해야 되는 것

1. 형제 노드끼리는 정렬이 보장 되지 않음 ⇒ 디버깅시 리스트를 잘 봐야함
2. 삽입 시 완전이진트리의 형태를 유지하기 위해 마지막에 삽입 → 순서 변경하면서 자리 찾아감