Coding 공부

def preorder(key):
    if tree[key] == ('.','.'):
        result[0] += key
        return
    result[0] += key
    if tree[key][0] != '.':
        preorder(tree[key][0])
    if tree[key][1] != '.':
        preorder(tree[key][1])

def inorder(key):
    if tree[key] == ('.','.'):
        result[1] += key
        return
    if tree[key][0] != '.':
        inorder(tree[key][0])
    result[1] += key
    if tree[key][1] != '.':
        inorder(tree[key][1])
def postorder(key):
    if tree[key] == ('.','.'):
        result[2] += key
        return
    if tree[key][0] != '.':
        postorder(tree[key][0])
    if tree[key][1] != '.':
        postorder(tree[key][1])
    result[2] += key


tree = {}


N = int(input())
for _ in range(N):
    root,left,right = input().split()
    tree[root] = (left,right)
result = ['','','']
preorder('A')
inorder('A')
postorder('A')

for answer in result:
    print(answer)

트리의 대표적인 순회 종류인 전위, 중위, 후위 탐색기법을 적용시킨 것이다. 트리에 대해서 아직 잘 몰라, 실제 이진 트리를 만들면서 더 연습해봐야겠다.

일단 풀이는 재귀방식을 이용해서, 구해줬다. 일단 

전위 순회 방식은 (루트 -> 왼쪽 -> 오른쪽 자식) 이므로, 함수를 돌릴때 root에 해당되는 함수에 들어온 key를 결과값에 넣어주고, 그 다음에 왼쪽 , 오른쪽 순으로 함수를 재귀적으로 실행시켜줬다.

중위 순회는 왼쪽 -> 루트 -> 오른쪽 순으로 해줬다.

후위 순회는 왼쪽 -> 오른쪽 -> 루트  순으로 해줬다.

# 11047 동전_0

N,K = map(int,input().split())
coins = []

for _ in range(N):
    coins.append(int(input()))
start = len(coins)-1
cnt = 0
while K > 0:
    if K - coins[start] >= 0:
        K -= coins[start]
        cnt += 1
    else:
        start -= 1


print(cnt)

이 문제는 목표하는 금액에서 내가 가지고 있는 큰 돈 부터 빼주면서 0보다 크거나 같으면 빼주면서 coin 번호를 하나씩 줄여주면서 풀었다. 

# 13549 숨바꼭질 3
import collections
import sys

for _ in range(1000):
    start,end = map(int,input().split())
    dp = [-1]*100001
    dp[start] = 0
    dq = collections.deque()
    dq.append((start,0))
    if start == end:
        print(0)
    else:
        while True:
            x,time = dq.popleft()
            nx = 2*x
            while 0<nx <=100000:
                if dp[nx] == -1:
                    dp[nx] = time
                    dq.append((nx,time))
                nx = 2*nx
        
            if dp[end] != -1:
                break
            for nx in [x+1,x-1]:
                if 0<=nx<=100000:
                    if dp[nx] == -1:
                        dp[nx] = time + 1
                        dq.append((nx,time+1))
        
        print(dp[end])

첫 풀이 방식이다.  bfs처럼 풀었는데 단 조건은 두가지 경우를 나눠서 먼저했다. 먼저 해당위치에서 2배에 해당되는 것들만 먼저 방문을 해줬다. 왜냐하면 이동시간이 0초이기 때문이다. 그리고 난뒤 1초가 걸리는 +1,-1을 해주고 bfs 형식으로 풀어줬다.

start,end = map(int,input().split())
dp = [-1]*100001
dp[start] = 0
stack = [(start,0)]
if start == end:
    print(0)
else:
    while stack:
        new_stack = []
        for x,time in stack:
            for ind,nx in enumerate([2*x,x+1,x-1]):
                if 0<=nx<100001:
                    if dp[nx] == -1:
                        if ind == 0:
                            dp[nx] = time
                            new_stack.append((nx,time))
                        else:
                            dp[nx] = time +1
                            new_stack.append((nx,time+1))
        if dp[end] != -1:
            print(dp[end])
            break
        new_stack.sort(key=lambda x :(x[1]))
        stack = new_stack

