Coding 공부

import collections

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

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

for _ in range(M):
    n1,n2,d = map(int,input().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

node = start

while True:
    visited[node] = False
    for ind,dis in graph[node]:
        distance[ind] = min(distance[ind],distance[node]+dis)
    next_node = -1
    next_min_distance = INF
    for ind in range(N+1):
        if visited[ind] and next_min_distance > distance[ind]:
            next_min_distance = distance[ind]
            next_node = ind
    if next_node != -1:
        node = next_node
    else:
        break

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

평소에 하던 다익스트라 문제였고, 평상시 하던대로 로직을 짜서 실행시켰다 하지만 시간초과라는 결과가 나왔다.

평소에 heapq라는 라이브러리가 익숙치 않아서 쓰지 않았던 heapq를 썼다. heapq를 써서 문제를 풀었다.

import heapq
import sys
N,M = map(int,input().split())
start = int(input())

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

for _ in range(M):
    n1,n2,d = map(int,sys.stdin.readline().split())
    graph[n1].append((n2,d))
visited = [True] * (N+1)
INF = float('inf')
distance = [INF]*(N+1)
distance[start] = 0

node_list = []
heapq.heappush(node_list,(0,start))

while node_list:
    current_distance,node= heapq.heappop(node_list)
    visited[node] = True
    if distance[node]<current_distance:
        continue
    for next_node,next_dis in graph[node]:
        if visited[next_node]:
            temp_distance = current_distance + next_dis
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(distance[next_node],next_node))

for ind in range(1,N+1):
    if distance[ind] == INF:
        print('INF')
    else:
        print(distance[ind])

heapq를 썼을시에는 통과가 가능했다.

시간복잡도는 heapq가 더 빠르니, heapq에 대해서도 공부해야겠다.

N = int(input())

arr = list(map(int,input().split()))
parent = {i:[] for i in range(N)}
child = {i:[] for i in range(N)}
root_node = -1
for ind in range(N):
    if arr[ind] == -1:
        root_node = ind
    else:
        parent[ind].append(arr[ind])
        child[arr[ind]].append(ind)
remove_node = int(input())
if root_node != remove_node:
    remove_nodes = set()
    stack = [remove_node]
    visited = [True] * N
    while stack:
        node = stack.pop(0)
        remove_nodes.add(node)
        for k in child[node]:
            if visited[k]:
                visited[k] = False
                stack.append(k)
        parent_node = parent[node][0]
        child[parent_node].remove(node)

    leef_nodes = set()

    for ind in range(N):
        if not len(child[ind]):
            leef_nodes.add(ind)
    print(len(leef_nodes-remove_nodes))
else:
    print(0)

가장 자신없고, 공부를 많이 안한 Tree 분야라, 코드가 난잡하다. 기본적인 원리는 parent_node들과 child_node들을 정리해주고, root_node를 구해준다.

만약 지워야할 remove_node와 root_node가 같을시 leafnode가 없으니 0을 출력해준다.

그 외에는 다음과 같이 진행을 한다. 지워진 node들과 leafnode가 될수 있는 node들을 구한뒤 leafnode에서 remove_node를 차집합을 해줘서 그 길이를 출력해준다. 이게 가능했던 이유는 , 반복문을 돌면서 remove_node로 들어간 node들의 child_node를 빼줬기 때문이다.

내가 푼 풀이는 난잡하게 여러 변수들이 존재하고, 깔끔하지 못해서 잘 푸신 다른분의 코드를 클론코딩하면서 공부도 했다.

---- 클론 코딩 및 분석---

# nh7881님 코드 분석

def find_leafs(index,child_nodes):
    # index가 -1이라는 것은 root_node가 remove_node인 경우이니, 그때에는 0을 반환을 해준다.
    if index == -1:
        return 0
    # child_node의 길이가 0인것은 child_Node가 없는 것이므로, leaf_node이다 그러므로 1을 반환해준다.
    if len(child_nodes[index]) == 0:
        return 1
    result = 0
    # 현재 노드인 index의 child_node를 가져와서, 재귀를 실행시켜준다.
    for child_node in child_nodes[index]:
        result += find_leafs(child_node,child_nodes)
    return result



