Coding 공부

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의 그림과 같이 자세하게 설명되어 있으므로, 위 사이트를 참조하길 바랍니다.

N = int(input())

arr = list(map(int,input().split()))
dp = [[0]*21 for _ in range(N)]

dp[0][arr[0]] = 1
for ind in range(1,N-1):
    for prev_num in range(21):
        if dp[ind-1][prev_num]:
            for new_num in [prev_num+arr[ind],prev_num-arr[ind]]:
                if 0<=new_num<=20:
                    dp[ind][new_num] += dp[ind-1][prev_num]

print(dp[N-2][arr[-1]])

매번 어려운 DP 문제이다. 

여기서 제일 헷갈렸던것은 인덱스였다. 

먼저 dp의 행은 주어진 입력의 몇번째 index에서의 행해진 것인지 나타낸다.

그리고 열은 이 문제는 0~20 사이의 값만 있으므로, 21개의 열을 미리 만들어줬다.

먼저 dp를 0으로 초기화 시킨다.

그리고 dp[0][arr[0]] = 1로 초기화 한다.

가장 첫번째 숫자는 무조건 더해져야하기 때문이다.

그리고 그 다음부터는 0~21 까지를 prev_num으로 반복문을 돌리고 현재 ind의 arr값과 더했을때

0~20 사이이면 현재 ind의 새로운값에 더해주면 된다.

그리고 이 모든 행위는 N-2번 인덱스에서 종료되기 때문에, 출력할때 [N-2][arr[-1]]을 해주도록 하자.

# 2493번 탑
from collections import deque
N = int(input())
arr =  list(map(int,input().split()))
result = [0]*N
stack = deque()
for ind in range(N):
    while stack and stack[len(stack)-1][1] < arr[ind]:
        stack.pop()
    if stack:
        result[ind] = stack[len(stack)-1][0]
    else:
        result[ind] = 0
    stack.append((ind+1,arr[ind])) 


    
print(*result)

   이 문제는 스택을 이용해 구현하는 문제인데, 스택과 큐와 같은 기본이 좀 부실하다보니 푸는데 어려움을 겪었던 문제였다.

첫 풀이는 앞에서부터 탐색하는 방식이다.

스택에는 앞에서부터 차근차근 인덱스와 탑의 높이를 넣어놓는다. 

그리고 스택에 놓여져있을때, 스택의 마지막 값이 탐색하는 탑의 높이보다 크거나 같을때 까지 계속 pop을 해준다. 

그리고 만약에 스택이 남아있으면 마지막 값을 결과값에 넣어주고, 아니면 0을 넣어준다.

예를 들어 설명하겠다.

7 3 5 9 2 8 이 있다고 하자

tower :  7 3 5 6 2 8

ind : 0

stack : []

result : [0,0,0,0,0,0]

처음에는 stack이 비어져있고, 가장 첫번째는 무조건 0이기 때문에 stack에 현재 타워의 index와 높이를 넣어준다.

tower : 7 3 5 9 2 8

ind : 1

stack : [(1,7)]

result : [0,1,0,0,0,0]

다음 타워는 높이가 3인데 스택의 끝에 있는 타워보다 높이가 낮기 때문에 그대로 수신이 가능하다. 그래서 결과에는 스택의 마지막에 있는 타워의 index를 넣어주고 stack에 넣어준다.

tower : 7 3 5 9 2 8

ind : 2

stack : [(1,7),(2,3)]

result : [0,1,1,0,0,0]

여기서 봐보면 현재 tower의 높이는 5이다. 하지만 stack에 끝에 있는 타워의 높이는 3이다. 그러면 이 tower에는 절대 다른 타워에서 수신을 할 수 없다. 왜냐하면 높이가 5인 타워가 높이가 3인 타워를 가리기 때문에, 신호를 수신할 수 없다. 그렇기 때문에 stack에서 없애주고, 그 다음 끝값과 비교한다. 여기서는 현재타워의 높이가 5이고, 스택의 마지막은 7이기 때문에 1번째 타워에서 신호가 수신이 가능하고, stack에 넣어준다.

