[코딩 인터뷰]개념과 알고리즘 - 재귀와 동적 프로그래밍(Python)

 

[ 트리플 스텝 ]

 어떤 아이가 n개의 계단을 오를 때 한 번에 1 계단 오르기도 하고, 2 계단이나 3 계단을 오르기도 합니다. 계단을 오르는 방법이 몇 가지가 있는지 계산하는 메서드를 구현하라.

✔️ 브루트포스

def countWays(n):
    if n < 0: return 0
    elif n == 0: return 1
    else: return countWays(n-1) + countWays(n-2) + countWays(n-3)

✔️ 메모이제이션

def countWays(n, memo=[]):
    if memo == []: memo = [-1]*(n+1)
    if n < 0: return 0
    elif n == 0: return 1
    elif memo[n] > -1: return memo[n]
    else:
        memo[n] = countWays(n-1, memo) + countWays(n-2, memo) + countWays(n-3, memo)
        return memo[n]

👀 3가지 경우(n-1, n-2, n-3번쨰 계단에서 n번째로 올라가기)를 모두 더하면 됩니다.

 

 

[ 격자판 상의 로봇 ]

 행의 개수는 r, 열의 개수는 c인 격자판의 왼쪽 상단 꼭짓점에 로봇이 놓여 있다고 상상해 볼 때, 이 로봇은 오른쪽 아니면 아래쪽으로만 이동할 수 있습니다. 하지만 어떤 셀은 '금지 구역'으로 지정되어 있어서 로봇이 접근할 수 없습니다. 왼쪽 상단 꼭짓점에서 오른쪽 하단 꼭짓점으로의 경로를 찾는 알고리즘을 설계하라.

def getPath(maze):
    if maze == [[]]: return None
    path = []
    failedPoints = []
    if solve(maze, len(maze)-1, len(maze[0])-1, path, failedPoints):
        return path
    return None

def solve(maze, row, col, path, failedPoints):
    if (col < 0) or (row < 0) or (not maze[row][col]): return False
    p = [row, col]
    if p in failedPoints: return False
    isO = (row == 0) and (col == 0)
    if isO or solve(maze, row, col-1, path, failedPoints) or solve(maze, row-1, col, path, failedPoints):
        path.append(p)
        return True
    else:
        failedPoints.append(p)
        return False

👀 목적지에서 출발점까지 거꾸로 찾아 나가는 방법을 사용했습니다.

 

 

[ 마술 인덱스 ]

 배열 A[0, ..., n-1]에서 A[i] = i인 인덱스를 마술 인덱스라 정의할 때, 정렬된 상태의 배열이 주어졌을 때, 마술 인덱스가 존재한다면 그 값을 찾는 메서드를 작성하라.

⭐ 배열 안에 중복된 값은 없습니다.

def magicIndex(array):
    for idx, i in enumerate(array):
        if idx == i: return i
   return -1

def magicIndex(array, start=0, end=0):
    if start == 0 and end == 0: end = len(array)-1
    if end < start: return -1
    midIndex = (start+end)//2
    midValue = array[midIndex]
    if midValue == midIndex: return midIndex

    leftIndex = min(midIndex-1, midValue)
    left = magicIndex(array, start, leftIndex)
    if left >= 0: return left

    rightIndex = max(midIndex+1, midValue)
    right = magicIndex(array, rightIndex, end)
    return right

👀 처음에는 for문을 이용하여 문제를 풀었는데 양쪽으로 나눠서 찾아보면 더 빨라집니다.

 

 

[ 부분집합 ]

 어떤 집합의 부분집합을 전부 반환하는 메서드를 작성하라.

from itertools import combinations
def getSubset(array):
    return sum([list(map(list, combinations(array, i))) for i in range(len(array)+1)], [])

👀 combinations를 이용하여 조합으로 풀었습니다.

 

 

[ 재귀 곱셈 ]

 * 연산자를 사용하지 않고 양의 정수 두 개를 곱하는 재귀 함수를 작성하라.

⭐ 덧셈, 뺄셈, 비트 시프팅 연산자를 사용할 수 있지만 이들의 사용 횟수를 최소화해야 합니다.

def minProduct(a, b):
    max_n = max(a, b)
    min_n = b if max_n == a else a

    if min_n == 0: return 0
    elif min_n == 1: return max_n

    s = min_n // 2
    halfProd = minProduct(s, max_n)

    return halfProd + halfProd + (max_n if min_n%2 != 0 else 0)

👀 두 수를 큰 수와 작은 수로 나누어서 작은 수의 절반이 짝수이면 그 결과를 곱절하고 짝수가 아니면 곱절에 큰 수를 더해줍니다.

 

 

[ 하노이타워 ]

 크기가 서로 다른 N개의 원반을 세 개의 기둥 중 아무 곳으로나 옮길 수 있을 때 첫 번째 기둥에서 마지막 기둥으로 옮기는 프로그램을 작성하라.

def hanoi(n, start=1, mid=2, end=3):
    result = []
    if n == 1:
        result.append([start, end])
    else:
        tmp = hanoi(n-1, start, end, mid)
        result += tmp
        result.append([start, end])
        tmp = hanoi(n-1, mid, start, end)
        result += tmp
    return result

👀 하노이 타워는 자주 나오는 문제이니 잘 알아두는 것이 좋습니다.

 

 

[ 중복 없는 순열 ]

 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라.

⭐ 단, 문자는 중복되어 나타날 수 없습니다.

from itertools import permutations
def getPerms(string):
    return sum([list(map(list, permutations(string)))], [])

👀 간단하게 permutations를 사용하였습니다.

 

 

[ 중복 있는 순열 ]

 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 문자는 중복되어 나타날 수 있지만, 나열된 순열은 서로 중복되면 안 됩니다.

from itertools import product
def printPerms(string):
    return sum([list(map(list, product(string, repeat=len(string))))], [])

👀 간단하게 product를 사용하였습니다.

 

 

[ 괄호 ]

 n-쌍의 괄호로 만들 수 있는 모든 합당한(괄호가 적절히 열리고 닫힌) 조합을 출력하는 알고리즘을 구현하라.

def addParen(list, leftRem, rightRem, string, index):
    if leftRem<0 or rightRem<leftRem: return None

    if leftRem == 0 and rightRem == 0:
        list.append(''.join(string))
    else:
        string[index] = '('
        addParen(list, leftRem - 1, rightRem, string, index+1)

        string[index] = ')'
        addParen(list, leftRem, rightRem - 1, string, index+1)
    return list

def generateParens(cnt):
    return addParen([], cnt, cnt, [0]*(cnt*2), 0)

👀 왼쪽 괄호를 다 소진하지 않은 한, 왼쪽 괄호는 항상 삽입할 수 있습니다. 오른쪽 괄호는 오른쪽 괄호 개수가 왼쪽 괄호보다 많아지면 발생합니다.