한동안 알고리즘 문제 풀이에 신경을 쓰지 못하여 부족한 DP에 대한 감을 잡으려고 고른 문제다.

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

DP 문제는 구현 자체가 어렵진 않지만 문제 해결법에 접근하는 과정이 다소 어려운 것 같다.

다른 알고리즘 같은 경우는 연습을 통해 익숙해진다면 DP는 아무리 연습해도 문제에 따라 쉽게 떠오르지 않는 알고리즘 같다.

문제 풀이

해당 문제의 소재는 다소 익숙한 원하는 금액을 지불하는 동전의 최소 개수다.

동전의 개수는 n개이고 가치의 합은 k이며 각각 1 <=n <=100, 1 <=k <=10000의 제한 조건을 갖는다.

같은 동전이 여러 번 주어질 수 있지만 가치의 합인 k를 dp 리스트로 잡고 각 인덱스마다 n번 반복하면 되므로 시간 복잡도는 O(n*k), 즉 최대 100만 번이라 딱히 고려하진 않아도 되는 조건이었다.

물론 필자는 효율성을 높이기 위해 Set로 형 변환했다가 다시 List로 형 변환했었다.

이렇게 Set로 형 변환하면 중복된 원소를 제거할 수 있다.

다만 이 문제에서 중요하게 고려해야 할 점은 가치의 합인 k로 만드는 것이 불가능할 수도 있단 점이다.

여태 경험했었던 동전 DP 문제는 애초에 불가능에 대한 조건은 없었기에 최소 개수만 구하는데 집중했었고 이번 문제도 처음에 똑같이 시도했다가 틀렸단 메시지를 받았다.

그 과정에서 문제를 다시 정확히 읽고 스스로 테스트 케이스를 만들어 오류를 잡아내는 연습도 필요한 것 같다.

각설하고 전체 코드를 통해 설명하도록 하겠다.

n,k=map(int,input().split())
coin=[]
for i in range(n):
    coin.append(int(input()))

coin=list(set(coin))
dp=[0 for i in range(k+1)]
for i in range(1,len(dp)):
    for j in range(len(coin)):
        if i-coin[j]==0:
            dp[i]=dp[i-coin[j]]+1
        elif i-coin[j]>0 and dp[i-coin[j]]!=0:
            if dp[i]==0:
                dp[i]=dp[i-coin[j]]+1
            elif dp[i-coin[j]]+1<dp[i]:
                dp[i]=dp[i-coin[j]]+1

if dp[k]==0:
    print(-1)
else:
    print(dp[k])

1번째 줄은 n과 k를 입력받고 2번째 줄의 coin은 동전의 가치를 입력받을 리스트다.

6번째 줄이 중복을 제거하는 코드이며 7번째 줄의 dp는 k인 가치의 합을 인덱스로 갖는 dp 리스트다.

어떤 것을 dp 리스트로 잡을지는 문제를 많이 풀다 보면 감 잡게 될 것이다.

이제 8번째 줄부터 이중 for문을 통해 전체 dp 리스트를 돌며 각 인덱스마다 coin 리스트를 반복해 해당 인덱스가 해당하는 값에서 동전을 쓸 수 있는지 확인하고 쓸 수 있다면 최소 개수인지 확인한다.

10번째 줄의 if 문은 동전의 가치를 현재의 가치에서 뺏을 때 0원이라면 동전을 한 개 사용할 수 있단 뜻이므로 현재 가치의 동전 개수를 업데이트했다.

12번째 줄의 if 문에 주목해야 하는데 현재 가치에서 동전의 가치를 뺀 값이 0보다 크고 그 뺀 값의 동전 개수가 0개보다 많을 때만 개수를 업데이트해줬다.

왜냐하면 만약 현재의 가치에서 동전의 가치를 뺀 가치에 대한 동전의 개수가 0개 라면 해당 가치로 동전을 조합할 수 없기 때문이다.

예를 들어 k가 10이고 n이 1이며 동전의 가치가 3일 때를 고려해 보자.

dp[10]인 상황에서 동전의 가치를 뺀 dp[7]을 생각해보면 dp[7]은 0이다.

3으로는 절대로 7을 만들 수 없기 때문이다.

따라서 7원으론 동전을 조합할 수 없기 때문에 10도 불가능하다는 얘기가 된다.

이 부분만 고려한다면 골드 문제를 도전하는 사람들에게 나머진 딱히 어려운 부분이 없을 것이라 생각한다.

이 문제를 통해 지문을 잘 읽고 테스트 케이스를 만들어보는 과정을 직접 해보는 것이 중요하다는 것을 체감했다.

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

문제 풀이

왼쪽 위칸인 [0,0]에서 출발 후 오른쪽 아래칸인 [N-1, N-1]에 도착하는 경로를 생각하는 그래프 탐색 문제였다.

다만 흔히 Queue나 Stack을 이용하여 BFS, DFS로 탐색하는 방법이 아닌 Priority Queue를 사용한 다익스트라 문제였다.

이 문제에서 중요한 점은 거리의 최소가 아니라 비용, 즉 가중치의 최소가 중요하기 때문이다.

