새싹프로그래머의 이야기

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

문제: 정수 삼각형이 주어졌을 때, 맨 위층부터 맨 아래층 까지 도달할 수 있는 경로 중 경로에 있는 값의 합이 최대가 되는 값을 구하는 문제입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys
input = sys.stdin.readline

n = int(input())

triangle = []

for _ in range(n):
    triangle.append(list(map(int,input().rstrip().split())))
if n == 1:
    print(triangle[0][0])
    sys.exit(0)

for i in range(2):
    triangle[1][i] += triangle[0][0]


for i in range(2,n):
    for j in range(len(triangle[i])):
        triangle[i][j] += triangle[i-1][j] if j == 0 else triangle[i-1][j-1] if j ==(len(triangle[i])-1) else max(triangle[i-1][j-1],triangle[i-1][j])

print(max(triangle[n-1]))

풀이 설명:

풀이 코드에서 핵심 코드인 다음 코드를 설명하고 넘어가겠습니다.

for i in range(2,n):
    for j in range(len(triangle[i])):
        triangle[i][j] += triangle[i-1][j] if j == 0 else triangle[i-1][j-1] if j ==(len(triangle[i])-1) else max(triangle[i-1][j-1],triangle[i-1][j])

각 줄의 양 끝 값은 이 전줄의 하나의 값이랑만 연결이 되기 때문에,

j == 0 일 경우, triangle[i - 1][j] 가 더해지게 했고

j == len(triangle[i]) - 1 일 경우, triangle[i - 1][j - 1]이 더해지게 하였습니다. 이때 인덱스가 (i - 1, j - 1)인 이유는 이전 줄은 현재 줄보다 길이가 1 작기 때문입니다.

마지막으로, 양 끝 값이 아닌 경우에는 이 전줄의 2개의 값과 연결이 되기 때문에

이어지는 두개의 값중 큰 값을 더하도록 하였습니다.

이 코드를 한줄로 표현하면 다음과 같이 나옵니다.

triangle[i-1][j] if j == 0 else triangle[i-1][j-1] if j ==(len(triangle[i])-1) else max(triangle[i-1][j-1],triangle[i-1][j])

 이 코드를 풀어 쓴다면 다음과 같이 나옵니다.

if j == 0 :
    triangle[i][j] += triangle[i - 1][j]
    
elif j ==(len(triangle[i])-1):
    triangle[i][j] += triangle[i-1][j-1]

elif 0 < j < (len(triangle[i])-1):
    triangle[i][j] += max(triangle[i - 1][j - 1], triangle[i - 1][j])

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

저번주 부터 다이나믹 프로그래밍 문제를 계속해서 못풀어서 한참 고생했습니다..

기초도 중요하지만 문제를 봤을 때, 사고하는 능력 또한 기를 필요가 있다고 느꼈습니다.

문제: 집의 색이 연속되지 않으면서, 집을 색칠 하는 비용 중 최소인 비용 찾는 문제 입니다.

풀이 방법: 다이나믹 프로그래밍

풀이 코드:

import sys

n = int(sys.stdin.readline())

rgb = []

for _ in range(n):
    rgb.append(list(map(int,sys.stdin.readline().rstrip().split())))

for i in range(1,n):
    rgb[i][0] = min(rgb[i-1][1],rgb[i-1][2]) + rgb[i][0]
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]

print(min(rgb[n-1]))

풀이 설명:

rgb의 비용을 연산하는 for문을 보면 다음과 같습니다.

for i in range(1,n):
    rgb[i][0] = min(rgb[i-1][1],rgb[i-1][2]) + rgb[i][0]
    rgb[i][1] = min(rgb[i - 1][0], rgb[i - 1][2]) + rgb[i][1]
    rgb[i][2] = min(rgb[i - 1][0], rgb[i - 1][1]) + rgb[i][2]

빨간색일 때, 현재 집의 비용에 이전 순서의 초록&파랑색 집의 비용중 최소 값을 더해줍니다.

