Coding 공부

# 2225번 합분해


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

dp = [[1]*(N+1) if i==0 else [0]*(N+1) for i in range(K)]


for ind in range(1,K):
    for prev_num in range(N,-1,-1):
        for current_num in range(N,-1,-1):
            if prev_num + current_num <=N:
                dp[ind][prev_num+current_num] += dp[ind-1][prev_num]


print(dp[K-1][N]%1000000000)

K 번을 더햇 N이 나오는 경우이므로, DP를 (N+1)*K 형태로 만들어 놨다. 그래서 이전 행에서의 prev_num과 현재의 current_num을 더해서 N을 넘지 않는 경우 새로운 행에 그 횟수를 저장해주는 방식을 해주었다.

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

dp = [[1]*(N+1) if ind==0 else [0]*(N+1) for ind in range(K)]


for k in range(1,K):
    for num in range(N+1):
        dp[k][num] = (dp[k-1][num] + dp[k][num-1])%1000000000

print(dp[K-1][N])

위의 방식대로 풀어도 시간내에 통과하지만 점화식을 구하면 좀 더 쉽게 구할 수 있다.

DP[K][N] = DP[K-1][N] + DP[K-1][N-1] + .... + DP[K-1][0] 이다.

DP[K][N-1] = DP[K-1][N-1] + DP[K-1][N-2] + .... + DP[K-1][0] 인 것을 알 수 있따.

이것을 봐보면 DP[K][N] = DP[K-1][N] + DP[K][N-1]인 것을 알 수 있다.

이 점화식을 통해 구하면 좀 더 쉽게 구할 수 있다.

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
apples = set(tuple(map(int,input().split())) for _ in range(K))
command_cnt = int(input())
# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
flag = True
next_time = commands[0][0]
break_flag = False
while True:
    if flag:
        next_time = commands[ind][0]


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if (next_x,next_y) not in snakes:
            if (next_x,next_y) in apples:
                snakes.appendleft((next_x,next_y))
                apples.remove((next_x,next_y))
            else:
                snakes.pop()
                snakes.appendleft((next_x,next_y))
        else:
            break_flag = True
    else:
        break_flag = True
    if break_flag:
        break



    if snake_times == next_time:
        snake_direction = (snake_direction + commands[ind][1])%4
        ind += 1
        if ind == command_cnt:
            flag = False
print(snake_times)

이 문제는 큐와 스택같은 자료구조에 대해서 알면 쉽게 풀 수 있는 문제이다.

물론 나는 오래걸렸다.

먼저 여기서는 방향 전환이 왼쪽, 오른쪽 밖에 없다. 만약에 동남서북(0,1,2,3) 형태로 방향을 저장해놓은 상태라면, 왼쪽일때는 -1을 해주고 오른쪽일때는 +1 을 해주고, 4로 나눈 나머지를 구해주면 된다.

기본적인 방법은 다음과 같다. snake는 기본적으로 deque 형태로 저장을 해준다.

먼저 snake_head를 기준으로 탐색해야한다. 나는 deque에서 왼쪽 즉 처음 들어온부분이 head로 가정했기 때문에, snake[0]을 가져온다. 그리고 snake의 방향에 맞게 진행을 해준다. 만약 범위를 벗어나거나 이미 snake에 있는 위치로 갈시, 예외처리를 해주고, 즉각적으로 멈출수 있게 break_flag를 해주었다.

그리고 둘 중 하나인데 만약에 뱀의 머리가 움직인 위치에 사과가 있을때에는, 뱀의 길이가 늘어난 것이기 때문에 새로운 head의 위치를 snake에 추가해주고, apple를 없애준다.

만약에 사과가 없을때에는 꼬리부분을 없애주고, 새로운 머리부분을 추가해준다.

매 타임마다 위와 같이 진행을 해주면 되는데, 여기서 명령어가 주어진다. 여기서 주의할 점은 시간이 끝난뒤 시행되는 것이기 때문에 time을 늘려주는 로직을 이 명령어를 조작하는 부분보다 상위에 두어야한다.