N = int(input())
graph  = list(map(int,input().split()))
# 최상위 노드를 찾아주기 위함이다. 초기값은 node에 존재하지 않는 값으로 해준다.
root_node = -1
remove_node = int(input())
child_nodes = {i:[] for i in range(N)}

for ind in range(N):
    # 우리는 leaf_node를 찾을것이고, 해당 index에 부모 node로 들어온 
    # input값을 반대로 바꿔주는 과정이 필요하다.
    # 만약에 지우는 node와 index가 같으면 굳이 parent을 찾아 child를 넣어주는 과정이 필요없다.
    # 그래서 continue로 넘어가준다.
    # 또한 유일하게 부모가 없는 root_node는 따로 구분을 해준다. if문의 순서가 remove_node가 먼저 앞으로
    # 오는 이유는 remove_node가 root_node일수 있기 때문이다. 이럴때를 구분해주기 위해, remove_node인지 판별하는게 먼저온다.
    # 그외에는 전부 parent_node를 기준으로 child를 추가해주는 방식으로 해준다.
    if remove_node == ind:
        continue
    if graph[ind] == -1:
        root_node = ind
        continue
    child_nodes[graph[ind]].append(ind)

# root_node를 기점으로 leaf_node를 찾는 재귀함수를 실행시켜준다.
print(find_leafs(root_node,child_nodes))

# # # 9019 DSLR 
# # # 레지스터 0이상 10000미만 십진수 저장
# # # n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4
# # # D는 n을 두배로 바꾼다. 결과값이 9999보다 큰 경우는 1만으로 나눈 값 (2n mod 10000)
# # # S : n에서 1을 뺀값 n이 0이면 9999로 대신 저장
# # # L : n을 각자리숫를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다.  d2, d3, d4, d1
# # # R : n을 오른쪽으로 회전 
import collections

def DSLR(num):
    D_num = num *2
    if D_num > 9999:
        D_num = D_num%10000
    S_num = num -1
    if not num:
        S_num = 9999
    L_num = (num*10)%10000 + num//1000
    R_num = num//10 + num%10*1000
    return [D_num,S_num,L_num,R_num]



T = int(input())
DSLR_IND = ['D','S','L','R']
for tc in range(T):
    A,B = list(map(int,input().split()))
    deque = collections.deque()
    deque.append((A,''))
    dp = [0]*10000
    dp[A] = 1
    flag = False
    while deque:
        num,result = deque.popleft()
        if num == B:
            break
        temp = DSLR(num)
        for ind in range(4):
            if not dp[temp[ind]]:
                dp[temp[ind]] = 1
                if temp[ind] == B:
                    result = result + DSLR_IND[ind]
                    flag = True
                    break
                deque.append((temp[ind],result+DSLR_IND[ind]))
        if flag:
            break
    print(result)

이 문제에서 어려웠던 점은 2가지였다.

첫번째는 시간초과의 압박이다. 스트링과 list의 특성을 이용해 L,R을 쉽게 구현을 할려고 했는데, str과 list를 이용해 L,R을 구현하는 순간 시간초과가 계속됬다.

두번째는 L,R의 제대로 된 이해였다.

문제를 처음봤을때 12가 있으면 이게 L이면 21이 되고 R이면 21이 되는줄 알았다. 이렇게 구현을 해놨었는데, 계속 틀렸습니다가 나와서 문제를 찬찬히 읽어보니 이 문제에서는 무조건 4자리로 강제가 되던것이다.

12가 그냥 12가 아닌 0012인 상태인것이다. 그래서 L을 하면 0120이 되는것이고 R을 하면 2001인 것이다. 이부분을 조심해줘서 풀면 되는 것이었다.

이 문제는 modular를 이용해 L,R을 구현해주면 된다.

L은 원래 Number에서 10배를 해주고 10000으로 나머지를 구한뒤, 제일 첫번째 숫자의 몫을 구하기 위해 Number의 1000으로 나눈 몫을 더해주면 된다.

