코딩테스트를 위한 자료구조 및 알고리즘 개론

two-sum¶

In [ ]:

def twoSum(nums: list[int], target: int) -> list[int]:
  for i in range(0, len(nums)-1):
    for j in range(i+1, len(nums)):
      if nums[i] + nums[j] == target:
        print(nums[i], nums[j])
        return [i, j]

twoSum([3, 2, 4], 6)

2 4

Out[ ]:

[1, 2]

재귀함수 이용¶

In [ ]:

def solution(nums, target):
    n = len(nums)
    def recur(ans, start):
        if len(ans) == 2:
            if nums[ans[0]] + nums[ans[1]] == target:
                return ans
            return False
        
        for i in range(start, n):
            ans.append(i)
            if recur(ans, i+1):
                return ans
            ans.pop()

    return recur([], 0)

    
print(solution(nums = [4,9,7,5,1], target = 14))

재귀함수는 함수가 자기 자신을 호출하여 문제를 해결하는 방식으로 작성됩니다. 재귀함수를 작성하는 일반적인 패턴은 다음과 같습니다:

1. 기저 조건(Base case): 재귀호출을 멈출 조건을 정의합니다. 기저 조건이 없으면 함수가 무한히 호출될 수 있습니다.
2. 재귀 호출(Recursive call): 기저 조건이 충족되지 않을 때, 자기 자신을 호출하여 문제를 더 작은 부분으로 나눕니다.

아래에 몇 가지 예제를 통해 재귀함수를 작성하는 패턴을 설명하겠습니다.

1. 팩토리얼 함수¶

팩토리얼 함수는 n! = n * (n-1)!로 정의됩니다. 기저 조건은 n이 0이 될 때입니다.

def factorial(n):
    # 기저 조건: n이 0이 되면 1을 반환
    if n == 0:
        return 1
    # 재귀 호출: n * (n-1)의 팩토리얼
    else:
        return n * factorial(n - 1)

# 예시 실행
print(factorial(5))  # 출력: 120

2. 피보나치 수열¶

피보나치 수열은 F(n) = F(n-1) + F(n-2)로 정의됩니다. 기저 조건은 n이 0 또는 1이 될 때입니다.

def fibonacci(n):
    # 기저 조건: n이 0 또는 1이면 n을 반환
    if n == 0:
        return 0
    elif n == 1:
        return 1
    # 재귀 호출: F(n-1) + F(n-2)
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# 예시 실행
print(fibonacci(6))  # 출력: 8

3. 리스트의 합 계산¶

리스트의 모든 요소의 합을 재귀적으로 계산하는 함수입니다.

def sum_list(lst):
    # 기저 조건: 리스트가 비어 있으면 0을 반환
    if not lst:
        return 0
    # 재귀 호출: 첫 번째 요소 + 나머지 리스트의 합
    else:
        return lst[0] + sum_list(lst[1:])

# 예시 실행
print(sum_list([1, 2, 3, 4, 5]))  # 출력: 15

4. 이진 트리의 노드 개수 세기¶

이진 트리의 노드 개수를 재귀적으로 세는 함수입니다. 여기서 트리는 노드 객체로 표현됩니다.

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def count_nodes(root):
    # 기저 조건: 노드가 없으면 0을 반환
    if root is None:
        return 0
    # 재귀 호출: 1 + 왼쪽 서브트리의 노드 수 + 오른쪽 서브트리의 노드 수
    else:
        return 1 + count_nodes(root.left) + count_nodes(root.right)

# 예시 트리 생성
root = TreeNode(1, TreeNode(2), TreeNode(3, TreeNode(4), TreeNode(5)))

# 예시 실행
print(count_nodes(root))  # 출력: 5

재귀함수를 작성할 때 가장 중요한 부분은 기저 조건을 정확하게 설정하는 것입니다. 기저 조건이 없거나 잘못 설정되면 함수가 무한히 호출되어 프로그램이 중단될 수 있습니다. 따라서 문제를 충분히 작은 단위로 나누고, 더 이상 나눌 수 없는 기저 조건을 명확히 정의하는 것이 중요합니다.

