1. 문제 2357번: 최솟값과 최댓값 (acmicpc.net) 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 이번엔 임의의 구간의 최솟값과 최댓값을 구하는 문제 2. 풀이 구간합이나 구간곱과 큰 차이 없긴한데 query 함수 구할때 조금 신경써야할듯 create_segment함수에는 왼쪽 자식과 오른쪽 자식의 최솟값과 최댓값을 저장해야함 최솟값 구하는 트리와 최댓값 구하는 트리 함수를 따로 만들수도 있지만... 그냥 인자 method를 받아서 method가 0이면 최솟..
1. 문제 11505번: 구간 곱 구하기 (acmicpc.net) 11505번: 구간 곱 구하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 곱을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 특정 구간의 합을 구하라는 것에서 특정 구간의 곱을 구하는 것으로 바뀜 근데 구간의 합을 구하는 것에서 몇가지 살짝? 신경써야함 2. 풀이 기본적으로 트리의 노드에 왼쪽 자식과 오른쪽 자식의 합을 저장하던 것을 왼쪽 자식과 오른쪽 자식의 곱을 저장하는 것으로 바꾸면 된다 tree[tree_index] = tree[2*tree_index]..
1. 개요 가중치가 있는 무방향 그래프에서 최소 신장 트리를 찾는 대표적인 알고리즘 중 하나이다. 크루스칼 알고리즘이 간선들을 선택해가면서 최소 신장 트리를 구성하는 반면에 프림 알고리즘은 정점을 선택하고, 인접한 정점 중에서 최소 비용을 가지는 간선을 하나씩 선택해가면서 최소 신장 트리를 구성하는 일종의 그리디 알고리즘이다. 다익스트라 알고리즘과 사실상 동일한 알고리즘이다. 참고로 다익스트라 알고리즘은 음수 가중치에서는 동작하지 않지만, 프림 알고리즘은 음수 가중치에서도 동작한다고 한다 2. 알고리즘 2-1) 임의의 정점을 하나 선택해서 최초의 트리를 구성 2-2) 선택한 정점과 트리에 포함된 정점들과 인접한 정점중 최소 비용의 간선이 존재하는 정점을 선택한다 2-3) 모든 정점이 선택될 때까지 위 과..
1. 신장트리(spanning tree) n개의 정점으로 이루어진 "무방향 그래프"에서 n개의 정점과 n-1개의 간선으로 이루어진 트리 하나의 그래프가 있을때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 이때, 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건이다. 그래서 이러한 그래프를 신장 트리라고 부른다. 위와 같은 그래프에서 신장 트리는 여러개 찾을 수 있다. 예를 들어 아래와 같은 그래프는 하나의 신장 트리이다. 하지만 다음 그림과 같은 그래프들은 신장 트리가 아니다. 구체적으로 다음은 노드 1을 포함하고 있지 않다 다음은 노드 4-6-7에서 사이클이 발생하므로 신장트리가 아니다. 2. 최소 신장 트리(Minimum spanning tree)..
1. 힙(heap) 프로그램 실행중에 내가 사용할 수 있는 메모리 양이 변할 수 있는 경우, 그 때 사용하는 메모리 공간을 힙이라고도 하는데.. 여기서는 자료구조를 말한다. 기본적으로 "완전 이진 트리"를 이용한 자료구조이다. 특히 "완전 이진 트리"에 있는 노드 중에서 키값이 가장 큰 노드나 가장 작은 노드를 찾기 위해 특별히 만든 자료구조 완전 이진 트리니까, n개의 노드가 주어진다면 길이 n+1의 단순 배열로 저장할 수 있다 처음에 만들때, 키값이 가장 큰 노드를 찾는 자료구조를 만들 것이냐, 키값이 가장 작은 노드를 찾는 자료구조를 만들 것이냐,를 정하고 들어간다. 2. 최대힙(max heap)과 최소힙(min heap) 2-1) 최대힙(max heap) 키값이 가장 큰 노드를 찾기 위한 완전 이..
1. 완전이진트리 기본 순회 3가지 다음과 같은 완전이진트리에서 전위순회, 중위순회, 후위순회를 구해본다면..? ##노드 번호로 순회함수 정의 ##완전이진트리의 왼쪽 자식은 2*v ##오른쪽 자식은 2*v+1 ##전위순회 def preorder(v): if v
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
