[정글 WEEK01_알고리즘] 개발 일지 - 1주차 마무리

 

공부 키워드

 - 배열, 문자열

 - 반복문과 재귀함수

 - 복잡도

 - 정렬

 - 완전 탐색

 - 정수론

 

 

배상원 교수님의 알고리즘 설계 기법 특강 - 0321

 '재귀' 함수 설계를 위한 특강이었다. 핵심적인 내용은 재귀도 결국 함수 호출이라는 거. 다만 내가 짠 함수를 호출하는 것이고, 내가 짠 함수의 역할과 인풋, 아웃풋이 확실하지 않으니 이 함수를 호출해도 프로그램이 정상 동작할 것이라는 믿음이 없는 것이다.

 

 함수를 호출할 때는 '블랙박스'처럼 내부 동작을 알 필요가 없다. 어떻게 구현할 것인지는 부차적인 문제이고 무엇을 구현할지에 대한 정의가 확실히 되어있어야 한다. 

 

 주어진 문제의 단위가 충분히 작아서 바로 풀 수 있으면 풀고, 그렇지 않으면 더 작은 문제로 쪼갠다. 문제를 쪼개 단순화하고, 정상 동작하게 만들었다면 호출해보자..! 함수의 역할, 인풋, 아웃풋을 확실히 했다면 그 다음은 재귀 요정🧚에게 맡기고 잊어버리는 게 정신 건강에 좋다는 말씀을 쉽게 못 잊을 것 같다.

 

 

깊이 있는 문제 풀이

예전같으면 풀린 문제는 그냥 넘어갔을텐데 좀 더 깊이 생각해볼 시간이 주어지니 여러 방식으로 풀게 된다. 약 63문제가 주어졌는데 그 중 가장 기억나는 몇몇 문제들을 뽑아서 정리했다. 

 

분할 정복

1) 백준 2530_색종이 만들기 → 2) 백준 1992_쿼드트리 → 3) 백준 1629_곱셉

 분할정복 키워드에 대한 단계별 풀이를 해봤다. 풀이 자체는 괜찮았는데 쿼드트리 문제가 이해가 안 돼서 문제를 풀기 전 한참 생각했다. 예제인 (0(0011)(0(0111)01)1) 을 보고 재귀의 형태를 ((LU(RU)(LD)RD)) 라고 잘못 생각했었고 (LU RU LD RD)라는 것을 깨닫고는 문제를 풀 수 있었다. 역시 문제를 풀 때는 문제를 정의하는 것부터 시작이다.

 

# 2530_색종이 만들기

N = int(input())
matrix = []
for _ in range(N):
    matrix.append(list(map(int, input().split())))

color_count = {0: 0,
               1: 0}

def dfs(x, y, length):
    global color_count
    color = matrix[x][y]

    if length < 1:
        return
    
    is_indivisible = True

    for i in range(x, x + length):
        for j in range(y, y + length):
            if matrix[i][j] != color:
                is_indivisible = False
                break

    if is_indivisible:
        color_count[color] += 1
    else:
        half = length // 2
        dfs(x, y, half)
        dfs(x + half, y, half)
        dfs(x, y + half, half)
        dfs(x + half, y + half, half)
    
dfs(0, 0, N)

print(color_count[0])
print(color_count[1])

# 1992_쿼드트리

N = int(input())
matrix = [list(input()) for _ in range(N)]

def dfs(x: int, y: int, length: int) -> int:
    first_color = matrix[x][y]
    if length == 1:
        return first_color
    
    is_all_same = True
    for i in range(x, x + length):
        for j in range(y, y + length):
            if matrix[i][j] != first_color:
                is_all_same = False
                break
        if not is_all_same:
            break

    if is_all_same:
        return first_color
    else:
        half_length = length // 2
        LU = dfs(x, y, half_length)
        RU = dfs(x, y + half_length, half_length)
        LD = dfs(x + half_length, y, half_length)
        RD = dfs(x + half_length, y + half_length, half_length)
        return f"({LU}{RU}{LD}{RD})"