기저 조건을 명확히 정의하는 것은 재귀함수를 작성할 때 매우 중요합니다. 기저 조건은 문제를 더 이상 작은 부분으로 나눌 수 없는, 즉 재귀 호출을 멈추고 직접 값을 반환해야 하는 상황을 나타냅니다. 기저 조건을 올바르게 정의하는 몇 가지 방법을 설명하겠습니다.

1. 문제의 가장 작은 단위를 식별¶

기저 조건은 문제를 더 이상 나눌 수 없는 가장 작은 단위를 식별하여 정의합니다. 예를 들어, 팩토리얼 함수에서는 n=0이 가장 작은 단위입니다.

def factorial(n):
    if n == 0:
        return 1  # 기저 조건: n이 0일 때
    else:
        return n * factorial(n - 1)

2. 종료 조건을 설정¶

재귀 호출이 끝나야 할 명확한 조건을 설정합니다. 이는 보통 재귀 호출 전에 문제의 크기나 상태를 검사하여 정의됩니다.

def fibonacci(n):
    if n == 0:
        return 0  # 기저 조건: n이 0일 때
    elif n == 1:
        return 1  # 기저 조건: n이 1일 때
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

3. 데이터 구조의 빈 상태를 확인¶

리스트, 트리, 그래프 등 데이터 구조를 사용할 때, 빈 상태를 기저 조건으로 사용합니다.

def sum_list(lst):
    if not lst:
        return 0  # 기저 조건: 리스트가 비었을 때
    else:
        return lst[0] + sum_list(lst[1:])

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def count_nodes(root):
    if root is None:
        return 0  # 기저 조건: 노드가 없을 때
    else:
        return 1 + count_nodes(root.left) + count_nodes(root.right)

4. 목표 상태를 확인¶

재귀 함수가 목표 상태에 도달했는지 확인합니다. 예를 들어, 경로 탐색 문제에서는 목표 지점에 도달했는지를 확인합니다.

def find_path(maze, start, end, path=[]):
    if start == end:
        return path + [end]  # 기저 조건: 목표 지점에 도달했을 때
    # 나머지 재귀 호출 로직 생략

5. 한계점 설정¶

재귀 호출이 너무 깊어지는 것을 방지하기 위해 한계점을 설정합니다. 이는 무한 재귀 호출을 방지하기 위한 안전장치로 사용됩니다.

def depth_limited_search(node, depth_limit):
    if depth_limit == 0:
        return None  # 기저 조건: 최대 깊이에 도달했을 때
    # 나머지 재귀 호출 로직 생략

기저 조건 설정의 일반적 절차¶

1. 문제를 충분히 이해하기: 문제를 해결하는 가장 작은 단위를 명확히 이해합니다.
2. 단순한 경우 식별: 더 이상 나눌 수 없는 가장 단순한 경우를 식별합니다.
3. 기저 조건 구현: 식별된 단순한 경우에 대한 처리를 함수의 기저 조건으로 구현합니다.
4. 테스트: 다양한 입력에 대해 기저 조건이 제대로 작동하는지 테스트합니다.

기저 조건을 명확히 정의하는 것은 문제를 재귀적으로 해결하는 데 있어서 핵심입니다. 이를 통해 함수가 적절한 시점에 재귀 호출을 멈추고 올바른 결과를 반환할 수 있습니다.

Combination¶

In [ ]:

import itertools
import numpy as np

In [ ]:

np.arange(4)

Out[ ]:

array([0, 1, 2, 3])

In [ ]:

def combine(n: int, k: int) -> list[list[int]]:
  return list(itertools.combinations(np.arange(1, n+1), k))
  
combine(4, 2)

Out[ ]:

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]

피로도 계산¶

올바른괄호¶

In [ ]:

