Coding 공부

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def count_group(val):
    k = 0
    temp = 0
    for ind in range(N):
        temp += arr[ind]
        if temp>=val:
            k += 1
            temp = 0
    return k
 
 
N,K = map(int,input().split())
 
arr = list(map(int,input().split())) 
 
 
left = 0
right = sum(arr)+1
 
while left+1<right:
    mid = (left+right)//2
    K_mid = count_group(mid)
    if K_mid >= K:
        left = mid
    else:
        right = mid
print(left)

 원래 잘 못푸는 이분탐색 문제라서 오래걸렸던 문제였다.

이 문제에서 구해야할 것은 최소의 최대값이다.

즉 여기서 mid의 값이 의미하는 것은 해당 시험 문제지의 최소 점수인것이다.

즉 이 최소 점수가 넘어가면, 그룹을 나누는것이다.

이렇게 나눈 최소 점수를 기준으로 시험지를 나눴을때의 그룹의 수가  K개 미만이 되면 False K개 이상이 되면 True로 하고

우리는 K개 이상의 가장 마지막 값을 구하고 싶은 것이므로, left를 출력해주면 된다.

이 문제 덕분에 이분탐색에 대해서 감을 잡게 되었고,

찾고 싶은 값이 있을때 어떻게 나눠야할지 대략 감을 잡았다.

아직 부족하지만, 어떻게 나눠야할지 알게 되었다.

https://blog.naver.com/jinhan814/222156334908

https://blog.naver.com/jinhan814/222135038870

https://eine.tistory.com/entry/%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89binary-search-%EA%B5%AC%ED%98%84%EC%8B%9C-%EA%B3%A0%EB%A0%A4%ED%95%A0-%EA%B2%83%EB%93%A4

https://blog.naver.com/kks227/220777333252

풀면서 참조한 블로그들이다. 이분탐색에 대해 잘 설명을 해놓은 블로그이니 추천을 드린다.

def checkWin(play):
    play_num = players[play]
 
    for x in range(3):
        if arr[x][0] == arr[x][1] == arr[x][2] == play_num:
            return 2
    
    for y in range(3):
        if arr[0][y] == arr[1][y] == arr[2][y] == play_num:
            return 2
 
    if arr[0][0] == arr[1][1] == arr[2][2] == play_num:
        return 2
 
    if arr[0][2] == arr[1][1] == arr[2][0] == play_num:
        return 2
 
    return 0 
 
 
def dfs(rc,play):
    global result
    if checkWin((play+1)%2)>1:
        return -1
    if rc <remain_cnt:
        check_result = 10
        for idx in range(remain_cnt):
            if not visited[idx]:
                visited[idx] = True
                x,y = remain_list[idx]
                arr[x][y] = players[play]
                check_result = min(check_result,dfs(rc+1,(play+1)%2))
                visited[idx] = False
                arr[x][y] = 0
        if check_result == 10 or check_result == 0:
            return 0
        else:
            return -check_result
    return 0 
arr = []
 
# 1 = X
# 2 = O
# 착수하는 사람 부터
cnt_1 = 0
cnt_2 = 0
remain_cnt = 0
remain_list = []
players = [1,2]
for x in range(3):
    temp = list(map(int,input().split()))
 
    for y in range(3):
        if temp[y] == 1:
            cnt_1 += 1
        elif temp[y] == 2:
            cnt_2 += 1
        else:
            remain_cnt += 1
            remain_list.append((x,y))
 
    arr.append(temp)
visited = [False for _ in range(remain_cnt)]
 
start = 0
if cnt_1 > cnt_2:
    start = 1
 
 
 
 
result = dfs(0,start)
answer = ['D','W','L']
print(answer[result])

 이 문제는 어려웠던 문제였다.  이 문제는 각각 최선의 수로 둔다는 것은 해당 수를 두고 다음턴에, 지지 않기를 바라는 상황이다.

그래서 상대턴이 시작할때, 이전턴에 뒀던 플레이어의 승리여부를 체크하고 체크를 한뒤에는 음수를 보내준다.

왜냐하면 서로 승패는 반대로 되기 때문이다. 그리고 승부가 나지 않았을 시에는 0을 반환하도록 한다.

def check():
    for x in range(3):
        prev_num = arr[x][0]
        if not prev_num:continue
        for y in range(1,3):
            if prev_num != arr[x][y]:
                break
        else:
            return prev_num
    
    for y in range(3):
        prev_num = arr[0][y]
        if not prev_num: continue
        for x in range(1,3):
            if prev_num != arr[x][y]:
                break
        else:
            return prev_num
 
    prev_num = arr[0][0]
    if prev_num:
        for k in range(1,3):
            if prev_num != arr[k][k]:
                break
        else:
            return prev_num
    
    prev_num = arr[0][2]
    if prev_num:
        for k in range(1,3):
            if prev_num != arr[k][2-k]:
                break
        else:
            return prev_num
 
    return 0
 
 