상당히 돌아가는 경로라 하더라도 비용이 최소면 해당 경로를 택하기 때문에 가중치의 합을 기준으로 최소 비용 경로를 고려해야 한다.

Priority Queue를 이용한 원리는 다음과 같다.

먼저 시작 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는다.

가중치의 합이 가장 작은 노드를 선택한 뒤 해당 노드에서 이동 가능한 노드를 가중치의 합과 함께 Priority Queue에 넣는 행동을 [N-1, N-1]에 도착할 때까지 반복한다.

[N-1, N-1]에 도착하면 해당 가중치를 저장하고 반복을 종료한다.

한 번은 중간에 이동 가능한 노드인지 체크하는 과정에서 이미 방문한 노드가 최소 가중치의 합을 보장하는지 의문을 품는 질문을 본 적이 있었는데 결론부터 말하자면 각 노드에서 가장 먼저 선택되었을 때의 가중치가 최소다.

Priority Queue를 통해 매번 가장 작은 가중치의 합을 선택하기 때문에 두 번째 방문할 때는 같거나 클 수밖에 없기 때문이다.

이제 전체 코드를 통해 설명하도록 하겠다.

import heapq
inf = float('INF')
dir = [[1, 0], [-1, 0], [0, 1], [0, -1]]
res_num = 1
while True:
    n = int(input())
    if n == 0:
        break
    else:
        graph = []
        queue = []
        res = [[inf for i in range(n)]for j in range(n)]
        for i in range(n):
            graph.append(list(map(int, input().split())))
        heapq.heappush(queue, (graph[0][0], 0, 0))
        res[0][0] = graph[0][0]
        while len(queue) > 0:
            temp = heapq.heappop(queue)
            if temp[1] == n-1 and temp[2] == n-1:
                break

            for i in range(len(dir)):
                dy = temp[1]+dir[i][0]
                dx = temp[2]+dir[i][1]
                if 0 <= dy < n and 0 <= dx < n and res[dy][dx] > temp[0]+graph[dy][dx]:
                    res[dy][dx] = temp[0]+graph[dy][dx]
                    heapq.heappush(queue, (temp[0]+graph[dy][dx], dy, dx))
        print("Problem %d: %d" %(res_num,res[n-1][n-1]))
        res_num += 1

4번째 줄까지는 Priority Queue를 사용하기 위한 heapq 선언, 방문하지 않은 노드는 무한대 선언, 노드의 방향 선언, 문제 번호 선언이다.

5번째 줄의 while문을 통해 0을 입력받을 때까지 반복적으로 문제를 처리했다.

12번째 줄의 res는 노드의 최솟값을 갱신하는 리스트로 마지막에 res [N-1][N-1]을 출력하면 된다.

15번째 줄은 시작 노드의 가중치와 y좌표, x좌표 순서대로 넣음으로써 자동으로 MinHeap 구조인 heapq에서 최소 가중치를 꺼내도록 하였다.

18번째 줄의 반복문은 Priority Queue가 빌 때까지 계속 원소를 꺼내는 작업을 하는데 도착지점에 도달한다면 탈출하도록 구현하였다.

방향 탐색을 하기 위해 22번째 줄에서 이동 가능한 노드인지 체크한 후 Priority Queue에 넣어주도록 구현하였다.

구현 방법이나 알고리즘 측면에서 어려운 문제는 아니었지만 우선순위 큐를 거의 사용해보지 않았다면 충분히 떠올리기 어려울 수 있다고 생각한다.

필자 또한 다양한 그래프 문제를 경험해봤지만 습관처럼 BFS, DFS를 사용했기에 해당 문제를 보고 바로 Priority Queue를 떠올리진 못했다.

보다 유연하고 다양하게 생각하도록 노력하는 게 중요한 것 같다.

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

문제 풀이

단순하게 주어진 기능들을 조건에 맞게 구현만 하면 되는 문제다.

각 기능들을 하나씩 보면 브론즈~실버 수준의 기능 구현이고 딱히 시간 복잡도나 공간 복잡도에 대해 고민할 필요가 없지만 아무래도 10개의 기능을 각 조건에 맞게 정확히 구현하는 부분에서 티어가 높게 측정되고 약 14%의 낮은 정답률을 보이는 것 같다.

실제로 필자도 주석을 통해 미리 구현 내용을 순서대로 적어두고 차근차근 구현하는 습관을 안 들이다 보니 다소 많은 양 때문에 헷갈리는 부분이 있어서 NameError, IndexError, UnboundLocalError 등의 런타임 에러가 났었다. 

이를 계기로 양이 많은 문제를 접하면 미리 주석을 사용해야겠다는 다짐을 하였다.

구현하는 과정에서는 딱히 어려운 부분이 없기에 전체 코드를 하나씩 따라가보며 설명하도록 하겠다.

def NUM_X(array,num):
    return array.append(num)

def POP(array):
    if len(array)==0:
        return "ERROR"
    else:
        array.pop()
        return 1

def INV(array):
    if len(array)==0:
        return "ERROR"
    else:
        temp=array.pop()
        array.append(temp*(-1))
        return 1

