파이썬 알고리즘 인터뷰 책을 정리한 포스트 입니다.

DFS(깊이 우선 탐색)

BFS(너비 우선 탐색)

  
def iter_BFS(start_v):
    discovered = [start_v]
    queue = [start_v]
    while queue:
        v = queue.pop(0)
        for w in graph[v]:
            if w not in discovered:
                discovered.append(w)
                queue.append(w)
    return discovered

BFS는 재귀로 동작하지 않는데

백트래킹

탐색을 하다가 더이상 갈 수 없으면 왔던 길을 돌아가 다른 길을 찾는다는 개념
백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법이다
재귀로 동작 한다
brute force와 유사하지만 한번 방문 후 가능성이 없는 경우 즉시 후보를 포기한다.

_{파이썬 알고리즘 인터뷰 chapter 12}

트리의 가지치기라고 한다

제약 충족 문제

백트래킹은 제약 충족 문제를 풀이하는데 필수적인 알고리즘이다
수많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제를 말한다
합리적인 시간 내에 문제를 풀기 위해 휴리스틱 조합 탐색 같은 개념을 함께 결합해 문제를 풀이한다

섬의 개수

Leetcode #200

1을 육지로, 0을 물로 가정한 2D 그리드맵이 주어졌을 때 섬의 개수를 계산하라

입력

11110

11010

11000

00000

출력

  
def numIsland(grid: list) -> int:
    def dfs(i, j):
        # 더이상 땅이 아니면 종료
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != 1:
            return
        grid[i][j] = 0

        dfs(i + 1, j)
        dfs(i - 1, j)
        dfs(i, j + 1)
        dfs(i, j - 1)

    cnt = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                # 모든 육지 탐색 후 카운트 1 증가
                cnt += 1
    return cnt

동서남북이 모두 연결된 그래프로 가정하고 동일한 형태로 처리할 수 있다
네 방향 DFS 재귀를 이용해 탐색을 끝내면 1이 증가하는 형태로 육지의 개수 파악 가능

중첩 함수

함수 내에 위치한 또 다른 함수, 바깥에 위치한 함수와 달리 부모 함수의 변수를 자유롭게 읽기 가능
단일 함수로 해결해야 하는 경우가 잦은 코딩에서는 매우 자주 쓰인다.

전화 번호 문자 조합

2에서 9까지의 숫자가 주어졌을 때 전화 번호로 조합 가능한 모든 문자를 출력하라

입력

“23”

출력

[“ab”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”]

  
def permute(nums: list) -> list:
    res = []
    prev_ele = []

    def dfs(ele):
        if len(ele) == 0:
            res.append(prev_ele[:])

        for e in ele:
            next_ele = ele[:]
            next_ele.remove(e)
            prev_ele.append(e)
            print(prev_ele)
            dfs(next_ele)
            prev_ele.pop()

    dfs(nums)
    return res

주어진 리스트를 돌면서 이전 값을 하나씩 붙여 재귀 호출을 진행한다
결과를 추출할 때 prev_ele[:]로 처리하는 것이 중요하다
res.append(prev_ele)를 하게 되면 결과 값이 추가되는것이 아니라 prev_ele에 대한 참조가 추가되어 참조값이 변경될 경우 같이 바뀌게 된다.
[:]로 처리하는 것 이외에도 copy()를 사용하거나 deepcopy()를 사용하는 방법이 있다.

itertools 모듈을 사용해보자

itertools 모듈은 반복자 생성에 최적화된 효율적인 기능을 제공한다
함수의 결과가 리스트 내 튜플이라는 것이 문제다
permutations() 함수가 튜플 모음을 반환하기 때문이다.

객체 복사

파이썬은 모든 것이 객체라는 특징이 있다.

  
li = [1, 2, 3]
cop = li.copy()  # 복사
obje = li        # 참조
print(id(li))    # 140188362526528
print(id(obje))  # 140188362526528
print(id(cop))   # 140188362533056

리스트의 id와 list를 복사한 것과 참조한 것의 id를 비교한 것이다.
각각의 id가 다른 것을 볼 수 있다.

순열

서로 다른 정수를 입력받아 가능한 모든 순열을 리턴하라

입력

[1,2,3]

풀이 코드

DFS를 활용한 순열 생성

  
import itertools

def permute(nums: list) -> list:
    res = []
    prev_ele = []

    def dfs(ele):
        # 리프 노드일 때 결과 추가
        if len(ele) == 0:
            res.append(prev_ele[:])

        # 순열 생성 재귀 호출
        for e in ele:
            next_ele = ele[:]
            next_ele.remove(e)
            prev_ele.append(e)
            print(prev_ele)
            dfs(next_ele)
            prev_ele.pop()

    dfs(nums)
    return res

주어진 배열의 조합은 그래프 형태로 나타낼 수 있다.

_{파이썬 알고리즘 인터뷰 chapter 12}

가장 아래에 있는 leaf 노드가 순열 조합의 최종 결과다. 그래프 형태로 자식 노드를 만들어가면 위와 같이 구성된다.

dfs() 탐색으로 진행하면서 이전 값을 하나씩 붙여가며 함수를 재귀 호출한다. 리프 노드에 도달한 경우, 결과에 하나씩 추가하게 된다. 결과를 추가할 때 prev_ele[:]로 해줘야 한다. prev_ele만 사용할 경우 참조된 값이 변경될 경우 같이 바뀌게 된다. [:]외에도 깊은 복사를 제공하는 deepcopy()메소드를 사용할 수 있다.

itertools 모듈 사용

  
def permute_itertools(nums: list) -> list:
    return list(itertools.permutations(nums))

itertools모듈은 반복자 생성에 최적화되어 있으며, C라이브러리로 설계되어 속도에도 이점을 가진다. permutation()을 사용하여 리스트에 존재하는 원소들의 모든 경우의 수를 얻을 수 있다.

그래프 (Python Algorithm interview 12장)