print(dfs(0, 0, N))

# 1629_곱셉

A, B, C = map(int, input().split())

def power(a, b, c):
    if b == 0:
        return 1
    elif b == 1:
        return a % c
    elif b % 2 == 0:
        return ((power(a, b // 2, c)**2) % c)
    else:
        return ((power(a, b // 2, c)**2) * a % c)
    
print(power(A, B, C))

 

스택

1) 백준 2493_탑

완전탐색 풀이를 하면 테스트케이스는 통과하는데 시간초과가 발생한다. 스택의 특성을 사용한 풀이는 전혀 생각나지 않아서 챗지피티의 도움을 받았고, 이해하는데 한참 걸렸지만 스택의 LIFO 구조를 활용하는 방법을 알게 되었다. 

# 완전 탐색 풀이

def find_nearest_tallest_tower(idx: int) -> int:
    height = towers[idx]
    for j in range(idx - 1, -1, -1):
        if towers[j] > height:
            return j + 1 
    return 0

N = int(input())
towers = list(map(int, input().split()))

for idx, tower in enumerate(towers):
    print(find_nearest_tallest_tower(idx), end=" ")

# 스택 풀이

N = int(input())
towers = list(map(int, input().split()))
answer = [0] * N
stack = [] # LIFO 이므로 나중에 들어간 탑을 먼저 확인할 수 있다.

for i in range(N):
    while stack and towers[i] > towers[stack[-1]]: # 현재 탑보다 큰 탑만 남긴다.
        stack.pop()
    
    if stack: # 현재 탑보다 큰 탑이 있다면 그것이 정답!(1부터 시작하는 인덱스이므로 + 1)
        answer[i] = stack[-1] + 1 
    
    stack.append(i) # 현재 탑의 인덱스 넣기
   
print(*answer)

 

재귀

1) factoial 

 팩토리얼 풀이를 반복문과 비교해봤다. 마지막은 '꼬리 재귀' 방식으로, 이론적으로는 스택 프레임을 재사용해서 재귀를 쓰면서도 메모리를 최적화할 수 있다는데 파이썬은 TCO(Tail Call Optimization)를 지원하지 않아서 재귀로 함수를 호출할 때마다 스택 프레임을 새로 쌓는다.

 파이썬은 "명확성이 속도보다 우선이다(Readability counts)"라는 철학에 따라 TCO를 암묵적 최적화로 간주하고 있으며, 더 직관적이고 명확하다고 판단한 반복문의 사용을 권장하고 있다. 따라서 파이썬에서는 반복이 가능한 재귀는 반복문으로 쓰는 것이 좋다고 한다. 

def interactive_factorial(n):
  acc = 1
  while n > 1:
    acc *= n
    n -= 1
  return acc

def recursive_factorial(n):
  if n == 1:
    return 1
  return (n) * recursive_factorial(n-1)

def tail_recursive_factorial(n, acc=1):
  if n == 1:
    return acc
  return tail_recursive_factorial(n-1, acc*n)

 

2) 백준 1914_하노이

 배상원 교수님도 설명해주신 하노이 문제. 위에 있는 n-1개의 원판을 현재 말뚝에서 중간 말뚝으로 옮기고, 맨 아래 가장 큰 원판을 목적지 말뚝으로 옮긴 후 다시 n-1개의 원판을 중간 말뚝에서 목적지 말뚝으로 옮기는 과정의 연속이다.

import sys

def hanoi(n, from_pole, to_pole, aux_pole):
    if n == 1:
        print(from_pole, to_pole)
        return
    hanoi(n-1, from_pole, aux_pole, to_pole)
    print(from_pole, to_pole)
    hanoi(n-1, aux_pole, to_pole, from_pole)

n = int(sys.stdin.readline().strip())
print(2**n - 1) # 전체 실행 횟수를 구하는 점화식
if n <= 20:
    hanoi(n, 1, 3, 2)