jenlog

🌝 Summer/Winter Coding(~2018) 문제 https://programmers.co.kr/learn/courses/30/lessons/12978 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr thinking 최단거리이기 때문에 다익스트라를 사용했다 나동빈님의 블로그를 보면 이해가 아주 쉽다. 굿 !!!!!! https://blog.naver.com/PostView.naver?blogId=ndb796&logNo=221234424646&redirect=Dlog&widge..

🚩 동적프로그래밍(DP) thinking 1. 규칙을 찾아보려 했으나 실패 -> 규칙 없음 ! 2. DP 접근 인풋숫자의 크기만큼 배열을 만들고, 계산횟수를 해당 인덱스에 입력 & 비교하면서 최소 연산값을 구하는 것이다. 앞에서 부터 계산을 해가면서 카운팅을 늘려나가는 것이 핵심이다 ! ◾ 점화식 : dp(N) = min ( dp(N//3)+1, dp(N//2)+1 , dp(N-1)+1 ) ◾ 시간복잡도 : {배열의 크기 x O(1)} => O(N) 코드 N = int(input()) dp = [0 for _ in range(N+1)] # 인덱스가 N이 되도록 N+1 크기의 배열을 만듦 for i in range(2, N+1): dp[i] = dp[i-1] + 1 # dp(N-1)+1 계산먼저 해주고 i..

🚩 트리(tree) 풀이 1 왼쪽 자식, 오른쪽 자식을 세트로 같이 더해주는 방식 T = int(input()) for tc in range(1, T+1): N, M, L = map(int, input().split()) # N:노드개수, M:리드노프개수, L:출력할 노드번호 tree = [0 for _ in range(N + 1)] for i in range(M): n, v = map(int, input().split()) tree[n] = v # 방법1 if N % 2 == 0: # 노드개수가 짝수인 경우를 위해 설정 tree.append(0) for i in range((N//2)*2, 1, -2): tree[i // 2] = tree[i] + tree[i + 1] print("#{} {}".for..

🚩 트리(tree) thinking [부모노드, 왼쪽자식, 오른쪽자식, 노드값] 의 2차원 리스트 형태의 트리를 만들고 input data 값을 넣어준다. 왼쪽자식, 오른쪽자식의 노드번호가 1씩 차이나므로 인덱스를 홀짝으로 접근해 값을 넣어줬고, 만약 전체 노드의 개수가 짝수인 경우 오른쪽 자식이 없으므로 0으로 다시 할당해주는 조건문을 설정했다. change 라는 함수를 통해 부모

🚩 트리(tree) 코드 T = int(input()) def in_order(i): global cnt if i