새싹프로그래머의 이야기

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

문제: A, B가 주어졌을 때, 2를 곱하거나 수의 가장 오른쪽에 1을 붙이는 연산을 통해 A를 B로 바꾸는데 필요한 연산 횟수를 출력하는 문제

풀이 방법: top- down , bfs

1번 풀이 코드:

<top-down>

import sys

a,b = map(int,sys.stdin.readline().rstrip().split())
cnt = 0
pause = 0

while b != a and b >= a:
    cnt += 1
    if b % 10 == 1:
        b //= 10
    elif b % 2 == 0:
        b //= 2
    else:
        pause = 1
        break

if not pause and a==b:
    print(cnt+1)
else:
    print(-1)

풀이 설명:

결과 값이 주어지므로, top - down 방식으로 구현하는 방법으로 코드를 짜보았습니다.

수의 오른쪽에 1을 붙이는 연산은 반대로 수를 10으로 나눴을 때 나머지가 1이라는 뜻입니다.

*2의 연산은 반대로 나누기 2 입니다.

따라서 다음과 같이 구현하였습니다.

while문의 종료조건은 b(나눠지는 수)가 a 같거나 크면서 같지 않을 때 연산이 진행되도록 하였습니다.

if b % 10 == 1:
    b //= 10
elif b % 2 == 0:
    b //= 2
else:
    pause = 1
    break

if문과 elif 문의 조건에 부합하지 못하는 경우는 구할 수 없는 수 이므로, pause 값을 1로 설정해주고 반복문을 종료해줍니다.

if not pause and a==b:
    print(cnt+1)
else:
    print(-1)

pause에 아무런 값이 설정되지 않고 a 가 b와 동일할 경우, 연산 횟수를 출력해줍니다.

2번 풀이코드: bottom-up 방식으로 bfs 입니다.

import sys
from collections import deque

a, b = map(int,sys.stdin.readline().rstrip().split())
deq = deque([(a,1)])
tot = -1

while len(deq) > 0:
    val, cnt = deq.popleft()
    if 2 * val <= b:
        deq.append([2*val,cnt + 1])

    if val*10+1 <= b:
        deq.append([10*val + 1 , cnt+1])

    if 2*val == b or 10*val + 1 == b:
        tot = cnt + 1
print(tot)

풀이 설명:

주어진 a 부터 b를 구해 나가는 과정입니다.

if 2 * val <= b:
    deq.append([2*val,cnt + 1])

if val*10+1 <= b:
    deq.append([10*val + 1 , cnt+1])

위와 같이, 두가지 연산에 대하여 조건을 충족할 경우 deque에 값을 추가해줍니다.

if 2*val == b or 10*val + 1 == b:
    tot = cnt + 1

연산을 하다보면, 원하는 값에 도달하는 경우가 있는데 이 경우 변수에 count 값을 저장하도록 하였고

만약 값에 도달하지 못하거나 값을 넘어가게 되면 while문의 종료조건을 통해 종료 되도록 설정하였습니다.

속도는 top-down 방식이 약 2배 빠른 것으로 나왔습니다. 아마 단순 연산이기 때문에 deque를 거치는 것이 오히려 더 느린 것이 아닐까 생각합니다.

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

처음 보는 백트래킹 문제라, 고민고민 하다가 결국 풀지 못하고 백트래킹에 대해서 구글링해서 푼 문제입니다.

DFS와 다르게 되돌아간다는 개념이 정말 신기하게 다가왔던 문제였습니다.

문제: 두 개의 수 N,M이 주어졌을 때, 1부터 N까지 자연수 중 M개의 수로 구성할 수 있는 모든 오름차순 수열을 모두 구하는 문제입니다.

풀이 방법: 백트래킹

풀이 코드:

import sys

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

lst = []

def backTracking(start):
    if len(lst) == m:
        print(' '.join(map(str,lst)))
        return

    for i in range(start,n+1):
        if i not in lst:
            lst.append(i)
            backTracking(i+1)
            lst.pop()

backTracking(1)

안녕하세요. 플러터를 통해서 앱 개발을 하던 중 다음과 같이 처음 보는 에러를 만나서 정리해보고자 합니다.

애플에서는 다음과 같은 에러가 발생하는 이유를 두가지로 설명하고 있습니다.

