Coding 공부

### FFT를 쓰는걸 보고 연습하는 문제 ####
import sys
from cmath import exp,pi
def fft(a):
    N=len(a)
    if N==1:
        return a
    a_even=fft(a[0::2])
    a_odd=fft(a[1::2])
    w_N=[exp(2j*pi*n/N) for n in range(N//2)]
    return [a_even[n] +w_N[n]*a_odd[n] for n in range(N//2)] + [a_even[n]-w_N[n]*a_odd[n] for n in range(N//2)]

def ifft(a):
    N=len(a)
    if N==1:
        return a
    a_even=ifft(a[0::2])
    a_odd=ifft(a[1::2])
    w_N=[exp(-2j*pi*n/N) for n in range(N//2)]
    return [a_even[n] +w_N[n]*a_odd[n] for n in range(N//2)] + [a_even[n]-w_N[n]*a_odd[n] for n in range(N//2)]

M=int(sys.stdin.readline())
N=2*M
even=0
for i in range(18):
    if M==2**i:
        even=-100
        break
    elif N<2**i:
        even=i
        break
A=list(map(int,sys.stdin.readline().split()))
B=list(map(int,sys.stdin.readline().split()))
if even==-100:
    A=A[:]+A[:]
    B=B[-1::-1]+[0]*M
    C=[0]*N
    A_fft=fft(A)
    B_fft=fft(B)
    for i in range(N):
        C[i]=A_fft[i]*B_fft[i]

    C_ifft=ifft(C)
    for k in range(N):
        C_ifft[k]=round(C_ifft[k].real/N)
    max_number=max(C_ifft)
else:
    N_prime=2**i
    N,N_prime=N_prime,N
    A=A[:]+[0]*(N-N_prime//2)
    B=B[-1::-1]+[0]*(N-N_prime)+B[-1::-1]

    C=[0]*N
    A_fft=fft(A)
    B_fft=fft(B)
    for i in range(N):
        C[i]=A_fft[i]*B_fft[i]
    C_ifft=ifft(C)
    for k in range(N):
        C_ifft[k]=round(C_ifft[k].real/N)
    max_number=max(C_ifft)
print(max_number)

casterian.net/archives/297

blog.naver.com/kks227/221633584963

FFT에 대한 자세한 설명은 위 2개의 블로그를 보면 될것 같다.

기본적으로 주어진 수가 2의 제곱수일때와 아닐때를 구분해서 FFT를 구현했고, A와 B를 FFT를 통해 DFT를 구해놓은 상태에서, 

이 이동의 값은 A,B의 합성곱을 나타낼수 있는데, 이걸 FFT를 통해 구해낸 DFT A와 DFT B의 곱셉으로 A와B의 합성곱의 DFT화 된 C를 구할 수 있다.

우리가 원하는 것은 실수부에 있는 것이므로, DFT화 된 C를 IFFT로 고속 역 푸리에변환을 해주고, 이때의 값을 반올림을 한 상태에서 최대값이 되는 것을 구하면 된다.

이 문제 자체를 합성곱으로 해서 풀어야한다는 것을 알았지만, 이 FFT를 어떻게 구현하는지에 대해서는 지식이 부족하여, 위 블로그들을 참조하여 구현했다.

제 설명보다는 위의 2 블로그를 참조하는 것을 추천합니다.

def calc(n,t):

    cnt=1
    while n!=0:
        while n%10 !=9:
            if n!=0:
                for i in str(n):
                    s_i[int(i)]+=cnt
                n-=1
            else:
                return
        if n<10:
            for i in range(n+1):
                s_i[i]+=cnt
            s_i[0]-=cnt
            return
        else:
            for i in range(10):
                s_i[i]+=(n//10+1)*cnt
        s_i[0]-=cnt
        cnt*=10
        n=n//10
    return









N=int(input())
s_i=[0]*10
calc(N,s_i)
print(*s_i)

수학과 관련된 문제이다. 어려웠다.

www.slideshare.net/Baekjoon/baekjoon-online-judge-1019

자세한 설명은 백준님의 설명을 보면 되겠다.

1 ~ N 까지인데, 이걸 A~B로 보고

A는 0을 끝자리로 B는 끝자리를 9로 맞춰준고 계산을 하는거다.

만약 A가 3827 B가 9257 이라 하면

A 를 3830으로 맞춰주고, B를 9249로 맞춰준다 이렇게 됬을시, 1의 자리의 개수는

0~9 까지 총 (924-383+1)개 만큼이 나온다. 이걸 결과값에 누적을 시켜놓고 A,B를 10으로 나눈 몫으로 바꿔준다.

그러면 A는 383 B는 924가 되는데, 이걸 다시 A는 끝자리를 0으로 B는 9로 맞춰준다.

위와 같이하면 A는 390 B는 919가 된다.

여기서 기본 개수인 cnt를 기존의 1에서 10배가 되어야하는데 그 이유는 십의 자리이기 때문이다.

가볍게 생각해보면 우리가 11~39 까지라고 했을시 십의 자리는 1~3 이다. 하지만 그 사이에 나온 숫자는 총 30개이다.

이렇듯 자리수에 따라 10배씩 해주면 된다.

이와 같은 방식으로 하면서 A의 수가 B를 넘어가게 되면 멈추면 된다.

위의 코드는 과거에 푼 코드로, A를 0으로 고정해놓고 푼 방식이다. 그렇다 보니 매 번 0의 자리 수의 개수를 현재의 cnt만큼 빼주는 것이다.

def calc(number,cnt):
    global number_list
    while number > 0:
        number_list[number%10] += cnt
        number = number//10



def solution(start,end):
    global number_list
    cnt = 1
    while start <= end:
        if start%10 != 0:
            while start % 10 != 0 and start <= end:
                calc(start,cnt)
                start += 1
        if start > end:
            break
        if end%10 != 9:
            while end % 10 != 9 and start <= end:
                calc(end,cnt)
                end -= 1
        distance = (end//10 - start//10 + 1)
        for i in range(10):
            number_list[i] += distance * cnt
        cnt *= 10
        start = start//10
        end = end//10







N = int(input())
start = 1
number_list = [0]*10
solution(start,N)
print(*number_list)

백준님의 설명대로 짤 시 오히려 더 간단하게 풀리는걸 알 수 있다.

위의 코드는 백준님의 설명대로 짠 코드이다.

N = int(input())

arr = list(map(int,input().split()))
minus_inf = -float('inf')
dp = [[minus_inf]*N for _ in range(2)]
dp[0][0] = arr[0]
for ind in range(1,N):
    dp[0][ind] = max(dp[0][ind-1]+arr[ind],arr[ind])
    dp[1][ind] = max(dp[0][ind-1],dp[1][ind-1]+arr[ind])

print(max(map(max,dp)))

DP 관련 문제이다. 점화식을 찾고, 그걸 표현하는데 오래걸렸다. 

기본 문제풀이 원리는 다음과 같다. 2개의 DP를 만들어

한쪽은 원래 그대로의 수열을 표현했을 때, 최대값을 저장해놓은 DP 배열

다른 한쪽은 수열 중 한 부분을 뺐을때, 최대값을 저장해놓는 DP 배열이다.

DP[flag][IDX] = flag가 0이면 계속해서 연속인 배열, 1이면, 배열 중 한 인덱스를 뺏을때의 배열을 나타낸다.

                     idx는 현재의 위치를 나타낸다.

먼저 원래 그대로 배열을 표현했을때 최대값이 될수 있는것은

현재 위치를 IDX라고 할시, DP[0][IDX] +arr[IDX]이나, arr[IDX] 중에 최대값이다. 계속 연속되는 합 같은경우 계속 이어져 오거나 현재위치부터 다시 시작하거나 둘중 하나이기 때문에 둘중 큰 값을 DP에 저장해놓는다.

그리고 배열 중 한 부분을 뺐을때 최대값이 될 수 있는것은

현재 IDX를 뺐을때와 현재 IDX는 포함하고 이전의 IDX 중 하나가 빠졌을때 둘 중 하나이다.

그러므로 점화식으로 나타내면 DP[1][IDX-1] + arr[IDX] , DP[0][IDX-1] 이다.

위와 같은 식으로 전체의 dp를 구한뒤 최대값을 출력해주면 된다.

import collections


def bfs(i):
    global N,graph,result
    stack = collections.deque()
    stack.append((i,0))
    visited = [True] * (N+1)
    visited[i] = False
    while stack:
        ind,dep = stack.popleft()
        for next_ind in graph[ind]:
            if visited[next_ind]:
                stack.append((next_ind,dep+1))
                visited[next_ind] = False
    return dep







N = int(input())
graph = [[] for _ in range(N+1)] 
while True:
    a,b = map(int,input().split())
    if a == -1 and b == -1:
        break
    graph[a].append(b)
    graph[b].append(a)


result = [50]*(N+1)
for i in range(1,N+1):
    result[i] = bfs(i)


min_list = [min(result),result.count(min(result))]
print(*min_list)
min_result = []
for i in range(1,N+1):
    if result[i] == min_list[0]:
        min_result.append(i)
print(*min_result)

 친구의 깊이를 물어보는 문제였다. 문제에서 들어오는 최대 인원이 50이므로 50으로 해놓은 상태에서 바꿨다.

그리고 깊이를 물어보는 것이기 때문에, DFS가 아닌 BFS를 이용해서 최단거리를 깊이로 생각해서 풀었다.

# 플로이드 와샬

N = int(input())
graph = [[0]+[50]*N if i!=0 else [50]*(N+1) for i in range(N+1)]
while True:
    a,b = map(int,input().split())
    if a == b == -1:
        break
    graph[a][b] = 1
    graph[b][a] = 1

for i in range(1,N+1):
    graph[i][i] = 0

for k in range(1,N+1):
    for from_node in range(1,N+1):
        for to_node in range(1,N+1):
            if graph[from_node][to_node] == 1 or graph[from_node][to_node] == 0:
                continue
            elif graph[from_node][to_node] > graph[from_node][k] + graph[k][to_node]:
                graph[from_node][to_node] = graph[from_node][k] + graph[k][to_node]


min_result = list(map(max,graph))

print(min(min_result),min_result.count(min(min_result)))
min_ind = []
for ind,val in enumerate(min_result):
    if val == min(min_result):
        min_ind.append(ind)
print(*min_ind)

플로이드 와샬 방식으로 푼 방식이다.

기본 원리는 같지만 연결을 표현한 방식이 달라졌을 뿐이다.

def dfs(i,cnt):
    global result
    visited[i] = False
    if cnt >= 5:
        result = True
        return
    for ind in graph[i]:
        if visited[ind]:
            dfs(ind,cnt+1)
    visited[i] = True


N,M = map(int,input().split())
graph = [[] for _ in range(N)]


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

visited = [True]*N
result = False
for i in range(N):
    dfs(i,1)
    if result:
        break
print(int(result))

DFS를 해서 깊이가 4 이상이면 True를 반환해주면 되는 문제이다.

위와 같이 재귀를 해서 풀어도 되고, 

import sys
input = sys.stdin.readline
def solution():
    global N
    for dep0 in range(N):
        for dep1 in graph[dep0]:
            for dep2 in graph[dep1]:
                if dep0 == dep2:
                    continue
                for dep3 in graph[dep2]:
                    if dep3 == dep1 or dep3 == dep0:
                        continue
                    for dep4 in graph[dep3]:
                        if dep4 != dep0 and dep4 != dep1 and dep4 != dep2:
                            return 1
    return 0

N,M = map(int,input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

print(solution())

깊이가 그리 깊지 않으니 하드코딩으로 분기처리를 해주어도 풀 수 있다.

N = int(input())


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

arr.sort()

start = 0
end = N-1
index_list = (arr[start],arr[end])
result = arr[end]+arr[start]

while start<end:
    temp = arr[end]+arr[start]
    if abs(result) > abs(temp):
        result = temp
        index_list = (arr[start],arr[end])
        if result == 0:
            break
    if temp >= 0:
        end -= 1
    else:
        start += 1


print(*index_list)

유명한 투 포인터 문제이다.

푸는 방법은 먼저 입력리스트를 정렬해준뒤에 0을 start로 N-1을 end로 둔다.

그리고 그 두 위치의 인덱스의 위치에 존재하는 값들의 합이 0보다 크면 end를 -1 하고 작으면 start를 +1 해준다. 그리고 그 합들이 0에 가까우면 교체해주는 방식으로 했다.

import sys
import heapq


def dijkstra(start,end,flag=True):
    global INF,N
    distance = [INF]*N
    distance[start] = 0
    node_list = []
    heapq.heappush(node_list,(0,start))
    while node_list:
        current_distance,node = heapq.heappop(node_list)
        if current_distance > distance[node]:
            continue          
        for next_node in graph[node]:
            temp_distance = current_distance + graph[node][next_node]
            if distance[next_node] > temp_distance:
                distance[next_node] = temp_distance
                heapq.heappush(node_list,(temp_distance,next_node))
    if flag and distance[end] != INF:
        stack = [(end,distance[end])]
        path_set = set()
        while stack:
            node,dis = stack.pop()
            for prev_node in parent[node]:
                if (prev_node,node) not in path_set:
                    if distance[prev_node] + graph[prev_node][node] == dis:
                        path_set.add((prev_node,node))
                        stack.append((prev_node,distance[prev_node]))
        
        for prev_node,next_node in path_set:
            del graph[prev_node][next_node]

    return distance[end]
INF = float('inf')
while True:
    N,M = map(int,sys.stdin.readline().split())
    if not N+M:
        break 
    S,D = map(int,sys.stdin.readline().split())

    distance = [[0]*N for _ in range(N)]
    graph = [{} for _ in range(N)]
    parent = [[] for _ in range(N)]
    for _ in range(M):
        U,V,P = map(int,sys.stdin.readline().split())
        graph[U][V] = P
        parent[V].append(U)
    min_distance = dijkstra(S,D)
    if min_distance == INF:
        print(-1)
    else:
        cu_distance = dijkstra(S,D,False)
        if cu_distance != min_distance:
            if cu_distance != INF:
                print(cu_distance)
            else:
                print(-1)

다익스트라 문제이다. 하지만 기존의 다익스트라와 달리, 최단경로를 찾아서 최적경로의 간선을 제거해줘야한다.

처음에, 최적경로 하나마다 삭제를 했더니, 최적경로의 간선은 다른 최적경로에서 사용을 할 수 있기 때문에 틀렸다고 나왔다.

두번째로는 시간초과의 늪에 많이 빠졌다. 처음에는 최적의 경로를 min_distance가 갱신될때마다 저장을 시켜놨더니 

시간이 초과가 되었다.

그래서 다음과 같은 로직으로 최적의 경로쌍을 찾아다

도착지점의 distance의 값을 distance[end]라 하겠다.

distance[prev_node] + graph[prev_node][end] == distance[end]을 만족하는 prev_node는 prev_node에서 end node로 오는 최단경로임을 알수 있다.

이 (prev_node,end) 쌍을 지울 집합에 추가해주고, prev_node를 stack에 넣어준다.

이 과정을 반복하면, 끝점에서부터 최단경로로 오는 간선들을 전부 찾을 수 있다.

그리고 난뒤 해당 간선들을 지우는 과정을 하면 된다.

그리고 마지막으로 다익스트라를 한번 더 한뒤 결과에 맞게 출력해주면 된다.

다익스트라는 자주 쓰지 않던 알고리즘이라 푸는데 어려웠고, 기본적으로 다익스트라는 최단경로의 길이를 출력해주는 것이기 때문에, 최단경로의 경로를 이용하기 위해서 다익스트라 과정에서 나온 결과물을 이용해야한다는 점을 배웠다.

드디어 150문제를 돌파했다.

골드4~5 문제가 60문제로 거의 반수가 낮은 난이도에 주력되어있어서, 상반기 시즌에 맞춰서 스퍼트를 올려서 골2~3 문제와 플5~골1 문제를 많이 연습 해봐야겠다.