Coding 공부

def solution(A,B):
    result = [[0]*(len(B)+1) for _ in range(len(A)+1)]
    for i in range(1,len(A)+1):
        for j in range(1,len(B)+1):
            if A[i-1] == B[j-1]:
                result[i][j] = result[i-1][j-1] + 1

    return max(map(max,result))

A = input()
B = input()

print(solution(A,B))

LCS 문제이다. 근데 이전에 풀었던 LCS와 다른 문제였다.

기본적인 틀은 똑같다. 대신 이 문제는 연속된 문자열이어야 하기 때문에, A[i-1] != B[i-1]일때는 아무것도 해주지 않는다.

# 3020 개똥벌레

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

bottom_list = [0]*H
top_list = [0]*H


for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[height] += 1

for ind in range(1,H):
    bottom_list[ind] += bottom_list[ind-1]
    top_list[ind] += top_list[ind-1] 

bottom_list.append(bottom_list[-1])
top_list.append(top_list[-1])
min_result = float('inf')
min_cnt = 0
for k in range(H):
    bottom_cnt = bottom_list[-1] - bottom_list[k]
    top_cnt = top_list[-1] - top_list[(H-1)-k]
    if bottom_cnt +top_cnt < min_result:
        min_result = bottom_cnt+top_cnt
        min_cnt = 1
    elif bottom_cnt + top_cnt == min_result:
        min_cnt += 1

print(min_result,min_cnt)

prefix sum 을 이용해서 푼 방식이다.  종유석과 석순을 구분해서 prefix_sum을 해주고, 그 다음에 상황에 맞게 최저값을 구해주면 된다.

# 3020 개똥벌레
import sys


N,H = map(int,sys.stdin.readline().split())

bottom_list = [0]*(H+1)
top_list = [0]*(H+1)

for ind in range(N):
    height = int(input())
    if ind%2:
        top_list[height] += 1
    else:
        bottom_list[H-height+1] += 1
for ind in range(H-1,0,-1):
    top_list[ind] += top_list[ind+1]


for ind in range(2,H+1):
    bottom_list[ind] += bottom_list[ind-1]

min_total = N
min_cnt = 0
for ind in range(1,H+1):
    sub_sum = bottom_list[ind] + top_list[ind]
    if sub_sum < min_total:
        min_total = sub_sum
        min_cnt = 1
    elif sub_sum == min_total:
        min_cnt += 1
print(min_total,min_cnt)

이 코드는 석순의 저장 방식을 다르게 하여, 한번에 계산이 편하게 한 방식이다.  

# 6593 상범 빌딩
from collections import deque


def printresult(flag,sec):
    if flag:
        return f'Escaped in {sec} minute(s).'
    else:
        return 'Trapped!'


while True:
    L,R,C = map(int,input().split())
    if L+R+C == 0:
        break
    building = []
    dx = [-1,1,0,0,0,0]
    dy = [0,0,-1,1,0,0]
    dz  = [0,0,0,0,-1,1]
    startpoint = []
    endpoint = []
    for ind in range(L):
        temp = []
        for x in range(R):
            input_list = list(input())
            for y,val in enumerate(input_list):
                if val == 'S':
                    startpoint = [x,y,ind]
                elif val == 'E':
                    endpoint = (x,y,ind)
            temp.append(input_list)
        building.append(temp)
        input()
    # 층,행,열
    stack = deque()
    stack.append(startpoint)
    building[startpoint[2]][startpoint[0]][startpoint[1]] = '#'
    minutes = 0
    flag = False
    while stack:
        new_stack = []
        minutes += 1
        for x,y,z in stack:
            for i in range(6):
                nx = x + dx[i]
                ny = y + dy[i]
                nz = z + dz[i]
                if 0<=nx<R and 0<=ny<C and 0<=nz<L:
                    if building[nz][nx][ny] != '#':
                        if (nx,ny,nz) == endpoint:
                            flag = True
                            break
                        else:
                            building[nz][nx][ny] = '#'
                            new_stack.append((nx,ny,nz))
        if flag:
            print(printresult(flag,minutes))
            break

        stack = new_stack[:]
    if not flag:
        print(printresult(flag,minutes))

BFS 관련 문제이다. 문제를 제대로 안 읽어서 input값을 제대로 안 받았더니 많이 틀렸던 문제이다.

일반적인 BFS를 3차원으로 바뀐것과 동일하고, range를 많이 쓰면 메모리 초과가 날 수 있으니 조심해서 풀면 되는 문제이다.

