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 _..

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 : ..

등차수열의 합백준 #1419📌 문제예제 입력1123예제 출력3📌 풀이Logic자연수 l, r, k 입력 받기k의 값에 따른 경우의 수 나누기 조건에 맞는 수열에서의 범위(start, end) 값 지정예외 처리 범위에 해당하는 개수 출력# 변수명l, r, k : 입력한 정수값start, end : 수열에서의 범위Pythonimport sysl, r, k = map(int, [sys.stdin.readline() for _ in range(3)])if (k == 2): start = max(0, l - 3) end = max(0, r - 2) print(end - start)elif (k == 3): start = max(0, (l - 1) // 3 - 1) end = max(..