ㅇ위와 똑같은 풀이이다. 하지만 여기서 달라진점은, 위에는 한개씩 진행한거에 반해 여기는 한단계씩 지금 내가 보유한 stack이 갈 수 있는 모든 곳을 다 넣어서, bfs를 돌린다는 것이다. 그리고 기준점은 시간이기때문에 시간을 기준으로 sort를 해주었다.

import heapq
start,end = map(int,input().split())
dp = [-1]*100001
dp[start] = 0

stack = []
heapq.heappush(stack,(0,start))
if start == end:
    print(0)
else:
    while stack:
        time,x = heapq.heappop(stack)
        for ind,nx in enumerate([2*x,x+1,x-1]):
            if 0<=nx<100001:
                if dp[nx] == -1:
                    if ind == 0:
                        dp[nx] = time
                        heapq.heappush(stack,(time,nx))
                    else:
                        dp[nx] = time +1
                        heapq.heappush(stack,(time+1,nx))
        if dp[end] != -1:
            print(dp[end])
            break

이 문제를 풀고보니 알고리즘 분류에 다익스트라가 있어서 그 방식으로 풀어본 코드이다. heapq를 이용한 방식이다.

import sys


def prime_num(num):
    sieve = [True]*num
    sieve[1] = False
    m = int(num**0.5) + 1

    for i in range(2, m):
        if sieve[i] == True:
            for j in range(i+i, num, i):
                sieve[j] = False

    return sieve



