'Python/알고리즘' 카테고리의 글 목록

다이나믹 프로그래밍 문제다.

d[n] = n원을 만들기 위해 사용하는 동전의 최소 개수로 두고 짰다.

k원을 만들기 위해 필요한 동전 수는 d[k]가 된다.

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

import sys
 
n, k = map(int, sys.stdin.readline().split())
coin = []
 
for i in range(n):
    coin.append(int(sys.stdin.readline()))
 
coin.sort()
d = [0]*(k+1)
 
for i in range(coin[0], k+1):
    temp = []
    if i in coin:
        d[i] = 1
    else:
        for j in coin:
            if i-j >= coin[0]:
                if d[i-j] != -1:
                    temp.append(d[i-j]+1)
        if len(temp) >0:
            d[i] = min(temp)
        else:
            d[i] = -1
 
print(d[k])
 

저작자표시

'Python > 알고리즘' 카테고리의 다른 글

트리 순회 (백준 1991, 파이썬) (0)	2019.09.06
트리의 높이와 너비 (백준 2250, 파이썬) (0)	2019.09.06
알고스팟 (백준 1261, 파이썬) (0)	2019.08.31
이모티콘 (백준 14226, 파이썬) (0)	2019.08.31
보석 도둑 (백준 1202, 파이썬) (0)	2019.08.21

node 클래스를 만들어두고

각 노드에 대한 객체를 만들면서 사전에 등록해 참조하기 쉽게 한다.

이후 전위순회, 중위순회, 후위순회를 해주며 해당 노드의 data를 출력해주기만 하면 된다.

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import sys
sys.setrecursionlimit(1000000)
 
n = int(sys.stdin.readline())
tree = dict()
root = 'A'
 
class node:
    def __init__(self):
        self.data = None
        self.left = None
        self.right = None
 
def preorder(node):
    sys.stdout.write(node.data)
    if node.left is not None:
        preorder(tree[node.left])
    if node.right is not None:
        preorder(tree[node.right])
 
def inorder(node):
    if node.left is not None:
        inorder(tree[node.left])
    sys.stdout.write(node.data)
    if node.right is not None:
        inorder(tree[node.right])
 
def postorder(node):
    if node.left is not None:
        postorder(tree[node.left])
    if node.right is not None:
        postorder(tree[node.right])
    sys.stdout.write(node.data)
 
 
for i in range(n):
    a, b, c = sys.stdin.readline().split()
    if a == root:
        tree[root] = node()
        tree[root].data = a
        if b != '.':
            tree[root].left = b
            tree[b] = node()
            tree[b].data = b
        if c!= '.':
            tree[root].right = c
            tree[c] = node()
            tree[c].data = c
    else:
        if b!= '.':
            tree[a].left = b
            tree[b] = node()
            tree[b].data = b
        if c!= '.':
            tree[a].right = c
            tree[c] = node()
            tree[c].data = c
 
preorder(tree[root])
sys.stdout.write('\n')
inorder(tree[root])
sys.stdout.write('\n')
postorder(tree[root])

저작자표시

'Python > 알고리즘' 카테고리의 다른 글

동전 2 (백준 2294, 파이썬) (0)	2019.09.10
트리의 높이와 너비 (백준 2250, 파이썬) (0)	2019.09.06
알고스팟 (백준 1261, 파이썬) (0)	2019.08.31
이모티콘 (백준 14226, 파이썬) (0)	2019.08.31
보석 도둑 (백준 1202, 파이썬) (0)	2019.08.21

inorder(중위 순회)를 사용해야하는 특이한 문제다.

문제에 나와있는 그림을 잘 살펴보면 각 노드에 해당하는 행과 열은 각각 그 노드의 깊이(depth)와 중위순회 순서를 나타내고있기 때문이다.

예를 들어 5번 노드는 3행 8열에 위치해 있는데, 이 노드는 깊이가 3, 중위순회 순서 8번에 해당하는 노드이다.

( 중위순회 순서 : 8-4-2-14-9-18-15-5-10-1-16-11-6-12-3-19-17-13-7 )

