Coding 공부

# 1309 동물원
# 9901로 나눈 수 출력

N = int(input())
mod = 9901
dp = [0]*(N+1)
if N == 1:
    print(3)
else:
    dp = [1,3]
    for i in range(2,N+1):
        current = 2*dp[-1]+dp[-2]
        dp[-2] = dp[-1]
        dp[-1] = current
    print(current%mod)

직접 그려봐서 점화식을 찾았다.

생각해보면 N-1일때, N-1의 위치에 왼쪽에 사자가 있을때, 오른쪽에 사자가 있을때와 둘다 없을때가 있을 것이다.

파란색 음영이 있는 곳이 사자가 있다고 한다고 가정하면, N-1 번 위치에 사자가 있을때에는 2가지의 경우의 수가 있다. 그리고 N-1에 사자가 없을때에는 총 3가지가 있다. 그 중에서 둘다 사자가 없는 경우는 N-2의 크기에서 사자를 놔두는 경우의 수가 같은 것이다.

점화식을 구하면,

F(N) = F(N-1)*2 +F(N-1) 로 나타낼 수 있다.

이렇게 구하고, 전체를 구해서 9901로 나눠도 되지만, 그냥 하면, 숫자가 워낙 커지므로 9901로 나눈 나머지로 계산하는 것이 더 빨리 결과가 나온다.

N = int(input())

prev = 1
result = 3
mod = 9901
for _ in range(N-1):
    temp = result
    result = (result*2 + prev)%mod
    prev = temp
print(result)

# 9251 LCS
def LCS(SA,SB,SALEN,SBLEN):
    global LCS_list

    for i in range(1,SALEN+1):
        for j in range(1,SBLEN+1):
            if SA[i-1] == SB[j-1]:
                LCS_list[i][j] = LCS_list[i-1][j-1]+1
            else:
                LCS_list[i][j] = max(LCS_list[i-1][j],LCS_list[i][j-1])




A = list(input())
B = list(input())

lenA = len(A)
lenB = len(B)

LCS_list = [[0]*(lenB+1) for _ in range(lenA+1)]

LCS(A,B,lenA,lenB)

print(LCS_list[lenA][lenB])

이전에 풀었던 LCS의 이전버전이다.

푸는 방식은 동일하고 여기서는 길이만 구해주는거라 길이만 구해줬다.

# 2133 타일 채우기

#  3*N 크기의 벽을 2*1 1*2로 채우는 경우의 수를 구해보자
# N = 1 => 0
# N = 2 => 3
# N = 3 => 0
N= int(input())
dp = [0]*31
dp[2] = 3
if N%2:
    print(0)
else:
    # 점화식
    # Dp(N) = DP(N-2)*3 + (2*Dp(N-4)+2*DP(N-6)+2*DP(2))
    for number in range(4,N+2,2):
        temp = 2
        for k in range(number-4,0,-2):
            temp += dp[k]*2
        temp += dp[number-2]*3
        dp[number] = temp
    print(dp[N])

 이런 류의 문제는 점화식을 찾아내지 못하면 힘든 문제인 것 같다.

직접 그려보고 패턴을 파악해서 점화식을 구해냈다.

1. N이 홀수이면 무조건 0 이다. (다 채울 수 있는 방도가 없기 때문이다.)

2. N이 짝수 일때만 구하면 되는데, 최초 값은 N=2일때 3이다.

3. N이 짝수일때 그려보면 해당 N에서만 발견되는 특정 조합이 2가지가 있다.

   - N= 6일때 다음과 같이 가운데가 가로로 누워있고, 양 끝이 세로로 세워진 케이스가 2개가 있다.

4. F(N)을 N일때 가지수라 한다면, F(N-2)*F(2) 만큼의 가지수가 생성이 된다. 이것은 왼쪽에 전체 크기의 N-2크기를 두고, 오른쪽에 크기가 (3*2) 타일을 뒀을때 생길 수 있는 가지수 이다.

5. 여기서 많이 해맸다. 우리는 기본적으로 왼쪽에 N-2 타일을 두고, 오른쪽에 2인 타일을 뒀다. 오른쪽에 타일을 뒀을때도 염두를 해야한다. 이 때 나올 수 있는것은 각 N마다 특수한 경우로 되는 2가지 일때의 모습에 오른쪽에 나머지 크기의 타일을 뒀을때이다. 

  - N이 8일때, 설명하면 다음 그림과 같다. 그림이 많이 조잡하다. 

  - 우측이 각 N에서 나오는 특수한 경우이고, 빨간색 네모만큼 놓는수 만큼 나올 수 있다.

  - 그러니 첫번째 그림은 F(2)*2 이고, 두번째 그림은 F(4) *2 이다.

위의 특징을 최종적으로 정리하면,

수식을 입력해본게 하도 옛날이라 개판이지만, 대략적으로 N=2일때 제외하고는 다음과 같이 진행해주면 된다.