R은 원래 Number를 10으로 나눈 몫을 구하고, 나머지에는 1000을 곱해서 더해주면 된다.

그리고 bfs를 이용해서 풀때, 목표값인 B와 비교를 해주는 것을 for문 밖 popleft를 한 바로 뒤에 나뒀더니, 의미없는 반복문이 더 진행이 되었기 때문에, for문 안에 두어서 바로바로 비교한뒤 flag를 두어서, 바로 결과가 출력되게 만들어줬다.

def check():
    global N,H
    for ind in range(N):
        current_ind = ind
        for k in range(H):
            if visited[k][current_ind]:
                current_ind += 1
            elif current_ind>0 and visited[k][current_ind-1]:
                current_ind -= 1
        if current_ind != ind:
            return False
            
    return True




def dfs(row_index,col_index,cnt,limit):
    global N,H,result
    if cnt > limit:
        return
    if check():
        result = min(cnt,result)
        return
    for k in range(row_index,H):
        if k == row_index:
            search_y = col_index
        else:
            search_y = 0
        for y in range(search_y,N-1):
            if not visited[k][y] and not visited[k][y+1]:
                visited[k][y] = 1
                dfs(k,y+2,cnt+1,limit)
                visited[k][y] = 0









N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
result = float('inf')
visited = [[0]*N for _ in range(H)]
for _ in range(M):
    row,node = map(int,input().split())
    visited[row-1][node-1] = 1
if check():
    print(0)
else:
    for limit_insert_rows in range(1,4):
        dfs(0,0,0,limit_insert_rows)
        if result != float('inf'):
            print(result)
            break
    else:
        print(-1)

문제에서 최고로 놓을  수 있는 사다리의 개수는 3개가 최대이므로, 기본적으로 전체 사다리를 놓을 수 있는 위치를 골라서 재귀로 푸는 방식으로 해줬다. 그리고 result값이 바뀌면 break로 탈출을 해줬다. 

사다리의 가로선의 정보를 node-1,node 둘 중 왼쪽인 node-1에 저장해줬다.

그리고 사다리가 놓을 수 없는 조건은 현재 위치인 [가로선][세로선] 과 [가로선][세로선+1] 위치에 전부 0이 존재하면 사다리를 놓을 수 있다고 가정했다. 그리고 난뒤 재귀함수에서 y축을 +2만큼 이동시켜줬다. 그 이유는 해당 가로선에서  내가 고른 세로선에서 사다리를 놓게 되면 세로선 과 세로선+1의 위치에는 사다리를 놓을 수 없다. 그러므로, y를 +2 해주었다.

그리고, 가로선 중에서 주어진 row_index가 같을때에만 그러고 그 다음 가로선부터는 전체 세로선에 대해서 탐색하면 된다.

이렇게 사다리를 추가해주면서, check()라는 함수를 통해, 문제에 주여진 조건인 start_index와 사다리를 통과하고 나온 index가 같은지 비교를 해줘서 True,False 값을 반환시켜주었다.

이렇게 풀었지만, 다른 사람들의 코드를 공부하고 더 나은 풀이로 나중에 고쳤다.

import sys
def check():
    global N,H
    for ind in range(N):
        current_ind = ind
        for k in range(H):
            current_ind += visited[k][current_ind]
        if current_ind != ind:
            return False
            
    return True




def dfs(ladder_index,cnt,limit):
    global N,H,result
    if limit == cnt:
        if check():
            result = limit
        return
    for ind in range(ladder_index,N*H):
        row_index = ind//N
        col_index = ind%N
        if col_index == N-1:
            continue
        if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
            visited[row_index][col_index] = 1
            visited[row_index][col_index+1] = -1
            dfs(ind+2,cnt+1,limit)
            if result != 4:
                return
            visited[row_index][col_index] = 0
            visited[row_index][col_index+1] = 0





