2023년 9월 15일 알고리즘 문제풀이

문제 1 백준 11047

문제 링크

1차 시도

나의 생각

최소한의 동전을 사용하기 위해선 최대한 가치가 큰 동전을 많이 사용해야 한다. 이를 위해 입력받은 동전을 큐에 저장해 최대 힙을 사용하였다. 가장 큰 동전부터 가능한 갯수만큼 사용했다. 기존에는 이중 반복문을 사용해서 가장 큰 동전을 여러번 쓰도록 구현했지만 시간초과가 문제가 되었다. 따라서 몫과 나머지를 이용해서 한번만 실행되도록 바꾸었더니 통과되었다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import sys
from heapq import heappush, heappop

n, k = map(int, sys.stdin.readline().split())
coins = []
for _ in range(n):
    heappush(coins, -1*int(sys.stdin.readline()))
cnt = 0
while k > 0 and coins:
    val = -1*coins[0]
    if k >= val:
        tmp = k//val
        cnt += tmp
        k %= val
    heappop(coins)

print(cnt)

문제 2 백준 1541

문제 링크

1차 시도

나의 생각

’-‘가 중요하다고 생각했다. 그 ‘-‘이후의 것들을 어떻게 묶느냐에 따라 전체 결과값을 최소로 만들 수 있기 때문이다. ‘-‘가 나오기 이전은 모두 ‘+’를 기준으로 나뉘면 숫자기 때문에 알맞게 더해주었다. 이후 부터는 ‘-‘ 뒤에 나오는 ‘+’ 들은 괄호를 통해 뺄셈으로 전환될 것이기 떄문에 그렇게 해주었다.

조금더 쉽게 말하면, 처음 ‘-‘나오기 전까지 값들은 모두 ‘+’일테니 더해주고, ‘-‘가 나온다면 그 다음 다른 ‘-‘가 나오기 전까지의 것들은 괄호로 묶어서 전체 값에서 빼는 값이 될 것이기 때문에 빼준다는 뜻이다.

결과

정답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
import sys

nums = sys.stdin.readline().rstrip().split('-')
ans = 0
for i in nums[0].split('+'):
    ans += int(i)

for i in nums[1:]:
    for j in i.split('+'):
        ans -= int(j)

print(ans)

문제 3 백준 2098

문제 링크

1차 시도

나의 생각

마지막에는 출발했던 도시로 돌아와햐므로 그 직전도시 까지의 비용까지만 구한 뒤 따로 더해주었다.

예를 들어, 도시가 5개일 때 출발도시가 1이라면 1번에서 출발하여 모든 도시를 경유하고 2번에서 끝나는 경우, 3번에서 끝나는 경우 , … 각 경우를 구했다. 각 케이스별로 끝나는 지점에서 처음 출발지인 1번으로 돌아오는 경로가 있다면 더해주고 없으면 후보로서 탈락이다. 남은 값들 중 최솟값을 가지는 경로가 1번 도시에서 1번 도시로 돌아오는 최소 비용의 경로이다. 이 과정을 모든 도시에서 진행한 후 가장 작은 값을 구하면 되겠다고 생각하였다.

비용 계산이 실행되지 않는다.

결과

오답

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
import sys

n = int(sys.stdin.readline())
graph = [[]]
for _ in range(n):
    graph.append([0] + list(map(int, sys.stdin.readline().split())))

visited = [0 for _ in range(n+1)]
visited[0] = 1


def dfs(s, e, cnt, arr):
    val = []
    if sum(arr) == n+1 and graph[s][e]:
        val.append(cnt + graph[s][e])
        return min(val)
    for i in range(1, n+1):
        if graph[s][i] and not arr[i]:
            arr[i] = 1
            dfs(i, e, cnt+graph[s][i], arr)
            arr[i] = 0

ans = 10**9