prime_list = prime_num(10001)
for t in range(int(input())):
    N = int(sys.stdin.readline())
    for number in range(N//2,0,-1):
        other_number = N - number
        if prime_list[other_number] and prime_list[number]:
            print(number,other_number)
            break

골드바흐의 추측 문제이다. 정수론에 관련된 문제로 소수를 구해서, 소수를 더해서 나오는 경우를 구하는데 그 중 두 소수의 차이가 작은 소수를 구하는 것이다.

구하는 방법은 다음과 같다. 먼저 나올 수 있는 경우가 1~10000이니깐, 1~10000 사이의 소수들을 전부 구해준다. 

그리고 난뒤 두 소수 차이가 가장 적은 경우를 구하는 경우이니깐 주어진 수 N의 절반인 N//2 부터 시작해서 0까지 반복을 하면서, 두 수가 전부 소수인 경우를 구해주면 된다.

# 1107 리모컨
def dfs(cnt,number):
    global min_result,N
    if cnt > 6:
        return
    else:
        if min_result == 0:
            return
        temp = abs(int(number) - N)+cnt
        if temp < min_result:
            min_result = temp
        for k in possible_button:
            dfs(cnt+1,number+str(k))




N = int(input())
K = int(input())
if K != 0:
    button_not = set(map(int,input().split()))
else:
    button_not = set()
allbutton = set(range(10))
possible_button = allbutton - button_not
min_result = abs(N-100)

for i in possible_button:
    dfs(1,str(i))
print(min_result)

문제를 풀 기본적인 컨셉은 재귀함수를 통해, 모든 경우에 대해서 전부 해보고, 6자리를 넘어가는 경우에는 되돌려줬다. 그리고 각 숫자에서 up,down버튼을 눌렀을때의 경우를 찾아서 결과값을 갱신해주었다.

여기서 처음 틀렸을때는, 아무 버튼도 고장나지않았을때이다. 그래서 입력 오류로 틀렸었다.

여기서는 최소가 나오더라도 계속 탐색을 하기 때문에 시간이 많이 걸린다. 개선된 풀이는 다음과 같다.

N = int(input())
K = int(input())

if K:
    button_not = set(map(int,input().split()))
else:
    button_not = set()

allbutton = set(range(10))
possible_button = allbutton - button_not
down_num = 1000000
up_num = 1000000
min_result = abs(N-100)
for num in range(N,1000001):
    for k in str(num):
        if int(k) not in possible_button:
            break
    else:
        down_num = num
        break

for num in range(N,-1,-1):
    for k in str(num):
        if int(k) not in possible_button:
            break
    else:
        up_num = num
        break
if abs(up_num-N) <= abs(down_num-N):
    close_num = up_num
else:
    close_num = down_num
print(min(len(str(close_num))+abs(N-close_num),min_result))

풀이의 접근은 다음과 같다. 우리가 틀려는 채널의 번호를 기준으로 위아래로 번호를 하나씩 늘리면서 가능한 번호인지 확인한다. 그렇게 구한 두수를 채널 번호와의 차이를 구한다. 그리고 그중에서 차이가 더 적은 번호를 선택을 한다. 만약에 둘의 차이가 같을시에는, 밑에 있는 번호가 자리수가 더 작을수 있으니, 아래번호를 선택한다.

이렇게 구한 채널번호를 누르고 위아래 버튼을 누르는 경우와, 처음부터 위아래 번호를 누르는 경우를 비교해서 더 낮은 경우를 선택한다.

# 15591 MooTube

N,Q = map(int,input().split())

graph = {i:[] for i in range(N+1)}

for _ in range(N-1):
    A,B,USADO = map(int,input().split())
    graph[A].append((B,USADO))
    graph[B].append((A,USADO))


for _ in range(Q):
    K,start = map(int,input().split())
    visited = [True]*(N+1)
    visited[start] = False
    stack = [(start,float('inf'))]
    result = 0
    while stack:
        node,usado = stack.pop()

        for next_node,next_usado in graph[node]:
            next_usado = min(usado,next_usado)
            if next_usado >= K and visited[next_node]:
                result += 1
                stack.append((next_node,next_usado))
                visited[next_node] = False
    print(result)

그래프을 활용한 문제이다. 여기서는 주어진 node를 기준으로 연결이 되어있는 것을 전부 확인하면서, 최소 USADO를 갱신해주면 된다. 그래서 만약에 중간에 주어진 K보다 USADO가 나올시에는 멈추도록해주고, 그외에 방문하지 않은 노드이고, K보다 큰 usado일때에는 stack에 넣어서 계속 check를 해주었다.

# 1987 알파벳

def dfs(x,y,visited,cnt):
    global result,const,ccs
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx< R and 0<= ny<C and visited[ord(arr[nx][ny])-const]:
            visited[ord(arr[nx][ny])-const] = False
            dfs(nx,ny,visited,cnt+1)
            visited[ord(arr[nx][ny])-const] = True
    if cnt > result:
        result = cnt
ccs = 0
R,C = map(int,input().split())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(input()) for _ in range(R)]
result = 1
visit = [True]*26
const = ord('A')
visit[ord(arr[0][0])-const] = False
dfs(0,0,visit,1)

print(result)

시간 초과의 늪에 빠졌던 문제이다. 기본적인 원리는 찾았으나, 문제를 해결하기 위한 방안을 찾기위해 노력했던 문제이다.

처음으로 풀었던 방식은 원래는 visited를 하나의 집합으로 해서 있는지 없는지 체크를 했다면, 알파벳에 해당되는 visited 리스트를 만들어주고 check 해주는 방식으로 풀었다.

# 1987 알파벳


R,C = map(int,input().split())

arr = [list(input()) for _ in range(R)]
check = [['']*C for _ in range(R)]

stack = [(0,0,1,arr[0][0])]
result = 0
dx = [-1,1,0,0]
dy = [0,0,1,-1]
while stack:
    x,y,cnt,total = stack.pop()
    if result < cnt:
        result = cnt
    if result == 26:
        break
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0 <= nx < R and 0<= ny <C:
            if arr[nx][ny] not in total:
                temp = total + arr[nx][ny]
                if check[nx][ny] != temp:
                    check[nx][ny] = temp
                    stack.append((nx,ny,cnt+1,temp))