N,M,H = map(int,input().split())
# H는 놓을 수 있는 개수
# M 은 가로선의 개수
# 앞은 가로선의 위치 뒤는 2개의 위치
if M == 0:
    print(0)
else:
    result = 4
    call = 0
    visited = [[0]*N for _ in range(H)]
    for _ in range(M):
        row,node = map(int,sys.stdin.readline().split())
        visited[row-1][node-1] = 1
        visited[row-1][node] = -1

    if check():
        print(0)
    else:
        for k in range(1,4):
            dfs(0,0,k)
            if result != 4:
                break
        if result != 4:
            print(result)
        else:
            print(-1)

 기본적인 원리는 비슷하다. 하지만 몇몇 부분에서 백트래킹을 해줬다.

먼저 좌측에만 가로선의 정보를 저장했던 거에서, 좌우측에 정보를 저장해줬다. 대신 그 값을 1과 -1을 저장시켜줬다.

이전 코드에서 좌측에 있는지 우측에 있는지 판별해서 세로선의 index를 바꿔주던거에서 좀 더 깔끔하게 바꿔주었다.

그리고 매 함수마다 check를 해주던 것을 cnt == limit에 도달했을때, check를 해주었다.

또한 결과값의 기본값이 바뀌었을때 break를 해주는 곳을 여러군데 추가해줬다.

가장 크게 바뀐 것은 2중 for문을 돌리던 것을 단일 for문으로 바꿔주었다.

다음과 같이 세로선 8과 가로선 4일때를 그려보면 다음과 같이 사다리를 그릴수 있을 것이다.

여기서 각각의 교차선을 구한다고 생각하면,

다음과 같이 세로선 8* 가로선 4 만큼의 교차선이 나올 수 있다. 그러므로 문제에 주어진 N*H 만큼의 교차선이 주어질 수 있다.

이 중에서 사다리를 놓을 수 있는 교차선은 빨간색 동그라미가 쳐진 교차선 뿐이다. N번 세로선인 8번 세로선에는 그 다음 세로선이 없기 때문에 사다리를 놓을 수 없다.

그 외의 나머지 부분 교차선에 사다리를 놓는다고 생각하고 재귀함수를 돌리면 된다. 위에서 설명 했듯이 한 곳에 사다리를 놓을시, 해당 교차선 위치에서 가로로 2칸만큼 더 가야지만 사다리를 놓을 수 있다. 

    for ind in range(ladder_index,N*H):
        row_index = ind//N
        col_index = ind%N
        if col_index == N-1:
            continue
        if not visited[row_index][col_index] and not visited[row_index][col_index+1]:
            visited[row_index][col_index] = 1
            visited[row_index][col_index+1] = -1
            dfs(ind+2,cnt+1,limit)
            if result != 4:
                return
            visited[row_index][col_index] = 0
            visited[row_index][col_index+1] = 0

함수에서 이부분이 교차선을 나타내고, 교차선의 가로선과 세로선을 찾아내서 세로선이 마지막 위치한 것이면 넘어가고, 

사다리를 놓을 수 있으면, 사다리를 놓은 뒤, 해당 index에서 +2를 해줘서 재귀함수를 해준다.

구현은 안했지만, 가능한 또 다른 방법은 사다리를 놓을 수 있는 교차선들을 전부 구해놓은 상태에서, 조합을 이용해 사다리를 1개 놓았을 때, 2개 놓았을 때, 3개 놓았을 때,를 구분하고, 고른 사다리가 문제가 없는지 판별해주고, 문제에 조여진 조건대로 시작 index와 도착 index를 같은지 판별하는 방법을 써도 될것 같다.

문제 자체는 어렵게 보이지 않았지만, 실제로 구현하는데에 어려운점이 많았고, 많이 틀렸던 문제였다.

중간중간 가능성이 없는것을 멈춰주고, 시간을 줄이는데 노력해야지 풀 수 있었던 힘들었던 문제였다.

# 18231 파괴된 도시






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

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

for _ in range(M):
    node1,node2 = map(int,input().split())
    graph[node1].append(node2)
    graph[node2].append(node1)