각 노드를 연결하기 위해 node 클래스를 만들어주고, 각 노드의 깊이와 중위순회 순서를 저장하기 위한 변수도 초기화시켜준다. (self.depth, self.order)

parent 배열은 각 노드가 부모 노드를 가지고있는지 판별하기 위한 배열인데,

노드를 연결할 때마다 parent 배열에 부모가 있다는 표시를 해주면

이후에 parent가 0인 노드를 찾으면 그게 root 노드가 된다.

left, right 배열에 각 깊이에 따른 노드의 열값 최솟값과 최댓값을 저장해둔 후,

right-left+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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

import sys
sys.setrecursionlimit(1000000)
 
class node:
    def __init__(self):
        self.left = -1
        self.right = -1
        self.depth = 0
        self.order = 0
 
def inorder(node, depth):
    global order
    if node == -1:
        return
    inorder(a[node].left, depth+1)
    a[node].depth = depth
    order += 1
    a[node].order = order
    inorder(a[node].right, depth+1)
 
n = int(sys.stdin.readline())
a = [node() for _ in range(10001)]
left = [0]*10001
right = [0]*10001
parent = [0]*10001
order = 0
 
for i in range(n):
    x, b, c = map(int, sys.stdin.readline().split())
    a[x].left = b
    a[x].right = c
    if b != -1:
        parent[b]+=1
    if c != -1:
        parent[c]+=1
 
 
root = 0
for i in range(1, n+1):
    if parent[i] == 0:
        root = i
 
inorder(root, 1)
maxdepth = 0
for i in range(1, n+1):
    depth = a[i].depth
    order = a[i].order
    if left[depth] == 0:
        left[depth] = order
    else:
        left[depth] = min(left[depth], order)
    right[depth] = max(right[depth], order)
    maxdepth = max(maxdepth, depth)
 
maxwidth = 0
anslevel = 0
 
for i in range(1, maxdepth+1):
    if maxwidth < right[i] - left[i] + 1:
        maxwidth = right[i]-left[i]+1
        anslevel = i
 
sys.stdout.write("{} {}".format(anslevel, maxwidth))

저작자표시

'Python > 알고리즘' 카테고리의 다른 글

동전 2 (백준 2294, 파이썬) (0)	2019.09.10
트리 순회 (백준 1991, 파이썬) (0)	2019.09.06
알고스팟 (백준 1261, 파이썬) (0)	2019.08.31
이모티콘 (백준 14226, 파이썬) (0)	2019.08.31
보석 도둑 (백준 1202, 파이썬) (0)	2019.08.21

최소 거리를 구하는 문제이기 때문에 BFS를 이용한다.

각 방을 노드로, 방과 방 사이를 이동하는데 부숴야하는 벽의 수를 노드 간 이동 비용이라고 했을 때,

벽이 없는 방(0)으로 이동하는데에는 비용이 0, 부숴야 하는 벽(1)으로 이동하는데에는 비용이 1 소모되는

0과 1의 비용을 가진 탐색이 된다.

비용이 0과 1로 나뉘어져있을때에는 deque를 사용해서 매 노드를 탐색할 때마다 갈 수 있는 노드에 대한 비용이 0이면 앞에, 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

import sys
from collections import deque
 
n, m = map(int, sys.stdin.readline().split())
a = []
 
for i in range(m):
    a.append(sys.stdin.readline())
 
dist = [[-1]*n for _ in range(m)]
dist[0][0] = 0
q = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
q.append([0, 0])
 
while q:
    x, y = q.popleft()
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if nx>=0 and nx<m and ny >=0 and ny<n:
            if dist[nx][ny] == -1:
                if a[nx][ny] == '0':
                    q.appendleft([nx, ny])
                    dist[nx][ny] = dist[x][y]
                elif a[nx][ny] == '1':
                    q.append([nx, ny])
                    dist[nx][ny] = dist[x][y]+1
 
print(dist[m-1][n-1])

저작자표시

'Python > 알고리즘' 카테고리의 다른 글