def DUP(array):
    if len(array)==0:
        return "ERROR"
    else:
        temp=array.pop()
        array.append(temp)
        array.append(temp)
        return 1

def SWP(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        array.append(temp1)
        array.append(temp2)
        return 1

def ADD(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp1+temp2)>10**9:
            return "ERROR"
        else:
            return array.append(temp1+temp2)

def SUB(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp2-temp1)>10**9:
            return "ERROR"
        else:
            return array.append(temp2-temp1)

def MUL(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        if abs(temp2*temp1)>10**9:
            return "ERROR"
        else:
            return array.append(temp2*temp1)

def DIV(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        op=1
        if temp1==0:
            return "ERROR"
        else:
            if temp1<0:
                temp1=temp1*(-1)
                op=op*(-1)
            if temp2<0:
                op=op*(-1)
                temp2=temp2*(-1)
            return array.append((temp2//temp1)*op)

def MOD(array):
    if len(array)<2:
        return "ERROR"
    else:
        temp1=array.pop()
        temp2=array.pop()
        op=1
        if temp1==0:
            return "ERROR"
        else:
            if temp2<0:
                op=op*(-1)
                temp2=temp2*(-1)
            return array.append((temp2%abs(temp1))*op)

command="START"
command_array=[]
while command!="QUIT":
    command=input()
    if command=="QUIT":
        pass
    elif command=="END":
        n=int(input())
        for i in range(n):
            res="START"
            stack=[int(input())]
            for j in range(len(command_array)):
                if len(command_array[j].split())==2:
                    temp=command_array[j].split()
                    res=NUM_X(stack,int(temp[1]))
                elif command_array[j]=="POP":
                    res=POP(stack)
                elif command_array[j]=="INV":
                    res=INV(stack)
                elif command_array[j]=="DUP":
                    res=DUP(stack)
                elif command_array[j]=="SWP":
                    res=SWP(stack)
                elif command_array[j]=="ADD":
                    res=ADD(stack)
                elif command_array[j]=="SUB":
                    res=SUB(stack)
                elif command_array[j]=="MUL":
                    res=MUL(stack)
                elif command_array[j]=="DIV":
                    res=DIV(stack)
                else:
                    res=MOD(stack)
                if res=="ERROR":
                    break
            if res=="ERROR" or len(stack)!=1:
                print("ERROR")
            else:
                print(stack[0])
        input()
        print()
        command=="START"
        command_array.clear()
    else:
        command_array.append(command)

딱 봐도 여태 포스팅한 코드들과는 확연히 양에서 차이가 난다.

비록 양은 많지만 어려운 부분은 없기에 미리 겁먹을 필요는 없다.

먼저 전체적인 구성은 각 기능에 해당하는 10개의 함수를 선언하고 메인 함수에서는 입력방식대로 입력을 받은 후 필요한 경우 해당하는 함수를 호출해서 연산 결과를 사용하는 방식으로 구현하였다.

1번째 줄의 NUM_X는 인자로 받은 숫자를 스택의 가장 위에 저장(Push)하는 함수다.

3번째 줄의 POP은 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 가장 위에 있는 숫자를 제거하는 함수다.

11번째 줄의 INV는 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 첫번째 수(가장 위에 있는 수)의 부호를 바꿔서 저장하는 함수다. (이제 보니 굳이 pop 하지 않고 array [len(array)-1]=-1*array [len(array)-1] 이렇게 직접 접근해서 한 줄로 처리 가능할 것 같다.)

19번째 줄의 DUP는 스택에 아무것도 없다면 ERROR를 반환하고, 있다면 가장 위에 있는 숫자를 한번 더 추가하는 함수다.

28번째 줄의 SWP는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자의 위치를 바꾸는 함수다.

38번째 줄의 ADD는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자를 더한다.

이때 문제 조건에서 연산 결과의 절댓값이 10^9를 넘어간다면 프로그램 에러이므로 꼭 이 부분을 처리해줘야 한다.

49번째 줄의 SUB는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자에서 첫 번째 숫자를 빼면서 이때도 마찬가지로 절댓값이 10^9를 넘어가는지 체크해야한다.

60번째 줄의 MUL은 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 첫 번째 숫자와 두 번째 숫자를 곱하고 값을 체크한다.

71번째 줄의 DIV는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자를 첫 번째 숫자로 나눈 몫을 저장하는데 이때 0으로 나눠지는지, 부호는 어떻게 되는지 정확히 판단해서 구현해야 한다.

89번째 줄의 MOD는 스택에 2개 이상의 데이터가 없다면 ERROR를 반환하고, 있다면 두 번째 숫자를 첫 번째 숫자로 나눈 나머지를 반환하는데 이때도 마찬가지로 부호와 0으로 나눠질 경우를 예외 처리해야 한다.

106번째 줄부터는 QUIT를 입력받기 전까지 반복하면서 명령어에 해당하는 함수를 실행시키면 된다.

이때 END를 입력받기 전까지 일련의 명령어를 입력받고 수행해야 하므로 명령어를 리스트에 저장해서 수행하는 것을 잊으면 안 된다.

다소 구현해야 하는 기능이 많고 예외처리를 해야 되는 부분도 많아서 각각의 구현 난이도는 쉽지만 어렵게 느껴질 수 있는 문제였다.

주석처리를 통해 차례대로 구현해야 하는 기능을 정리하는 습관을 들여야겠다.

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

문제 풀이

어렸을 때 많이 했던 뿌요뿌요(PuyoPuyo) 게임의 연쇄작용을 구현하는 문제이다.

테트리스와 비슷하지만 뿌요뿌요는 같은 색의 슬라임들이 4개 이상 연결되어있으면 터지고 빈 공간을 채운다는 점이 조금 다르다.

따라서 만약 테트리스였다면 행을 기준으로 탐색을 했겠지만 뿌요뿌요는 전체 탐색을 하면서 빈 공간이 아닐 때는 4개 이상 연결되었는지 BFS를 통해 체크하며 4개 이상인 모든 부분들을 빈 공간으로 치환하고 다시 바닥으로 정렬하는 과정을 반복해야 한다.

이때 터질 수 있는 뿌요가 여러 그룹이 있다면 동시에 터지고 한 번의 연쇄가 추가된다고 하니 연쇄를 추가하는 부분을 정렬하는 과정에 위치시키면 적절할 것이다.

사실 12X6 크기의 행렬이라 상당히 크기가 작아 시간이나 공간에 대한 효율성을 따질 필요성까진 없지만 구현하는 과정에서 다소 헷갈리거나 복잡한 부분이 있었기에 문제를 세분화하여 주석을 통해 구현해야 할 기능들을 구분해놓고 구현하는 것이 도움 될 것 같다.

코드가 짧은 편은 아니라서 한눈에 들어오긴 힘들겠지만 한 줄씩 따라가다 보면 이해할 수 있을 것이다.

graph=[]
dir=[[-1,0],[1,0],[0,-1],[0,1]]
queue=[]
for i in range(12):
    graph.append(list(input()))
res=0

while True:
    check=True    #터졌는지 체크하는 변수
    visited=[[0 for i in range(6)]for j in range(12)]
    changed_col=[]
    del_queue=[]
    for i in range(12):
        for j in range(6):
            #뿌요가 존재하는 칸인 경우
            if graph[i][j]!="." and visited[i][j]==0:
                curr_char=graph[i][j]    #현재 뿌요 저장
                temp_cnt=0
                queue.append([i,j])
                visited[i][j]=1
                
                #현재뿌요와 연결되어있는 뿌요 탐색
                while len(queue)>0:
                    curr=queue.pop(0)
                    temp_cnt+=1
                    for k in range(len(dir)):
                        dy=dir[k][0]+curr[0]
                        dx=dir[k][1]+curr[1]
                        if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char and visited[dy][dx]==0:
                            queue.append([dy,dx])
                            visited[dy][dx]=1

                #연결된 뿌요가 4개 이상일 경우
                if temp_cnt>=4:
                    check=False
                    changed_col.append(j)
                    del_queue.append([i,j])
                    while len(del_queue)>0:
                        temp=del_queue.pop(0)
                        graph[i][j]="."
                        for k in range(len(dir)):
                            dy=dir[k][0]+temp[0]
                            dx=dir[k][1]+temp[1]
                            if 0<=dy<12 and 0<=dx<6 and graph[dy][dx]==curr_char:
                                del_queue.append([dy,dx])
                                graph[dy][dx]="."
                                if dx not in changed_col:
                                    changed_col.append(dx)

    if check:
        break
    else:
        res+=1
        #빈칸없게 위에 있는 뿌요들을 정렬
        for i in range(len(changed_col)):
            for j in range(10,-1,-1):
                if graph[j][changed_col[i]]!=".":
                    curr=j
                    while curr<=10 and graph[curr+1][changed_col[i]]==".":
                        graph[curr+1][changed_col[i]],graph[curr][changed_col[i]]=graph[curr][changed_col[i]],graph[curr+1][changed_col[i]]
                        curr+=1

print(res)

6번째 줄까지는 그래프를 입력받고 방향 리스트, 사용할 큐 초기화, 결과 변수를 선언했다.

8번째 줄의 while문은 더 이상 터진 뿌요들이 없을 때까지 터뜨리고 빈칸을 정렬하는 과정을 반복하는 부분이다.

check변수를 통해 터진 뿌요가 없을 경우 반복문을 탈출하고 매번 방문했는지 체크하는 visited 리스트를 초기화하도록 구현하였다.

13번째 줄부터는 전체 리스트를 반복하면서 뿌요가 존재할 경우 현재 뿌요를 저장하고 근접한 동일 뿌요들의 개수를 세서 4개 이상이라면 해당하는 뿌요들을 빈칸으로 초기화하였다.

이때 뿌요는 5종류가 있지만 변수에 현재 위치한 뿌요를 저장함으로써 종류에 대한 고려를 하지 않도록 했고 47번째 줄의 changed_col은 삭제된 뿌요가 존재하는 열을 추가하여 이후에 뿌요들을 정렬할 때 불필요한 탐색을 줄이는 방식으로 구현하였다.

53번째 줄에서 res+=1을 통해 카운트를 증가시키는데 문제에서 터질 수 있는 뿌요가 여러 그룹이라면 동시에 터지며 한 번의 연쇄가 추가되므로 다 터지고 난 뒤에 추가하도록 증가시키는 위치를 주의해야 한다.

터진 뿌요가 없다면 50번째 줄에서 반복문을 탈출하겠지만 터진 뿌요가 존재한다면 빈칸보다 위에 뿌요가 존재하지 않도록 정렬시킨 후 다시 반복문으로 돌아가면 된다.

그래프의 행을 기준으로 리스트 시작은 위, 끝은 바닥을 뜻하므로 끝부터 시작까지 역으로 오면서 뿌요를 최대한 리스트의 끝까지 정렬하는 것에 주의해야 한다.

해당 반복문이 끝나면 결과 변수인 res를 출력하면 끝이다.

그래프의 크기도 작고 특별한 알고리즘도 없이 흔한 그래프 이론으로 푸는 구현 문제였지만 구현 과정이 다소 길어지다 보니 충분히 헷갈릴 수도 있는 문제였다.

따라서 구현해야 하는 부분과 과정을 간략하게 주석으로 써놓고 차근차근 작성해 나가는 것이 실수를 방지하기 위해 중요한 것 같다.

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

문제 풀이

전형적으로 시작 노드에서 도착 노드까지 장애물을 피해 도착하는 최단 거리를 출력하는 문제이다.

다만 다소 어렵게 느껴질 수 있는 부분은 기존의 그래프 탐색은 방문 가능한 노드인지(장애물이 아닌지), 방문한 노드인지를 체크하고 탐색하지만, 이 문제에선 최대 한 개의 벽을 부수고 이동할 수 있다는 개념이다.

아마 정답 비율이 낮은 이유(약 23%)는 이 개념 때문이지 않을까 추측해본다.

이 문제에서는 살짝 다르게 생각하는 방법이 필요하다.

물론 문제대로 매번 현재 상태가 벽을 부수고 이동한 상태인지 아닌지 기록할 수도 있겠지만 3차원 리스트로 생각하면 좀 더 이해하기 쉬울 것이다.

즉, 기존의 2차원 리스트를 2개 갖는 3차원 리스트로 생각하고 벽을 부수지 않은 상태라면 0번째 인덱스의 2차원 리스트, 벽을 부순 상태라면 1번째 인덱스의 2차원 리스트로 생각하면 된다.

벽을 부수는 것을 한 층 올라간다고 생각하면 이해가 쉬울 것이다.

이렇게 개념만 잡고 간다면 나머지는 기존의 2차원 리스트에서 최단 거리를 찾는 알고리즘과 같기 때문에 어렵지 않게 구현할 수 있을 것이다.

전체 코드를 따라가면서 이해하면 도움 될 것이다.

import sys
from collections import deque

#위,오른,아래,왼
dx=[-1,0,1,0]
dy=[0,1,0,-1]
n,m=map(int,input().split())
graph=[]
res=-1
queue=deque()
for i in range(n):
    graph.append(list(map(int,list(sys.stdin.readline().rstrip()))))
visited=[[[0 for i in range(m)] for j in range(n)]for k in range(2)]

       #벽 부수기 전,시작위치,거리
queue.append([0,0,0,1])
visited[0][0][0]=1
while len(queue)>0:
    temp_list=queue.popleft()
    for i in range(4):
        x=temp_list[1]+dx[i]
        y=temp_list[2]+dy[i]
        if 0<=x<n and 0<=y<m:
            if x==n-1 and y==m-1:
                res=temp_list[3]+1
                break
            elif graph[x][y]==0 and visited[temp_list[0]][x][y]==0:
                visited[temp_list[0]][x][y]=1
                queue.append([temp_list[0],x,y,temp_list[3]+1])
            elif graph[x][y]==1:
                if temp_list[0]==0 and visited[0][x][y]==0:
                    visited[1][x][y]=1
                    queue.append([temp_list[0]+1,x,y,temp_list[3]+1])

    if res!=-1:
        break
if n==1 and m==1:
    print(1)
else:
    print(res)

먼저 최대 1000000개의 노드가 가능한 그래프이고 3차원 리스트로 생각하므로 최대 2000000개가 가능하기에 최대한 시간을 줄일 필요성이 있었다.

따라서 sys 모듈을 이용하여 입력 시간을 줄였고 시작과 끝부분에서 데이터 삽입 삭제가 가능한 deque 모듈을 사용하여 BFS에서 최대한 시간을 줄이려고 노력했다.

그냥 List에서 BFS를 위해 pop(0)을 한다면 매번 O(n)의 시간 복잡도가 걸리기 때문이다.

5, 6번째 줄에선 한 노드를 기준으로 0번째 인덱스부터 차례대로 위 노드, 오른쪽 노드, 아래 노드, 왼쪽 노드로 가능한 방향을 저장한 리스트이다.

10번째 줄은 BFS 탐색을 위해 데크로 선언하였다.

11번째 줄에선 그래프로 저장하며 13번째 줄의 visited 리스트는 각 각 방문한 노드인지 체크하는 리스트인데 중요한 것은 3차원 리스트로 선언한 것이다.

최대 한 번 벽을 부수고 이동할 수 있기 때문에 2개의 2차원 리스트로 선언했고 만약 2번 3번 벽을 부수고 이동한다면 각 층을 올라간다고 생각하여 3개, 4개의 2차원 리스트로 선언하면 된다.

16번째 줄에서 데크에 넣은 리스트는 벽을 부수기 전, 시작 위치, 거리이다.

그러고 나서 18번째 줄에서 BFS를 실행하면 된다.

19번째 줄의 popleft()는 O(1)의 시간 복잡도가 걸리고 24번째 줄에선 도착하면 res를 갱신한 뒤 BFS를 탈출한다.

27번째 줄은 방문 가능한 노드일 경우 데크에 넣는 코드고 30번째 줄은 벽이 있을 때 부수고 온 상태가 아니라면 벽을 부수고(층을 이동하여) 노드를 데크에 넣어준다.

마지막으로 res를 출력하면 통과할 수 있다.

알고리즘 구현 자체는 다른 그래프 탐색과 비슷한 수준이지만 벽을 부수고 이동할 수 있다는 조건 때문에 어렵게 다가왔다.

주어진 조건을 이해와 구현이 쉬운 방법으로 변환하는 게 핵심 포인트이며 이처럼 다차원 리스트로 변환하여 생각하는 방법은 은근히 나오니 꼭 익숙해지는 게 좋을 것 같다.

비슷하게 다차원 리스트를 이용하는 문제를 추천하며 마무리 짓도록 하겠다.

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

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

문제 풀이

최대 공약수와 최소 공배수에 관한 수학 문제이다.

문제에 들어가기 앞서 최대 공약수와 최소 공배수에 대한 관계와 최대 공약수를 구하는 방법인 유클리드 호제법을 알고 있어야 수월하게 풀 수 있다.

간단하게만 설명하자면 두 수 A, B가 있을 때 동시에 나눠서 나머지가 0이 되는 가장 큰 수를 최대 공약수라 하고 A의 배수, B의 배수 중 가장 작은 수를 최소 공배수라 한다.

여기까지는 누구나 알고 있지만 관계에 대해서 이해해야 보다 수월하게 풀 수 있다.

최대 공약수를 c, 최소 공배수를 d라 하고 A를 c로 나눈 몫을 a, B를 c로 나눈 몫을 c로 한다면 a와 b는 서로소 관계(1을 제외한 공약수가 없는 관계)가 된다.

따라서 a x b x c = d 가 성립하기 때문에 이를 자유자재로 이용할 수 있어야 한다.

또한 유클리드 호제법은 두 수가 있을 때 큰 수를 작은 수로 나눈 나머지가 0이 될 때까지 반복하여 최대 공약수를 구하는 방식이다.

전체 코드에서 구현 방법을 보면 이해될 것이다.

def gcd(num1,num2):
    if num2%num1==0:
        return num1
    else:
        return gcd(num2%num1,num1)
a,b=map(int,input().split())
b=b//a
res=[]
for i in range(1,b+1):
    if b%i==0:
        if i<b//i:
            if gcd(i,b//i)==1:
                res.append([i*a+(b//i)*a,i*a,(b//i)*a])
        else:
            if gcd(b//i,i)==1:
                res.append([i*a+(b//i)*a,(b//i)*a,i*a])
if len(res)>0:
    res.sort(key=lambda x:x[0])
    print(res[0][1],res[0][2])

먼저 유클리드 호제법을 사용하는 최대 공약수를 구하는 함수를 gcd로 선언했다.

gcd는 최대 공약수(Greatest Common Divisor)의 약자이기 때문인데, 이처럼 코드를 작성할 때는 해당 변수가 무엇을 뜻하는지, 해당 함수가 어떤 기능을 하는지 의미하는 이름으로 짓는 게 차후에 코드를 이해하기 편해서 좋다.

num2가 num1보다 더 큰 수이고 함수를 보면 알 수 있듯이 큰 수를 작은 수로 나눴을 때 나머지가 0이면 작은 수를 리턴, 아니라면 나머지와 나눴던 작은 수를 매개변수로 재귀 호출한다.

이렇게 반복하면 최대 공약수를 얻을 수 있다.

7번째 줄에서 b를 a로 나눈 몫으로 저장하는 이유는 최소 공배수에서 최대 공약수를 없애고 서로소인 두 수의 곱만 고려하기 위해서다.

만약 서로소 관계인 두 수를 구한다면 각 각 최대 공약수를 곱해서 출력하면 답을 구할 수 있을 것이기 때문이다.

8번째 줄의 res 리스트는 서로소인 두 수와 두 수의 합을 저장하는 용도다.

문제에서 분명 조건에 부합하는 자연수 쌍은 여러 개 있을 수 있는데 두 자연수의 합이 최소인 경우를 출력하라 했으니 합을 기준으로 정렬하여 가장 작은 경우를 출력하면 될 것이다.

따라서 9번째 줄에서 1부터 b까지 반복을 하는데 i로 b를 나눈 나머지가 0이면 두 수의 곱으로 나타낼 수 있는 숫자고 두 번째 if문은 더 큰 수를 gcd 함수의 두 번째 인자에 넣기 위한 조건문이다.

또한 gcd 함수의 반환 결과가 1이라면 두 수가 서로소 관계이므로 두 수의 합과 두 수를 최대 공약수를 곱해서 res 리스트에 넣었다.

반복문이 종료되면 res 리스트를 두 수의 합을 기준으로 오름차순 정렬하고 첫 번째 원소에 들어가 있는 두 수를 출력하면 통과한다.

문제를 통과하긴 했지만 조금 더 생각하면 탐색하는 범위를 절반 정도로 줄일 수 있을 것 같다.

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

문제 풀이

자연수로 이루어진 수열이므로 연속된 합을 구하는 다양한 알고리즘 중에 투 포인터(Two Pointer) 알고리즘을 사용하는 문제다.

만약 투 포인터에 대해 잘 모르겠다면 밑에 있는 더보기를 눌러서 설명을 보고 이해하기 바란다.

더보기

 

 

투 포인터 알고리즘이란 두 개의 지점을 이동시키면서 연속된 숫자의 합(구간 합)을 구하는 알고리즘이다.

 

비슷한 알고리즘으로 슬라이딩 윈도우(Sliding Window)가 있는데 이 둘의 차이점은 구간의 길이다.

 

슬라이딩 윈도우는 구간의 길이가 정해져 있고, 투 포인터는 상황에 따라 변한다.

 

또한 투 포인터는 음수가 존재할 경우 구간의 길이가 증가했을 때 구간 합이 증가할지 감소할지 보장할 수 없으므로 양의 정수만 존재할 때 사용 가능하다는 특징이 있다. 

 

그림을 통해 이해하면 쉬울 것이다.

 

 

다음과 같이 자연수로 이루어진 리스트가 있을 때 합이 5인 구간의 최소 길이를 찾는 예시를 보자.

 

이때 두 가지 변수를 Left, Right로 선언하고 처음부터 Right 변수를 오른쪽으로 움직이며 구간 합에 원소를 합하고 Left 변수를 오른쪽으로 움직이며 구간합에 원소를 빼는 방식이다.

 

 

먼저 Right 변수가 첫 번째 원소를 가리킬 때다.

 

Sum에 해당하는 원소를 더하고 5와 비교했을 때 더 작으므로 구간을 늘려야 한다.

 

따라서 Right 변수를 옮겨야 한다.

 

 

Right 변수를 옮기고 나서 구간합이 5가 되므로 이 구간의 길이를 갱신시키면 된다.

 

최소 길이를 구해야 하므로 Left 변수를 옮기면 된다.

 

 

Left 변수를 옮기고 나서 Sum이 5보다 작으므로 Right 변수를 옮긴다.

 

 

Right 변수를 옮긴 뒤 Sum이 5보다 크므로 Left 변수를 옮겨 구간 합을 더 작게 만든다.

 

 

Left 변수를 옮기고 Sum이 5보다 더 크지만 동일한 원소(구간의 길이가 1)를 가리키므로 Right 변수를 옮긴다.

 

 

Right 변수를 옮긴 뒤 Sum이 5보다 크므로 Left 변수를 옮긴다.

 

 

Left 변수를 옮긴 뒤 해당 원소를 빼주니 Sum이 5이다.

 

해당 구간의 길이는 1이므로 구간 길이를 갱신해주고 Right 변수를 옮긴다.

 

 

Right 변수를 옮기니 리스트를 벗어나므로 탐색을 종료한다.

 

인덱싱을 어떻게 구현하는지는 본인의 자유이며 인덱싱 과정이 헷갈릴 수 있기에 여러 가지 방법 중에 가장 자신한테 적합한 방식을 적용하는 편이 좋을 것 같다.

 

다음은 문제를 푼 전체 코드이다.

n,s=map(int,input().split())
left=-1
right=0
min_len=100001
num_array=list(map(int,input().split()))
temp_sum=num_array[0]
while right<n:
    if temp_sum>=s:
        if min_len>right-left:
            min_len=right-left
        left+=1
        temp_sum-=num_array[left]
    else:
        right+=1
        if right<n:
            temp_sum+=num_array[right]
if min_len==100001:
    print(0)
else:
    print(min_len)

문제에서 수열의 길이 N은 100000 미만이므로 100000 이상의 숫자 중 아무거나 구간의 최소 길이로 정하고 그걸 갱신하면 최소 길이를 구할 수 있다.

만약 처음에 정한 숫자가 그대로 있다면 합이 s보다 큰 구간이 없단 뜻이며 4번째 줄에선 선언하고, 17번째 줄에선 판단하도록 구현했다.

7번째 줄의 while문에서는 right 변수가 수열의 길이를 넘어가면 안 되므로 길이(n) 미만일 때까지만 반복을 한다.

또한 while문 내부에서는 구간합이 S이상이면 길이를 갱신하고 Left를 이동시켜 원소를 구간합에서 빼고 구간합이 S미만이면 Right를 이동시켜 원소를 구간합에 더하도록 구현했다.

인덱싱 과정이 다소 헷갈릴 수 있는 알고리즘이라서 소수의 원소를 집어넣고 접근하는 과정을 하나씩 출력하다 보면 실수를 줄일 수 있을 것이다.

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

문제 풀이

전형적으로 백트래킹을 이용하면 풀 수 있는 문제다.

지문에서 N번째 숫자를 묻고 N은 1,000,000(백만) 이하의 자연수 혹은 0이므로 상당히 큰 숫자들을 비교해야 할 것 같지만 정작 주의해야 할 조건은 딱 하나다.

1. 앞 자릿수부터 뒤로 갈수록 숫자가 작아져야 한다.

예시에 나온 322처럼 같은 숫자가 연속해서 등장해도 감소하는 수가 아니므로 생각 가능한 최대 숫자는 9876543210이다.

물론 이 숫자 또한 90억이 넘는 숫자이므로 0부터 9876543210까지 차례대로(선형적으로) 감소하는 숫자인지 판단하려면 엄청난 연산 횟수가 나올 수밖에 없다.

하지만 이 숫자들을 자릿수를 기준으로 비교한다면 얘기가 달라진다.

즉, 1자리 수부터 10자리 수까지 앞자리보다 작은 숫자들만 이어 붙여준다면 불필요한 연산을 획기적으로 줄일 수 있다.

이 과정에서 백 트래킹을 재귀로 구현하며 무한 루프에 빠지지 않도록 탈출 조건을 잊지 않도록 한다.

아이디어만 떠올린다면 구현 자체는 어렵지 않은 문제이므로 전체 코드를 보면서 설명하겠다.

def add_digit(digit,num):    #자리수에 따라 증가
    if digit==1:
        decreasing.append(num)
    else:
        for i in range(num%10):
            add_digit(digit-1,num*10+i)

def backtracking(digit):    #백트래킹 시작
    for i in range(digit-1,10):
        add_digit(digit,i)
    
decreasing=[]        #감소하는 숫자 리스트
for i in range(1,11):
    backtracking(i)

n=int(input())
if n>=len(decreasing):        #감소하는 숫자가 없을 때
    print(-1)
else:
    print(decreasing[n])

크게 구성을 함수 두 개, 메인으로 나누었다.

물론 메인에서 중첩 for문을 통해 1자리 수부터 10자리 수까지 가능한 숫자들을 매개변수로 보낸다면 하나의 함수만 써도 되지만 직관적인 이해를 돕기 위해 기능을 분리하여 함수 두 개로 구현하였다.

첫 번째 함수 add_digit은 특정 자릿수까지 감소하는 숫자를 이어 붙이는 함수고 두 번째 함수 backtracking은 1 자릿수부터 10 자릿수까지 백 트래킹을 반복하는 함수다.

함수의 특성상 먼저 선언되어있어야 호출 가능하므로 조금 복잡하지만 함수의 흐름대로 설명하겠다.

먼저 12번째 줄에 decreasing으로 감소하는 숫자들을 넣을 리스트를 선언했다.

그리고 13번째 줄은 자릿수를 매개변수로 백 트래킹을 시작하기 위한 반복문이고 이해가 쉽도록 1부터 10까지 반복한다.

즉 1 자릿수부터 10자리 수까지 찾겠다는 의미이다.

그럼 8번째 줄인 backtracking 함수로 넘어가는데 이미 받은 digit변수와 같이 0부터 9까지 숫자를 파라미터로 넘긴다.

이 0부터 9는 실제 감소하는 수가 될 숫자들이다.

그렇게 add_digit으로 넘어가면 digit이 1자리일 때는 더 이상 추가할 숫자가 없으므로 decreasing 리스트에 숫자를 넣고 함수가 자동 종료된다.

만약 digit이 2 이상일 땐 뒷자리에 숫자를 추가해야 하므로 반복문을 통해 digit을 감소시킨 후 재귀 호출한다.

이때 추가해야 할 숫자가 바로 앞자리 숫자보다 작아야 하므로 num%10을 통해 바로 앞자리 숫자를 구하고 해당 숫자 미만까지만 반복문을 돌린다.

물론 2자리 수 이상부터는 첫자리에 0이 올 수 없지만 num%10은 0이라 for문을 수행하지 않아서 고려하지 않아도 된다.

또한 뒷자리에 숫자를 이어 붙이므로 원래 숫자인 num에 10을 곱해서 자릿수를 늘린 후 i를 더하면 원하는 숫자가 된다.

위의 재귀가 끝나면 decreasing 리스트에는 0부터 9876543210까지 감소하는 수가 들어가게 되고 N을 입력받아서 리스트의 인덱스를 벗어나면 불가능한 수이므로 -1을 출력, 벗어나지 않으면 해당 인덱스의 숫자를 출력하면 통과한다.

아무래도 이 문제가 골드로 측정된 것은 숫자를 자릿수로 비교하는 생각의 전환, 백 트래킹 적용 때문인 것 같다.

비교적 코드도 짧고 구현도 쉬운 편이기 때문이다.

아마 다양한 문제를 접하다 보면 이 정도 아이디어와 구현은 쉽게 떠올리고 구현할 수 있을 것이다.