destory_cnt = int(input())
destroy_citys = list(map(int,input().split()))
result = []
destroyed = []
for destroy_city in destroy_citys:
    temp = [destroy_city]
    for city in graph[destroy_city]:
        if city not in destroy_citys:
            break
        else:
            temp.append(city)
    else:
        result.append(destroy_city)
        destroyed.extend(temp)
    if len(set(destroyed)) == destory_cnt:
        print(len(result))
        result.sort()
        print(' '.join(list(map(str,result))))
        break
else:
    print(-1)

이 문제는 여러가지 경우의 답이 나올수 있으나, 정답이 되는 1개만 출력하면 된다.

기본 원리는 이렇다. 그래프라는 딕셔너리에 양방향으로 노드를 전부 저장해놓는다.

그리고 파괴된 도시 목록을 입력을 받아, for문을 돌리는데, 만약 파괴된 도시 중 하나의 인접 노드들 중에 파괴된 노드들이 하나도 없으면 for문을 중지하고, 나온다. 그렇지 않을경우는 해당 도시는 파괴가 시작된 도시로 볼 수 있으므로, 결과목록에 넣어준다.

또한 해당 도시로 폭파된 도시 목록도 별도의 리스트에 저장해준다.

이렇게 반복을 해주면서, 별도로 저장해놓은 폭파된 도시목록을 set을 해줬을때의 길이가, 전체 파괴된 도시수와 동일하다면 for문을 중지하고, 결과를 보여준다.

위의 해당사항이 하나도 없을 시에는 -1을 출력해주면 된다.

# Longest Common Subsequence
#  최장 공통 부분 수열
def LCSlength(X,Y):
    for i in range(1,len(X)+1):
        for j in range(1,len(Y)+1):
            if X[i-1] == Y[j-1]:
                LCS_ARRAY[i][j] = LCS_ARRAY[i-1][j-1] + 1
            else:
                LCS_ARRAY[i][j] = max(LCS_ARRAY[i][j-1],LCS_ARRAY[i-1][j])
    
def findBackTrack(C,X,Y,i,j):
    if i == 0 or j == 0:
        return ''
    if X[i-1] == Y[j-1]:
        return findBackTrack(C,X,Y,i-1,j-1) + X[i-1]
    if C[i][j-1] > C[i-1][j]:
        return findBackTrack(C,X,Y,i,j-1)
    return findBackTrack(C,X,Y,i-1,j)




string_1 = list(input())
string_2 = list(input())
LCS_ARRAY = [[0]*(len(string_2)+1) for _ in range(len(string_1)+1)]
LCSlength(string_1,string_2)
result = findBackTrack(LCS_ARRAY,string_1,string_2,len(string_1),len(string_2))
print(len(result))
print(result)

이론에 대한 설명은 다른 사람들의 블로그에 더 자세히 설명되어있고,

저같은 경우 ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

위키를 참조하면서 풀었다.

LIS와 LCS같은 DP 문제들은 반복 숙달이 되지 않으면 실전에서 푸는게 어려워 보인다.

제가 이해한 기본적인 원리는 다음과 같다.  문자열 S1 과 문자열 S2가 있으면, 이 두 문자열의 길이만큼의 2차원 행렬을 만들어준다.

이 행렬은 두 문자열이 같은 문자열을 얼마나 가지고 있는지 판별이 되는 행렬이다. 이행렬의 이름을 LCS라 하고, 이 행렬의 크기는 (문자열 S1의 길이 +1) X (문자열 S2의 길이 +1)이 된다. 왜냐하면 아무것도 선택하지 않았을때를 초기화 해주는 부분이 있기 때문이다.

그리고 S1,S2를 기준으로 2중 for문을 돌려준다. 그러면서 s1과 s2에서 똑같은 문자열이 발견이 되면, 

LCS[i][j]에 = LCS[i-1][j-1] +1 을 해준다.

왜 대각선 성분에 있는걸 더해주는 이유는 똑같은 문자열이 발견되기 직전의 각각의 index에 존재하는 값이 해당 부분직전까지의 최대값이기 때문이다.