초록색일 경우, 현재 집의 비용에 이전 순서의 빨강&파랑색 집의 최소 비용을 더해주고

파랑색일 경우, 현재 집의 비용에 이전 순서의 빨강&초록색 집의 최소 비용을 더해줍니다.

이렇게 되면 마지막 집의 비용이 담긴 배열에는 마지막 집의 색상 별로 전체 비용이 담기게 됩니다.

이를 다음과 같이 min 함수를 이용하게 되면 전체 비용중 최소 값이 출력되게 됩니다.

print(min(rgb[n-1]))

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

이번주 내내 solved.ac의 클래스 4에서 다이나믹 프로그래밍 문제를 3문제를 연달아 못풀었다..

그래서 당분간은 다이나믹 프로그래밍 문제를 풀어가며 해당 알고리즘을 공부해볼 생각이다.

문제:  2xn 타일이 주어졌을 때, 1x2 와 2x1 타일로 채울 수 있는 경우의 수를 구하는 문제입니다.

풀이 방법: 다이나믹 프로그래밍으로 풀었습니다.

풀이 코드:

n = int(input())
dp = [0,1,2,3]



if n <= 3:
    print(dp[n])
else:
    for i in range(4,n+1):
        dp.append(dp[i-1] + dp[i-2])

    print(dp[n] % 10007)

풀이 설명:

n = 1일 때, 만들 수 있는 경우의 수는 1개 입니다.

n = 2일 때는, 2x1 타일로만 구성할 수도 있고 1x2 타일로만 구성할 수 있으므로 2개 입니다.

n = 3일 때는 3가지

n= 4일 때는 5가지

n = 5일 때는 8가지가 나오는 것을 알 수 있었습니다.

이를 바탕으로, 점화식 f(n) = f(n-1) + f(n-2)  ( n >= 3 ) 을 구할 수 있었고

이 점화식을 위 코드로 구현하여 문제를 해결하였습니다.

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

처음 다익스트라 문제를 풀었을 때는, 코드를 짜는데 시간이 되게 오래 걸렸었습니다.

근데, 골드 4 난이도임에도 빠른 시간 내에 코드를 짜서 살짝 울컥했습니다.

공부해왔던게 효과가 있구나 라는 생각과 동시에 저도 모르게 살짝 울컥하더라구요.. 너무 뿌듯했습니다.

이런 기분때문에 공부를 계속할 수 있는 것 같습니다.

코딩 공부하는 모든 분들도 성취감을 느껴가며 즐겁게 공부하셨으면 좋겠습니다!

문제: 방향그래프가 주어졌을 때, 모든 정점으로의 최단거리를 구하는 문제입니다.

풀이 방법: 다익스트라 알고리즘을 활용하였습니다.

풀이 코드:

import sys
import heapq

INF =1e9

v,e = map(int,sys.stdin.readline().split())

k = int(input())

graph = [[]for _ in range(v+1)]

dist = [INF] * (v+1)
dist[k] = 0

for _ in range(e):
    start, end, cost= map(int,sys.stdin.readline().split())
    graph[start].append((cost,end))

def dijkstra(k):
    queue = []
    heapq.heappush(queue,(0,k))

    while queue:
        cost,node = heapq.heappop(queue)

        for nextCost,nextNode in graph[node]:
            distance = dist[node] + nextCost
            if distance < dist[nextNode]:
                dist[nextNode] = distance
                heapq.heappush(queue,(distance,nextNode))

dijkstra(k)

for i in range(1,v+1):
    if dist[i] == INF:
        print('INF')
    else:
        print(dist[i])

풀이 설명:

핵심은 다익스트라 알고리즘 이므로, 다익스트라 알고리즘을 보고 가겠습니다.

def dijkstra(k):
    queue = []
    heapq.heappush(queue,(0,k))

초기 값은 다익스트라 함수에 주어진 시작 노드 입니다.

이때 cost는 0으로 설정하여 heapq에 넣어줬습니다.

