문제 출처: 백준 온라인 저지

문제 설명

🔎 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다.

단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다.

- 비용은 대칭적이지 않다. 
- 즉, W[i][j] 는 W[j][i]와 다를 수 있다.
- 모든 도시간의 비용은 양의 정수이다.
- W[i][i]는 항상 0이다.
- 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

위 예제를 그림으로 나타내면 이와 같다.

여기서 정답인 경로는 여러가지가 존재하지만, 하나만 꼽아보자면 2 ➡ 0 ➡ 1 ➡ 3 ➡ 2 순으로 순회할 경우 총 비용이 35로 최소가 된다.

이런 방식으로 접근을 한다면 그래프를 순회하는 알고리즘 중 하나를 사용해야 한다는 것을 알 수 있다.

나는 여기서 DFS를 이용하기로 했다.

<정답 코드>

def dfs(x, val, depth=1):
    global cost
    global first
    global n

    if depth == n:
        for nx, _cost in graph[x]:
            if nx == first:
                cost = min(cost, val+_cost)
        return

    if visit[x]:
        return

    visit[x] = True

    for nx, _cost in graph[x]:
        if not visit[nx]:
            dfs(nx, val+_cost, depth+1)
            visit[nx] = False


n = int(input())
graph = [[] for _ in range(n)]
cost = float('inf')

for i in range(n):
    arr = list(map(int, input().split()))
    for j in range(n):
        if i == j or arr[j] == 0: continue
        graph[i].append((j, arr[j]))

for i in range(n):
    visit = [False] * n
    first = i
    dfs(i, 0)

print(cost)

우선은 2차원 배열형태로 접근하는게 아니라 그래프 형태로 접근하기 위해서 입력을 그래프 형식으로 전환한 뒤 시작하였다.

접근은 아래와 같다.

1. 모든 도시에서 한번씩 시작하며 dfs를 순회한다.
2. dfs를 순회할 때는 시작 지점인 first를 기록하고 시작한다.
3. 한번 방문하고 함수를 빠져나오게 될 때 visit을 초기화 해주어 모든 경로를 탐색할 수 있게 한다.
4. dfs의 depth가 n이 될 때 까지 recursion하며, depth가 n일 때 현재 도시에서 first로 갈 수 있으면 cost를 업데이트 해준다.

처음에는 DP나 다익스트라 문제인 줄 알았다.

하지만, 모든 도시를 다 방문해야하고 출발 지점이 정해져있지 않았으며 한번 방문한 도시는 다시 방문할 수 없었기에 dfs를 통해 접근해야 한다는 사실을 깨달았다.

문제 출처: 프로그래머스

문제 설명

🔎 1와 0로 채워진 표(board)가 있습니다. 표 1칸은 1 x 1 의 정사각형으로 이루어져 있습니다. 표에서 1로 이루어진 가장 큰 정사각형을 찾아 넓이를 return 하는 solution 함수를 완성해 주세요. (단, 정사각형이란 축에 평행한 정사각형을 말합니다.)

제한사항
- 표(board)는 2차원 배열로 주어집니다.
- 표(board)의 행(row)의 크기 : 1,000 이하의 자연수
- 표(board)의 열(column)의 크기 : 1,000 이하의 자연수
- 표(board)의 값은 1또는 0으로만 이루어져 있습니다.

처음에는 이런 방식으로 접근했다.

지금 현재 방문하고 있는 칸이 1이라면, 대각선 아래방향(↘) 을 먼저 확인해 이게 1이라면 대각선 아래의 상,좌를 확인해 사각형이 구성되는지 확인했다.

예제 케이스는 board의 크기가 작기도 하고, 피드백이 바로 가능했기에 맞았지만 테스트케이스는 절반만 맞고 효율성은 통과하지 못했다.

BFS를 통해서 row, column 길이에 제한을 두고 풀어볼까 했지만 이 또한 이전 풀이와 시간복잡도가 다르지 않을 것으로 판단했다.

DP문제라는 힌트를 듣고서 스스로 풀이에 도전했지만, 결국 해답을 찾지 못해 다른 사람들의 도움을 빌려 문제를 해결할 수 있었다.

<정답 코드>