1. 최대 활성화 가능한 프로세스 수 초과

2. 열린 파일의 최대 수 초과

즉, 말 그대로 resource가 부족한 것이기 때문에, 충분한 resource만 확보해준다면 해결 가능한 문제인거 같습니다.

이제 해결 방안 두가지를 소개해드릴텐데요. 이 두가지 방법을 통해 잘 해결 되셨으면 좋겠습니다.

첫번째로는 시스템 제한 설정을 변경하는 것입니다. 최대 활성화 가능한 프로세스 수와 파일 수를 늘려주는 것이죠.

1. Terminal을 실행시킵니다.

2. sudo launchctl limit 명령어를 실행 시킵니다.

2번 명령어를 실행 시키시면, 현재 최대 프로세스 수는 2000, 파일 수는 256개 인 것을 보실 수 있습니다.

3. sudo launchctl limit maxproc 2000 2500  : 최대 프로세스 수를 2000 -> 2500으로 변경하는 명령어입니다.

4. sudo launchctl limit maxfiles 2000 unlimited : 최대 파일 수를 256 unlimited -> 2000 unlimited로 변경하는 명령어입니다.

5. 컴퓨터 재부팅 후, 2번 명령어를 재입력해주시면 변경되신 것을 확인하실 수 있으실겁니다.

두번째로는, 불필요한 파일 / 캐시 삭제를 통해 메모리 확보하기 입니다. 

제가 활용했던 방법인데요.

순서는 다음과 같습니다.

1. 왼쪽 상단의 사과 > 이 Mac에 관하여 > 저장 공간 > 관리 > 개발자 로 들어가시게 되면 아래와 같이 Macintosh HD가 나오게 됩니다.

왼쪽 개발자를 들어가셔서 '캐시' 부분을 삭제해줍니다.

2. 휴지통을 비워줍니다.

3. 불필요한 파일, 어플리케이션을 지워줍니다.

사실 2번까지만 해도 충분하게 메모리를 충분하게 비울 수 있으실텐데,

그래도 안돌아갈 경우 3번까지 실행해보시고 에뮬레이터를 다시 실행하면 잘 동작하는 것을 볼 수 있으실겁니다.

위 방법으로 잘 해결 되셨으면 좋겠습니다 :) 

혹시나 추가로 궁금한 점 등이 있으실 경우, 댓글로 남겨주시면 답변 남겨드리겠습니다.

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

문제: 모든 주사위를 한 번씩 던졌을 때 나온 숫자들의 합의 기댓값을 구하는 문제입니다.

풀이 방법: 분할정복

풀이 코드: 

import sys
import math

n = int(input())
modular = 1000000007
total = 0
numerator = []
dominator = []


def getLcd(dominator:list):
    dom = dominator[0]
    for i in range(len(dominator)-1):
        dom = math.lcm(dom,dominator[i+1])
    return dom

