폐관코딩

신장트리 신장 트리(spanning tree)란 그래프내의 모든 정점을 포함하는 트리다. 신장 트리는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 한다. 그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재 가능하다. 싸이클이 없는 무방향 그래프 최소 비용 신장 트리 최소 비용 신장 트리는 신장 트리 중에서 사용된 간선들의 가중치 합이 최소인 신장 트리를 말한다. 최소 비용 신장 트리를 구하는 방법으로는 Kruskal과 Prim이 제안한 알고리즘이 대표적으로 사용되고 있으며, 이 알고리즘들은 최소 비용 신장 트리가 간선의 가중치의 합이 최소이어야 하고, 반드시 (n-1)개의 간선만 사용해야 하며, 사이클이 포함되어서는 안 된다는 조..

이진검색트리란? 이진트리이면서 각 노드에 하나의 키(데이터)를 가지고있으며 임의의 노드v에 대하여 왼쪽 부트리에 있는 키들은 key[v] 보다 작고 오른쪽부트리에 있는 값은 크거나 같다. dynamic set 을 효과적으로 지원하기위한 자료구조(search, insert, delete) 예컨대 이진탐색의 경우 탐색에 소요되는 계산복잡성은 𝑂(log𝑛)O(log⁡n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. 연결리스트의 경우 자료 입력, 삭제에 필요한 계산복잡성은 𝑂(1)로 효율적이지만 탐색하는 데에는 𝑂(𝑛)의 계산복잡성이 발생. 두 마리 토끼를 잡아보자는 것이 이진탐색트리의 목적. 이진탐색트리를 순회할 때는 중위순회(inorder) 방식을 씁니다. (왼쪽 서브트리-노드-오른쪽 서브트리 순으로 순회..

분할정복 기법 + 메모이제이션으로 푸는 알고리즘 작은 문제들을 풀다보면 같은 문제들을 반복해서 풀 수 있고, 그 문제들은 매번 재계산 하는것이 아닌 따로 값을 저장해 두었다가 재사용하는 기법. 예를들어 피보나치 수열을 들 수 있다. 위와 같은 점화식의 피보나치 수열은 n이 1보다 클 경우 자신의 이전 항 들의 값으로 이루어짐. f(5)를 구하기 위해선 f(5) = f(4) + f(3) f(4) = f(3) + f(2) f(3) = f(2) + f(1) f(2) = 1 f(1) = 0 위 처럼 f(1) = 2 f(2) = 3 f(3) = 3 f(4) = 2 f(5) = 1 위처럼 중복해서 계산이 필요하고 이는 숫자가 커질수록 더 많은 연산을 필요로하며 '지수 시간 시간복잡도'를 발생 정해진 시간안에 문제해..

탐욕적 기법(Greedy Algorithm), 이 기법은 항상 눈앞의 가장 큰 이익만을 쫒는 방법이다. 그리디 알고리즘의 가장 큰 특징은 문제의 성질이 동일하게 보존되고, 그로 인해 같은 전략을 반복적으로 실행 할 수 있는 것이다. 그리디의 대표적인 문제는 동전문제, 도시락 문제가있다. 예로 500원, 100원, 50원, 10원의 동전을 이용하여 가장 적은 갯수의 동전을 구하는 알고리즘이 대표적인 그리디문제인데 이는 각 동전이 배수라는 성질이 보존되기에 가능한 문제이다. 만약 60원, 50원,10원의 동전으로 220원을 표현할 때 그리디알고리즘으로 풀고자 60원 3개, 10원 4개로 생각하여 7개를 사용한다면, 50원4개, 10원 2개를 사용한 6개보다 많이 쓴 것으로 틀린 답이 된다. 예제로 백준의 알..

모든 문제를 푸는 데 있어서 가장 쉽고 간단한 방법. 완전탐색, 브루트포스(Brute-force)는 가능한 경우를 일일이 다 탐색하는것. 절대 틀릴 일은 없는 강력한 방식이지만, 당연히 시간은 최대로 들어간다. 따라서 알고리즘에 잘 나오진 않지만 기본이 되기 때문에 알아보자 예제는 백준알고리즘 2798번 블랙잭문제 문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다. 한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다. 김정인 버전의 블랙잭에서 각 카드에는 양의 정수가 쓰여 있다. 그 다음, 딜러는 N장의 카드를 모두 숫..

1. 언어 : python 2. 참고할 만한 사이트 : 백준, 알고스팟, 프로그래머스, 유튜브, 등. 3. 공부 순서 브루투포스(완전 탐색) 그리디알고리즘(탐욕법) DFS(깊이우선) BFS(너비우선) 분할 정복 큐 스택 다이나믹 프로그래밍 (초급) 이분 탐색 다이나믹 프로그래밍 (중급) 다익스트라 벨만 포드 플로이드 최소 스패닝 트리 세그먼트 트리(탑-다운) 인덱스 트리(바텀-업) 팬윅트리 LCA(Lowest Common Ancestor) 비트마스크 서로소 집합그리디알고리즘(탐욕법)