def solution(board):
    answer = 0
    r = len(board) + 1
    c = len(board[0]) + 1
    DP = [[0]*c for _ in range(r)]
    
    for i in range(1, r):
        for j in range(1, c):
            if board[i-1][j-1]:
                DP[i][j] = min(DP[i-1][j], DP[i][j-1], DP[i-1][j-1])+1
            
            answer = max(answer, DP[i][j])
    
    return answer**2

접근은 아래와 같다.

1. board보다 width, hegith가 1씩 더 큰 dp 배열을 만든다.
2. (1, 1)부터 순회를 시작해서 현재 위치가 1에 board에서 1에 해당한다면, 현재 위치의 상, 좌, 대각선 좌측 위(↖) 중에서 가장 작은 값 +1 로 업데이트 한다.

풀이가 생각보다 간단한 것에 놀랬고, 언제 쯤 이런 생각을 바로바로 떠올릴 수 있게 될까 내심 걱정도 됐다.

문제 출처: 프로그래머스

문제 설명

🔎 한 방향으로만 진행하는 컨테이너 벨트에 놓인 순서대로 번호가 있는 택배 상자를 순차적으로 꺼내서 택배 기사님에게 전달합니다.
택배는 반드시 1, 2, 3, ..., n 순서대로 꺼내서 전달해야하며, 만약 꺼내야할 상자가 뒤에 있다면 앞에 있는 택배 상자들은 꺼내서 임시 컨테이너 벨트에 넣습니다. 임시 컨테이너 벨트에서 꺼내는 동작 또한 순차적으로 진행되어야 합니다. 만약 양 컨테이너 벨트에서 원하는 물건을 꺼낼 수 없는 경우 더 이상 상자를 전달하지 않습니다.

5개의 상자가 있고, 택배 기사님이 원하는 순서가 [4, 5, 1, 2, 3] 이라면
원래 컨테이너 벨트에서 [1, 2, 3]을 빼내서 임시 컨테이너 벨트에 [3, 2, 1] 순서로 놓고, 4를 택배 기사님께 전달합니다. 이후 [5]를 원래 컨테이너 벨트에서 빼 전달합니다.
[1]은 원래 컨테이너 벨트에서도, 임시 컨테이너 벨트에서도 바로 얻을 수 없으므로 더 이상 상자를 전달하지 않습니다.

택배 기사님이 원하는 상자 순서를 나타내는 정수 배열 order가 주어졌을 때, 몇 개의 상자를 실을 수 있는지 return 하는 solution 함수를 완성하세요.

처음 문제를 읽었을 때 너무 길고 이해하는데 오래 걸려서 이해한 맥락으로 문제를 요약하였다.

문제는 길었으나 간단히 보면 queue를 이용해서 문제를 풀라는 말이었다.

<정답 코드>

from collections import deque
def solution(order):
    answer = 0
    q = deque([i+1 for i in range(len(order))])
    temp = deque()
    
    for i in order:
        if q and q[0] <= i:
            while q[0] != i:
                temp.appendleft(q.popleft())
            q.popleft()
            answer += 1
        
        else:
            if i == temp[0]:
                temp.popleft()
                answer += 1
            else:
                return answer
        

    return answer

접근은 아래와 같다.

1. 두 개의 컨테이너 벨트를 deque로 구현한다. 기존 컨테이너 벨트는 순서대로 채운다.
2. 상자를 전달하기 위해서는 아래 두가지 조건에 만족되어야 한다.
   1. 기존 컨테이너 벨트에 그 상자가 존재할 경우 그 상자 앞의 모든 상자를 임시 컨테이너 벨트로 옮긴 후 전달한다.
   2. 상자가 임시 컨테이너 벨트에 존재한다면, 그 상자가 맨 앞에 있을 경우에만 전달 가능하다.

위 조건을 만족하지 않으면 바로 탈출하게 끔 코드를 작성하였다.

프로그래머스로 문제를 접하면 엄청난 길이의 문제 설명으로 당황할 수 있지만, 핵심만 파악한다면 쉽게 풀 수 있는 문제라고 생각한다.

문제 출처: 프로그래머스

문제 설명

🔎 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.]
밤늦게 귀가할 때 안전을 위해 항상 택시를 이용하던 무지는 최근 야근이 잦아져 택시를 더 많이 이용하게 되어 택시비를 아낄 수 있는 방법을 고민하고 있습니다. "무지"는 자신이 택시를 이용할 때 동료인 어피치 역시 자신과 비슷한 방향으로 가는 택시를 종종 이용하는 것을 알게 되었습니다. "무지"는 "어피치"와 귀가 방향이 비슷하여 택시 합승을 적절히 이용하면 택시요금을 얼마나 아낄 수 있을 지 계산해 보고 "어피치"에게 합승을 제안해 보려고 합니다.