코드를 보면 좀 헷갈리는 이유는 S1,S2의 index는 0부터 시작하기 때문이다. s1,s2의 i,j index의 LCS의 길이값은 LCS의 i+1,j+1 index에 저장이 된다.

만약 같지 않을 경우, [i-1, j], [i,j-1] 둘중 큰 값을 넣어주면 된다.

이렇게 구한 LCS를 이용해서 역추적으로 최장 공통 부분수열을 구성 값을 구해준다.

이 방법은 단 1개를 구하는 것이므로, 다른 방법은 위의 위키를 참조하거나, 다른 사람 블로그를 참조하길 바란다.

백트래킹으로 찾는 방법인데, 각가의 끝 인덱스에서 시작해서 만약에 두 인덱스에서의 S1,S2의 값이 같으면, 그 부분을 결과에 return 시켜주고, 현재 index는 두 값이 같기 때문에, i-1,j-1위치에서 백트래킹을 해준다.

그리고 그 외에는 LCS의 길이가 변경되는 순간이 같은 문자열이 존재하는 구간이기 때문에, 

[i-1][j] 와 [j][j-1의 LCS의 길이를 비교해서 더 큰 곳으로 이동해서 계쏙 반복을 해준다.

이 이론에 대해서는 아직 제대로 공부를 안했기 때문에 미숙한 부분이 많고,

저보다 더 나은 설명을 한 블로그들이 많으니 그 블로그를 참조하는 것을 권장합니다.

# 2565 전깃줄

N = int(input())
dp = [0]*501
arr = []
for _ in range(N):
    n1,n2 = map(int,input().split())
    arr.append((n1,n2))
arr.sort()
result = []
result.append(arr[0][1])
temp = 0
for k1,k2 in arr[1:]:
    for ind,val in enumerate(result):
        if val > k2 and k2 not in result:
            result[ind] =k2
            temp = 0
        elif val < k2 and k2 not in result:
            temp = k2
    if temp:
        result.append(temp)
    temp = 0


print(N-len(result))

개인적으로 어려워 하는 LIS 계열의 문제였다.

전깃줄 A를 기준으로 sort를 해준 다음에,  전깃줄 B를 기준으로 가장 긴 증가하는 수열의 구해주면 된다.

그렇게 되면, 선이 꼬이지 않고 설치할 수 있는 최대수가 되고, 주어진 N에서 최대수를 빼주면 된다.

코드 자체를 설명해보면 초기값으로 가장 첫번쨰  B 전깃줄을 넣어주고,

전체 데이터 들어진 행렬을 반복문을 돌리면서, LIS가 저장된 값과 비교를 하면서 LIS에 저장된 값보다 적으면 바로 그자리를  교체 해준다. 그리고 LIS가 저장된 값보다 전부다 크면 끝에 추가해주면 된다.

이 방법은 실제 LIS의 수열을 구하는 것이 아닌, 최장 길이를 구하기 위한 O(Nlogn)의 방식이다. 만약 실제 LIS를 구해야 하는 경우에는 다른 풀이를 찾아야한다.

# 1038 감소하는 수
# X의 자릿수가 가장 큰 자릿수
import collections
def dfs(N):
    deque = collections.deque()
    for i in range(1,10):
        deque.append((i,str(i)))
    while deque:
        if len(result) == N+1:
            break
        cur_num,to_num = deque.popleft()
        if cur_num != 0:
            for k in range(cur_num):
                temp = to_num + str(k)
                deque.append((k,temp))
                result.append((temp))


N = 1023
result = []
for i in range(10):
    result.append(i)

if N >=10:
    dfs(N)
if len(result) > N:
    print(result[N])
else:
    print(-1)

 기본적인 백트래킹 문제이다. 처음에 1~9의 수를 넣어주고, 그보다 낮은 자리수에서 더 낮은 값을 넣어주면서 결과값에 넣어주고, 해당 길이를 초과하는 N이 나올시에는, -1을  출력하도록 했따.