while queue:
    cost,node = heapq.heappop(queue)

    for nextCost,nextNode in graph[node]:
        distance = dist[node] + nextCost
        if distance < dist[nextNode]:
            dist[nextNode] = distance
            heapq.heappush(queue,(distance,nextNode))

이후 비용을 계산하는 반복문 입니다.

heapq에서 순차적으로 값을 꺼내옵니다.

cost와 node가 꺼내지는데요.  다음과 같이 heapq에서 꺼내진 node로 부터 연결된 노드들을 탐색합니다.

for nextCost,nextNode in graph[node]:
    distance = dist[node] + nextCost
    if distance < dist[nextNode]:
        dist[nextNode] = distance
        heapq.heappush(queue,(distance,nextNode))

node - newNode까지의 거리를 계산하고, 거리를 저장하는 배열인 dist에 저장된 값과 비교해줍니다.

현재 계산된 거리의 Cost가 더 낮을 경우, dist배열에 갱신해주고 갱신된 Cost와 함께 heapq에 넣어주는 과정을 반복시킵니다.

이를 통해, 시작 노드로 부터 연결된 모든 노드들을 탐색하게 됩니다.

다익스트라처럼 다른 알고리즘들도 잘 활용할 수 있도록 공부하자는 마음을 다잡는 문제였습니다.

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

문제: 숫자 A,B,C 가 주어졌을 때, A를 B번 곱했을 때 C로 나눈 나머지를 구하는 문제입니다.

풀이 방법: 분할 정복 방식으로 풀었습니다.

풀이 코드:

import sys

a,b,c = map(int,sys.stdin.readline().split())

