Coding 공부

import sys

def input():
    return sys.stdin.readline()

N = int(input())
INF = float('inf')
dp = [INF for _ in range(101)]
dp[2] = 1
dp[3] = 7
dp[4] = 4
dp[5] = 2
dp[6] = 6
dp[7] = 8
dp[8] = 10

for num in range(9,101):
    for i in range(2,8):
        if i != 6:
            dp[num] = min(dp[num],dp[num-i]*10+dp[i])
        else:
            dp[num] = min(dp[num],dp[num-i]*10)
for _ in range(N):
    k = int(input())
    
    max_value = ('7' if k%2 else '1' ) +'1'*(k//2-1)
    print(dp[k],max_value)

이 문제를 푸는 방식은 다음과 같다.

2개부터 8개까지의 성냥개비를 이용해서 만들 수 있는 최소의 수가 있다.

먼저 이 수들을 각각 저장을 해주는 것이다.

단 여기서 주의해야할 점은 성냥개비의 개수가 6개일때다.

6개일때는 원래 최저의 수는 0이지만, 자리수가 1개일때 0이 올수가 없다. 이 점만 주의해주면 된다.

이렇게 2~8개의 최소 숫자를 구해주고

9개부터는 그리디하게 찾아주면 된다.

dp [ 현재 성냥의 개수 - i개 ] *10 + dp[i] 와 dp[현재 성냥의 개수] 의 최소값을 비교해서 갱신해주면 된다.

그리고 위에 말했듯이 6개일때는 가장 작은 수는 0 이므로 *10만 해주면 된다.

이렇게 최소 숫자를 구했으면,

최대 숫자를 구해야한다.

여기서 가장 큰 숫자를 만드는 법은 가장 적은 개수로 만들수 있는 1로 채우는 것이다.

그런데 이럴때 문제는 성냥의 개수가 홀수일때 문제가 된다.

성냥의 개수가 홀 수 일때 1개가 남아서, 어떠한 숫자도 만들수 없다.

그러므로 주어진 성냥개비의 숫자가 홀수이면, 가장 앞의 수를 1이 아닌 성냥개비 3개로 만들수 있는 가장 큰수를 만들어줘야한다.

그에 부합하는 숫자는 7 이므로,

주어진 성냥 개비의 숫자가 홀수이면 7 아니면 1을 붙이고, 성냥개비를 2로 나눈 몫에서 1을 뺀숫자만큼 붙여주면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

def make_group(limit):
    temp = 0
    cnt = 0
    result = []
    group_cnt = K
    for ind in range(N):
        temp += arr[ind]
        if temp>limit:
            temp = arr[ind]
            result.append(cnt)
            group_cnt -= 1
            cnt = 0
        cnt += 1
        if group_cnt == (N-ind):
            result.append(cnt)
            group_cnt -= 1
            while group_cnt:
                result.append(1)
                group_cnt -= 1
            return result

def count_group(val):
    k = 0
    temp = 0
    for ind in range(N):
        temp += arr[ind]
        if temp>val:
            temp = arr[ind]
            k += 1
    if temp:
        k += 1
    return k


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

arr = list(map(int,input().split())) 


left = max(arr)-1
right = sum(arr)
answer = right
while left+1<right:
    mid = (left+right)//2
    K_mid = count_group(mid)
    if K_mid > K:
        left = mid
    else:
        right = mid
print(right)
print(*make_group(right))

최근 풀었던 문제들 중에서 가장 어렵게 푼 문제였다.

이 문제는 단순한 이분탐색으로 끝나는 것이 아닌, 그룹을 구하는게 힘들었다.

그룹을 만드는 방식은 다음과 같다.

문제에 주어진 M개의 그룹을 강제적으로 만들어줘야한다.

즉 우리가 그룹을 만들어야하는 개수와 현재 남은 구슬의 수가 동일하다면,

나머지 구슬들을 전부 1개씩으로 만들어줘야한다.

이 점을 주의해서 풀어주면 문제를 해결할 수 있는 문제였다.

import sys
import heapq

def dijkstra(flag=False,*arg):
    distance = [INF for _ in range(N+1)]
    distance[1] = 0
    node_list = []
    if flag:
        remove_node = arg[0]
    heapq.heappush(node_list,(0,1))
    
    while node_list:
        cur_dis,node = heapq.heappop(node_list)
        if cur_dis>distance[node]:
            continue
        for next_node in graph[node]:
            if flag and ((node,next_node) == remove_node or (next_node,node) == remove_node):
                continue 
            temp_distance = cur_dis + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    if not flag:
        stack = [(N,distance[N])]
        while stack:
            node,dis = stack.pop()
            for prev_node in graph[node]:
                if (prev_node,node) not in short_list:
                    if distance[prev_node] + graph[prev_node][node] == dis:
                        short_list.add((prev_node,node))
                        stack.append((prev_node,distance[prev_node]))

    return distance[N]
    

def input():
    return sys.stdin.readline()


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

graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay

INF = float('inf')

short_list = set()
short_time = dijkstra()
short_list = list(short_list)

result = -1
for node in short_list:
    remove_time = dijkstra(True,node)
    result = max(result,remove_time - short_time)

print(result if result != INF else -1)

문제를 푸는 방식은 다음과 같다.

먼저 다익스트라로 최단 거리를 구한다.

그와 동시에 이동경로를 구해야한다.

즉 우리는 다익스트라를 하면서 누적된 이동거리 리스트를 이용해서 역산을 통해 최단 거리의 이동 경로를 구한다.

이렇게 구한 이동경로를 하나씩 검문을 하는 것이다.

그리고 그 검문을 했을때의 다익스트라를 구하고, 이 때의 최대값을 구하고, 지연된 시간을 구하면 된다.

이 문제는 다익스트라를 통해 이동경로를 추적하고, 그 이동경로를 활용해서 풀 수 있는 문제였다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())