for i in range(1, n+1):
    visited[i] = 1
    if dfs(i, i, 0, visited):
        tmp = dfs(i, i, 0, visited)
        ans = min(ans, tmp)
    visited[i] = 0
print(ans)

2차 시도

나의 생각

외판원 순회 문제라고 불리는 TSP(Traveling Salseman problem) 문제이다. Introduction To Algotithms 3rd Edition에서 공부하길, 이 문제에 관한 최적의 알고리즘을 아직 모른다고 한다. 이 말을 하는 이유는.. 결국 이 문제는 모든 경우를 다 순회해봐야 하는데 그 과정을 조금이나마 줄이고자 하는 것이 핵심이라는 것으로 내가 이해했기 떄문이다.

이 문제에서 다들 비트마스크를 쓰는 이유가 이 떄문이라고 생각한다. 그동안 우리가 방문처리를 위해 흔히 사용한 길이가 n인 리스트를 이용해 모든 과정을 순회하기엔 메모리 낭비가 너무 심하니까. n개의 숫자로 이루어진 정수 하나로 표현하면 훨씬 간편할 것이다.

그럼 그동안 DFS니 뭐니 할 때 진작에 비트마스크를 썼으면 그때도 좋았지 않았을까? 라는 생각이 들어서 좀 찾아보았다. 역시 일장일단이 있다. 컴퓨터 아키텍처에서 정수를 표현하는데 4바이트(32비트) 나 8바이트(64비트)를 사용한다. 이게 비트마스크를 이용해 표현할 수 있는 길이라는 의미이다. 입력크기가 32,64만 넘어가면 배열로 다루지 않고 비트마스크를 사용하는 것이 오히려 더 복잡해진다. 그동안 공부해봐서 알겠지만 보통 단위가 100,000 정도 되니까 쓸 일이 극히 적은것 같긴 하다. TSP는 워낙 복잡한 알고리즘이라 입력 크기가 적은 경우가 많고 그 덕분에 사용할 수 있었다는 것으로 받아들였다.

따라서 비트마스크는 ‘현재 방문상태를 정수화해논 것’쯤이라고 생각하자. 자세한 연산이나 내용은 따로 찾아서 공부하는게 좋겠지만 이번 문제 풀이를 위해 필요한 간단한 것은 적어놓겠다. 파이썬에서 0b는 2진법을 의미한다. 0010 이라는 이진법을 0b0010이라고 쓰는 것이다.

• shift 연산 : a << b는 a의 비트를 b칸 만큼 왼쪽으로 미는 것이다. 0b0010 << 2 는 0b1000 이 된다. 0b1000 >> 2는 0b10 이 된다.
• and 연산 : &는 모두 1일 경우 1을 반환한다. 0b11111111 & 0b00110011 는 0b00110011
• or 연산 : |는 하나라도 1일 경우 1을 반환한다. 0b11000 | 0b00011는 0b11011

우선은 이 정도만 알아두면 코드에 나오는 건 알 수 있을 것이다.

이 문제에서 dp는 2차원 배열이긴 하지만 좌표의 개념이 아님을 우선 알아야 한다. 그동은 dp[a][b] 는 a부터 b 라던가, (a,b)를 의미하였지만 여기서 첫번째 index는 도시의 번호, 두번째 index는 도시의 방문상태를 비트마스크로 표현한 것을 말한다. 따라서 dp[a][b] 는 이전에 a번 도시를 b라는 방문처리 상태로 방문한 적이 있는가? 라는 의미이다. 방문처리 상태라 하면 이전에 어떤 도시들을 방문하고 거쳐 왔는지를 말한다.

