Coding 공부

# # # 9466 텀 프로젝트
import sys
sys.setrecursionlimit(100000)



def dfs(node):
    global result
    visited[node] = False
    total.append(node)
    next_node = graph[node]
    if not visited[next_node]:
        if next_node in total:
            find_index = total.index(next_node)
    
            result +=total[find_index:]
        return
    else:
        dfs(next_node)


for _ in range(int(input())):
    N = int(input())
    graph = [0]+list(map(int,sys.stdin.readline().split()))
    visited = [True] *(N+1)
    result = []
    for ind in range(1,N+1):
        if visited[ind]:
            total = []
            dfs(ind)
    print(N-len(result))

문제를 풀때, 어떻게 풀어야할지 고민을 했던 문제이다. 문제를 읽어보면, 사이클을 이루는 경우에만, 팀이 될수 있다는 것을 알 수 있다. 

그래서 DFS 재귀를 통해서, 내가 방문한 곳을 다시 방문하게 된다면, 사이클을 이루게 되는 것이기 때문에, 결과값에 추가해주었다. 중간의 find_index 같은 경우 사이클을 이루어지는 최초지점을 찾아서 저장해주기 위함이다.

만약 1,2,3,4,5 가 있고, 각각 2,3,4,5,2를 선택했다고 하면 dfs를 했을때 total에는 [1,2,3,4,5]가 저장되어있을 것이다. 하지만, 1은 문제에 주어진 조건을 만족하지 못하고, 팀이 되지 못한다. 그래서 사이클이 최초로 시작되는 2를 기준으로 잘라주기 위함이다.

for _ in range(int(input())):
    N = int(input())
    graph = list(map(int,input().split()))
    visited = [0]*N
    cnt = 0
    for current_node in range(N):
        if not visited[current_node]:
            next_node = current_node
            while visited[next_node] == 0:
                visited[next_node] = 1
                next_node = graph[next_node] - 1
            cycle_index = current_node
            while cycle_index != next_node:
                cnt += 1
                cycle_index = graph[cycle_index] - 1

    print(cnt)

            

좀 더 깔끔한 풀이다. 위와 비슷하지만, 최초로 사이클이 시작되는 노드는 중간의 while문을 통과하고 나온 next_node일것이다.

그러면 처음 노드인 current_node를 복사해, cycle_index라고 하고, 이 cycle_index가 next_node와 같지 못하면, 사이클에 포함되지 않는 노드임을 알 수 있다. 이 next_node는 사이클이 최초로 발생하는 노드의 위치이기 때문에, 만약 current_node에서 사이클이 시작됬다면 cycle_node와 next_node는 동일할 것이다. 

그래서, 이 cycle_node를 똑같이 반복문을 돌리면서 next_node와 같아질때까지 반복을 한다. 그게 곧 팀에 포함되지 않는 사람의 수를 나타내는 것임을 알 수 있다.

# 1759 암호 만들기
def check(input_val,vowel):
    
    check_list = [0,0]
    for val in input_val:
        if val in vowel:
            check_list[0] += 1
        else:
            check_list[1] += 1

    if check_list[0] >= 1 and check_list[1] >= 2:
        return True
    else:
        return False 




def dfs(cnt,ind,result):
    global vowel
    if ind == C:
        if cnt == L and check(result,vowel):
            total.append(result)
            return
    else:
        dfs(cnt+1,ind+1,result+input_list[ind])
        dfs(cnt,ind+1,result)




L,C = map(int,input().split())
vowel = 'aeiou'
input_list = list(input().split())
input_list.sort()

total = list()
dfs(0,0,'')
for val in total:
    print(val)

재귀를 이용해서 조합을 만들어준 것과 같다. 각 인덱스에 들어와서, 해당 문자를 포함하거나 포함하지 않는 경우를 구분해서 재귀를 돌려주었다.

그리고 주어진 길이만큼 되면, 그 안에 모음과 자음 숫자에 따라 True False를 반환해주고, True일때 결과값에 추가해줬다.

from itertools import combinations

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

input_value = list(input().split())

input_value.sort()
vowel = set(['a','e','i','o','u'])
for combi in combinations(input_value,L):
    password = set(combi)
    if password & vowel:
        if len(password-vowel)>=2:
            print(''.join(combi)) 

좀 더 간단한 풀이이다. 위에서 말했듯이 이것은 조합을 구하는것과 동일하다.

combinations 라이브러리를 활용해 전체 combinations을 구하고, 집합의 특성을 이용해, 교집합이 존재하는지, 차집합을 통해 길이가 2이상인지 구분해줘서, 만약 두개다 통과하다면, 원하는 값이므로 출력해주는 방식으로 풀었다.

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를 해주었다.