문제 자체는 점화식인 것을  알았지만, 이에 맞는 점화식을 구하는데 너무 힘들었다. 이와 비슷한 문제를 풀어서 연습을 더 해야할 것 같다.

# 입력 지폐의 금액 T 동전의 가지수 k 각 동전 하나의 금액 pi ni가 주어진다.
# 방법의 수는 2^31 -1 을 초과하지 않는다.



T = int(input())

k = int(input())

money = [list(map(int,input().split())) for _ in range(k)]

money.sort(reverse=True)
dp = (T+1)*[0]

dp[0] = 1
for coin_val,coin_cnt in money:
    for current_money in range(T,1,-1):
        for current_cnt in range(1,coin_cnt+1):
            if current_money - current_cnt*coin_val >= 0:
                dp[current_money] += dp[current_money-current_cnt*coin_val]
print(dp[T])

DP 관련 문제였다. 풀고보니 평범한 배낭과 비슷한 로직이었다. 거기서는 가치를 판단하여, 가치값의 최대를 찾는거였다면, 여기는 방법의 가지수를 찾는 것이라 다르지만, 하나의 dp를 이용해 역으로 진행하면서, 누적시켜주는 것에 있어서 비슷하다고 봤다.

기본적이 원리는 다음과 같다.

동전의 가지수 k개가 주어지면,

첫번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어 본다.

그리고 두번째 동전으로 만들 수 있는 모든 동전의 종류를 만들어서 누적시켜준다.

이렇게 k번을 반복을 해준다.

여기서 주의해야할 점은 아래에서 위로 올라가면, 이전에 만들어진 것 때문에, 원치 않는 결과가 나올 수 있으므로,

주어진 목표 금액인 T에서 -1씩 줄여주면서 다이나믹 프로그래밍을 해준다.

여기서 평범한 배낭과 또 다른 점은, 같은 동전이 여러개 존재하는 것이다.

그래서 동전의 개수 n개만큼 반복을 시켜주면서 진행해야한다.

즉 3원짜리 동전이 5개가 있다하면,

1회차   // 2회차

T - 3*1 ,| (T-1) - 3*1, ....

T - 3*2, |(T-1) - 3*2 ,...

T - 3*3, |(T-1) - 3*3, ...

T- 3*4,  |(T-1) - 3*4 .....

T - 3*5, |(T-1) - 3*5 ....

이렇듯 동전의 개수만큼 진행시켜줘야, 그 동전으로 만들 수 있는 모든 경우를 탐색할 수 있다.

여기서 또 주의해야할 점은 T는 동전의 개수를 조정하는 반복문 밖에 있어야한다.

원래 DP에 약하기도 했지만 비슷한 문제를 풀어본 경험이 있었는데도, 푸는데 시간이 오래걸렸다.

이전에 풀었던 문제들도 다시 공부하여, DP에서 필요한 점화식을 빨리 구하는데 노력해야겠다.

# 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를 구해야 하는 경우에는 다른 풀이를 찾아야한다.

n=int(input())
card=[0]
card+=list(map(int,input().split()))
dp=[0]*(n+1)

dp[1]=card[1]
dp[2]=max((card[2],card[1]*2))