가장 먼저 이해해야 할 것은 출발지를 정하는 것이 무의미하다는 것이다. 모든 도시를 순회해야 하고 출발지로 돌아와야 하기 떄문에 모든 도시를 포함하는 사이클이 완성된다는 의미이다. 1->2->3->4->5->1 이라는 경로의 비용과 3->4->5->1->2->3 이라는 경로의 비용은 당연히 같을 수밖에 없다. 따라서 임의의 출발지를 설정하고 그 때 최소 비용을 구하면 결국 전체 최소비용을 구하는 것과 같은 결과를 낸다. 편하게 index 0을 출발지로 하자. 도시는 1번부터지만 행렬의 index는 0부터이다. 이제부터 도시 이름으로 말하지 않고 index로 통일하겠다.

방문처리는 비트마스크를 이용한다. 0b1 은 0번만, 0b11은 0,1번 2개를, 0b111은 0,1,2 3개를 거쳤다는 의미이다. 절대 str 형태가 아님을 기억하자! 0b1 은 int로 1, 0b111은 7이다. 0번에서 출발했을 때 모든 도시를 다 돈 후에는 어떤 값이 나와야 할까? 도시가 5개라면 0b11111 이다. 1이 5개 있다. 이를 다르게 표현하면 0b100000 - 1 이라고 할수 있다. 잘 보면 6자리다. 0b100000을 위에 써놓은 shift연산으로 표현한 것이 코드 10행의 (1<<n)이다. 따라서 10행은 모든 도시를 방문했는지 확인하는 것이다.

1차 시도에 말했던 것처럼, 끝 도시를 출발했던 0번 도시로 설정하지 않는다. 모든 도시를 순회한 이후로 별도로 돌아오는 것을 처리해주면 된다. 마지막에 도착한 도시에서 0번으로 돌아올 수 있다면 값을 더해주면 된다.

21행을 살펴보자. visit과 1 << i의 and 연산이다. 1 << i는 1을 i만큼 왼쪽으로 밀어서 i번째 자리만 1이고 그 오른쪽은 모두 0을 가질 것이다. i가 4라면 0b1000이 된다. and 연산이기 떄문에 visit의 4번째 자리가 1이라면 여기 자리만 1을 반환하여 0b1000이 되고, visit의 4번째 자리가 0이라면 나머지 자리는 0이기 떄문에 0을 반환한다. 조건문에서는 0인지를 물어보는 것은 i번째가 방문처리가 안되어있는지, i가 방문한적 없는지를 의미하는 것이다. graph[s][i]는 경로가 존재하는지를 확인하는 것이다.

22번행은 탐색하는 과정이다.visit | (1 << i)는 or 연산자다. 기존 visit | 10000 와 같은 의미이다. 물론 i가 5라는 가정하에 쓴 것이다. 이 연산의 결과는 visit에서 5번째(i번째) 자리의 숫자가 0이라면 1로 바뀌는 것이다. 즉 i번 도시를 방문처리 하는 코드이다. 그 후 dp[s][visit]을 업데이트한다. 기존에 계산해놓은 값과 현재 새롭게 계산하여 더 적은 비용으로 바꾼다.

search함수는 인자로 받은 현재 도시에서 출발하여 아직 방문하지 않은 도시를 방문한 후 0번 도시로 돌아오는 최소 비용을 반환한다. 이 과정에서 dp에 저장하여 재귀과정에서 반복된 연산을 최소화하는 것이다.

결과

이해

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import sys

n = int(sys.stdin.readline())
graph = []
for _ in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))
dp = [[0 for _ in range(1 << n)] for _ in range(n)]

def search(s, visit):
    if visit == (1 << n) - 1:
        if graph[s][0]:
            return graph[s][0]
        else:
            return 1e9

    if dp[s][visit]:
        return dp[s][visit]

    tmp = 1e9
    for i in range(1,n):
        if visit & (1 << i) == 0 and graph[s][i]:
            tmp = min(search(i, visit | (1 << i)) + graph[s][i], tmp)
    dp[s][visit] = tmp
    return dp[s][visit]

print(search(0,1<<0))

• Previous
  InnoDB 버퍼 풀
• Next
  JUnit 들여다보기(1)