최단거리, 최저비용이라는 맥락에서 한가지 알고리즘을 떠올리는 것 자체는 어렵지 않으나 거기서 한단계 더 나아가야한다는 부분이 어려웠던 문제였다.

문제를 읽고 '다익스트라' 를 사용해야겠다 마음을 먹고,

s로 부터 a와 b까지의 최단 경로를 구해서 겹치는 부분의 비용을 제거하면 된다고 생각했으나, 그것과는 별개인 문제였다.

당장에 주어진 예시만 봐도 S -> A는 4->1->6이 최단경로고, S->B는 4->2가 최단거리였다. 여기서 겹치는 구간은 없었으나, 5까지 함께하면 더 저렴한 비용으로 갈 수 있었다.

한참을 고민하다가 결국 검색을 했었고, 생각보다 간단한 원리에 감탄했고 한번 더 배울 수 있었다.

<정답 코드>

from queue import PriorityQueue
def solution(n, s, a, b, fares):
    answer = float('inf')
    road = [[] for _ in range(n+1)]
    
    for u, v, cost in fares:
        road[u].append((v, cost))
        road[v].append((u, cost))
    
    def dijkstra(x):
        dist = [float('inf')] * (n+1)
        dist[x] = 0
        q = PriorityQueue()
        q.put((0, x)) # cost, 도착지, 출발지
        
        while q.qsize() > 0:
            cur = q.get()
            _x = cur[1]
            
            for nx, cost in road[_x]:
                if dist[_x] + cost < dist[nx]:
                    dist[nx] = min(dist[nx], dist[_x] + cost)
                    q.put((dist[nx], nx))
        
        return dist
    
    #----------------참고 코드----------------#
    dist = [[]]
    
    for i in range(1, n+1):
        dist.append(dijkstra(i))
        
    for i in range(1, n+1):
        answer = min(answer, dist[s][i] + dist[i][a] + dist[i][b])
    
    return answer

접근은 아래와 같다.

1. 모든 노드에 대해 각 지점 별 최단비용 거리를 다익스트라 함수로 구한다.
   1. 이를 기록하는 dist 배열은 빈 배열이 하나 추가된 상태로 구현한다. (index=0에 해당하는 노드가 존재하지 않기 때문)
2. 모든 노드의 최단거리 목록을 순회하면서,  S-> i, i->A, i->B를 모두 더한 값 중 최소가 되는 값이 정답이다. (i = 현재 순회중인 노드)

모든 경로에 대한 다익스트라 배열을 구한다는 것을 생각해내지 못해 스스로는 풀지 못했던 문제다.

레벨별 문제에 슬슬 익숙해지려 하니, level3문제들이 대체로 기본 알고리즘 + 한 단계 발전인 느낌이 드는 것 같다. 재미있다.

대체로 빠른 속도를 내는 O(E logV)의 시간복잡도를 가진 다익스트라 함수였지만, 꽤 오래걸리는 예제도 있었다.

오히려 O(n³)의 시간복잡도를 가진 플로이드-와샬 알고리즘이 더 빨리 작동할 수 있다는 글을 보아 아래에 정리했다.

플로이드-와샬 알고리즘 풀이

플로이드 와샬 : i에서 k를 거쳐 j로 가는 최단거리를 구하는 알고리즘, 3중 반복문을 사용하기 때문에 O(n³)의 시간복잡도를 갖는다.

<플로이드 와샬 풀이>

def solution(n, s, a, b, fares):
    answer = float('inf')
    cost = [[float('inf')] * (n+1) for _ in range(n+1)]

    # cost 중에서 fares에서 제시된 도로
    for u, v, _cost in fares:
        cost[u][v] = _cost
        cost[v][u] = _cost

    #플로이드 와샬 알고리즘
    for k in range(1, n+1):
        for i in range(1, n+1):
            for j in range(1, n+1):
                if i == j:
                    cost[i][j] = 0
                else:
                    cost[i][j] = min(cost[i][j], cost[i][k] + cost[k][j])


    for i in range(1, n+1):
        answer = min(cost[s][i] + cost[i][a] + cost[i][b], answer)

    return answer

