Coding 공부

import sys
 
 
def input():
    return sys.stdin.readline().rstrip()
 
 
def find_parents(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parents(make_set[ind])
    return make_set[ind]
 
def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
    if ranks[X] < ranks[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if ranks[X] == ranks[Y]:
        ranks[X] += 1
 
 
N,M = map(int,input().split())
 
arr = [0] + list(input().split())
weight_list = []
for _ in range(M):
    x,y,pay = map(int,input().split())
    if arr[x] != arr[y]:
        weight_list.append((pay,x,y))
 
weight_list.sort(reverse=True)
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]
 
cnt = 0
result = 0
while weight_list:
    pay,x,y = weight_list.pop()
    X,Y = find_parents(x), find_parents(y)
 
    if X != Y:
        union(X,Y)
        cnt += 1
        result += pay
    if cnt == N-1:
        break
 
if cnt != N-1:
    print(-1)
else:
    print(result)

이 문제는 처음부터 간선을 저장할때 두 노드가 남초+여초인 조합인 경우에만 저장을 해서 크루스칼을 해주면 된다.

그리고 크루스칼을 진행하고, 전체 cnt의 개수가 N-1이 안되는 경우에는 전부 연결이 안되는 경우이니 -1을 출력해주고

같을 때에는 result를 출력해주면 된다.

def Innerbound(x,y):
    if 0<=x<N and 0<=y<M:
        return True
    else:
        return False
 
def dfs(idx,bit,total):
    global result
    if bit == 2**(N*M)-1:
        result = max(result,total)
        return
    else:
        if 2**idx&bit:
            dfs(idx+1,bit,total)
        else:
            x,y = idx//M, idx%M
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx + 1
                    ny = ny
                else:
                    break
            for rx in range(nx-1,x-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = rx*M + y
                temp_bit = temp_bit^(2**next_idx)
                visited[rx][y] = True
            nx,ny = x,y
            temp_bit = bit
            temp_num = 0
            while Innerbound(nx,ny):
                if visited[nx][ny]:
                    next_idx = nx*M + ny
                    visited[nx][ny] = False
                    temp_bit = temp_bit|(2**next_idx)
                    temp_num = temp_num*10 + arr[nx][ny]
                    nx = nx
                    ny = ny + 1
                else:
                    break
            for ry in range(ny-1,y-1,-1):
                dfs(idx+1,temp_bit,total + temp_num)
                temp_num = temp_num//10
                next_idx = x*M + ry
                temp_bit = temp_bit^(2**next_idx)
                visited[x][ry] = True
 
 
N,M = map(int,input().split())
 
arr = [list(map(int,list(input()))) for _ in range(N)]
 
visited = [[True for _ in range(M)] for _ in range(N)]
result = 0
dfs(0,0,0)
print(result)

처음에 모든 경우들을 각각 하나씩 그려보면서 dfs를 해주었다.

가로 혹은 세로로 최대한 세울 수 있는 직사각형을 그려주고 그때부터 dfs를 하고 하나씩 내려주면서 dfs를 해주었다.

이 방식은 오래걸리는 방식이였고, 다른 사람들의 풀이를 보고 다시 푼 방식은 다음과 같다.

N,M = map(int,input().split())
 
arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
# 0은 가로인걸로 1은 세로인걸로 판별
for bit_shape in range(2**(N*M)):
    total_sum = 0
    for x in range(N):
        sub_sum = 0 # 작은 단위의 SUM
        for y in range(M):
            idx = x*M + y
            if not bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    
    for y in range(M):
        sub_sum = 0
        for x in range(N):
            idx = x*M + y
            if bit_shape & (1<<idx):
                sub_sum = sub_sum*10 + arr[x][y]
            else:
                total_sum += sub_sum
                sub_sum = 0
        total_sum += sub_sum
    result = max(result,total_sum)
print(result)

이 방식은 모든 경우를 먼저 구하는 거다. 이 문제는 최대 16개의 칸을 가지는 것이다.

이것을 비트로 표현해서 0이면 가로로 그려진 직사각형 1이면 세로인 직사각형으로 구분을 해주는것이다.

그러면 우리는 2**(N*M)의 경우의 수를 가질수 있다. 최대 65536가지이므로, 빠르게 구할 수 있다.

비트로 현재 종이조각의 상태를 구분하고, 그 상태에 맞게 숫자를 세서 최대값을 구하면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
def union(a,b):
    A = find_parent(a)
    B = find_parent(b)
    if A != B:
        if rank[A] < rank[B]:
            A,B = B,A
        make_set[B] = A
        if rank[A] == rank[B]:
            rank[A] += 1
        return True
    return False
 
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]
 
def kruskal():
    value = 0
    for p,x,y, in weight_list:
        if union(x,y):
            value += 1^p
    return value
 
 
N,M = map(int,input().split())
weight_list = []
for _ in range(M+1):
    x,y,p = map(int,input().split())
    weight_list.append((p,x,y))
make_set = list(range(N+1))
rank = [1]*(N+1)
weight_list.sort()
a = kruskal()
weight_list.sort(reverse=True)
make_set = list(range(N+1))
rank = [1]*(N+1)
b = kruskal()
print(a**2-b**2)

이 문제는 크루스칼을 활용해서 풀면 되는 문제이고, 크루스칼에 사용되는 간선을 오름차순과 내림차순으로 각각 정렬해서 

그때 크루스칼을 해서 값을 구한뒤 제곱값을 빼주면딘다.

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()
def path(s,e):
    if next_node[s][e] == None:
        return [0]
    else:
        result = [s]
        while s != e:
            s = next_node[s][e]
            result.append(s)
        return result
N = int(input())
M = int(input())
INF = float('inf')
distance_list = [[0 if i==j else INF for j in range(N+1)] for i in range(N+1)]
 
next_node = [[None for _ in range(N+1)] for _ in range(N+1)]
graph = [{} for _ in range(N+1)]
for _ in range(M):
    x,y,pay = map(int,input().split())
    if distance_list[x][y] > pay:
        distance_list[x][y] = pay
        next_node[x][y] = y
 
 
for mid in range(1,N+1):
    for start in range(1,N+1):
        for end in range(1,N+1):
            if distance_list[start][end] > distance_list[start][mid] + distance_list[mid][end]:
                distance_list[start][end] = distance_list[start][mid] + distance_list[mid][end]
                next_node[start][end] = next_node[start][mid]
 
 
for i in range(1,N+1):
    print(*[val if val != INF else 0 for val in distance_list[i][1:]])
 
 
for start in range(1,N+1):
    for ends in range(1,N+1):
        if distance_list[start][ends] == INF:
            print(0)
        else:
            answer = path(start,ends)
            if len(answer) == 1:
                print(0)
            else:
                print(len(answer),*answer)

플로이드 와샬을 이용해서 풀어야하는데

여기서 중요한 점은 이동지점을 추적해야한다.

그 방법은 start-> end까지 갈때 들리는 노드를 갱신을 해주는 것이다.

a->b로 갈때 b로 간다고 저장을 해놨을때

중간에 값을 갱신한 mid가 있으면

a->b에 b가 아닌 mid를 저장해준다.

이렇게 함으로서

end_node가 동일한 것이 나올때까지 계속 반복을 해주면 되는 것이다.

플로이드 와샬은 자주 사용했지만, 경로를 구해본적은 처음이여서 힘들었다.

이 부분은 외우고 나중에 사용할 수 있도록 노력해야겠다.

import sys
 
 
def input():
    return sys.stdin.readline().rstrip()
 
 
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
 
 
T = int(input())
 
 
for tc in range(1,T+1):
    N = int(input())
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]
 
    for _ in range(int(input())):
        x,y = map(int,input().split())
        union(x,y)
    print(f'Scenario {tc}:')
    for _ in range(int(input())):
        x,y = map(int,input().split())
        if find_parents(x) != find_parents(y):
            print(0)
        else:
            print(1)
 
    if tc != T:
        print()