def dfs(rc,player):
    check_num = check()
    if check_num != 0:
        return check_num
 
    if rc == 0: return -1
    response = []
    for x in range(3):
        for y in range(3):
            if arr[x][y]:continue
            arr[x][y] = player
            response.append(dfs(rc-1,3-player))
            arr[x][y] = 0
    if player in response:return player
    if -1 not in response: return (3-player)
    return -1
 
arr = [list(map(int,input().split())) for _ in range(3)]
cnt_1 = 0
cnt_2 = 0
player = 1
r_cnt = 0
for x in range(3):
    for y in range(3):
        if arr[x][y] == 1:
            cnt_1 += 1
        elif arr[x][y] == 2:
            cnt_2 += 1
        else:
            r_cnt += 1
 
 
if cnt_1 > cnt_2:
    player = 2
 
 
result = dfs(r_cnt,player)
 
if result == -1:
    print('D')
elif result == player:
    print('W')
else:
    print('L')

이 풀이가 좀 더 직관적일 수 있다.

모든 결과들을 저장한뒤에 해당 결과 내에서, 해당 플레이어의 번호가 있으면 승리한 것이므로, 해당 플레이어 번호를 보내주고,

무승부인 -1이 없으면 상대방이 이긴거기 때문에 상대방의 플레이어 번호를 return 해준다.

그리고 둘다 아닌경우에는 무승부이므로 -1을 반환해준다.

이 문제는 최선의 수가 무엇인지, 어떻게 승패를 판단하는지 어려웠던 문제였다.

import sys
sys.setrecursionlimit(123456)
def dfs(node):
    if not graph[node]:
        if pet_list[node]>0:
            return pet_list[node]
        return 0 
    else:
        temp = 0
        for child_node in graph[node]:
            temp += dfs(child_node)
        temp += pet_list[node]
        if temp <0:
            temp = 0
        return temp
 
def input():
    return sys.stdin.readline().rstrip()
N = int(input())
 
graph = [[] for _ in range(N+1)]
pet_list = [0 for _ in range(N+1)]
for i in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[i] = pay
        graph[island].append(i)
    else:
        pet_list[i] = -pay
        graph[island].append(i)
 
 
 
 
print(dfs(1))

이 문제는 기본적인 트리 문제였다. 그래프의 경로와 각 양과 늑대를 양수와 음수로 각각 매칭을 했다.

그리고 재귀를 통해서 리프노드까지 간 뒤에 양수이면 양수를 음수이면 0을 보내줬다.

그리고 그렇게 return 된 값들을 전부 더한뒤에

현재 아일랜드의 값을 더해주고, 그 값이 0미만이 되면 0으로 보내주고 그게 아니면 원래대로 보내주면 풀리는 문제이다.

import sys
from collections import defaultdict,deque
def input():
    return sys.stdin.readline().rstrip()
 
 
N = int(input())
 
graph = defaultdict(list)
pet_list = [0 for _ in range(N+1)]
parents = [0 for _ in range(N+1)]
for next_node in range(2,N+1):
    pet,*arg = input().split()
    pay,island = map(int,arg)
    if pet == 'S':
        pet_list[next_node] = pay
    else:
        pet_list[next_node] = -pay
    graph[island].append(next_node)
    parents[next_node] = island
 
que = deque()
que.append(1)
stack = []
while que:
    cur_node = que.popleft()
    stack.append(cur_node)
    for next_node in graph[cur_node]:
        que.append(next_node)
 
while stack:
    cur_node = stack.pop()
    pet_list[parents[cur_node]] += max(0,pet_list[cur_node])
 
print(pet_list[0])

재귀를 이용하지 않고 푸는 방법이다.

먼저 bfs로 탐색하면서 그 순서를 stack에 넣어주고, 끝에서부터 하나씩 꺼내주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
 
 
N = int(input())
A = list(map(int,input().split()))
dict_A = {}
for k in range(N):
    dict_A[A[k]] = k
 
B = list(map(int,input().split()))
convert_B = [0]*N
for ind,k in enumerate(B):
    convert_B[ind] = dict_A[k]
LIS = [convert_B[0]]
 
 
 