뱀이 움직이 시간이 끝난 시간과 명령어에 들어온 시간이 같으면 명령어 대로 방향을 바꿔준다.

그리고 이 명령어의 길이가 3일때, 만약에 3번째 명령까지 반영해서 방향을 바꿔주었으면 마지막 방향대로 계속 진행을 해야하기 때문에 flag를 통해 예외 처리를 해주었다.

# # 3190 뱀
from collections import deque

N = int(input())
K = int(input())
board = [[0]*(N+1) for _ in range(N+1)]
for _ in range(K):
    x,y = map(int,input().split())
    board[x][y] = 1

command_cnt = int(input())

# direction 0동 1남 2서 3북
dx = [0,1,0,-1]
dy = [1,0,-1,0]
commands = []
snakes = deque()
snakes.append((1,1))
board[1][1] = 2
for _ in range(command_cnt):
    time,dire = input().split()
    if dire == 'D':
        dire = 1
    else:
        dire = -1
    commands.append((int(time),dire))

snake_times = 0
ind = 0
snake_direction = 0
next_time,next_direction = commands[0]
break_flag = True
while True:


    snake_times += 1

    snake_head = snakes[0]
    next_x = snake_head[0] + dx[snake_direction]
    next_y = snake_head[1] + dy[snake_direction]
    if 1<= next_x <=N and 1<= next_y<=N:
        if board[next_x][next_y] != 2:
            if board[next_x][next_y] == 1:
                snakes.appendleft((next_x,next_y))
                board[next_x][next_y] = 2
            else:
                board[next_x][next_y] = 2
                tail_x,tail_y = snakes.pop()
                board[tail_x][tail_y] = 0
                snakes.appendleft((next_x,next_y))
            break_flag = False
    if break_flag:
        break
    break_flag = True



    if snake_times == next_time:
        snake_direction = (snake_direction + next_direction)%4
        if ind < command_cnt-1:
            ind += 1
            next_time,next_direction = commands[ind]

print(snake_times)

위의 내가 했던 부분과 거의 동일하다. 대신 board라는 2차원 리스트에 뱀의 위치와 사과의 위치를 표시해주었다 이렇게 하면, 첫번째 코드에서 썼던 not in snakes와 같은 logN이 걸리는 시간이 좀 더 줄어드는 장점이 있다.

from collections import deque

def bfs(x,y,color):
    global N
    stack = deque()
    stack.append((x,y))
    if color == 'B':
        chk = 2
    else:
        chk = 3
    visited[x][y] = chk
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if not visited[nx][ny] and arr[nx][ny] == color:
                    visited[nx][ny] = chk
                    stack.append((nx,ny))
    
def new_bfs(x,y,chk):
    global N
    stack = deque()
    stack.append((x,y))
    visited[x][y] = 0
    while stack:
        x,y = stack.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <=nx<N and 0<=ny<N:
                if visited[nx][ny] == chk:
                    visited[nx][ny] = 0
                    stack.append((nx,ny))

N = int(input())


arr = [list(input()) for _ in range(N)]
dx = [-1,1,0,0]
dy = [0,0,-1,1]
visited = [[0]*N for _ in range(N)]
cnt_a = 0
cnt_b = 0
for x in range(N):
    for y in range(N):
        if not visited[x][y]:
            bfs(x,y,arr[x][y])
            cnt_a += 1

for x in range(N):
    for y in range(N):
        if visited[x][y]:
            new_bfs(x,y,visited[x][y])
            cnt_b += 1

print(cnt_a,cnt_b)

2개의 BFS로 나누어, 3개의 색으로 구분할때와 2가지 색으로 구분할때 나눠서 탐색해주면 된다.

