Baekjoon 1520번 내리막길, 2629 양팔저울 - Python 문제 풀이

1520번 내리막길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

문제 설명

일단 이거 내가 못푼다. 구글의 도움을 받아서 해결해보자..

DFS, DP라는 용어가 반복되어서 보인다.

DFS

: Depth first search의 약자로서 그래프 자료에서 데이터를 탐색하는 알고리즘이다.

위에서 아래로 찾는 방식이고 스택 자료구조를 이용한다.

 

동작 구조는 아래와 같다.

 

위 사진 에서 노드들을 찾아가는 순서는 이와 같다. 

A가 갈 수 있는건 B와 C인데 기본적으로 작은 순서로 진행되기에 A->B가 된 것이다.

스택에는 순서대로 쌓인다. (당연)

여기까지는 수월하다.

그러나 E는 방문하지 않은 노드가 존재하지 않는다.

그래서 스택에서 E를 반환하고 스택의 최상단인 D에게 방문하지 않은 노드인 F로 가겠다는 말이다.

이렇게 F가 스택에 쌓이고 다음 노드를 찾지만 F또한 연결되어 있는 노드 중 방문하지 않은 노드가 없다.

F도 반환해 보지만 D도 방문하지 않은 노드가 없다. 그래서 D도 반환한다.

B도 같은 상황이라 B까지 반환하고 스택의 최상단은 A가 된다.

A는 연결된 노드 중 아직 방문하지 않은 C노드가 있기에 C노드로 가준다.

 

C에서 연결된 노드는 3개가 있고 이 중 가장 작은 G노드로 간다.

G또한 연결된 노드중 방문하지 않은 노드가 없으니 이후에는 위와 같은 방법으로 G 반환 후 최상위 스택인 C에서 방문하지 않은 노드 중 작은 값인 H로 가고 이 또한 연결된 노드 중 방문하지 않은 노드가 없으니 H도 반환된다.

C에서 연결된 노드 중 방문하지 않은 노드인 I로 이동후 I 에서 J로 방문하고 끝이난다.

 

이러한 과정이 DFS 알고리즘의 흐름이다.

DP

Dynamic Programming의 약자. 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

- 큰 문제를 작은 문제로 쪼개서 저장해두고 재활용한다.

- 중복계산을 피할 수 있음. (효율 굿.)

 

예를 들어보면 피보나치 수열을 들 수 있다.

f(n)=f(n-1)+f(n-2) 이라는 함수를 만들고 진행한다고 하면 함수를 1번 호출 할 때 같은 값을 2번씩 구하게 된다.

n의 값이 증가할 수록 호출되는 함수의 횟수는 매우 크게 증가하게 된다. 

이러한 상황이 생기지 않게 하기 위해 다이나믹 프로그래밍을 하면 연산된 결과를 배열에 담아 한번 계산한 연산을 반복하지 않게끔 할 수 있다.

 

다이나믹 프로그래밍에는 2가지 방법이 있다.

1. 탑다운

- 한번 계산한 결과를 메모리 공간에 저장. (메모제이션)

- 재귀함수 사용.

 

2. 보텀업

- 작은 문제 + 작은 문제 = 큰 문제 형식.

- 반복문 이용.

 

이제 구글의 도움을 받은 코드를 살펴보자..!

import sys
# 재귀 제한을 설정하는 아래 명령어를 사용하기 위해 선언. (입력제한)
sys.setrecursionlimit(10**6)
# 재귀 호출의 최대 깊이를 설정. 10의 6제곱으로 설정해둠.
n,m = map(int,input().split())
# 공백 기준 여러값 한번에 받기. 이 내용은 다른 알고리즘 풀이에 상세히 설명되어있음.
arr = [list(map(int,input().split())) for _ in range(n)]
# 이중리스트 Comprehension. 리스트를 초기화할 때 사용되는 기법
#[[표현식 for 요소 in 시퀀스] for 요소 in 시퀀스] 이 형태를 띠고 있음.
dp = [[-1]*m for _ in range(n)]
#2차원 배열 dp를 만들어서, 모든 요소를 -1로 초기화. 메모이제이션. 방문한 적 없는 곳은 -1로 표시됨.
dxs = [1,-1,0,0]
dys = [0,0,1,-1]
#이동방향 리스트. dxs는 행, dys는 열 이동을 나타냄.

