Coding 공부

# 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을  출력하도록 했따.  

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)인 이유는 중간까지 하면, 그 다음부터는 앞의것의 반복이기 때문이다.

#  17086 아기 상어
import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]

def bfs(x,y):
    deque = collections.deque()
    deque.append((x,y,0))
    visited = [[True]*M for _ in range(N)]
    visited[x][y] = True
    while deque:
        x,y,cnt = deque.popleft()
        if arr[x][y]:
            return cnt
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<= nx <N and 0<=ny <M:
                if visited[nx][ny]:
                    deque.append((nx,ny,cnt+1))
                    visited[nx][ny] = False


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


arr = [list(map(int,input().split())) for _ in range(N)]
result = 0
for x in range(N):
    for y in range(M):
        if not arr[x][y]:
            temp = bfs(x,y)
            result = max(temp,result)

print(result)

처음에는 각 점에서 BFS를 해서 상어와의 위치값이 가장 먼 값을 구하는 방법을 했다.

import collections
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
N,M = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
shark = collections.deque()
for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            shark.append((i,j,arr[i][j]))

while shark:
    x,y,dis = shark.popleft()
    for i in range(8):
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<= nx <N and 0<=ny<M:
            if not arr[nx][ny]:
                arr[nx][ny] = 1
                shark.append((nx,ny,dis+1))


print(dis-1)

 두번째 풀이는 그 반대로, 상어를 기준으로 bfs를 진행했다. 어차피 bfs는 거리순으로 진행되기 때문에, 가장 마지막에 나오는 dis가 최대 거리이므로, 마지막 dis에서 1을 빼줬다.

M,N = map(int,input().split())
S = int(input())
# 북쪽 1 ==>0
# 남쪽 2 ==>N-1
# 서쪽 3 =>0
# 동쪽 4 => N-1
input_list = []
total_length = (N+M)*2
for tc in range(S+1):
    n1,n2 = map(int,input().split())
    if n1 == 1:
        input_list.append(n2)
    elif n1 == 2:
        input_list.append(M+N+(M-n2))
    elif n1 == 3:
        input_list.append(2*M+N+(N-n2))
    else:
        input_list.append(M+n2)

patrol = input_list[-1]
result = 0


for idx in range(S):
    temp = abs(input_list[idx]-patrol)
    result += min(temp,total_length-temp)
print(result) 

이 문제를 처음 풀때는 여러가지 경우로 나눌까 하다가, 생각해보니 이 문제는 직사각형의 테두리만 도는 것이고, 테두리의 둘레 값은 고정적이다. 그래서 한쪽만 구하면 반대편 값은 저절로 구해지는 것을 알수 있었다.

그래서 사각형을 하나의 직선 좌표로 바꾸었다.

순서는 북->동->남->서 순으로 (0,0) 좌표를 끊었다고 생각했을때 쭉 눌어지는 것처럼 했다.

위와 같은 직사각형을 밑과 같은 일직선으로 변경 후 두 점사이의 거리를 구했다.

전체 둘레에서 두 점사이의 거리를 뺀값과 두점 사이의 거리 중 더 짧은 것을 결과값에 더해주었다.

# 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를 하면 된다.

def dfs(bomblist):
    global N,result
    while bomblist:
        x,y = bomblist.pop()
        for i in range(8):
            nx = x + dx[i]
            ny = y + dy[i]
            if (nx == 0 or nx == N-1) or (ny == 0 or ny ==N-1):
                if arr[nx][ny] == 0:
                    break
        else:
            for i in range(8):
                nx = x + dx[i]
                ny = y + dy[i]
                if (nx == 0 or nx == N-1) or (ny == 0 or ny ==N-1):
                    arr[nx][ny] -= 1
            result += 1
    return

            



N = int(input())
dx = [-1,0,1,-1,1,-1,0,1]
dy = [-1,-1,-1,0,0,1,1,1]
arr = [list(input()) for _ in range(N)]
result = 0
if N >4:
    result += (N-4)**2
bomb = []
for x in range(N):
    for y in range(N):
        if x == 1 or x == N-2:
            if arr[x][y] == '#':
                bomb.append((x,y))
            else:
                arr[x][y] = int(arr[x][y])
        elif 1<x<N-2:
            if y == 1 or y == N-2:
                bomb.append((x,y))
            else:
                if arr[x][y] != '#':
                    arr[x][y] = int(arr[x][y])
        else:
            if arr[x][y] != '#':
                arr[x][y] = int(arr[x][y])
dfs(bomb)
print(result)

 지뢰찾기를 하는 문제이다. 테두리에만 숫자가 있고, 그 안은 파악되지않는 지뢰구역이 있다.

이 지뢰구역에서 최대로 설치가능한 지뢰의 개수를 구하는 문제이다.

먼저, 테두리에 직접적으로 닿아있는 칸들을 제외한 나머지 칸들은 전부 지뢰가 있다고 가정을 해야, 최대 지뢰를 구할 수 있다.

그리고 두번째로 테두리에 근접해있는 칸들을 기준으로 8칸을 탐색을 해서, 그 안에 0이 있다면, 해당 구역은 지뢰가 존재할수 없는 공간이니 넘어간다.

하지만, 0이 존재하지 않는 경우 지뢰가 존재하는 경우이니, 지뢰의 수를 1개 늘려주고, 해당 구역의 주변 8칸의 숫자를 1씩 줄여준다.

이걸 반복해준다.

여기서 쓴 코드적인 부분은 for else 문이다.

for문을 반복하면서, break를 한번도 마주치지 않으면 자동적으로 else문이 실행되는 것이다.

이걸 통해 따로 flag같은 True False 값 같은 분기점이 없이 진행이 가능했다.