for i in range(3,n+1):
    dp[i]=card[i]
    for j in range(1,i//2+1):
        dp[i]=max(dp[i],dp[j]+dp[i-j])


print(dp[n])

초창기에 풀었던 문제이다. 

현재 DP에서의 초기값을 넣어주고, 두개를 더해서 i가 되는 경우를 갱신해주면 된다.

J의 range(i//2+1)인 이유는 중간까지 하면, 그 다음부터는 앞의것의 반복이기 때문이다.

# 5569 출근경로
#  남북방향 도로 w개 동서 방향 도로가 h개
# 남북방향은 서쪽부터 1,2,....w
# 동서도 남쪽부터 1....h
# 교차로 (i,j) 
# 1번 이후부터 가능

w,h = map(int,input().split())
dp = [[[[0]*2 for _ in range(2)] for _ in range(h)] for _ in range(w)]

# 3번째 인덱스 0 북쪽, 1은 동쪽
# 4번째 인덱스는 방향전환 여부 1이 가능 0이 불가능
# 자세한 설명을 하자면, 3번째 인덱스는 그 전 위치에서 올라온 방향을 나타내는 것이다.
# 3번째 인덱스가 0 이면 x-1,y의 위치에서 북쪽으로 올라왔을때를 말한다.
# 4번째 index는 현재 x,y 좌표에 있는 값이 회전이 가능한지에 대해 적어놓은것이다.
# 1이면 회전이 가능한 것이고, 0이면 회전이 불가능한 것이다.

# 처음에, x=0일때와 y=0일때 초기화 작업을 해준다.
for i in range(1,w):
    dp[i][0][0][1] = 1
for i in range(1,h):
    dp[0][i][1][1] = 1


for x in range(1,w):
    for y in range(1,h):
        # (x,y) 좌표에서 3번째 index가 0 인 경우는 (x-1,y)에서 온 경우이다.
        # 여기서 회전이 가능할때와 불가능할때를 구분해서 해야한다.
        # 회전이 불가능한 경우는 (x-1,y) 위치에서 3번째 index가 1이고, 네번째 index가 1인경우이다.
        # 동쪽에서 오고, 회전이 가능할때이다. 북쪽으로 방향이동을 할수 있고, 그 다음에는 방향을 전환할수 없기 떄문이다.
        # 회전이 가능한 경우는 (x-1,y) 기준으로 3번째 index가 0인 경우 전부이다.
        # 왜냐하면 (x-1,y)에서 3번째 index가 0인경우는 (x-2,y)에서 온 경우이므로, 어떠한 경우에서도 회전이 가능하기 때문이다.
        dp[x][y][0][0] = dp[x-1][y][1][1]
        dp[x][y][0][1] = dp[x-1][y][0][0] + dp[x-1][y][0][1]
        # (x,y) 좌표에서 3번째 index가 1인 경우는 (x,y-1)에서 온 경우이다.
        # 여기서 회전이 가능할때와 불가능할때를 구분해야한다.
        # 회전이 불가능한 경우는 (x,y-1) 위치에서 3번째 index가 0이고, 네번째 index가 1인 경우이다.
        # (x,y-1)으로 올때 (x-1,y-1)에서 올라와서 방향전환을 (x,y-1)에서 해서 방향전환을 할 수 없기때문이다.
        # 회전이 가능한 경우는 (x,y-1) 위치에서 3번째 index가 1인 모든 경우이다.
        dp[x][y][1][0] = dp[x][y-1][0][1]
        dp[x][y][1][1] = dp[x][y-1][1][0] + dp[x][y-1][1][1]
result = sum(dp[w-1][h-1][0]) + sum(dp[w-1][h-1][1])
print(result%100000)

다이나믹 프로그래밍를 이용해 푼 문제 중에서 내게 어려웠던 문제였다.

DP를 잘 모르는 상태에서 DP를 어떻게 설계를 해서, 저장시켜놓을지가 고민이었다.

그리고 여기서 좀 헷갈렸던 것이, DP에 이전 위치에서 올라온 방향을 저장해주는 3번째 index와, 회전이 가능한지 구분해주는 4번쨰 index가 헷갈렸다.

회전이 가능한 것은 현재 (x,y) 좌표에서 회전 가능여부를 보는 것이고, 3번째 index는 그 전 위치에서 북쪽에서 왔는지 동쪽에서 왔는지 구분해줘야했다.

서로 다른 기준점으로 인해, DP를 설계하는데 어려움을 겪었다.

위의 코드의 주석에서도 설명했지만, 총 4가지 경우를 나누어서, 정리해야한다.

1. 이전 위치에서 북쪽으로 이동해서 도착했고,, 다음번에 회전이 가능한 경우

2. 이전 위치에서 북쪽으로 이동해서 도착했고, 다음번에 회전이 불가능한 경우

3. 이전 위치에서 동쪽으로 이동해서 도착했고, 다음번에 회전이 가능한 경우

4. 이전 위치에서 동쪽으로 이동해서 도착했고,다음번에 회전이 불가능한 경우

1번 경우를 설명하자면, (x,y) 위치에 올때, 북쪽으로 이동해서 도착하고, 회전이 가능할려면, (x-1,y)에서 와야하며, 거기서도 북쪽으로 도착해야지만, 쭉 직진으로 온거기 때문에 회전이 가능하다.

이러한 경우는 [x-1][y][0][0]와 [x-1][y][0][1] 이다. 인덱스를 분석하면

[x-1][y][0][0]은 x-2,y의 위치에서 x-1,y로 북쪽으로 해서 왔고, x-2,y의 위치에서 이미 방향을 전환했기때문에, x-1,y에서 방향전환을 못하는 빨강색 화살표를 의미한다.

[x-1][y][0][1] 은 x-2,y의 위치에서 x-1,y로 북쪽으로 해서 왔고, x-2,y에서 방향전환을 안하고 왔기 때문에, x-1,y의 위치에서 방향전환이 가능한 파랑색 화살표를 의미한다.

그러므로 [x][y][0][1] = [x-1][y][0][0] + [x-1][y][0][1] 이다.

2번 경우는 (x-1,y)에서 방향전환을 해서 (x,y)를 왔기 때문에 다음번에 회전을 못하는 경우이다.

이런 경우는 (x-1,y)에서 동쪽에서 왔고, (x-1,y)에서 회전이 가능한

[x-1][y][1][1] 일때, [x][y][0][0]이 될수 있다.

3,4번 경우는 위를 회전한 것이다.

그림이 조잡해서 약간 이해하기 힘들지만, 위와 같이 총 4가지 경우를 나누어서 dp를 하면 된다.