[내일배움캠프 5-3일] 동적 계획법, 유기농 배추 리뷰

동적 계획법

부분 문제의 반복 + 저장

 

• Memoization : 결과를 기록하는 것, 이미 실험한 내용을 기록하여 사용하는 것
• Overlapping Subproblem : 문제를 쪼갤 수 있는 구조, 각 구간마다의 시간을 계산하면 최적의 시간이 나옴.

즉 Overlapping Subproblem인 경우 동적 계획법을 사용.

이때 사용하는 방법은 Memoization을 이용함.

---

그냥 푼 피보나치 수열.

# 그냥 계산
def fibo(n):
    if n in [1, 2]:
        return 1
    return fibo(n-1) + fibo(n-2)

그냥 재귀적으로 푸는 방식.

100번째 피보나치 수열을 구한다면 연산이 엄청나게 많이 필요하다.

예를 들어 f(6)을 구한다면 f(5)연산과 f(4)연산이 필요함.

f(5)연산은 또 f(4)연산과 f(3)연산을 해야 함.
즉 f(n)에서 n의 값이 커질수록 반복되는 연산이 굉장히 많이 늘어난다는 것.

---

Dynamic Programming으로 푼 피보나치 수열

# DP
# n번째 녀석의 값이 뭔지 memo에 저장
memo = {1: 1, 2: 1}

def fibo(n):
    # 만약 n이 메모에 있다면 그 값을 그대로 반환
    if n in memo:
        return memo[n]
    # 없다면 메모에 새로 적음, 이후 그 값을 반환
    # 즉 연산을 함과 동시에 따로 기억하고, 이후 다시 사용한다는 것
    memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]

memo라는 딕셔너리를 따로 만들어서 저장.

f(n)을 구할 때 n이 메모에 있는지 확인하고, 없다면 메모에 저장하는 것.

연산을 함과 동시에 따로 저장하고 이후 이미 저장한 부분은 다시 사용한다는 것.

---

유기농 배추 리뷰

저번에 함수를 전부 이해하지 못해서 다시 풀어봄.

T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())

    # 0으로 채워진 grid를 우선 생성
    grid = [[0] * N for _ in range(M)]

    # 주어진 좌표를 1로 변경
    for _ in range(K):
        X, Y = map(int, input().split())
        grid[X][Y] = 1

우선 밭을 구성하는 부분을 조금 수정했다.

grid를 모두 0으로 초기화하는 과정에서 튜터님이 푼 방식을 보니 더 간결했다.

grid = [[0 for _ in range(N)] for _ in range(M)]  --->  grid = [[0] * N for _ in range(M)] 으로 변경

 

def count_worms(grid):
    # 상하좌우 방향을 나타내는 리스트
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    # 지렁이 수 초기화
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            # 현재 위치에 배추가 없으면, 즉 1이 아니면 continue
            if grid[row][col] != 1:
                continue

            # 1 만나면 우선 배추더미 만난 것이므로 +1
            cnt += 1
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                # 방문했다면 0으로 값을 변경, 다시 탐색하지 않도록
                grid[x][y] = 0
                # 상하좌우 새로운 x와 y값을 만들어 탐색
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    # 해당 칸을 상하좌우로 탐색할 때 grid밖으로 넘어가거나 값이 1이 아닌 경우 continue
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != 1:
                        continue
                    stack.append((nx, ny))
    return cnt

우선 상하좌우를 탐색하기 위해 dx, dy리스트를 정의해 놓음.

이후 그리드를 하나씩 돌면서 현재 값이 1이 아니면 넘어가고 1을 만나면 cnt를 증가시킨 후 stack에 현재 위치를 추가함.

여기서부터 상하좌우를 탐색한다.

우선 다시 방문하는 것을 방지하기 위해 0으로 값을 변경.

nx, ny라는 새로운 좌표를 저장하는데, 이는 x, y에 아까 만든 상하좌우 리스트를 돌며 더해 만들어준다.

이때 제한을 걸어주는데 grid범위 밖으로 나가거나, 1이 아닌 경우 continue.

stack에 새로 탐색한 nx, ny를 추가.

최종적으로 모든 좌표를 탐색하고 cnt를 반환한다.

 

def count_worms(grid):
    # 상하좌우 방향을 나타내는 리스트
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    rows, cols = len(grid), len(grid[0])
    # 지렁이 수 초기화
    cnt = 0

    for row in range(rows):
        for col in range(cols):
            # 현재 위치에 배추가 없으면, 즉 1이 아니면 continue
            if grid[row][col] != 1:
                continue

            # 1 만나면 우선 배추더미 만난 것이므로 +1
            cnt += 1
            stack = [(row, col)]

            while stack:
                x, y = stack.pop()
                # 방문했다면 0으로 값을 변경, 다시 탐색하지 않도록
                grid[x][y] = 0
                # 상하좌우 새로운 x와 y값을 만들어 탐색
                for i in range(4):
                    nx = x + dx[i]
                    ny = y + dy[i]
                    # 해당 칸을 상하좌우로 탐색할 때 grid밖으로 넘어가거나 값이 1이 아닌 경우 continue
                    if nx < 0 or nx >= rows or ny < 0 or ny >= cols or grid[nx][ny] != 1:
                        continue
                    stack.append((nx, ny))
    return cnt


T = int(input())
for _ in range(T):
    M, N, K = map(int, input().split())

    # 0으로 채워진 grid를 우선 생성
    grid = [[0] * N for _ in range(M)]

    # 주어진 좌표를 1로 변경
    for _ in range(K):
        X, Y = map(int, input().split())
        grid[X][Y] = 1

    print(count_worms(grid))

최종 코드

좌표값을 정하는 부분, 즉 X, Y와 rows, cols 부분이 헷갈리는데 이를 주의해야 할 듯.

---

오늘의 회고

오늘 집중을 잘 못하고 중간에 휴식을 조금 했다.

그래도 강의는 결국 완강함.(3주차 부분은 꼼꼼하게 학습하지는 못했다)

문제를 많이 풀지 못해 아쉽다.

 

내일 목표는 cs 발제 듣고 계획 잘 세워보기