여기서 별다른 건 없고, visited 라는 리스트를 두번 만드는게 싫어서, 첫번째 bfs에서 visited에 체크하는 숫자를 청색 vs 녹색,빨간색을 서로 다르게 해주었고,

두번째 bfs에서는 원본 배열이 아닌 visited 함수를 통해 bfs를 돌려주었다.

# 14503 로봇 청소기

# r,c 는 r은 북쪽(X) c는 서쪽(Y)
# 동서남북
# sudo
# 1. 현재위치 청소
# 2. 현재 위치에서 왼쪽으로 회전 + 전진 -> 청소 반복
#  없으면 그 방향으로 계속 회전
# 4방향 전부 청소 완료하면 한칸 후진
# 후진이 안되면 멈춤
# d 0,1,2,3 북동남서
# 빈칸은 0, 벽은 1
N,M = map(int,input().split())
robotX,robotY,direction = map(int,input().split())

arr = [list(map(int,input().split())) for _ in range(N)]
rotate = [3,0,1,2]
visited = [[True] *M for _ in range(N)]
cnt = 1
stack = [(robotX,robotY,direction)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]
visited[robotX][robotY] = False
while stack:
    x,y,cu_dire = stack.pop()
    if visited[x][y]:
        visited[x][y] = False
        cnt += 1
    for _ in range(4):
        nx = x + dx[rotate[cu_dire]]
        ny = y + dy[rotate[cu_dire]]
        if 0<= nx <N and 0<= ny<M:
            if visited[nx][ny] and not arr[nx][ny]:
                stack.append((nx,ny,rotate[cu_dire]))
                break
        cu_dire = rotate[cu_dire]
    else:
        reverse_dire = (cu_dire+2)%4
        nx = x + dx[reverse_dire]
        ny = y + dy[reverse_dire]
        if 0<= nx< N and 0<= ny <M and not arr[nx][ny]:
            stack.append((nx,ny,cu_dire))
        else:
            break

print(cnt)

    

이 문제는 문제에 주어진 조건대로 구현을 하는 문제였다. 

문제에 주어진 조건대로 구현을 하면 되는데, 여기서 몇가지 주의점이 있다. 보통 DFS나 BFS에서는 시간을 아껴주기 위해, stack에 append 할때 방문을 표시해준다. 하지만 여기서는 한번 청소했던 곳을 다시 방문할 수 있고, 청소는 단 한번만 해주기 때문에, stack에서 빼줄때, 그때 visitied를 방문표시를 해주고, 청소회수를 늘려주었다. 이러는게 문제에 주어진 구현 순서인 1번에 적합한 것 같다.

1. 현재 위치를 청소한다.
2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.
   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

2.1 ~ 2.2 구간이 중간에 있는 반복문에 있는 부분이다. 여기서는 사전에 작업을 해주었다. 위에 주석에도 있지만, 0,1,2,3을 북동남서로 저장해주고, 그에 해당되는 dx,dy를 구현해주었다. 

그리고, rotate라는 변수에, 인덱스값은 현재의 방향 그리고 값은 왼쪽으로 회전시 나오는 방향을 넣어주었다.

평소에는 북남동서등 같은 방향끼리, 하는 경우가 많은데 여기서는 북동남서로 2칸씩 떨어트린 이유는 후진을 구현할때, 이렇게 2칸씩 떨어트려주면 (direction+2)%4 로 하면 쉽게 방향을 구할 수 있기 때문이다. 정 아니면 rotate와 동일하게 후진시 변경되는 리스트를 미리 만들어둬도 된다.

이렇게 반복문을 다 돌렸는데도 한번도 만족하지 않으면, else로 들어가 2.3~2.4 로직을 진행한다.

후진이 가능하면, stack에 집어넣고, 그렇지 않으면 종료를 해주면 된다.

구현관련된 문제는 하나씩 단계별로 구현하는 연습을 더 자주해야할것 같다.

# 16946 벽 부수고 이동하기 4