print(result)

시간이 빠른 방식은 다음과 같다. visited를 체크하는 것은 하나의 스트링을 통해 그 안에 있는지 없는지 확인하는 것이다.

여기까지는 동일하다. 하지만 결정적으로 다른것은 check라는 행렬을 통해 또 체크 하는 것이다.

지금까지 온 이동경로를 넣어놓는 check라는 행렬이다. 이 행렬에 존재하는 값과 같으면, 이미 그에 대해서 전부 탐색을 한 것이기 때문에 또 다시 탐색할 필요가 없다.

탐색한 경로들을 캐싱해놓은것과 같다. 서로다른 루트로 왔다 하더라도 다음위치에 똑같은 값으로 들어오는 거면 굳이 한번 더 검색을 할 필요가 없다.

이 방법은 dfs나 bfs 상관은 없으나 bfs를 할 시, collections의 deque를 쓰도록 하자. 안 그러면 시간 초과가 난다.

import heapq
import sys
N = int(input())


max_heapq = []
min_heapq = []
for _ in range(N):
    number = int(sys.stdin.readline())
    if len(max_heapq) == len(min_heapq):
        heapq.heappush(max_heapq,-number)
    else:
        heapq.heappush(min_heapq,number)
    if min_heapq and max_heapq and min_heapq[0] < -max_heapq[0]:
        max_number = -heapq.heappop(max_heapq)
        min_number = heapq.heappop(min_heapq)

        heapq.heappush(max_heapq,-min_number)
        heapq.heappush(min_heapq,max_number)
    print(-max_heapq[0])

우선순위 힙을 사용하는 기본적인 문제인 것 같다.

과거에도 다익스트라 알고리즘 문제를 풀때 우선순위힙큐를 사용했지만, 여전히 우선순위 힙을 사용하는데, 어려움을 겪었던 문제다.

문제 자체의 기본적인 생각은 다음과 같다. 

가운데 값을 기준으로 가운데 값보다 큰 경우는 무조건 우측에 두는 것이다.  그리고 작은 값은 좌측에 두는 것이다.

그러므로, min_heapq는 가운데 값을 기준으로 우측에 있는 값이고, max_heapq는 가운데 값을 기준으로 좌측에 있는 값이다.

문제 조건 중 가운데 값을 출력하고, 짝수일경우 가운데 값 2개 중 작은 값을 출력을 해야한다. 그러므로, max_heapq가 min_heapq보다 크기가 커야한다. 그래서 max_heapq와 min_heapq가 같은 크기이면, max_heapq에 먼저 넣어주고, 아닐 경우 min_heapq를 넣어줘야한다.

그리고 heapq는 무조건 최소값을 pop해주는 특징이 있으므로, max_heapq를 저장할때에는 가장 큰 값이 가장 먼저 나올수 있도록 -를 곱해줘야한다.

순서에 따라 맞춰서 max_heapq와 min_heapq에 순차적으로 넣어줘야한다. 하지만, 들어오는 입력값에 따라 가끔씩 min_heapq의 첫번째값이 max_heapq의 첫번째값보다 작은 경우가 생길수가 있다. 그럴 경우 두개를 바꿔주는 과정이 필요하다.

무조건 max_heapq의 첫번째 값이 전체의 가운데값이 되기위한 조치이다.

그리고 난뒤에, max_heapq의 첫번째 값을 출력해주면 된다.

heapq라는 라이브러리를 사용하면, 그리 어렵지 않은 문제이다. 하지만 나는 아직 트리와 우선순위힙에 대해서 잘 모르므로, 나중에 트리와 우선순위힙에 대해 더 자세히 공부하고, 라이브러리가 아닌 직접 구현으로 풀 수 있도록 연습해야겠다.