def DivideAndConquer(num1,num2):
    if num2 == 1:
        return num1 % c

    tmp = DivideAndConquer(num1,num2//2)
    if num2 % 2 == 0:
        return tmp ** 2 % c
    else:
        return tmp**2 * num1 % c
print(DivideAndConquer(a,b))

풀이 설명:

나누는 수인 b가 짝수일 경우와 홀수일 경우를 나누어 생각했습니다.

입력 예제인 10,11,12로 예시를 들어보겠습니다.

b가 짝수 일 경우(a= 10, b = 10 ,c =12), 10^5 * 10^5로 나눌 수 있습니다.

b가 홀수 일 경우에는 (a=10, b=11, c=12), 10^5 * 10^5 * 10으로 나눌 수 있죠.

위와 같은 분할에다가, 나머지연산에 다음과 같이 분배 법칙을 적용할 수 있습니다.

(a*b)%c = ((a%c) * (b%c)) % c 로 분배법칙이 성립하죠.

분할과 분배법칙을 적용하여, 문제가 풀리도록 코드를 구성해주었습니다.

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

문제: 주어진 숫자 카드에 대해서, 각 수가 적혀진 숫자카드가 몇장 있는지 출력하는 문제입니다.

풀이 방법: heapq를 사용했습니다. 

이진 탐색 문제인 것은 알았습니다.

다만, 주어진 값들을 count 하면 되는 문제이므로 heapq.heappop()이 이진 탐색과 같은 log의 시간 복잡도를 갖는다는 것을 활용하였습니다.

풀이 코드:

import heapq
import sys

MAX = 10000000 * 2 + 2

n = int(sys.stdin.readline().rstrip())
lst = list(map(int,sys.stdin.readline().rstrip().split()))

m = int(sys.stdin.readline().rstrip())
lst2 = list(map(int,sys.stdin.readline().rstrip().split()))

count = [0] * MAX

while lst:
    count[heapq.heappop(lst)] += 1


for i in range(m):
    print(count[lst2[i]],end = ' ')

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

문제: 주어진 괄호로 이루어진 문자열이 올바른 괄호 문자열인지 판단하는 문제입니다.

풀이 방법: stack(list)을 활용하여 '(' 에 대해서 ')'가 맞게 있는지 확인하였습니다.

풀이 코드:

import sys

t = int(sys.stdin.readline())
for _ in range(t):
    stack = []
    ps = list(sys.stdin.readline().rstrip())
    vps = True

    for nps in ps:
        if nps =='(':
             stack.append(nps)
        else:
           if stack:
               stack.pop()
           else:
               vps = False
               break

    if vps and not stack:
        print('YES')
    else:
        print('NO')

풀이 설명:

for nps in ps:
    if nps =='(':
         stack.append(nps)
    else:
       if stack:
           stack.pop()
       else:
           vps = False
           break

여기가 핵심 코드인데요. 

입력 값을 하나씩 확인하면서 '(' 를 만날 경우, stack에 담아줍니다.

그러고 난 후, ')'를 만날 경우, stack에서 '(' 를 하나씩 pop 해주게 되면, '()'가 이루어집니다.

이때, ')' 가 '('  보다 많아서 입력받은 문자열은 남아있는데, stack이 빈 경우가 생기게 됩니다. 

혹은 '')(' 패턴이 들어간 경우에도 stack이 빈 경우가 생기게 됩니다. ex. ')('  '()  )(  ()'

if stack:
    stack.pop()
else:
    vps = False
    break

위 코드를 통해, stack이 비었는지 여부를 확인해주고 만약에 비었다면 ')' 갯수가 더 많은 것이므로 vps라는 변수에 False를 설정하고 break 해줍니다.

만약 반복문이 종료가 되었을 때, ')'  갯수가 적어서 '(' 이 남아있는 경우가 있으므로 이 부분도 신경써줘야 합니다.

if vps and not stack:
    print('YES')
else:
    print('NO')

위 코드와 같이, 구성해줬는데요.

vps가 True, 그리고 stack이 빈 경우에만 'YES'를 출력하고 이외에는 다 'NO'를 출력하도록 설정되어있습니다.

')' 갯수가 많거나 ')(' 패턴이 있다면, vps가 False 일 것이고 

')' 갯수가 적을 경우, stack에 '(' 이 남아있을 것이므로 'NO'가 출력되게 될 것입니다.

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

문제: 고속도로 길이와 지름길이 주어졌을 때, 고속도로를 운전해야하는 최소 거리를 구하는 문제 입니다.

풀이 방법:  다이크스트라 알고리즘을 활용하였습니다. 알고리즘을 활용하여, 지름길 정보에 대해 계속해서 갱신해주는 방식을 사용하였습니다.

풀이 코드:

import sys
import heapq
MAX = 10001

n,d = map(int,sys.stdin.readline().rstrip().split())

road = [[]*(MAX) for _ in range(MAX)]
heap = []
dist = [i for i in range(MAX)]

for _ in range(n):
    start, end, cost = map(int,sys.stdin.readline().rstrip().split())
    heapq.heappush(heap,(end,start,cost))

while heap:
    newEnd, newStart, newCost = heapq.heappop(heap)

    if newCost > (dist[newEnd] - dist[newStart]) or newEnd > d:
        continue

    distance = dist[newStart] + newCost

    if dist[newEnd] > distance:
        dist[newEnd] = distance

    for i in range(newEnd+1,MAX):
        dist[i] = min(dist[i],dist[i-1]+1)

print(dist[d])

풀이 설명:

dist = [i for i in range(MAX)]

먼저 지름길이 없을 경우에는 목적지 x 까지 주행해야 하는 거리는 x이므로, 다음과 같이 저장해줬습니다.

for _ in range(n):
    start, end, cost = map(int,sys.stdin.readline().rstrip().split())
    heapq.heappush(heap,(end,start,cost))

지름길에 대한 정보를 heapq를 활용해 저장하였습니다. 다만 저장할 때, 출발점으로부터 가까운 지름길 정보부터 갱신해주기 위해 (end,start,cost)형태로 저장하였습니다.

*heapq.heappush를 사용하면 end 값 기준으로 오름차순 정렬하여 데이터가 저장됩니다.

while heap:
    newEnd, newStart, newCost = heapq.heappop(heap)

    if newCost > (dist[newEnd] - dist[newStart]) or newEnd > d:
        continue

    distance = dist[newStart] + newCost

    if dist[newEnd] > distance:
        dist[newEnd] = distance

그런 다음 저장된 값을 순차적으로 접근하면서, 지름길에 대한 정보를 업데이트 해줬습니다. 

기존에 다른 지름길을 통해 이미 end값 까지 도착하는 거리가 갱신되었을 수 있으므로, if문을 통해 현재 계산된 거리와 기존에 저장된 거리를 비교하여 최소값을 저장해주었습니다.

for i in range(newEnd+1,MAX):
    dist[i] = min(dist[i],dist[i-1]+1)

마지막으로, 지름길 정보가 갱신 될 때 마다 지름길에 대한 정보를 전체 거리정보가 담겨있는 dist에 업데이트 해줬습니다.

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

어제 1916번 최소비용 구하기 문제를 풀며, 아직 다익스트라 알고리즘에 대해 이해가 부족하다고 느껴 해당 문제를 찾아서 풀어봤습니다.

문제: 도시의 개수, 도로의 개수, 찾고자 하는 거리 정보, 출발 도시의 번호, 그리고 도로의 정보가 주어졌을 때, 거리가 K인 도시를 찾는 문제입니다.

풀이 방법: 다익스트라 알고리즘을 활용했습니다.

풀이 코드:

import sys
import heapq


n,m,k,x = map(int, sys.stdin.readline().rstrip().split())
graph = [[] *(n+1) for _ in range(n+1)]

for _ in range(m):
    node1, node2 = map(int,sys.stdin.readline().rstrip().split())

    graph[node1].append(node2)

q = [(0,x)]

dist = [1E9] * (n+1)
dist[x] = 0

while q:
    cost, node = heapq.heappop(q)

    if dist[node] < cost: continue

    for i in graph[node]:
        newCost, newNode = 1, i

        distance = newCost + cost
        if dist[newNode] > distance:
            dist[newNode] = distance
            heapq.heappush(q,(distance,newNode))
        else:
            continue

if dist.count(k) == 0:
    print(-1)
else:
    for j in range(1,n+1):
        if dist[j] == k:
            print(j)

풀이 설명:

graph에는 도시 ~ 도시 까지 도로 정보를 담습니다. 

for _ in range(m):
    node1, node2 = map(int,sys.stdin.readline().rstrip().split())

    graph[node1].append(node2)

graph에는 도시 ~ 도시 까지 도로 정보를 담습니다. 

q = [(0,x)]

dist = [1E9] * (n+1)
dist[x] = 0

그리고 heapq에는 (거리, 도시)의 값이 들어 갑니다. 초기 값은 (0, 시작 도시)로 설정합니다.

dist는 거리를 계산하여 담을 배열로 시작점 ~ 시작점의 거리는 0이므로, 0으로 설정해줍니다.

while q:
    cost, node = heapq.heappop(q)

    if dist[node] < cost: continue

    for i in graph[node]:
        newCost, newNode = 1, i

        distance = newCost + cost
        if dist[newNode] > distance:
            dist[newNode] = distance
            heapq.heappush(q,(distance,newNode))
        else:
            continue

while문을 통해서 갈 수 있는 도시들의 정보를 꺼냅니다.

다음 heapq를 통해 얻은 정보를 통해 for문으로 graph에서 연결된 도시 정보를 끌어옵니다.

마지막으로 연결된 도시의 거리정보를 계산한 다음 계속해서 거리정보 값들 중 작은 값으로 거리 값을 갱신해줍니다.(dist 배열)

시작점 = 1, 도로 정보 (1,2) (2,3) (3,4) 가 주어졌다고 가정해보겠습니다. 

위 예시를 통해 자세히 설명하자면, heapq에는 초기값 (0,1)가 들어갔다가 while 문 안에서 (0,1)이 pop 되겠죠.

그럼 for문을 통해 1에서 갈 수 있는 2의 값이 꺼내지고(in graph[1]), 도시 1에서 2로 가는 거리의 값인 1이 dist[2]의 값으로 계산 된 후 다시 heapq에는 (1(dist),2(node))가 들어가게 됩니다.

그럼 다음 싸이클에서는 newCost = 1, newNode = 2가 나오게 되고, for문을 통해 2에서 갈 수 있는 노드를 찾게되겠죠.

그럼 또 (2,3)인 도로 정보가 graph[2]에 담겨있으니, 이번에는 1->2까지의 거리 + 2->3까지의 거리가 계산된 후 (2(dist),3(node))

결과적으로 노드 4까지 도달하게 되면, 1에서 2,3을 거쳐 4까지 도달하는 최소 거리가 계산되게 됩니다.

if dist.count(k) == 0:
    print(-1)
else:
    for j in range(1,n+1):
        if dist[j] == k:
            print(j)

시작점으로 부터 도달할 수 있는 모든 노드의 거리 정보를 계산하고 나면, 다음 구문을 통해 요구하는 결과 값을 출력해줍니다.

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

solved.ac의 class 4로 진입했는데 갑자기 난이도가 너무 높아져서 당황했습니다. 진짜 해결 방안이 쉽사리 떠오르지 않더라구요. 

문제 푸는데 시간이 꽤 오래 걸린 문제였습니다...

문제: 도시 ~ 도시의 비용이 주어졌을 때, 출발 도시에서 도착 도시까지의 최소비용을 구하는 문제 입니다.

풀이 방법: heapq를 이용하여 최소 cost 계산.

풀이 설명:

일단 입력 값에 대해 다음과 같이 graph를 구성하였습니다.

for _ in range(m):
    node1, node2, value = map(int,sys.stdin.readline().rstrip().split())
    graph[node1].append((value,node2))

이때, 값을 (value,node) 순으로 구성한 이유는 heapq를 비용 기준으로 활용할 계획이기 때문입니다.

graph와 heapq를 통해 시작점으로 부터 갈 수 있는 노드의 비용들을 탐색하고, 이 과정에서 도착 노드에 대해 나오는 결과 값들 중 최소 값만 저장되도록 다음과 같이 코드를 작성하였습니다 . 

heapq.heappush(heap, [0, start])# 초기 값을 시작점으로 setting
dist[start] = 0# 시작점 cost = 0

while heap:
    cost, node = heapq.heappop(heap)

    if cost > dist[node]:
        continue

    for i in graph[node]:# 시작점으로부터 도달할 수 있는 노드 탐색
        nextCost, nextNode = i
        distance = nextCost + cost

        if dist[nextNode] > distance:
            dist[nextNode] = distance# 기존 입력된 거리와 새로 계산된 거리의 최소 값 저장
            heapq.heappush(heap, [distance, nextNode])
        else:
            continue

풀이 코드:

import sys
import heapq

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())

graph = [[]*(n+1) for _ in range(n+1)]
dist = [1E9]*(n+1)
heap = []

for _ in range(m):
    node1, node2, value = map(int,sys.stdin.readline().rstrip().split())
    graph[node1].append((value,node2))

start, destination = map(int,sys.stdin.readline().rstrip().split())

heapq.heappush(heap, [0, start])# 초기 값을 시작점으로 setting
dist[start] = 0# 시작점 cost = 0

while heap:
    cost, node = heapq.heappop(heap)

    if cost > dist[node]:
        continue

    for i in graph[node]:# 시작점으로부터 도달할 수 있는 노드 탐색
        nextCost, nextNode = i
        distance = nextCost + cost

        if dist[nextNode] > distance:
            dist[nextNode] = distance# 기존 입력된 거리와 새로 계산된 거리의 최소 값 저장
            heapq.heappush(heap, [distance, nextNode])
        else:
            continue
print(dist[destination])