# dfs를 해준다. 여기서 일반적인 dfs와 다른점은 방문표시 대신 해당 위치의 값을 들어온 index값으로 변형시켜준다.
def dfs(x,y,index):
    global index_dict,N,M

    stack = [(x,y)]
    cnt = 1
    arr[x][y] = index
    while stack:
        cx,cy = stack.pop()
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0<=nx<N and 0<=ny<M:
                if not arr[nx][ny]:
                    stack.append((nx,ny))
                    arr[nx][ny] = index
                    cnt += 1
    # dfs를 전부 한뒤에 그 개수를 딕셔너리에 저장해준다.
    index_dict[index] = cnt




# dfs를 이용해서 쉽게 풀수 있었던 문제


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

dx = [-1,1,0,0]
dy = [0,0,-1,1]
arr = [list(map(int,list(input()))) for _ in range(N)]
# 원본이 저장된 arr
result = [['0']*M for _ in range(N)]
# 결과값들을 저장해놓는 result 배열을 만들어둔다.

# 빈칸인 개수를 세주기 위해서 초기값을 -1로 해줬다. 왜냐하면 arr에는 1,0이 있으므로 겹쳐지지 않게 -1부터 시작해서 1씩 작아지게 해줬다.
# 그리고 해당 인덱스에 연결된 개수를 저장하기 위한 index_dict라는 딕셔너리를 미리 만들어줬다.
index = -1
index_dict = {}

# 빈칸의 개수를 세어주기 위한 dfs 공정
for x in range(N):
    for y in range(M):
        if not arr[x][y]:
            dfs(x,y,index)
            index -= 1

for x in range(N):
    for y in range(M):
        if arr[x][y] == 1:
            # 원본 배열에서 벽이 있을때, 그 벽 주변의 상황을 파악하고, 그 중에 1이 아닌 우리가 설정한 index값을 집합에 저장해준다.
            temp = set()
            for i in range(4):
                nx = x + dx[i]
                ny = y + dy[i]
                if 0<=nx<N and 0<=ny<M:
                    if arr[nx][ny] != 1:
                        temp.add(arr[nx][ny])
            # 기본값은 1이고, temp에 저장된 index들을 반복문을 돌려 움직일수 있는 칸의 개수를 세준다.
            move_wall = 1
            for index in temp:
                move_wall += index_dict[index]
            # 그리고 result에 10으로 나눈 나머지를 string형태로 저장해준다.
            result[x][y] = str(move_wall%10)
# join을 이용해 출력해준다.
for row in result:
    print(''.join(row))

 이 문제는 union find 문제와 비슷하게 빈 위치의 그룹을 지어주면 된다.

최종 결과가 나올 result라는 2차원 배열을 '0'으로 초기화 해줬다. 왜냐하면, 나중에 출력을 할때, join을 쓰기 위해, 문자열 형태로 초기화 해줬다.

먼저 주어진 행렬의 빈칸들의 그룹의 정보를 저장해줄 index_dict을 만들어줬다. 여기서 key는 index 을 기준으로 해줬고, value는 그 그룹의 개수이다.

여기서 index 초기값을 -1을 해준 이유는 문제에서 0,1을 이미 쓰고 있어서, 겹치지 않기 위해 음수로 해줬다.

그러면 주어진 행렬에서 dfs 아니면 bfs를 해주면서, 빈칸들의 그룹들을 나눠 주는 작업을 해주고, 그 그룹의 크기와 index를 index_dict에 저장을 해주면서, 원본행렬에도 index를 대신 넣어준다.

벽 부수고 이동하기를 해주는 방법은 원본 행렬에서 1인 곳을 찾아서, 상하좌우에 있는 1이 아닌 값들을 집합에 저장을 해준다. 그리고 집합에 저장된 index들을 꺼내 전체 index_dict에 저장된 값들을 더해주면 된다. 그리고 원래 있던 벽이 무너지는 거니 1이 기본값이다.

