여행자의 책

https://algospot.com/judge/problem/read/TRAVERSAL algospot.com :: TRAVERSAL 트리 순회 순서 변경 문제 정보 문제 트리를 순회하는 알고리즘은 트리의 모든 노드들을 특정 순서에 맞춰 방문하지만, 트리는 배열처럼 1차원적인 구조가 아니기 때문에 단 한 가지의 당연한 algospot.com import sys input = sys.stdin.readline def get_sub_tree(root, inorder): root_idx = inorder.index(root) left_tree = inorder[:root_idx] right_tree = inorder[root_idx + 1:] return root_idx, left_tree, right_tr..

https://www.acmicpc.net/problem/2842 2842번: 집배원 한상덕 상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 www.acmicpc.net 1. 풀이 사용한 알고리즘은 bfs + 투포인터 이다. 먼저 주어진 지역의 고도 행렬을 중복이 없은 1차원 리스트로 만들어 준 후에 오름차순 정렬해준다. 이 리스트를 heights라고 하겠다. 이후에 초기값이 0인 left, right를 지정해놓고 포인터 값을 변경해가며 heights를 이용해 bfs를 시행하면 되는데 구체적인 로직은 다음과 같다. heights[left:righ..

배열의 부분합을 구할 떄 사용하는 자료구조 일반적인 for으로 구현하면 N이 리스트의 길이일떄 O(N)의 시간복잡도로 계산 가능하지만 세그먼트 트리를 사용하면 O(logN)으로 가능하다. 초기화 과정 O(logN) 출력 O(logN). 세그먼트 트리는 크게 두가지 함수가 존재한다. 하나는 주어진 정수 리스트를 바탕으로 세그먼트 트리를 만드는 init함수와 만든 세그먼트 트리를 이용해 특정 구간합을 반환하는 query함수이다. 구체적인 구현은 아래와 같다. 세그먼트 트리는 이진 트리로 루트, 왼쪽자식, 오른쪽 자식으로 구성되어있다. 한편 세그먼트 트리를 구성하는 leaf 노드를 제외한 모든 정점의 값은 해당 정점을 중심으로 왼쪽 자식과 오른쪽 자식으로 합이고 리프노드의 자리에는 주어진 정수 리스트의 값이 ..

나이브한 방식의 최소 공통 조상 찾기 def solution(N, tree, v1, v2): level = [0 for i in range(N+1)] parent = [0 for i in range(N+1)] visited = [0 for i in range(N+1)] def dfs(here, depth): visited[here] = True level[here] = depth for there in tree[here]: if not visited[there]: parent[there] = here dfs(there, depth+1) root = 1 #root 1로 가정 dfs(root, 1) def LCA(v1, v2): """ v1, v2의 공통조상을 찾아주는 알고리즘 """ #같은 레벨로 만들어 ..

무작정 큐에 집어넣는게 능사가 아니고 어떤 조건에서 넣어야하는지 항상 판단할 것. 이렇게 풀면 언어의 한계로 통과되지 않음. 아래 다른 분이 푸신 것을 참고해서 풀 것 https://rebas.kr/799 BOJ 16933 · 벽 부수고 이동하기 3 알고리즘 분류 : BFS 벽 부수고 이동하기 시리즈 세 번째 문제이다. 이번에는 이동할 때 낮과 밤이 매번 바뀌고, 낮에만 벽을 부술 수 있다. BOJ 14442번 '벽 부수고 이동하기 2' 문제에서 낮과 밤 설 rebas.kr import sys from collections import deque def solution(): """ 이 풀이가 틀린 풀이는 아니지만 언어의 한계로 시간초과가 난다.""" input = sys.stdin.readline N, ..

2021.07.13 - [Algorithm/프로그래머스] - [프로그래머스, 2021 카카오 인턴쉽] 표 편집 python 2021.07.13 - [Algorithm/프로그래머스] - [프로그래머스, 2021 카카오 인턴쉽] 거리두기 확인하기 python https://programmers.co.kr/learn/courses/30/lessons/81304 코딩테스트 연습 - 미로 탈출 4 1 4 [[1, 2, 1], [3, 2, 1], [2, 4, 1]] [2, 3] 4 programmers.co.kr 미친 문제.. 애초에 못 풀었을 기본은 다익스트라로 시작점으로부터 도착점까지 최단거리를 찾는 문제지만 함정 방문 여부에 따라 달라지는 경우의 수를 구분해야하는 문제이다. 그래프 탐색 방법에는 매번 두 종류..

import sys """ 내가 두명의 부하 직원에게 연락하라고 시키면 결과적으로 총 걸리는 시간은 둘 중에 가장 큰 값 """ def solution(): input = sys.stdin.readline #입력받는 부분 N = int(input()) bose_info = list(map(int, input().split())) #트리로 만들어 준다. tree = [[] for _ in range(N)] for me, bose in enumerate(bose_info): if bose != -1: tree[bose].append(me) #dp[i] : i번째 노드를 루트로 하는 서브트리에 뉴스를 전달하는데 필요한 최대 시간 dp = [0 for i in range(N)] def dfs(here): tem..

import sys sys.setrecursionlimit(1000000) def solution(): input = sys.stdin.readline N = int(input()) #wolves[i] : i번째 섬에 있는 늑대 수 wolves =[0 for _ in range(N+1)] #sheeps[i] : i번쨰 섬에 있는 양의 수= sheeps = {i:0 for i in range(1, N+1)} #트리 tree =[[] for _ in range(N+1)] for i in range(2, N+1): t, a, p = input().split() a = int(a) p = int(p) if t == "W": wolves[i] = a else: sheeps[i] = a tree[p].append(..

import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def solution(): n = int(input()) # 노드 100,000개는 log_2(100,000) = 16.xxx # 16개 색깔로 색칠 가능하다. # dp[i][color] : i번째 노드를 color로 색칠했을 때 최소값 dp = [[0] * 16 for i in range(n)] #방문 여부를 체크해준다. visit = [False for i in range(n)] #인접 리스트로 트리의 간선을 기록해준다. tree = [[] for i in range(n)] for i in range(n - 1): a, b = map(int, input().split()) tree..

1. 버블 알고리즘 def buble_sort(arr): N = len(arr) for i in range(N): for j in range(i+1, N): if arr[i] > arr[j]: arr[i], arr[j] = arr[j], arr[i] return arr 2. 병합 정렬 알고리즘 def merge_sort(arr): N = len(arr) if N < 2: return arr mid = N // 2 left, right = arr[:mid], arr[:mid] left_arr = merge_sort[:mid] right_arr = merger_sort[mid:] result = [] l = r = 0 while l < len(left_arr) and h < len(right_arr): if..