graph = [defaultdict(list) for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y].append((pay,True))
    graph[y][x].append((pay,False))


node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1,True))
result = []

while node_list:
    cur_dis, cur_node , parent_node , cur_flag = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        if cur_flag:
            result.append((parent_node, cur_node))
        else:
            result.append((cur_node, parent_node))
    for next_node in graph[cur_node]:


        for pay,flag in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node , flag))
    
print(len(result))
for row in result:
    print(*row)

처음으로 풀었던 방식이다. 문제의 출력을 입력에 주어진 간선으로 출력해야하는 줄 알고, 좀 복잡하게 풀었다.

이 문제를 처음 본 순간 MST 문제 인줄 알았는데, MST 문제는 아니였다.

1번 조건만 보고 모든 노드들이 연결되는 최소인줄 알고 MST인줄 알았는데,

2번 조건을 찬찬히 읽어보니 다익스트라 문제였다.

네트워크를 복구해서 통신이 가능하도록 만드는 것도 중요하지만, 해커에게 공격을 받았을 때 보안 패킷을 전송하는 데 걸리는 시간도 중요한 문제가 된다. 따라서 슈퍼컴퓨터가 다른 컴퓨터들과 통신하는데 걸리는 최소 시간이, 원래의 네트워크에서 통신하는데 걸리는 최소 시간보다 커져서는 안 된다.

그 2번 조건은 다음과 같다.

슈퍼컴퓨터를 기준으로 모든 컴퓨터들은 최소 시간을 보장해야한다.

즉 슈퍼컴퓨터를 기준으로 모든 노드들에 대한 최소 시간의 다익스트라를 구해야하는 문제이다.

이 점만 주의하면 일반적인 다익스트라 풀이와 동일하다.

import sys
from collections import defaultdict
import heapq
def input():
    return sys.stdin.readline().rstrip()
N,M = map(int,input().split())



graph = [defaultdict(list) for _ in range(N+1)]

for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y].append(pay)
    graph[y][x].append(pay)


node_list = []
INF = float('inf')
distance_list = [INF for _ in range(N+1)]
distance_list[1] = 0
heapq.heappush(node_list,(0,1,1))
result = []

while node_list:
    cur_dis, cur_node , parent_node  = heapq.heappop(node_list)
    if cur_dis > distance_list[cur_node]:
        continue
    if cur_node != parent_node:
        result.append((parent_node, cur_node))
    for next_node in graph[cur_node]:


        for pay in graph[cur_node][next_node]:
            if cur_dis + pay < distance_list[next_node]:
                distance_list[next_node] = cur_dis + pay
                heapq.heappush(node_list,(distance_list[next_node], next_node , cur_node ))

print(len(result))

for row in result:
    print(*row)

개선한 풀이이다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline()

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

arr = [list(input()) for _ in range(N)]

start = [0,0,0]
node_list = []
total_cnt = 0
for x in range(N):
    for y in range(N):
        if arr[x][y] == 'S':
            start = [0,x,y]
            arr[x][y] = '0'