트리 순회 (백준 1991, 파이썬) (0)	2019.09.06
트리의 높이와 너비 (백준 2250, 파이썬) (0)	2019.09.06
이모티콘 (백준 14226, 파이썬) (0)	2019.08.31
보석 도둑 (백준 1202, 파이썬) (0)	2019.08.21
재귀호출로 최댓값 구하기 (모두의 알고리즘 with 파이썬 4-2) (0)	2019.07.04

목적지까지 최단거리(시간)를 구하는 문제이기 때문에 BFS를 이용한다.

리스트 d[s][c] 에는 화면에 이모티콘 s개, 클립보드에 이모티콘 c개가 있는 상황까지 도달하기 위한 최소 시간이다.

d[s][c]가 -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

import sys
from collections import deque
 
n = int(sys.stdin.readline())
d = [[-1]*1001 for _ in range(1001)]
d[1][0] = 0  # 화면 1개, 클립보드 0개
q = deque()
q.append((1,0))
 
while q:
    s, c = q.popleft()
 
    if d[s][s] == -1:
        d[s][s] = d[s][c] + 1
        q.append((s, s))
    if s+c<=n and d[s+c][c] == -1:
        d[s+c][c] = d[s][c] + 1
        q.append((s+c,c))
    if s-1>=0 and d[s-1][c] == -1:
        d[s-1][c] = d[s][c] + 1
        q.append((s-1,c))
ans = -1
for i in range(n):
    if d[n][i] != -1:
        if ans == -1 or ans > d[n][i]:
            ans = d[n][i]
print(ans)

저작자표시

'Python > 알고리즘' 카테고리의 다른 글

트리의 높이와 너비 (백준 2250, 파이썬) (0)	2019.09.06
알고스팟 (백준 1261, 파이썬) (0)	2019.08.31
보석 도둑 (백준 1202, 파이썬) (0)	2019.08.21
재귀호출로 최댓값 구하기 (모두의 알고리즘 with 파이썬 4-2) (0)	2019.07.04
열 개씩 끊어 출력하기 (백준 11721, 파이썬) (0)	2019.07.02

한 가방에는 딱 하나의 보석만 담을 수 있기 때문에 최대한 비싼 보석을 하나라도 더 챙기는것이 중요하다.

비싼 보석인데 무겁다고 해서 더 싸고 가벼운 보석에게 가방을 양보하면 그 가방에 다른 보석을 더 담을 수 있는것도 아니기 때문에 양보한 의미가 없기 때문이다. 비싼 보석이 무겁더라도 담을만한 가방이 있다면 우선 담아야 한다.

포인트는 최대한 비싼 보석부터 최대한 작은 가방에 담는 것이다.

이 문제는 우선순위 큐를 이용해야 한다.

우선순위 큐에는 가방의 최대 크기를 넘기지 않는 무게의 모든 보석을 가격을 우선순위로 담은 후에

가방의 수만큼 꺼내면 된다.

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

import sys
from queue import PriorityQueue
 
n, k = map(int, sys.stdin.readline().split())
 
jew = []
bag = []
for i in range(n):
    jew.append(list(map(int, sys.stdin.readline().split())))
for i in range(k):
    bag.append(int(sys.stdin.readline()))
jew.sort(key = lambda item: item[1], reverse = True) 
for i in range(n):
    jew[i].insert(0, i) 
 
jew.sort(key = lambda item: item[1])  
bag.sort() 
q = PriorityQueue()
 
idx = 0
sum = 0
for i in range(k):  
    while (idx < n and bag[i] >= jew[idx][1]):  
        q.put((jew[idx][0], jew[idx][2]))
 
        idx += 1
    if not q.empty():
       sum += q.get()[1]
print(sum)
 

저작자표시

'Python > 알고리즘' 카테고리의 다른 글

알고스팟 (백준 1261, 파이썬) (0)	2019.08.31
이모티콘 (백준 14226, 파이썬) (0)	2019.08.31
재귀호출로 최댓값 구하기 (모두의 알고리즘 with 파이썬 4-2) (0)	2019.07.04
열 개씩 끊어 출력하기 (백준 11721, 파이썬) (0)	2019.07.02
1로 만들기 (백준 1463, 파이썬) (0)	2019.07.02

코딩이 가득한 코딩노트