tower : 7 3 5 9 2 8

ind : 3

stack : [(1,7),(3,5)]

result : [0,1,1,0,0,0]

위와 같은 방식으로 하면 스택내에는 현재 타워의 높이인 9보다 높은 타워가 없기 때문에 스택이 전부 비워지고, 결과값에는 0을 넣어줄 수 있다

tower : 7 3 5 9 2 8

ind : 4

stack : [(4,9)]

result : [0,1,1,0,4,0]

현재 타워의 높이가 2이므로 스택의 끝값보다 작기 때문에 수신이 가능하다. 그리고 스택에 넣어주면 된다.

tower 7 3 5 9 2 8

ind : 5

stack : [(4,9),(5,2)]

result : [0,1,1,0,4,4]

똑같이 진행해주면 된다.

위와 같이 스택의 특성을 알고, 하나하나 진행해주면 쉬운 문제인데, 알고리즘 기초인 스택과 큐에 대해서 약하다보니 오래걸렸던 문제이다.

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

result = [0]*N
stack = []

for ind in range(N-1,-1,-1):
    while stack and arr[stack[-1]] < arr[ind]:
        result[stack.pop()] = ind + 1
    stack.append(ind)

print(*result)

이 방법은 끝에서부터 진행하는 방법이다. stack에 인덱스를 넣어주고 거꾸로 오면서 stack에 끝에 있는 값이 현재의 타워보다 작을때, 그때 stack에서 꺼내서 결과값에 저장하는 방식이다.

# 실패한 방법

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

arr = [list(map(int,list(input()))) for _ in range(N)]
result = 0
max_size = min(N,M)

for x in range(N):
    for y in range(M):
        if result == max_size:
            break
        if arr[x][y] == 1:
            for sizes in range(result,max_size+1):
                temp = 0
                for dx in range(sizes):
                    for dy in range(sizes):
                        if 0<=x+dx<N and 0<=y+dy<M: 
                            temp += arr[x+dx][y+dy]
                if temp == sizes**2:
                    result = sizes
                else:
                    break
print(result**2)

처음에 단순하게 현재의 max_size만큼을 각 위치에서 탐색을 해서 갱신해주는 방식을 했다. 이렇게 하니 시간 초과가 나왔다.

N,M = map(int,input().split())
arr = [[0]*(M+1)]
for _ in range(N):
    arr.append([0]+list(map(int,list(input()))))
result = 0
max_size = min(N,M)

for x in range(1,N+1):
    for y in range(1,M+1):
        if arr[x][y]:
            arr[x][y] = min(arr[x-1][y],arr[x][y-1],arr[x-1][y-1])+1
            result = max(arr[x][y],result)
        if result == max_size:
            break

print(result**2)

위와 같은 정사각형이 있으면,  우하단을 기준으로 상하, 대각선이 전부 1이어야만 정사각형이 모양이된다. 만약 3개 중 하나라도 0이 있으면 크기가 2인 정사각형이 모양이 안된다. 그러므로 여기서 될수 있는 정사각형의 크기는 2이다.

이걸 좀 더 확장해서 3*3를 그려보도록 하자.

위와 같이 있다고 했을때 행과 열 중 0인 곳은 크기가 1를 초과하는 것을 못 만드므로 예외로 하겠다. 그러면 실질적으로 1,1 부터 탐색을 한다.

위와 같은 로직으로 하면 다음과 같이 우하단이 3이 되는 것을 알 수 있다 

이렇게 한군데가 비어있으면

이렇듯 우하단이 2가 되는 것을 알 수 있다.

그러므로 이 문제는 (x,y) 좌표 기준으로 (x-1,y),(x,y-1),(x-1,y-1)의 값의 최소값에 + 1을 해주면 된다.

그리고 저장된 값 중에서 가장 큰 값이 이 행렬에서 제일 큰 정사각형이므로, 제곱을 해서 출력을 하면 된다.