그리고 결과값을 10으로 나눈 나머지를 문자열 형태로 저장해줬다.

# 1937 욕심쟁이 판다 실패(Fail)
def dfs(x,y):
    global N
    stack = [(x,y,0)]
    last_direction = []
    while stack:
        cx,cy,distance = stack.pop()
        flag = True
        for i in range(4):
            nx = cx + dx[i]
            ny = cy + dy[i]
            if 0 <= nx<N and 0<=ny<N:
                if bamboo[cx][cy] < bamboo[nx][ny]:
                    if dp[nx][ny] == -1:
                        stack.append((nx,ny,distance+1))
                    else:
                        if distance + dp[nx][ny] + 1 > dp[x][y]:
                            dp[x][y] = dp[nx][ny] + distance + 1
                           
                    flag = False
        if flag:
            if dp[x][y] < distance + 1:
                dp[x][y] = distance + 1



N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]

result = - 1
for x in range(N):
    for y in range(N):
        if dp[x][y] == -1:
            dfs(x,y)
print(max(map(max,dp)))

이 문제를 단순하게 DFS로 풀면 시간 초과가 날수 밖에 없다. 왜냐하면 입력이 최대가 500*500 이므로, dp를 통해 이미 탐색한 값들을 저장해놓는 과정이 필요하다. 위의 코드는 시간초과가 난 코드이다. 

dp를 사용하긴 했지만, 각 (x,y) 축에서 dfs를 하지만, 이 이동경로에 있는 좌표들에 대해서 이미 한번 측정한 값인데, 다시 한번 dp를 측정해야하는 것이다.

import sys


def dfs(x,y):
    if dp[x][y] != -1:
        return dp[x][y]
    else:
        dp[x][y] = 1
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<N and 0<=ny<N:
                if bamboo[nx][ny]>bamboo[x][y]:
                    distance = dfs(nx,ny) + 1
                    dp[x][y] = max(distance,dp[x][y])
        return dp[x][y]







N = int(input())
dx = [-1,1,0,0]
dy = [0,0,-1,1]
bamboo = [list(map(int,input().split())) for _ in range(N)]
dp = [[-1]*N for _ in range(N)]
result = - 1
for x in range(N):
    for y in range(N):
        if dp[x][y] == -1:
            dfs(x,y)

print(max(map(max,dp)))

재귀를 이용한, 이동 경로에 대해서 전부 한번에 업데이트를 해주는 것이다.

최초 이동경로에서 (x0,y0) = > (x1,y1) => (x2,y2) => ...=>(xn,yn) 각 경로마다 최대로 갈수 있는 이동경로들을 저장해준다. 그리고 return된 값에 + 1을 해줘 해당 칸에 갔을때의 이동거리를 측정해주고, 최대값을 갱신해주면 된다.

이렇게 하면 장점은 어느 곳에서 한번 방문했던 곳은 더 이상 dfs를 하지않고 해당 위치에서의 최대값을 반환해주는 것이다.

이 문제는 각 위치마다의 최대경로를 구하는 로직과, 그걸 이용해서 시간복잡도를 줄이는게 중요한 문제였다.

# # # 9466 텀 프로젝트
import sys
sys.setrecursionlimit(100000)



def dfs(node):
    global result
    visited[node] = False
    total.append(node)
    next_node = graph[node]
    if not visited[next_node]:
        if next_node in total:
            find_index = total.index(next_node)
    
            result +=total[find_index:]
        return
    else:
        dfs(next_node)


for _ in range(int(input())):
    N = int(input())
    graph = [0]+list(map(int,sys.stdin.readline().split()))
    visited = [True] *(N+1)
    result = []
    for ind in range(1,N+1):
        if visited[ind]:
            total = []
            dfs(ind)
    print(N-len(result))

문제를 풀때, 어떻게 풀어야할지 고민을 했던 문제이다. 문제를 읽어보면, 사이클을 이루는 경우에만, 팀이 될수 있다는 것을 알 수 있다. 