def find_lis(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
def find_lds(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if array[i] < array[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
        




N = int(input())

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

lis_dp = find_lis(arr)
result = 0
for ind in range(N):
    lds_dp = find_lds(arr[ind:])
    result = max(result,lis_dp[ind] + max(lds_dp) -1)
print(result)

처음에 푼 방식이다. 먼저 가장 긴 증가 부분 수열의 길이를 구하고 난뒤,

각 index마다 잘라서 가장 긴 감소 부분 수열을 구해서 더해주었다.

이러한 방식으로 푸니깐 시간이 오래걸렸다.

def find_lis(array):
    dp = [0]*len(array)

    for i in range(len(array)):
        dp[i] = 1
        for j in range(i+1):
            if arr[i] > arr[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
def find_lds(array):
    dp = [0]*len(array)

    for i in range(len(array)-1,-1,-1):
        dp[i] = 1
        for j in range(i+1,len(array)):
            if array[i] > array[j]:
                dp[i] = max(dp[i],dp[j] + 1)
    return dp
        




N = int(input())

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

lis_dp = find_lis(arr)
lds_dp = find_lds(arr)

result = 0
for ind in range(N):
    result = max(result,lis_dp[ind]+lds_dp[ind]-1)
print(result)

그 다음으로 푼 방식이다.

LIS를 두군데로 해서 구해주었다.

앞에서 가장 긴 뒤에서 가장 긴 증가 부분수열을 구해주었다.

긴 바이토닉 부분 수열을 보면 가운데를 중심으로 좌측에서는 긴 증가부분 수열이고, 우측은 감소부분수열인데, 이걸 역으로 보면 우측을 거꾸로 돌리면 증가 부분 수열이 된다.

이러한 점을 이용해 좌측에서부터의 긴 증가부분 수열과 수열을 거꾸로 해서 긴 증가부분 수열의 길이를 구해, 서로 더해주면 긴 바이토닉 부분 수열이 나온다.

# 2631 줄 세우기
# LIS의 길이를 구하기 위한 방법 복잡도 O(Nlogn)로 구하기 
N = int(input())
arr = list(int(input()) for _ in range(N))
LIS = []
LIS.append(arr[0])
temp = 0
for number in arr[1:]:
    for ind,val in enumerate(LIS):
        if number > val and number not in LIS:
            temp = number
        elif number < val and number not in LIS:
            LIS[ind] = number
            temp = 0
    if temp:
        LIS.append(temp)
    temp = 0
print(N-len(LIS))
    

 이 문제는 최장 증가 부분 순열을 활용한 문제이다.  크기대로 줄을 세우는 것이기 때문에, 주어진 배열에서, 가장 긴 증가 부분 순열을 제외하고 나머지 부분을 움직이면 정답을 구할 수 있따.

import sys
def find_index(origin):
    global N,M
    min_value = 10001
    min_index = []
    for x in range(N):
        for y in range(M):
            if (x+y)%2:
                if min_value > origin[x][y]:
                    min_value = origin[x][y]
                    min_index = [x,y]
    return min_index

N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
if not N%2 and not M%2:
    low_index = find_index(arr)
    result = ''
    front_result = ''
    tail_result = ''
    front_times = low_index[0]//2
    tail_times = (N-1 -low_index[0])//2
    for ind in range(1,M*front_times*2+1):
        a = ind//M
        b = ind%M
        if not b:
            front_result += 'D'
        else:
            if a%2:
                front_result += 'L'
            else:
                front_result += 'R'
    for ind in range(1,M*tail_times*2):
        a = ind//M
        b = ind%M
        if not b:
            tail_result += 'D'
        else:
            if a%2:
                tail_result += 'R'
            else:
                tail_result += 'L'
    if tail_times:
        tail_result = 'D'+tail_result
    front_index = [front_times*2,0]
    move = ['D','R','U','R']
    front_direction = [(1,0),(0,1),(-1,0),(0,1)]
    tail_direction = [(-1,0),(0,-1),(1,0),(0,-1)]
    tail_index = [front_index[0]+1,M-1]
    front_cnt = 0
    tail_cnt = 0
    while True:
        nx = front_index[0] + front_direction[front_cnt][0]
        ny = front_index[1] + front_direction[front_cnt][1]
        if nx == low_index[0] and ny == low_index[1]:
            break
        else:
            front_result += move[front_cnt]
        front_cnt = (front_cnt+1)%4
        front_index = [nx,ny]
    if tail_index[0] != front_index[0] or tail_index[1] != front_index[1]:
        while True:
            nx = tail_index[0] + tail_direction[tail_cnt][0]
            ny = tail_index[1] + tail_direction[tail_cnt][1]
            if nx == front_index[0] and ny == front_index[1]:
                tail_result = move[tail_cnt] + tail_result
                break
            else:
                tail_result = move[tail_cnt] + tail_result
            tail_cnt = (tail_cnt+1)%4
            tail_index = [nx,ny]

    result = front_result + tail_result

else:
    if N%2:
        result = ''
        for ind in range(1,N*M):
            a = ind//M
            b = ind%M
            if not b:
                result += 'D'
            else:
                if a%2:
                    result += 'L'
                else:
                    result += 'R'
    else:
        result = ''
        for ind in range(1,N*M):
            a = ind//N
            b = ind%N
            if not b:
                result += 'R'
            else:
                if a%2:
                    result += 'U'
                else:
                    result += 'D'   
print(result)

 처음 풀었던 방식이다. 이 문제는 먼저 크게 3가지 경우로 나뉠 수 있다.

1 ) 행과 열이 전부 짝수 일때

2 ) 행과 열 중 하나라도 홀수 일때

   2.1) 행이 짝수 일때

먼저 구현하기 쉬운 2번 케이스 부터 하면, 행과 열중 하나라도 홀수이면, 모든 칸을 지나갈수 있다.

그래서 모든 칸을 지나가도록 설정을 해주면 된다.

나는 먼저 기본적으로 

----------->

              ↓

<-----------

이런 식으로 스네이크 방식대로 간다고 해줬다, 몇번 인덱스에서 화전하는지만 주의해서 그때의 방향에 맞게 회전을 해주면 된다.

하지만 이 방법은 행이 짝수이고 열이 홀수 일때는 하지 못한다.

행이 짝수이고 열이 홀수 일때는, 

↓  ↑

↓  ↑

↓  ↑

↓→↑

상하로 지그재그인 방식대로 해주었다.

그리고 어려운 행과 열이 둘다 짝수 일때이다.

행과 열이 전부 짝수이면, 모든 칸은 들릴수 없고, 단 1칸만 들리지 못한다.

그 칸은 주어진 행렬을 체스판 위에 있다고 하면 처음 시작 위치인 (0,0)을 흰색칸이라고 한다면, 검정색 칸 1칸을 들리지 못한다.

그렇기 때문에 검은색 칸 중에서 가장 값이 작은 것을 찾아 그 칸을 들릴지 않고 나머지칸을 전부 도는 것이 베스트이다.

들릴지 않을 칸을 구했으면, 다음과 같이 구한다. 지그재그 방식으로 갈때 보면, 행이 2칸을 기준으로 원위치로 열의 위치가 동일하게 올 수 있고, 계속 반복되는 것을 알 수 있다.

그렇기 때문에 주어진 행렬을 처음부터 2칸씩 나눈다고 생각을 하고, 들리지 않는 칸이 있는 2칸짜리 행을 제외한 나머지는 위에서 했던 좌우 지그재그 방식으로 반복문을 해준다.

그리고 마지막 남은 2칸은 앞뒤로 check를 해주면서 하면 된다.

 그려보면 알지만 D->R->U->R 순으로 반복해서 움직여준다. 

단 들리지않는 칸을 만났을시에는 그 칸을 피해서 R로 움직여주면 된다.

나는 위에서 내려올때, 끝에서 역으로 올라오는 것을 따로 구해서 합쳐주는 방식으로 했다.

주의 할점은 출력에 표시되는 방향은 똑같지만 꼬리부분에서 올라가는 것은 거슬러 가는것이기 때문에 실질적인 방향이 반대인것만 주의 하면 된다.

import sys
def find_index(origin):
    global N,M
    min_value = 10001
    min_index = []
    for x in range(N):
        for y in range(M):
            if (x+y)%2:
                if min_value > origin[x][y]:
                    min_value = origin[x][y]
                    min_index = [x,y]
    return min_index
N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
if not N%2 and not M%2:
    low_index = find_index(arr)
    result = ''
    front_times = low_index[0]//2
    tail_times = (N-1 -low_index[0])//2
    front_result = ('R'*(M-1)+'D'+'L'*(M-1)+'D')*front_times
    tail_result = ('D'+'L'*(M-1)+'D'+'R'*(M-1))*tail_times

    front_index = [front_times*2,0]
    move = ['D','R','U','R']
    front_direction = [(1,0),(0,1),(-1,0),(0,1)]
    tail_direction = [(-1,0),(0,-1),(1,0),(0,-1)]
    tail_index = [front_index[0]+1,M-1]
    front_cnt = 0
    tail_cnt = 0
    while True:
        nx = front_index[0] + front_direction[front_cnt][0]
        ny = front_index[1] + front_direction[front_cnt][1]
        if nx == low_index[0] and ny == low_index[1]:
            break
        else:
            front_result += move[front_cnt]
        front_cnt = (front_cnt+1)%4
        front_index = [nx,ny]
    if tail_index[0] != front_index[0] or tail_index[1] != front_index[1]:
        while True:
            nx = tail_index[0] + tail_direction[tail_cnt][0]
            ny = tail_index[1] + tail_direction[tail_cnt][1]
            if nx == front_index[0] and ny == front_index[1]:
                tail_result = move[tail_cnt] + tail_result
                break
            else:
                tail_result = move[tail_cnt] + tail_result
            tail_cnt = (tail_cnt+1)%4
            tail_index = [nx,ny]

    result = front_result + tail_result

else:
    if N%2:
        result = ('R'*(M-1)+'D'+'L'*(M-1)+'D')*(N//2)+('R'*(M-1))
    else:
        result = ('D'*(N-1)+'R'+'U'*(N-1)+'R')*(M//2) +('D'*(N-1))
print(result)

이 문제를 풀다보면 알지만, 굳이 모든 칸을 하나하나 탐색하면서, 반복문을 돌릴필요가 없다. 위에서 말했다 시피 2칸 단위로  지그재그로 이루어져있기때문에 2칸을 기준으로 좌우지그재그를 출력해주면된다.

위 코드가 그러한 방식을 이용한 것이다.

행과 열 중 홀수 일때는 모든 칸을 들릴수있고, 그 방법이 패턴화되어있기 때문에, 곱하기를 해주면 된다.

그리고 행과 열 둘다 짝수 일때에도, 2칸단위는 전부 그냥 곱하기를 해주고, 마지막 부분만 탐색을 해주면된다.

# # 1600 말이 되고픈 원숭이
from collections import deque
K = int(input())
W,H = map(int,input().split())

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

stack = deque()
stack.append((0,0,0,K))

visited = [[[0 for z in range(K+1)] for y in range(W)] for _ in range(H)]
visited[0][0][0] = 1
horse_move = [(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1),(1,2),(-1,2),(-2,1)]
move = [(-1,0),(1,0),(0,-1),(0,1)]
result = -1
while stack:
    x,y,cnt,horse_cnt = stack.popleft()
    if x+1 == H and y+1 == W:
        result = cnt
        break
    for dx,dy in move:
        nx = x + dx
        ny = y + dy
        if 0<=nx<H and 0<=ny<W:
            if not arr[nx][ny]:
                if not visited[nx][ny][horse_cnt]:
                    stack.append((nx,ny,cnt+1,horse_cnt))
                    visited[nx][ny][horse_cnt] = 1
    if horse_cnt:
        for dx,dy in horse_move:
            nx = x + dx
            ny = y + dy
            if 0<=nx<H and 0<=ny<W:
                if not arr[nx][ny]:
                    if not visited[nx][ny][horse_cnt-1]:
                        stack.append((nx,ny,cnt+1,horse_cnt-1))
                        visited[nx][ny][horse_cnt-1] = 1



print(result)

이 문제는 두가지의 이동방식이 있고, 그것을 구분해서 BFS를 해주면 된다. 하지만 여기서 주의할 점은 다음과 같다.

방문 표시를 체크를 하는데 주의를 해야한다.

1

4 4

0 0 0 0

0 0 0 0

0 0 1 1

0 0 1 0

위와 같이 되어 있다고 했을시, 방문표시를 따로 구분하지 않고 한가지로 했을시에는, 말로 왔는지, 원숭이로 왔는지 정확히 모르기 때문에 원하는 답이 안나올 수 있다.

그래서 visitied를 기존의 x,y 좌표 뿐만아니라 말의 이동회수를 기준까지 포함해서, 방문표시를 해주었다. 이부분만 조심해주면, 문제를 풀 수 있다.

def ccw(start,second,third):
    vector1 = [second[0]-start[0],second[1]-start[1]]
    vector2 = [third[0]-start[0],third[1]-start[1]]
    outer = vector1[0]*vector2[1] - vector2[0]*vector1[1]
    if outer < 0:
        print(-1)
    elif not outer:
        print(0)
    else:
        print(1)


P1 = list(map(int,input().split()))
P2 = list(map(int,input().split()))
P3 = list(map(int,input().split()))


ccw(P1,P2,P3)

# https://gaussian37.github.io/math-algorithm-ccw/

기하학과 관련된 문제이다.

CCW에 대한 자세한 설명은

https://gaussian37.github.io/math-algorithm-ccw

위 사이트를 참조하길 바란다.

쉽게 말하면 첫번째 좌표를 (0,0)으로 이동시킨다고 했을 때, 

첫번째 좌표에서 두번째 좌표로 가는 벡터 V1과

첫번째 좌표에서 세번쩨 좌표로 가는 벡터 V2를 구해 외적을 구하게 되면, 

이 선이 반시계 방향인지, 시계방향인지 직선인지 구할 수 있는 것이다.

 위의 사이트에  CCW의 그림과 같이 자세하게 설명되어 있으므로, 위 사이트를 참조하길 바랍니다.