전형적인 분리집합 문제였다.

들어오는 입력대로 union을 해주었고, 서로의 부모가 다를시에는 0 같을 시에는 1이 출력되게 했다.

import sys
from collections import deque
def input():
    return sys.stdin.readline().rstrip()
 
def pop(queue,flag):
    if flag:
        return queue.pop()
    else:
        return queue.popleft()
T = int(input())
 
for _ in range(T):
    commands = list(input())
    N = int(input())
    if N:
        arr = deque(input().replace('[','').replace(']','').split(','))
    else:
        input()
        arr = deque()
    # 0 정방향 1 역방향
    flow = 0
    flag = True
    for command in commands:
        if command == 'R':
            flow = (flow+1)%2
        else:
            if arr:
                pop(arr,flow)
            else:
                flag = False
                break
    if flag:
        if flow:
            arr.reverse()
        print(f'[{",".join(arr)}]')
    else:
        print('error')

이 문제는 deque를 통해, 역방향인지 정방향인지에 따라 나눠서 결정을 지으면 되는 문제였다.

정방향인지 역방향인지에 따라 pop을 하는 위치를 바꿔주고, 최종 결과를 출력을 할때에도, 구분을 해줬다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
while True:
    N,M = map(int,input().split())
    if not N+M:
        break
    dp = [[0 for _ in range(M+1)]]
 
    for _ in range(N):
        temp = [0]+list(map(int,input().split()))
        dp.append(temp)
    result = 0
    
    for x in range(1,N+1):
        for y in range(1,M+1):
            dp[x][y] = min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1]) + 1 if dp[x][y] else 0
 
            if result<dp[x][y]:
                result = dp[x][y]
    print(result)

이 문제는 유명한 문제이다. 원래 행렬에서 최상단과 좌측에 0인 배열을 넣어주고, 탐색을 해주면 된다.

그리고 (x-1,y), (x,y-1), (x-1,y-1) 의 최소값에 + 1을 해준다. 만약 dp[x][y]에 1이 있을 경우에만

그렇지 않을때에는 0을 넣어주면 된다.

그리고 탐색을 하면서 최대값을 갱신해주면 된다.

import sys
 
def input():
    return sys.stdin.readline().rstrip()
 
T = int(input())
 
for _ in range(T):
    d,n = map(int,input().split())
 
    mod = [ 0 for _ in range(d)]
    arr = list(map(int,input().split()))
    prefix_sum = [0] + arr[:]
    mod[0] += 1
    for i in range(n):
        prefix_sum[i+1] += prefix_sum[i]
        prefix_sum[i+1] %= d
        mod[prefix_sum[i+1]] += 1
    result = 0
 
    for i in range(d):
        result += (mod[i] * (mod[i]-1))//2
 
    print(result)

이 문제는 누적합을 활용한 문제이다. 

먼저 누적합을 구하면서 해당 누적합을 d로 나눈 나머지를 mod에 개수로 세어준다.

그러면 우리는 좌측부터 누적했을 때의 d로 나눴을 때  나오는 나머지의 값들이 언제 나오는지 알 수 있다.

그러면 우리는 d로 나눠지는 모든 경우의 수는

같은 나머지를 가지는 구간에서 2개를 뽑아서 그 두 구간을 빼주면 나머지가 0이 됨을 알 수 있다.

그러므로, 우리는 0부터 d-1까지 nC2를 해주면 된다.

그리고 우리는 0부터 하기 위해서, 0일때에 기본값으로 다른 나머지와 달리 1을 넣어주었다.