for ind in range(1,N):
    if convert_B[ind] > LIS[-1]:
        LIS.append(convert_B[ind])
    else:
        left = -1
        right = len(LIS)
        while left + 1 < right:
            mid = (left + right)//2
 
            if LIS[mid] >= convert_B[ind]:
                right = mid
            else:
                left = mid
        LIS[right] = convert_B[ind]
 
print(len(LIS))

사실 이 문제는 LCS로 분류되어있지만, LIS 태그도 포함되어 있어야한다고 생각한다.

기존의 LCS로 하면 N^2이 걸리기 때문에, 입력사항을 보면 터질수 밖에 없다.

근데 우리는 여기서 문제의 조건을 잘 봐야한다.

문제의 조건에서 1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때 라고 되어있다.

이 말은 각 수열에 있는 값들은 중복되는것은 없고, 하나하나가 유니크 하나는 것이다.

이 최장 부분수열에서는 인덱스가 증가하는 방향으로 부분수열을 구해야한다.

그렇다는 말은 A와 B라는 각 리스트가 있을 때, B의 각 값들이 A에 어디에 있는지 해놓으면,

B의 값은 A에 위치한 인덱스로 대치가 된다.

그런데 우리는 부분수열을 구할때, 인덱스가 증가하는 수선대로 해야한다.

즉 이렇다는 말은 A의 인덱스로 바뀐 B의 수열을 최장 증가 부분 수열의 길이를 구하면,

이것은 곧 A와 B의 최장 부분 수열이 됨을 알 수 있게 된다.

이러한 트릭을 가지고, LIS의 길이를 구하는 이분탐색 기법을 통해서 구해주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def check(mid):
    idx = 0
    temp = []
    cnt = 0
    while idx<N:
        if cnt >M:
            return False
        if temp:
            min_value,max_value = min(temp),max(temp)
            if abs(arr[idx]-min_value)>mid or abs(arr[idx]-max_value)>mid:
                cnt += 1
                temp = [arr[idx]]
            else:
                temp.append(arr[idx])
        else:
            temp.append(arr[idx])
        idx += 1
    if temp:
        cnt += 1
    if cnt>M:
        return False
    return True
        
 
N,M = map(int,input().split())
 
arr = list(map(int,input().split()))
 
 
left = -1
right = 10001
while left+1<right:
    mid = (left+right)//2
 
    if check(mid):
        right = mid
    else:
        left = mid
 
print(right)

이 문제는 구간의 최대값과 최소값을 비교한 값이 최대가 되어야하고 M개 이하의 그룹으로 나뉘어야한다.

이 문제를 푸는 법은 이분탐색을 이용해서 풀면된다. 이분탐색의 탐색근거가 되는 값은 최대-최소의 값이다.

이 값이 벗어나는 경우 새로운 그룹을 만들어주고, 총 그룹의 수가 M개 초과가 되면 False를 만족하면 True로 하면서

True를 만족 최소의 값을 구하면 된다.

위의 풀이는 list에 계속 넣다 빼다보니 시간이 좀 오래걸린다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def check(mid):
    min_value = arr[0]
    max_value = arr[0]
    idx = 1
    cnt = 1
    while idx<N:
        if cnt>M:
            return False
        if min_value>arr[idx]:
            min_value = arr[idx]
        if max_value < arr[idx]:
            max_value = arr[idx]
        
        if max_value-min_value>mid:
            min_value = arr[idx]
            max_value = arr[idx]
            cnt += 1
        idx += 1
    if cnt>M:
        return False
    else:
        return True
        
 
N,M = map(int,input().split())
 
arr = list(map(int,input().split()))
 
 
left = -1
right = 10001
while left+1<right:
    mid = (left+right)//2
 
    if check(mid):
        right = mid
    else:
        left = mid
 
print(right)

똑같은 원리지만, 훨씬 빠른 풀이다. 리스트를 저장하는게 아니라, 최소 최대값을 계속 갱신을 해주면서,

그 값이 주어진 mid보다 크면, 최소 최대값을 현재 탐색중인 값으로 초기화 해준뒤 cnt를 늘려주면 된다.

이 풀이가 좀 더 깔끔한 풀이라 생각한다.

import sys
from collections import Counter
def input():
    return sys.stdin.readline().rstrip()
 
cnt = 0
total_dict = Counter()
while True:
    name = input()
    if not name:
        break
    total_dict[name] += 1
    cnt += 1
 
key_list = sorted(total_dict.keys())
 
for key in key_list:
    print(f'{key} {total_dict[key]*100/cnt:.4f}')

이 문제는 골드5라 되어있지만, 실버 수준인것 같다.