def solution(s):
    if s[0] in [')', ']', '}']:
      return False
    
    stack = []
    for p in s:
      if p in ['(', '[', '{']:
        stack.append(p)
      else:
        if not stack:
          return False
        stack.pop()
    
    return not stack

In [ ]:

s_list = ["()()", "(())()", ")()(", "(()("]

for s in s_list:
  print(solution(s))

True
True
False
False

BFS¶

In [ ]:

from collections import deque
def bfs(graph, start_v):
  q = deque()
  # 시작점 예약
  q.append(start_v)
  # 방문 표시
  visited = {start_v: True}

  while q:
    print(q)
    print(visited)
    # 방문   
    cur_v = q.popleft()   
    print(cur_v)  
    # 다음 방문 예약
    for next_v in graph[cur_v]:
      if next_v not in visited:
        q.append(next_v)
        visited[next_v] = True
        
graph = {
    0: [1, 3, 6],
    1: [0, 3],
    2: [3],
    3: [0, 1, 2, 7],
    4: [5],
    5: [4, 6, 7],
    6: [0, 5],
    7: [3, 5],
}
bfs(graph, start_v=0)

deque([0])
{0: True}
0
deque([1, 3, 6])
{0: True, 1: True, 3: True, 6: True}
1
deque([3, 6])
{0: True, 1: True, 3: True, 6: True}
3
deque([6, 2, 7])
{0: True, 1: True, 3: True, 6: True, 2: True, 7: True}
6
deque([2, 7, 5])
{0: True, 1: True, 3: True, 6: True, 2: True, 7: True, 5: True}
2
deque([7, 5])
{0: True, 1: True, 3: True, 6: True, 2: True, 7: True, 5: True}
7
deque([5])
{0: True, 1: True, 3: True, 6: True, 2: True, 7: True, 5: True}
5
deque([4])
{0: True, 1: True, 3: True, 6: True, 2: True, 7: True, 5: True, 4: True}
4

DFS¶

In [ ]:

from collections import deque

graph = {
    0: [1, 3, 6],
    1: [0, 3],
    2: [3],
    3: [0, 1, 2, 7],
    4: [5],
    5: [4, 6, 7],
    6: [0, 5],
    7: [3, 5],
}
visited = {}

def dfs(cur_v):
  # 방문 표시
  visited[cur_v] = True
  print(visited)
  for next_v in graph[cur_v]:
    if next_v not in visited:
      # 다음 방문
      dfs(next_v)
      
dfs(cur_v=5)

{5: True}
{5: True, 4: True}
{5: True, 4: True, 6: True}
{5: True, 4: True, 6: True, 0: True}
{5: True, 4: True, 6: True, 0: True, 1: True}
{5: True, 4: True, 6: True, 0: True, 1: True, 3: True}
{5: True, 4: True, 6: True, 0: True, 1: True, 3: True, 2: True}
{5: True, 4: True, 6: True, 0: True, 1: True, 3: True, 2: True, 7: True}

keys and rooms¶

In [ ]:

# BFS
from collections import deque
class Solution:
    def bfs(self, graph, start_v):
        q = deque()
        
        visited = {}
        for num in range(len(graph)):
            visited[num] = False
        
        # 시작점 예약
        q.append(start_v)
        # 방문 표시
        visited[start_v] = True

        while q:
            # 방문   
            cur_v = q.popleft()    
            # 다음 방문 예약
            
            for next_v in graph[cur_v]:
                if not visited[next_v]:
                    q.append(next_v)
                    visited[next_v] = True
        
        return all(visited.values())

    def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
        return self.bfs(rooms, start_v=0)

In [ ]:

# DFS
from collections import deque
class Solution:
  def canVisitAllRooms(self, rooms: List[List[int]]) -> bool:
    def dfs(cur_v):
      # 방문 표시
      visited[cur_v] = True
      for next_v in rooms[cur_v]:
        if not visited[next_v]:
          # 다음 방문
          dfs(next_v)
  
    visited = {}
    for num in range(len(rooms)):
      visited[num] = False
    
    dfs(cur_v=0)
    
    return all(visited.values())