def dfs(x,y):
    # 도착지점에 도달하면 1을 반환
    if x == n-1 and y == m-1:
        return 1

    # 이전에 도착했던 곳이라면 dp[x][y] 값 반환
    if dp[x][y] != -1:
        return dp[x][y]
    
    # 처음 온 곳이라면 0으로 초기화
    dp[x][y] = 0

    for dx,dy in zip(dxs,dys):
        nx, ny = x+dx, y+dy
        if 0<=nx<n and 0<=ny<m and arr[nx][ny] < arr[x][y]: 
        #그래프 범위 안에 있고, 다음 위치의 값이 현재 위치의 값보다 작은 경우에만 이동.
            dp[x][y] += dfs(nx,ny)

    return dp[x][y]
    

print(dfs(0,0))

 코드 설명은 주석으로 달아두었다. 

 

예제의 출력값를 잘 충족한다.

 

구글에 검색하는것보다 스스로 해결할 수 있을 때 다시 도전해보겠다. 다이나믹 프로그래밍과 DFS의 기초문제를 더 풀어봐야겠다.

---

2629 양팔저울

https://www.acmicpc.net/problem/2629

2629번: 양팔저울

문제 설명

 

- 추의 개수는 30이하. n개의 추의 무게(500 이하 자연수)가 오름차순으로 주어짐.

- 구슬의 개수는 7이하. m개의 구슬의 무게(40000 이하 자연수)가 오름차순으로 주어짐.

 

이것또한 구글의 도움을 받았다. 그런데 다이나믹이 아니여도 풀이할 수 있더라..신기했다.

n,chu_lst = int(input()),list(map(int,input().split()))
m,check_chu_lst = int(input()),list(map(int,input().split()))
#split()함수는 여러 인자를 받을 때 띄어쓰기나 특수기호로 값을 구분해서 받아준다.
#그렇다면 int(input().split())하면 될 것 같지만 아니다. 
#int형은 리스트(list)를 정수형으로 변환시켜주지 못하기 때문에 오류가 날 것이다. 
#고로 map(함수, 자료형)이라는 정수 변환함수를 사용하여 map(int, input().split)으로 작성한다.

dp = [ 0 ]
for chu in chu_lst:
    tmp=[]
    for i in dp:
        tmp.append(i+chu)
        tmp.append(abs(i-chu))
    dp = list(set((dp + tmp)))
    #각 추의 무게를 하나씩 순회하면서 가능한 모든 조합을 계산.
    #tmp 리스트에는 현재까지의 조합(dp)에 현재 추를 더한 값과 현재 추를 뺀 값의 절댓값을 추가.
    #이후 dp와 tmp를 합쳐서 중복을 제거하고 다시 dp에 할당.

for chu in check_chu_lst:
    print('Y' if chu in dp else 'N',end=' ')
    #확인할 추의 무게를 하나씩 순회하며 해당 무게가 dp 리스트에 있는지 확인.
    #만약 해당 무게가 dp 리스트에 있다면 'Y'를 출력하고, 없다면 'N'을 출력.

추를 한개씩 추가해주면서 구할수 있는 무게를 담은 리스트를 만들어서 진행된 코드다.

코드에 대한 설명은 주석으로 달아두었다.

예제1 결과

예제2 결과

예제의 출력값을 잘 충족한다.

 

이것 또한 내가 스스로 코드를 작성할 수 있는 그 날까지 열심히 공부해야겠다.