Opal1031

트리의 순회백준 #2263📌 문제예제 입력31 2 31 3 2예제 출력2 1 3📌 풀이Logic정점 개수 N 입력 받기inorder, postorder 입력 받기inorder: 루트의 위치를 찾아서 left / right 경계를 나누는 용도left -> root -> rightpostorder: postorder의 마지막 요소는 트리의 rootleft -> right -> rootpreorder stack 생성 [in 시작 idx, in 끝 idx, post 시작 idx, post 끝 idx]# 변수명n : 노드 개수inorder, postorder, preorder : 각 방식의 리스트inorder_index : 각 값의 인덱스를 찾기 위한 딕셔너리left_size : 현재 서브트리에서 root 기..

동전 1백준 #2293📌 문제예제 입력3 10125예제 출력10📌 풀이Logic동전의 종류 n과 가치의 합 k 입력 받기각 동전의 가치 입력 받기DP 리스트 생성DP[x] = 합이 x가 되는 경우의 수# 변수명n : 동전의 종류k : 원하는 가치의 합coins : 각 동전의 가치dp : 합이 x가 되는 경우의 수Pythonimport sysinput = sys.stdin.readlinen, k = map(int, input().split())coins = [int(input()) for _ in range(n)]dp = [0] * (k + 1)dp[0] = 1for coin in coins: for s in range(coin, k + 1): dp[s] += dp[s - coin]p..

LCS 2백준 #9252📌 문제예제 입력ACAYKPCAPCAK예제 출력4ACAK📌 풀이Logic#9251에서 기능 추가가장 긴 LCS를 역으로 추적하는 방식str1, str2의 길이 i, j가 0이 될 때 까지,,각 str의 문자를 비교하며 LCS에 추가# 변수명str1, str2 : 비교할 두 문자열i, j : 두 문자열의 길이Pythonimport sysstr1 = sys.stdin.readline().strip()str2 = sys.stdin.readline().strip()dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]for i in range(1, len(str1) + 1): for j in range(1, len(str2) + ..

LCS백준 #9251📌 문제예제 입력ACAYKPCAPCAK예제 출력4📌 풀이Logic두 문자열 입력 받기DP 테이블 생성2차원 배열 DP는 str1의 처음 i글자와 str2의 처음 j글자 까지의 LCS 길이를 저장str1[i - 1]와 str2[j - 1]이,,,같으면 공통 문자를 LCS에 추가다르면 둘 중 더 긴 LCS 선택DP[-1][-1] 출력 # 변수명str1, str2 : 비교할 두 문자열Pythonimport sysstr1 = sys.stdin.readline().strip()str2 = sys.stdin.readline().strip()dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]for i in range(1, len(str1) ..

조 짜기백준 #2229📌 문제예제 입력102 5 7 1 3 4 8 6 9 3예제 출력20📌 풀이Logic학생 수 N, 학생들의 점수 scores 입력 받기DP 테이블 생성i번째 학생까지 고려할 때, 마지막 조의 시작점을 K로 정의K를 i - 1 ~ 0까지 줄여가며 diff 계산각 학생을 마지막으로 포함하는 조의 모든 경우 시도기존의 dp[i]값과 dp[k] + diff 중 큰 값으로 갱신# 변수명N : 학생 수scores : 학생들의 점수 리스트diff : 해당 범위에서 max - min 값Pythonimport sysN = int(sys.stdin.readline().strip())scores = list(map(int, sys.stdin.readline().split()))dp = [0 for _..

RGB거리백준 #1149📌 문제예제 입력326 40 8349 60 5713 89 99예제 출력96📌 풀이Logic집의 수 N 입력 받기각 집의 RGB 비용 입력 받기DP 테이블 생성dp[i][j] -> i번재 집을 j색으로 색칠첫 번째 집은 입력값 그대로마지막 집까지 계산 후 최소값 출력# 변수명N : 집의 수cost : 각 집의 RGB 색칠 비용 리스트Pythonimport sysN = int(sys.stdin.readline())cost = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]dp = [[0] * 3 for _ in range(N)]dp[0] = cost[0]for i in range(1, N): dp[i][0] ..

나이트의 이동백준 #7562📌 문제예제 입력380 07 01000 030 50101 11 1예제 출력5280📌 풀이Logic테스트 케이스 수 T 입력 받기체스판의 크기 I 입력 받기나이트의 현재 위치 / 이동하려는 위치 좌표쌍 입력 받기BFS 함수 구현 (deque)현재 위치에서 8방향 이동 가능 여부 확인이동 가능한 경우 해당 라운드 board에 표기# 변수명T : 테스트 케이스 수I : 체스판의 크기start_x, start_y : 나이트의 현재 위치 좌표쌍end_x, end_y : 나이트의 이동하려는 위치 좌표쌍dq : 현재 나이트의 위치를 저장하는 deque(해당 라운드 출발 지점)visited : 백트래킹을 위한 리스트 (이미 방문한 노드로는 이동하지 않음)Pythonimport sysfro..

DSLR백준 #9019📌 문제예제 입력31234 34121000 11 16예제 출력LLLDDDD📌 풀이Logic테스트 케이스 T 입력 받기두 개의 정수 A, B 입력 받기BFS 함수 구현 (deque)기존의 값을 DSLR의 형태로 변환변환한 값 visited에 표기변환한 값에 변환 명령어를 추가하여 deque에 추가최종 값을 완성한 경우, 변환 명령어 전체 출력# 변수명T : 테스트 케이스 수prev : 초기 값result : 최종 값dq : 현재 라운드에서 (레지스터 값, 명령어)를 저장하는 dequeD, S, L, R : 해당 라운드의 레지스터 값을 DSLR의 형태로 변환했을 때의 값Pythonimport sysfrom collections import dequedef DSLR_calc(prev,..

토마토백준 #7576📌 문제예제 입력6 40 0 0 0 0 00 0 0 0 0 00 0 0 0 0 00 0 0 0 0 1예제 출력8📌 풀이Logic상자 크기 M * N 입력 받기토마토 정보 입력 받기BFS 함수 구현(deque)익은 토마토(1) 위치 파악해당 토마토에서 4방향으로 이동 가능 여부 확인이동 가능 : 익은 토마토로 표시(1) & visited[True] & day 정보 변경이동 불가능(비어있는 경우) : visited[True]익지 않은 토마토 존재 시 -1 출력 후 종료모든 토마토가 익는 데 걸린 날짜 출력(max_day)# 변수명M, N : 박스 크기box : 토마토 정보 입력 리스트dq : 현재 라운드에서 익은 토마토를 저장하는 deque(해당 라운드 출발 지점)visited : 백..

노드 사이의 거리백준 #1240📌 문제예제 입력4 22 1 24 3 21 4 31 23 2예제 출력27📌 풀이Logic노드 개수 M, 노드 쌍 개수 N 입력 받기N - 1개의 노드 쌍 및 거리 입력 받기BFS 함수 구현(deque)현재 노드가 end이면 누적된 distance를 출력 후 종료graph를 참고하여 next_node를 방문하지 않았다면, dist 증가 및 distance 갱신# 변수명N : 노드 개수M : 노드 쌍 개수graph : 노드 쌍 정보 리스트node1, node2, length : 노드 쌍 정보start, end : 거리를 알고 싶은 두 노드dq : 현재 노드를 저장하는 dequevisited : 백트래킹을 위한 리스트 (이미 방문한 노드로는 이동하지 않음)distance : ..