def getFraction(numerator:list,dominator:list,dom):

    sumNumerator = 0

    for i in range(len(dominator)):
        sumNumerator += numerator[i] * (dom//dominator[i])
    return (sumNumerator,dom)


def DQ(num,x):
    if x == 1:
        return num
    tmp = DQ(num,x//2)
    if x % 2 == 1:
        return tmp *tmp* num % modular
    else:
        return tmp * tmp % modular


for _ in range(n):
    n, s = map(int,sys.stdin.readline().rstrip().split())
    numerator.append(s)
    dominator.append(n)

sumN, lcd = getFraction(numerator,dominator,getLcd(dominator))

total = DQ(lcd,modular-2)

print((sumN*total) % modular)

풀이 설명:

먼저 기대값을 계산하는 법에 대해서 설명을 드리겠습니다.

문제 예시인 n = 3, s = 7 일 경우,  7 * ( 3 ^ -1 ) mod 1000000007의 경우는 7 * ( 3 ^ 1000000005 ) mod 1000000007과 같습니다.

그리고 예를들어 기약 분수가 7/3 , 6/5 두개가 주어졌다면, 53/15에 대하여 연산해주면 됩니다.

표현하자면, 53 * ( 15 ^ 1000000005) mod 1000000007로요.

보시면 아시겠지만, 1000000005 제곱을 해주어야 하기 때문에 분할 정복을 활용하여 문제를 풀어주었습니다.

코드는 다음과 같이 구성하였습니다.

for _ in range(n):
    n, s = map(int,sys.stdin.readline().rstrip().split())
    numerator.append(s)
    dominator.append(n)

분자, 분모의 값은 입력 받아 리스트에 저장해주었습니다.

def getLcd(dominator:list):
    dom = dominator[0]
    for i in range(len(dominator)-1):
        dom = math.lcm(dom,dominator[i+1])
    return dom

위 코드는 분모가 될 최소 공배수를 구하는 코드입니다.

math.lcm 함수를 통해 분모들을 비교하면서 최종적인 최소공배수를 구해주었습니다.

예를 들어 3,5,7이 있다면 (3 , 5 , 7)의 최소 공배수는 3과 5의 최소 공배수인 15와 7의 최소 공배수와 동일하기 때문에 다음과 같이 구해주었습니다.

def getFraction(numerator:list,dominator:list,dom):

    sumNumerator = 0

    for i in range(len(dominator)):
        sumNumerator += numerator[i] * (dom//dominator[i])
    return (sumNumerator,dom)

그 다음은 기약분수를 구하는 코드입니다.

7/3 의 분자를 15로 바꾸어주려면 분자에도 5를 곱하여 35/15를 만들어 주어야 합니다.

따라서 구해놓은 분모들의 최소공배수를 현재 분수의 분모로 나누어 몫을 구해준 다음 

몫을 분자의 값과 곱해준 값을 모두 더해주었습니다.

(이미 분모들의 최소 공배수는 앞에서 구해주어서, 분자들의 값의 합만 구하면 주어진 분수들의 합을 구할 수 있습니다.)

그런 다음, 최종 기약 분수의 분자 분모 값을 return 해주었습니다.

def DQ(num,x):
    if x == 1:
        return num
    tmp = DQ(num,x//2)
    if x % 2 == 1:
        return tmp *tmp* num % modular
    else:
        return tmp * tmp % modular

다음은 분할정복을 통해 값을 구하는 코드입니다.

sumN, lcd = getFraction(numerator,dominator,getLcd(dominator))

total = DQ(lcd,modular-2)

print((sumN*total) % modular)

최종적으로 값을 출력하는 부분입니다.

분수들의 값을 모두 더한 분자 분모를 구해줍니다.( sumN, lcd )

원하는 값은 lcd * (sumN ^  1000000005) mod  1000000007 이므로,

sumN ^  1000000005 mod  1000000007 값을 분할 정복으로 구해줍니다.

위에서 구한 값을 lcd 와 곱한 후  1000000007 로 나눈 나머지를 구해 출력해주면 됩니다.

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

문제: 도시 간 이동하는 버스 정보와 그 비용이 주어졌을 때, 출발 도시에서 도착 도시까지 드는 최소 비용 / 최소 비용을 갖는 경로에 있는 도시의 갯수 / 최소 비용을 갖는 경로로 방문하는 도시를 순서대로  출력하는 문제입니다.

풀이 방법: 다잌스트라 알고리즘

풀이 코드:

import sys
import heapq

n = int(input())
m = int(input())

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

for _ in range(m):
    startNode, endNode, cost = map(int,sys.stdin.readline().rstrip().split())

    graph[startNode].append((cost,endNode))

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

q = [(0,start)]
route = [[] for _ in range(n+1)]
distance = [1E9] * (n+1)
distance[start] = 0

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

    if cost > distance[node]:
        continue
    for newCost, newNode in graph[node]:
        dist = newCost + distance[node]
        if dist < distance[newNode]:
            distance[newNode] = dist
            heapq.heappush(q,(distance[newNode],newNode))  # 위 코드 까지는 다잌스트라
            route[newNode] = [node] # 방문하는 경로 저장

pos = end
minRoute = [end]
while pos != start:
    minRoute.append(route[pos][0])
    pos = route[pos][0]

print(distance[end])
print(len(minRoute))
for i in minRoute[::-1]:
    print(i,end =' ')

풀이 설명:

for _ in range(m):
    startNode, endNode, cost = map(int,sys.stdin.readline().rstrip().split())

    graph[startNode].append((cost,endNode))

시작점과 도착점 정보로, 단방향성 정보가 주어집니다. 따라서 다음과 같이 그래프에 저장해주었습니다.

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

    if cost > distance[node]:
        continue
    for newCost, newNode in graph[node]:
        dist = newCost + distance[node]
        if dist < distance[newNode]:
            distance[newNode] = dist
            heapq.heappush(q,(distance[newNode],newNode))  # 위 코드 까지는 다잌스트라
            route[newNode] = [node] # 방문하는 경로 저장

이제 코드에서 핵심되는 부분은 다잌스트라 알고리즘을 통해 최소 비용 및 방문하는 도시를 탐색하는 부분입니다. 

여기서 기존 다잌스트라 알고리즘과 다른 부분은 경로를 저장해주는 부분입니다.

route[newNode] = [node] # 방문하는 경로 저장

위 코드를 통해 최소 비용의 거리가 갱신되었을 경우 , 경로를 저장하도록 하였는데요. 

값을 append로 덧붙여 주는 것이 아닌 갱신 되었을 때 해당 값만 저장하도록 하여 최소 비용에 들어가는 도시만을 저장해였습니다.

예를 들어, 출발점과 도착점을  1 -> 2, 3 -> 4 가 있다고 하였을 때,

route[ 2 ] = [ 1 ] , route[ 4 ] = [ 3 ] 과 같은 형태로 저장되게 됩니다.

도착점에 대해 시작점의 정보를 value로 가질 수 있게 저장한 것입니다.

pos = end
minRoute = [end]
while pos != start:
    minRoute.append(route[pos][0])
    pos = route[pos][0]

저장한 경로를 바탕으로 위 코드를 통해 최소비용을 갖는 루트의 각 도시 정보를 구했습니다.

최소 비용을 갖는 루트가 1 -> 4 - > 5 라고 하였을 때,

route[ 5 ] =  [ 4 ]

route[ 4 ] = [ 1 ]  와 같이 저장이 되게 됩니다.

이를 도착점 부터 탐색하여 도착점 5를 통해 중간 도시인 4를, 중간 도시 4를 통해 시작 도시 1을 배열에 저장해줍니다.

print(distance[end])
print(len(minRoute))
for i in minRoute[::-1]:
    print(i,end =' ')

마지막으로 각 정보를 출력해주는데, 거쳐간 도시의 정보는 역순으로 저장해주었으므로 역순으로 출력해주었습니다.

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

문제: 루트가 없는 트리가 주어졌을 때, 루트를 1로 하여 각 노드의 부모 노드를 출력하는 문제 입니다.

풀이 방법: bfs 

풀이 코드:

import sys
import heapq

n = int(input())

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

for _ in range(n-1):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

data = []
visited = [False] * (n+1)

def bfs():
    q = [1]
    visited[1] = True
    while q:
        parent = heapq.heappop(q)
        for node in graph[parent]:
            if not visited[node]:
                visited[node] = True
                heapq.heappush(data,(node,parent))
                heapq.heappush(q,node)

bfs()

while data:
    print(heapq.heappop(data)[1])

풀이 설명:

for _ in range(n-1):
    a,b = map(int,sys.stdin.readline().rstrip().split())
    graph[a].append(b)
    graph[b].append(a)

먼저 방향성이 없는 노드의 2개가 주어지므로, 다음과 같이 graph에 양방향으로 저장해주었습니다.

data = []
visited = [False] * (n+1)

최종적으로 값을 출력하기 위한 data를 담기 위해서 data라는 Array를 선언해주었습니다.

그리고 bfs 탐색에서 방문 여부를 저장하기 위한 visited Array를 선언했습니다.

 bfs 동작하는 방식을 보면 다음과 같습니다.

def bfs():
    q = [1]
    visited[1] = True
    while q:
        parent = heapq.heappop(q)
        for node in graph[parent]:
            if not visited[node]:
                visited[node] = True
                heapq.heappush(data,(node,parent))
                heapq.heappush(q,node)

bfs를 통해 노드를 탐색했는데, 제일 핵심되는 부분은 탐색을 하면서 (현재 노드, 현재 노드의 부모 노드) 정보를 data라는 배열에 heapq 모듈을 통해 담은 것입니다.

최종 출력 값의 요구하는 점이 2번째 노드부터 순서대로 출력하는 것입니다.

따라서, heapq 모듈의 heapq.heappush()는 (현재 노드, 현재 노드의 부모 노드) 의 형식으로 저장하게 되면 현재 노드 기준 오름차순 정렬을 해서 저장을 해주므로 heapq 모듈을 활용하였습니다. (또한 log의 시간복잡도를 가지므로, 시간복잡도 측면에서도 우수하다는 이점도 있습니다.)

저희는 1을 루트로 하기로 했으므로, 큐의 역할을 하는 배열에 1을 넣고 탐색을 시작합니다.

for node in graph[parent]:
    if not visited[node]:
        visited[node] = True
        heapq.heappush(data,(node,parent))
        heapq.heappush(q,node)

1부터 노드를 탐색하며 방문하지 않은 노드에 대해서 처리를 진행해주는데 graph의 index로 들어가는 값이 부모 노드, graph[index] 안에 담긴 값이 index의 자식 노드 라고 볼 수 있습니다.

이를 바탕으로 앞서 말씀드린 것과 같이, 이와 같이 탐색과 데이터 저장을 동시에 진행하였습니다.

while data:
    print(heapq.heappop(data)[1])

마지막으로 다음과 같이 최종 값들을 출력해주었습니다.

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

문제: 가장 긴 바이토닉 부분 수열을 출력하는 문제

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

풀이 코드:

import sys

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

dp = [1]*(n+1)
af = [1] *(n+1)

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j] >= dp[i]:
            dp[i] = dp[j] + 1

for i in range(n-1,-1,-1):
    for k in range(n-1,i-1,-1):
        if array[i] > array[k] and af[k] >= af[i]:
            af[i] = af[k] + 1

for i in range(n+1):
    dp[i] += af[i]

print(max(dp)-1)

풀이 설명:

결국은 바이토닉 수열이란 1 < k < n 을 만족하는 숫자 k,n 이 있을 때   1 ~ k번째 수까지 오름차순, k ~ n번째 수까지는 내림차순이 되는 수열을 말합니다.

따라서 저는 k번째 수가 있을 때,

k번째 수까지 구할 수 있는 오름차순 수열의 최대 길이를 구하고

수열 끝에서부터 k번째 수 까지 역순으로 보았을 때 만들 수 있는 오름차순 수열의 최대 길이를 구한 다음 두 값을 더하는 방식으로 코드를 구현하였습니다.

dp = [1]*(n+1)
af = [1] *(n+1)

먼저, k번째 수로 만들 수 있는 수열의 길이를 저장하기 위해 1로 초기화한 array를 만듭니다.

1로 초기화한 이유는 1개의 수로 길이가 1인 수열을 만들 수 있기 때문입니다.

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j] >= dp[i]:
            dp[i] = dp[j] + 1

array[ i ]로 만들 수 있는 최대 길이의 오름차순 길이는 array[ i ] 보다 작은 수 중 제일 큰 수로 만들 수 있는 길이의 + 1 입니다.

따라서, i 번째 수로 만들 수 있는 수열의 값을 구하기 위해 0 ~ i -1 번째 까지 탐색하여 array[ i ] 보다 작은 수를 찾고 그 작은 수로 만들 수 있는 수열의 길이가 array[ i ] 번째 수로 만들 수 있는 수열의 같거나 길 경우 +1 을 하여 dp에 저장해줍니다.

이렇게 되면, 다음과 같이 동작되게 됩니다.

i = 0 일 때, 제일 앞 노드이므로 아무런 동작이 일어나지 않습니다.

i = 1 일 때, 앞에 10인 노드가 있으므로 [10, 20]인 길이가 2짜리 수열을 만들 수 있습니다.

따라서 array[1] > array[0] 가 성립하고, dp[0] >= dp[1]이 성립하므로 dp[1] = dp[0] + 1  = 2도 성립합니다.

i = 2일 때는 다음과 같습니다.

먼저 j = 0일 때, 10을 만나게 되면 30 > 10이고 , dp[0]  > = dp[2] 이므로  dp[2] = 2가 됩니다.

[ 10, 30 ]인 수열을 만들 수 있으므로 맞죠.

j = 1일 때, 20을 만나게 되면 30 > 20이고, dp[1] >= dp[2] 이므로 dp[2] = 3이 됩니다.

즉, 최종적으로 [10,20,30] 인 수열로 만들 수 있는 오름차순 수열의 최대 길이를 구하게 됩니다.

for i in range(n-1,-1,-1):
    for k in range(n-1,i-1,-1):
        if array[i] > array[k] and af[k] >= af[i]:
            af[i] = af[k] + 1

수열 [30,20,10] 이 있으면 10 -> 30 으로 가는 방향으로 오름차순 수열 길이를 계산하는 코드입니다.

역순으로 탐색했을 뿐 원리는 위와 같습니다.

for i in range(n+1):
    dp[i] += af[i]

print(max(dp)-1)

10 20 30 20 10 이란 수열이 있을 때,

dp에는 10 20 30을 의미하는 값인 3이 저장되어있을 것이고

마찬가지로 af에도 30 20 10을 의미하는 값인 3이 저장되어 있을 것입니다.

그럼 30이 이중으로 세어진 것이므로 최대 값에 -1을 더해준 값을 출력해줍니다.

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

DP.. 정복까진 아니더라도 어느정도 풀 수 있는 정도로까지 올리기도 만만치 않네요..

아직 알고리즘 개념에 대한 이해가 부족한 것인지 컴퓨팅적 사고력이 부족한 것인지 조금 더 스스로 되돌아보고 부족한 부분을 찾아봐야겠습니다.

문제: 주어진 수열에서 가장 길게 증가하는 부분 수열의 길이를 구하는 문제입니다.

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

풀이 코드:

import sys

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

dp = [1]*(n+1)

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j]+1 > dp[i]:
            dp[i] = dp[j]+1

print(max(dp))

풀이 설명:

dp = [1]*(n+1)

첫번째로 모든 수열의 길이는 자기 자신만 해도 길이가 1이 되므로 길이를 저장할 배열 dp를 1로 초기화 해주었습니다.

그럼 수열의 길이는 어떻게 구할까요? 

예를 들어, 10 20 30 40 50 인 수열이 있다고 해보겠습니다.

10으로 만들 수 있는 수열은 1이 되겠죠.

그럼 20으로 만들 수 있는 수열은 자신보다 작은 수인 10을 통해 {10, 20} 을 만드는 것입니다.

30으로 만들 수 있는 수열은 자신 보다 작은 수인 [10,20]을 통해 {10, 20, 30}을 만든 것이구요.

그럼 다음과 같은 결론을 얻을 수 있습니다.현재 수로 만들 수 있는 제일 긴 수열의 길이는 자신보다 작은 수 중에서 제일 큰 수 (현재 값이 30인 경우, 20을 의미함.)로 만들 수 있는 수열의 길이 + 1이라는 것을요.

for i in range(n):
    for j in range(i):
        if array[i] > array[j] and dp[j]+1 > dp[i]:
            dp[i] = dp[j]+1

따라서, 코드를 다음과 같이 구현하였습니다.

현재 값( array[ i ] )보다  작은 값 ( array [ j ] )이 있을 경우, dp[i] = dp[j] + 1로 해주었습니다.

다만 조건문에 dp[ j ] + 1 > dp[ i ]라는 조건을 담아, dp[ j ] 에 해당되는 수열의 길이 중 제일 큰 값이 dp [ i ]에 담기도록 하였습니다.

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

문제: 이진 트리가 주어졌을 때, 전위 순회 / 중위 순회 / 후위 순회 결과를 출력하는 문제 입니다.

풀이 방법: 3가지 트리 순회

풀이 코드:

import sys

n = int(input())
binaryTree = dict()

for _ in range(n):
    root,left,right = sys.stdin.readline().rstrip().split()
    binaryTree[root] = [left,right]

def preorderTraversal(node):
    if node != '.':
        print(node,end='')
        for newNode in binaryTree[node]:
            preorderTraversal(newNode)

def inorderTraversal(node):
    if node != '.':
        newNode1, newNode2 = binaryTree[node]
        inorderTraversal(newNode1)
        print(node,end='')
        inorderTraversal(newNode2)

def postorderTraversal(node):
    if node != '.':
        for newNode in binaryTree[node]:
            postorderTraversal(newNode)
        print(node,end='')

preorderTraversal('A')
print()
inorderTraversal('A')
print()
postorderTraversal('A')

풀이 설명:

binaryTree = dict()

for _ in range(n):
    root,left,right = sys.stdin.readline().rstrip().split()
    binaryTree[root] = [left,right]

해당 노드를 직접 방문하여 어떠한 처리를 해주는 것이 아닌 노드의 위치만 구분 할 수 있으면 되므로 dictionary를 사용해주었습니다.

A의 왼쪽 노드가 B, 오른쪽 노드가 C라고 했을 때 A,B,C를 입력하게 되면

binaryTree[A] = [ B , C ]가 되어  binaryTree[A][0]는 왼쪽 노드를 binaryTree[A][1]은 오른쪽 노드를 의미하게 됩니다.

문제에서 주어진 트리는 다음과 같습니다.

def preorderTraversal(node):
    if node != '.':
        print(node,end='')
        for newNode in binaryTree[node]:
            preorderTraversal(newNode)

전위 순회는 현재 노드 - 왼쪽 서브 트리 - 오른쪽 서브 트리 순으로 순회하는 방식을 말합니다.

따라서, node에 대한 출력을 먼저 해준 후, 왼쪽 트리부터 순회를 시작합니다.

다음과 같이 탐색을 하게 된다면, binaryTree[node][0]가 왼쪽 노드를 의미하므로 왼쪽 먼저 탐색을 진행한 후, 오른쪽 노드를 탐색하게 됩니다.

문제에서 주어진 트리를 예시로 보자면,  A - B -D - C - E - F -G 순으로 탐색하게 됩니다.

def inorderTraversal(node):
    if node != '.':
        newNode1, newNode2 = binaryTree[node]
        inorderTraversal(newNode1)
        print(node,end='')
        inorderTraversal(newNode2)

다음은 중위 순회입니다. 중위 순회는 왼쪽 서브트리 - 현재 노드 - 오른쪽 서브트리 순으로 순회하는 방식입니다.

다음과 같이 코드를 구성해 왼쪽 서브 트리 순회 후 현재 노드를 출력되게 한 후, 오른쪽 서브트리를 순회 하도록 코드를 구성하였습니다.

def postorderTraversal(node):
    if node != '.':
        for newNode in binaryTree[node]:
            postorderTraversal(newNode)
        print(node,end='')

마지막으로 후위 순회 입니다. 후위 순회는 왼쪽 서브트리 - 오른쪽 서브 트리 - 현재 노드 순으로 순회하는 방식입니다.

따라서 다음과 같이 왼쪽 - 오른쪽 서브 트리를 모두 순회한 후 현재노드를 출력하는 방식으로 코드를 구현하였습니다.

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

문제: 임의의 수열에서 몇 개의 수를 선택하여 구할 수 있는 수 중  가장 큰 값을 구하는 문제 입니다.

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

풀이 코드:

import sys

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

dp = [0] * n

dp[0] = array[0]

for i in range(1,n):
    dp[i] = max(dp[i-1]+array[i],array[i])

print(max(dp))

임의의 몇개를 구해서 최대가 되는 값을 구하는 문제 이므로, 이전까지의 연속 합 + 현재 값  / 현재 값을 비교해서 더 큰 값을 dp에 저장해 줍니다.

<문제 예시> 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 를 들어 설명해보겠습니다.

10 -4 3 1 5 6을 거치면서

dp = [10,6,9,10,15,21]이 저장됩니다.

이후 -35를 만나게 되면

dp[6]에는 -14가 저장되게 됩니다.

여기에서 저 연산이 빛을 발휘하게 됩니다.

12을 만났을 경우, dp[7]에는 -14 + 12 = -2가 아닌 12가 저장되게 됩니다.

즉, 이전까지 선택된 연속된 값이 현재 값보다 작으므로 12부터 다시 선택하게 되는 효과를 발휘하는 것입니다.

최종 dp에는 [10, 6, 9, 10, 15, 21, -14, 12, 33, 32] 값이 담겨서 

제일 큰 값을 출력해주게 되면 선택할 수 있는 연속된 수 중 제일 큰 합을 구할 수 있습니다.