어려운 알고리즘도 없고, 단순히 formating을 이용한 반올림을 하면 된다.

전체 수를 딕셔너리에 저장을 하고, 정렬을 한뒤에 4자리까지만 출력되게 하면 된다.

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()
 
def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start):
    stack = [(start,0,0)]
    visited = [True for _ in range(N+1)]
    while stack:
        node,parent,dis = stack.pop()
 
        if cycle_check_node[node]:
            distance[start] = dis
            return
        visited[node] = False
 
        for next_node in graph[node]:
            if next_node == parent:continue
            if visited[next_node]:
                stack.append((next_node,node,dis+1))
 
 
 
N = int(input())
 
graph = [[] for _ in range(N+1)]
 
for _ in range(N):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
 
visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
distance = [0 for _ in range(N+1)]
 
cycle_check(1,0)
 
 
for k in range(1,N+1):
    if not cycle_check_node[k]:
        dfs(k)
 
 
print(*distance[1:])

  처음 풀이는 생각나는대로 풀었다. 먼저 2가지 함수로 나눠서 했다.

처음은 cycle을 체크하는 함수이다. 어느 노드에서든지 시작을 해서, 한번 방문을 했던 노드가 나올때까지

부모노드를 제외한 자식노드를 탐색해간다. 그러다보면 cycle의 시작지점을 방문하게 되는데 이때,

우리는 해당 node의 번호를 리턴해준다. 그러면 우리는 return 된 값이 0보다 크면

이 노드는 사이클에 포함된 노드임을 알 수 있다. 그러므로 return이 된 값이 0보다 크면 cycle임을 체크해주고,

시작지점에 도착하면, return 된 node와 값이 같으므로, 그걸로 판별뒤, 그 뒤에는 0을 반환해주면 된다.

그러면 우리는 0이 반환이 되면, 해당 노드는 사이클이 아닌것을 알게 된다.

이렇게 cycle을 체크한 뒤에

dfs를 돌려 cycle을 최초로 만나는 지점까지의 거리를 구해서 저장해주면 된다.

import sys
sys.setrecursionlimit(10000)
def input():
    return sys.stdin.readline().rstrip()
 
def cycle_check(node,parent):
    if visited[node]:
        return node
    else:
        visited[node] = True
        for next_node in graph[node]:
            if next_node == parent:continue
            return_node = cycle_check(next_node,node)
            if return_node > 0:
                cycle_check_node[node] = True
                distance[node] = 0
                if return_node == node:
                    return 0
                else:
                    return return_node
        cycle_check_node[node] = False
        return 0
def dfs(start,parent):
    if distance[start] != INF:
        return distance[start]
    for next_node in graph[start]:
        if next_node == parent:continue
        distance[start] = min(dfs(next_node,start)+1,distance[start])
 
    return distance[start]
 
    
 
 
 
N = int(input())
 
graph = [[] for _ in range(N+1)]
 
for _ in range(N):
    x,y = map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
 
 
visited = [False for _ in range(N+1)]
cycle_check_node = [False for _ in range(N+1)]
INF = float('inf')
distance = [INF for _ in range(N+1)]
 
cycle_check(1,0)
 
for k in range(1,N+1):
    if not cycle_check_node[k] and distance[k] == INF:
        dfs(k,0)
 
print(*distance[1:])

이 방식은 좀 더 깔끔한 코드이다. 모든 노드들을 dfs를 각각돌리는것이 아닌. cycle인 부분에서부터 1씩 거리를 늘리면서 하나씩 해주는 방식이다.

이 방식이 좀 더 깔끔한 방식이다.

import sys
 
sys.setrecursionlimit(20000)
 
def solution(k, num, links):
    left = sum(num)//k
    right = sum(num)
    N = len(num)
    degrees = [0 for _ in range(N)]
    for ind in range(N):
        if links[ind][0] != -1:
            degrees[links[ind][0]] += 1
        if links[ind][1] != -1:
            degrees[links[ind][1]] += 1
    root = -1
    for ind in range(N):
        if not degrees[ind]:
            root = ind
            break
    INF = float('inf')
    def check(node):
        nonlocal links,INF,dp,mid
        if links[node][0] == -1 and links[node][1] == -1:
            if num[node]<=mid:
                dp[node][0] = num[node]
                dp[node][1] = 1
            else:
                dp[node][0] = 0
                dp[node][1] = INF
        else:
            for ind in range(2):
                if links[node][ind] != -1:
                    check(links[node][ind])
            left_node = links[node][0]
            right_node = links[node][1] 
            if dp[left_node][0] + dp[right_node][0] + num[node] <= mid:
                dp[node][0] = dp[left_node][0] + dp[right_node][0] + num[node]
                dp[node][1] = dp[left_node][1] + dp[right_node][1] -1
                return
            if right_node == -1:
                if num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF
 
            else:
                if num[node] + min(dp[right_node][0],dp[left_node][0])<= mid:
                    dp[node][0] = num[node] + min(dp[right_node][0],dp[left_node][0])
                    dp[node][1] = dp[right_node][1] + dp[left_node][1]
                elif num[node] <= mid:
                    dp[node][0] = num[node]
                    dp[node][1] = dp[left_node][1] + dp[right_node][1] + 1
                else:
                    dp[node][0] = 0
                    dp[node][1] = INF
 
            
 
 
 
    while left+1<right:
        mid = (left+right)//2
        dp = [[0,1] for _ in range(N+1)]
        check(root)
        if dp[root][1]<=k:
            right = mid
        else:
            left = mid
    return right