heapq.heappush(node_list,start)
INF = float('inf')
visited = [[True for _ in range(N)] for _ in range(N)]
distance = [[INF for _ in range(N)] for _ in range(N)]
result = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
cnt = 0
while node_list:
    cur_dis,x,y, = heapq.heappop(node_list)
    if not visited[x][y]:
        continue
    if cur_dis > distance[x][y]:
        continue
    result += cur_dis
    cnt += 1
    visited[x][y] = False

    temp_visited = [[True for _ in range(N)] for _ in range(N)]
    queue = deque()
    queue.append((x,y,0))
    temp_visited[x][y] = False
    while queue:
        qx,qy,dis = queue.popleft()

        for i in range(4):
            nx = qx + dx[i]
            ny = qy + dy[i]

            if temp_visited[nx][ny] and arr[nx][ny] != '1':
                temp_visited[nx][ny] = False
                queue.append((nx,ny,dis+1))
                if arr[nx][ny] == 'K' and distance[nx][ny] > dis+1:
                    distance[nx][ny] = dis + 1
                    heapq.heappush(node_list,(dis+1,nx,ny))
if cnt<M+1:
    print(-1)
else:
    print(result)

 이 문제는 MST와 너비 우선 탐색을 활용한 문제였다.

일단 경계선은 전부 1로 되어있으므로, 경계체크를 해줄 필요는 없다.

문제를 푸는 아이디어는 다음과 같다. 

프림알고리즘을 이용한다.

그런데 프림 알고리즘을 활용할려면, 각 노드 사이의 간선의 정보를 알아야한다.

이 것은 BFS를 통해 로봇과 K들 사이의 간선들을 구하는 것이다.

즉, heap에 들어온 Node를 기준으로 다른 열쇠들 간의 간선의 정보를 찾으면 된다.

그래서 프림 알고리즘을 해서 나오는 노드를 기준으로 BFS를 돌리고, 열쇠이고, 현재 누적된 거리가 더 짧으면

거리를 갱신하고, 그 때의 위치 정보 및 거리를 heap에 넣어준다.

이런식으로 해서 프림알고리즘을 돌리면서 매번 BFS를 돌려서 해당 노드에서 다음노드로 갈수 있는 간선정보를 찾아

heap에 넣어주는 식으로 해주면 된다.

그리고 여기서 주의해야할 점은 모든 열쇠를 찾지 못하는 경우도 있다.

우리는 총 M + 1개의 노드를 가진 그래프에서 프림 알고리즘을 돌린것과 마찬가지이므로,

프림 알고리즘에서 방문한 노드의 수가 M+1개 보다 적으면 -1을 출력 해주며 된다.

import sys
def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False

def input():
    return sys.stdin.readline().rstrip()

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


dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}

arr = [list(input()) for _ in range(N)]
make_set = [i for i in range(N*M)]
ranks = [1 for _ in range(N*M)]


for x in range(N):
    for y in range(M):
        point = x*M+y
        dx,dy = dire[arr[x][y]]
        next_point = (x+dx)*M+y+dy
        union(point,next_point)

result = 0
for x in range(N):
    for y in range(M):
        point = x*M+y
        if point == find_parents(point):
            result += 1
print(result)

 이 문제는 union find를 통해 집합이 몇개가 되는지 확인하면 된다.

그 방법은 현재 노드와 부모노드가 동일한 개수를 세주면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()

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


dire = {
    "U": [-1,0],
    "L": [0,-1],
    "R" : [0, 1],
    'D': [1,0]
}
arr = [list(input()) for _ in range(N)]
visited = [[-1 for _ in range(M)] for _ in range(N)]

result = 0
for x in range(N):
    for y in range(M):
        if visited[x][y] != -1:
            continue

        point = x*M+y
        nx,ny = x,y
        while visited[nx][ny] == -1:
            visited[nx][ny] = point
            dx,dy = dire[arr[nx][ny]]
            nx = nx + dx
            ny = ny + dy
        if visited[nx][ny] == point:
            result += 1
print(result)

다르게 푸는 방식은 visited를 만들어놓고 같은 point가 되는 지점에 돌아왔을때 result + 1 해주는 것이다.

안전지대가 된다는 것은 한 지점에서 출발했다가 원래지점으로 돌아온다는것을 뜻하므로, 그 조건을 만족하는 개수를 세주면 된다.

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을 반환해준다.

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