다익스트라에서 dist로 구현되었던 전체 구간에 대한 비용을 cost로 작성하였다.

1. fares에서 제시된 노드 간의 연결은 해당 비용으로 업데이트 해준다.
2. cost 배열에서 서로 다른 상수 i, j에서 i -> j의 비용 중에서 i -> k -> j로 방문했을 때 더 저렴한 경우 그 비용으로 업데이트 해준다. (반복문의 순서를 바꾸면 다르게 작동하므로 순서에 유의)

이후의 과정은 다익스트라와 동일하다.

평균적인 속도는 다익스트라보다 느리게 작동하지만, 최대의 경우에도 2600ms 이내에 해결한다는 것에서 의미가 있는 풀이었다.

문제 출처: 프로그래머스

문제 설명

🔎 자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

- x에 n을 더합니다.
- x에 2를 곱합니다.
- x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

아주 전형적인 DP문제였다. 그리고 어디서 풀어본 적도 있는 것 같은 문제였다.

<정답 코드>

def solution(x, y, n):
    answer = 0
    DP = [float('inf')] * (y+1)
    DP[x] = 0
    
    for i in range(x+1, y+1):
        if i < x+n and i < 2*x:
            continue
            
        DP[i] = min(DP[i-n]+1, DP[i])
        
        if i%2==0:
            DP[i] = min(DP[i], DP[i//2]+1)
        
        if i%3==0:
            DP[i] = min(DP[i], DP[i//3]+1)

    return DP[y] if DP[y] != float('inf') else -1

접근은 아래와 같다.

1. 정답을 저장할 DP배열을 만든다. (0부터 시작해도 되고 x부터 시작해도 된다. 편한대로)
2. n의 크기가 지정되어 있지 않으므로 x+n 또는 x*2 중 더 작은 수 부터 순회를 시작한다.
3. i의 크기에 따라 i-n, i//2 (2로 나누어 떨어진다면), i//3 (3으로 나누어 떨어진다면)의 DP 값 중 가장 작은 것 +1로 업데이트한다.

처음에 return 값에서 -1을 처리하지 않고 float 그대로 출력되게 놔두는 실수를 해서 valueError가 발생했었다.

끝까지 집중해서 다 풀자.

문제 출처: 프로그래머스

문제 설명

🔎 정수로 이루어진 배열 numbers 가 있습니다. 배열 의 각 원소들에 대해 자신보다 뒤에 있는 숫자 중에서 자신보다 크면서 가장 가까이 있는 수를 뒷 큰수라고 합니다.
정수 배열 numbers 가 매개변수로 주어질 때, 모든 원소에 대한 뒷 큰수들을 차례로 담은 배열을 return 하도록 solution 함수를 완성해주세요. 단, 뒷 큰수가 존재하지 않는 원소는 -1을 담습니다.

이 문제는 이미 백준에서 한번 풀어본 적이 있는 문제였다. (=> 백준 오큰수)

예시를 맞추려고만 하면 아주 쉬운 문제이긴 하나, 시간 복잡도를 고려해서 정답을 맞추려면 조금 생각해야 하는 문제였다.

정답은 "자료구조" 안에 있다.

<정답 코드>

def solution(numbers):
    n = len(numbers)
    answer = [-1] * n
    stack = [0]
    
    for i in range(1, n):
        while stack and numbers[stack[-1]] < numbers[i]:
            answer[stack.pop()] = numbers[i]
        stack.append(i)
        
    return answer

스택을 이용해 문제를 해결했다.

접근은 아래와 같다.

1. 정답을 기록할 answer 배열에 numbers의 길이만큼 -1을 입력한다.
2. number를 순회하되, stack을 이용해 순회하도록 작성한다.
   1. 순회 도중에 stack이 비어있을 경우도 있으므로 [0]으로 초기화해 빈 배열인지 점검할 수 있도록 한다.
   2. numbers[i]보다 작고, stack에 index가 기록되어있는 배열들은 전부 numbers[i]로 기록한다.

원리 자체는 쉬우나, 빨리빨리 떠올리기에는 연습이 필요한 문제인 것 같다.

문제 출처: 백준 온라인 저지

문제 설명

🔎 N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다.

입력
- 첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
- 둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력
- 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
- 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

드디어 브루트포스 1번 카테고리를 끝내고 N, M 시리즈로 넘어왔다.

이 전에 문제들을 풀면서 N과 M 문제를 4번까지 끝내놔서 바로 5번으로 넘어왔는데, 1번 카테고리에서 고생한 것과 달리 좀 쉬운 문제가 나와서 한숨을 돌렸다.

<정답 코드>

from itertools import permutations

n, m = map(int, input().split())
arr = list(map(int, input().split()))

for p in sorted(permutations(arr, m)):
    print(*p)

접근은 따로 설명하지 않겠다.

이번 문제에서는 순열이라는 언급이 바로 나왔으며, 모든 가능한 경우의 수를 출력하고 N과 M이 8 이하라는 조건이 있었기에 망설임 없이 permutations를 이용했다.

ㅇ후에 올라올 N과 M시리즈는 정답률이 50% 미만인 것 들에 대해서만 포스팅 하기로 결정했다.

문제 출처: 프로그래머스

문제 설명

🔎n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다.
예를 들어서 3명의 사람이 있다면 다음과 같이 6개의 방법이 있습니다.
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
사람의 수 n과, 자연수 k가 주어질 때, 사람을 나열 하는 방법을 사전 순으로 나열 했을 때, k번째 방법을 return하는 solution 함수를 완성해주세요.

제한사항
- n은 20이하의 자연수 입니다.
- k는 n! 이하의 자연수 입니다.

정답에 대한 접근은 옳게 했으나, 멍청하게 구현하는 바람에 많은 시간을 허비해버렸다.

기본적으로 순열에 대한 이해가 있으면 어렵지 않게 풀 수 있는 문제인 것 같다.

<정답 코드>

def solution(n, k):
    people = [i for i in range(1, n+1)]
    answer = []
    facto = [1, 1]
    
    for i in range(2, n+1):
        facto.append(facto[i-1]*i)
        
    k -= 1
    
    while n:
        tmp = facto[n-1]
        answer.append(people[k//tmp])
        people.pop(k//tmp)
        k, n = k%tmp, n-1

    return answer

접근은 팩토리얼 계산을 위한 DP와 순열의 계산식을 이용했다.

n명의 서로 다른 사람들을 배치하는 방법은 n!가지 방법이 있다. 5명의 사람들을 배치한다고 가정해보자.

그러면 순열 계산식에 따라 5! = 120가지의 배치 방법이 있다. 번호가 작은 순으로 배치 순서를 매긴다고 하면, 아래 배치 방법이 첫번째 방법이 된다.

여기서 가장 첫번째 오는 사람으로 1번을 고정해놓는다면, 

이와 같이 나타난다. 

그 개수를 구해보면, 1을 제외한 나머지를 먼저 배치한 후 앞에 1을 배치하는 방법과 같으므로 (5-1)! = 24가지 방법이 있다.

이 원리로 2번이 가장 앞에 오게되는 배치들 중 가장 첫번째 순서는 1번이 가장 앞에오는 경우의 수 +1이 된다. 즉, 25번째 배치 방법부터 2번이 가장 앞에 오게 된다. 

그렇다면 k가 25보다 작으면 1번이 반드시 가장 처음에 나타나야 한다. 3번이 가장 앞에 오는 경우도 마찬가지다. 3번이 가장 앞에 나타나는 순서는 2 * (5-1)! + 1 = 49, 즉 k가 49이상이어야 3번이 가장 앞에 올 수 있고, 49보다 작은 경우 2번 또는 1번이 가장 앞에 온다.

이 원리를 모든 자리에 적용한다.

k를 통해 가장 먼저 등장할 번호를 구한다. k를 (n-1)!로 나눈 몫이 그 번호가 될 것이다. 해당 번호 사람을 answer배열에 세워둔 후, 그를 뺀 나머지 사람들에서 다음 차례에 올 사람을 구해야 하므로, 사람 배열에서 해당 번호 사람을 pop해준다.

그리고 k를 k % (n-1)!로, n을 n-1로 업데이트 해주면서 n이 0이 될 때 까지 반복하면 정답이 된다.

(k-1을 해주고 반복문을 시작한다. 이것은 우리가 리스트를 살필 때 첫번째 인덱스가 1이 아닌 0인 원리와 같다.)

원리가 그렇게 어렵진 않았지만, 해당 번호 사람을 제거할 때 pop을 사용하지 않고 굳이 set을 이용해 구현해보겠다는 무모한 도전 때문에 한두번 실패했었다.