풀기 힘들었던 문제이다.

이 문제는 트리 DP와 파라메트릭 서치를 활용한 문제로

k개의 그룹으로 나눌 수 있는 최소 값을 찾는것이다.

카카오 해설에서도 알수 있듯이 이분탐색으로 찾으면 되고,

이 이분 탐색의 중간값인 mid가 의미하는 것은 이 트리를 나눌 최대의 인원을 의미한다.

한 그룹의 인원이 mid가 넘어가지 않게 해주면 된다.

즉 mid의 값이 크면 k는 적게 나올것이고, mid의 값이 작으면 k보다 많게 나올 것이다.

우리는 left+1<right일때 끝나고

left일때 false이므로,

우리가 구하고자 하는 값은 right임을 알 수 있다.

문제에 들어가면,

가장 밑 노드에서부터 해주면 된다.

먼저 dp 테이블은 N*2의 크기로 해주었고,

dp[x][0] 은 x 노드에서의 최소 그룹인원의 수

dp[x][1] 은 x 노드에서의 그룹의 개수를 의미한다.

각 노드는 처음에 하나의 그룹이므로, dp[x][0]은 0으로 dp[x][1]은 1로 초기화를 해주었다.

총 4가지 경우가 있을것이다.

1. 자식노드 2개에 누적된 그룹인원과 현재노드의 인원과  더해도 mid보다 작거나 같다.

    그러면 dp[parent][0] = num[parent] + dp[left_node][0] + dp[right_node][1]이 될것이다.

    그리고 그룹의 수는 자식노드의 그룹의 수를 더해준 것에서 -1을 해준다.

    이러는 이유는 우리가 각 노드를 하나의 그룹으로 생각했기 때문에, 처음에 1로 전부 초기화 되어 있어서 그런다.

   자식노드와 현재그룹을 더해서 한개의 그룹이 된 것이므로 - 1을 해준다.

2. 자식노드 둘 중 1개 그룹인원과  현재 노드의 인원과 더하면 mid보다 작거나 같다.

   이럴때에는 그룹인원이 많은쪽의 간선을 끊는것과 마찬가지 이므로

   dp[parent][0] = num[parent] + min(dp[left_node][0], dp[right_node][1])

  을 해주고, 그룹은 두 자식노드의 그룹인원을 더해주면 된다.

3. 현재 그룹인원의 mid보다 작거나 같고, 자식노드들의 인원을 더하면 mid보다 크다.

   이럴 경우는 간선을 전부 끝는 것이다.

   그래서 dp[parent][0] = num[parent]를 해주고,

   그룹의 수는 1개를 더 더해주면 된다.

4. 현재 그룹의 인원의 mid보다 크다.

   이럴때에는 어떤 방도로도 mid보다 작거나 같은 그룹으로 나눌수 없으므로, 그룹인원의 수를 0으로 초기화 해주고, 그룹의 수를 INF로 해준다.

이 문제는 평소 코에서 나오지 않는 트리dp 문제인데다가, 이분탐색까지 활용해야되서 어려웠던 문제였다.

dp 테이블을 설계하는 것부터, 그룹의수가 k이면서 최소의 그룹인원 수를 어떻게 찾아하는지 생각하기 어려운 문제였다.

이 문제는 카카오 시험이 끝난뒤, 알고리즘 고수분들을 이야기를 통해, 어떻게 풀어야할지 감을 잡았고,

문제가 나오고 실제로 푸는데에도 시간이 오래걸린 문제였다.

이 문제가 다시 나오면 풀수 있다는 확신은 없지만, 한번 경험해봤으니 이러한 문제도 있다라는 것을 배운점에 만족했다.