Coding 공부

a= int(input())
def cal(a):
    temp = []
    for i in a:
        temp.append(i-1)
        if i%3==0:
            temp.append(i/3)
        if i%2==0:
            temp.append(i/2)
    return temp
cnt=0
minimum=[a]
while True:
    if a==1:
        print(cnt)
        break
    temp=minimum[:]
    minimum=[]
    minimum=cal(temp)
    cnt+=1
    if min(minimum)==1:
        print(cnt)
        break

유명한 DP 문제이다.

각각의 연산을 한뒤에 새롭게 옮겨가는 LIST를 따로 만들어주고, 그걸 갱신하면서 횟수가 어느회차인지 알면된다.

N = int(input())
number_list = [N]
cnt = 0
flag = False
if N == 1:
    print(0)
else:
    while True:
        new_number = []
        for numbers in number_list:
            if numbers == 1:
                flag = True
                break

            if not numbers%3:
                new_number.append(numbers/3)
            if not numbers%2:
                new_number.append(numbers/2)
            new_number.append(numbers-1)
        if flag:
            print(cnt)
            break
        cnt += 1
        number_list = new_number[:]

똑같은데 이런식으로도 만들수 있다.

print(''.join(sorted(input())[::-1]))

정렬을 해준뒤 역으로 출력해준다.

T=int(input())
cnt=0
for test_case in range(T):
    sp=list(input())
    total=[]
    for i,v in enumerate(sp):
        if i!=len(sp)-1:
            if sp[i]!=sp[i+1]:
                total.append(sp[i])
        else:
            total.append(sp[i])
    for k in total:
        if total.count(k)>1:
            break
    else:
        cnt=cnt+1
print(cnt)

풀이 방식은 다음과 같다.

 마지막 위치를 제외한 현재위치와 다음위치를 비교를 해서 같지 않을때에 그때 현재위치의 문자열을 total에 넣어준다.

마지막 위치는 total에 넣어준다.

그리고 난뒤에 total을 반복문을 돌리면서 그 개수가 1개를 초과하면, 그룹 단어가 아니므로 멈춰주고, 한번도 만나지 않으면, 그룹 단어이므로 cnt를 늘려준다.

from collections import deque


def dfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    stack = [V - 1]
    
    while stack:
        x = stack.pop()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N - 1, -1, -1):
            if graph[x][k] >= 1:
                graph[x][k] = 0
                graph[k][x] = 0
                stack.append(k)
    
    return result


def bfs():
    graph = [[0] * N for _ in range(N)]
    for i in range(M):
        x, y = arr[i]
        graph[x - 1][y - 1] += 1
        graph[y - 1][x - 1] += 1

    result = [V]
    q = deque()
    q.append(V - 1)

    while q:
        x = q.popleft()
        if x + 1 not in result:
            result.append(x + 1)
        for k in range(N):
            if graph[x][k] >= 1:
                graph[x][k] -= 1
                graph[k][x] -= 1
                
                q.append(k)
    
    return result



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

dfs_res = dfs()
for i in range(len(dfs_res)):
    print(dfs_res[i], end=" ")
print()
bfs_res = bfs()
for i in range(len(bfs_res)):
    print(bfs_res[i], end=" ")
print()

DFS와 BFS 문제이다.

웹개발 중 코테 대비하면서 연습용으로 오랜만에 풀었던 문제라, 코드가 별로이다.

def solution(start,flag):
    global N
    stack = [start]
    visited = [True]*(N+1)
    ind = 0
    if flag:
        ind = -1
    result = []
    while stack:
        node_number = stack.pop(ind)
        if not visited[node_number]:
            continue
        visited[node_number] = False
        result.append(node_number)
        for next_node in sorted(graph[node_number],reverse=flag):
            if visited[next_node]:
                stack.append(next_node)
    return result




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


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

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



print(*solution(V,True))
print(*solution(V,False))

 기본적인 풀이는 같다. DFS이냐, BFS이냐에 따라 트리거를 주었고, DFS일때는 pop하는 index를 -1로 아니면 0으로 주었다.

그리고 dfs는 뒤에서부터 pop이 되므로, graph를 내림차순으로 정렬해주고, bfs는 오름차순으로 정렬해주는것만 다르다.

N,K=map(int,input().split(' '))
result=[]
temp=K-1
first=list(range(1,N+1))
for i in range(N):
    if temp < len(first):
        result.append(first.pop(temp))
        temp+=K-1
    else:
        temp=temp%len(first)
        result.append(first.pop(temp))
        temp+=K-1
print('<',end='')
for k in result:
    if k==result[-1]:
        print(k,end='')
    else:
        print(k,end=', ')
print('>')

요세푸스 문제이다.

과거에 푼 문제라 정확한 풀이가 기억은 안나지만, 풀이 자체는 단순하게, K를 계속 옮겨가면서 풀었던 기억이 난다.

from collections import deque

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

stack = deque(range(1,N+1))
result = []
while stack:
    stack.rotate(-(K-1))
    result.append(str(stack.popleft()))
print(f'<{", ".join(result)}>')
    

지금 푼다면 이렇게 풀 것이다.

단순하게 큐를 만들고 rotate로 회전을 시킨 뒤, 가장 좌측에 있는걸 뺄것이다.

### 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를 구한뒤 최대값을 출력해주면 된다.