그래서 DFS 재귀를 통해서, 내가 방문한 곳을 다시 방문하게 된다면, 사이클을 이루게 되는 것이기 때문에, 결과값에 추가해주었다. 중간의 find_index 같은 경우 사이클을 이루어지는 최초지점을 찾아서 저장해주기 위함이다.

만약 1,2,3,4,5 가 있고, 각각 2,3,4,5,2를 선택했다고 하면 dfs를 했을때 total에는 [1,2,3,4,5]가 저장되어있을 것이다. 하지만, 1은 문제에 주어진 조건을 만족하지 못하고, 팀이 되지 못한다. 그래서 사이클이 최초로 시작되는 2를 기준으로 잘라주기 위함이다.

for _ in range(int(input())):
    N = int(input())
    graph = list(map(int,input().split()))
    visited = [0]*N
    cnt = 0
    for current_node in range(N):
        if not visited[current_node]:
            next_node = current_node
            while visited[next_node] == 0:
                visited[next_node] = 1
                next_node = graph[next_node] - 1
            cycle_index = current_node
            while cycle_index != next_node:
                cnt += 1
                cycle_index = graph[cycle_index] - 1

    print(cnt)

            

좀 더 깔끔한 풀이다. 위와 비슷하지만, 최초로 사이클이 시작되는 노드는 중간의 while문을 통과하고 나온 next_node일것이다.

그러면 처음 노드인 current_node를 복사해, cycle_index라고 하고, 이 cycle_index가 next_node와 같지 못하면, 사이클에 포함되지 않는 노드임을 알 수 있다. 이 next_node는 사이클이 최초로 발생하는 노드의 위치이기 때문에, 만약 current_node에서 사이클이 시작됬다면 cycle_node와 next_node는 동일할 것이다. 

그래서, 이 cycle_node를 똑같이 반복문을 돌리면서 next_node와 같아질때까지 반복을 한다. 그게 곧 팀에 포함되지 않는 사람의 수를 나타내는 것임을 알 수 있다.

# 1759 암호 만들기
def check(input_val,vowel):
    
    check_list = [0,0]
    for val in input_val:
        if val in vowel:
            check_list[0] += 1
        else:
            check_list[1] += 1

    if check_list[0] >= 1 and check_list[1] >= 2:
        return True
    else:
        return False 




def dfs(cnt,ind,result):
    global vowel
    if ind == C:
        if cnt == L and check(result,vowel):
            total.append(result)
            return
    else:
        dfs(cnt+1,ind+1,result+input_list[ind])
        dfs(cnt,ind+1,result)




L,C = map(int,input().split())
vowel = 'aeiou'
input_list = list(input().split())
input_list.sort()

total = list()
dfs(0,0,'')
for val in total:
    print(val)

재귀를 이용해서 조합을 만들어준 것과 같다. 각 인덱스에 들어와서, 해당 문자를 포함하거나 포함하지 않는 경우를 구분해서 재귀를 돌려주었다.

그리고 주어진 길이만큼 되면, 그 안에 모음과 자음 숫자에 따라 True False를 반환해주고, True일때 결과값에 추가해줬다.

from itertools import combinations

L,C = map(int,input().split())

input_value = list(input().split())

input_value.sort()
vowel = set(['a','e','i','o','u'])
for combi in combinations(input_value,L):
    password = set(combi)
    if password & vowel:
        if len(password-vowel)>=2:
            print(''.join(combi)) 

좀 더 간단한 풀이이다. 위에서 말했듯이 이것은 조합을 구하는것과 동일하다.

combinations 라이브러리를 활용해 전체 combinations을 구하고, 집합의 특성을 이용해, 교집합이 존재하는지, 차집합을 통해 길이가 2이상인지 구분해줘서, 만약 두개다 통과하다면, 원하는 값이므로 출력해주는 방식으로 풀었다.