본문 바로가기

ComputerScience/Algorithm

 (21)
Matroid Theory Definition 1.1 (Walk) Given a graph $G$, a walk in $G$ is a finite sequence of edges of the form $v_0,v_1,...,v_m$ where $v_i$ is a vertex of $G$. If the edges in the walk is distinct, then it is a trail. If the vertices in the walk is distinct, then the trail is a path. (except $v_0 = v_m$) Definition 1.2 (Closed Path) If $v_0=v_m$ in a path, then it is a closed path which is know as a cycle De..
Dynammic Programming Memoization vs Tabulation memoization은 top-down이며 필요한 subprobelm 만 풀지만, function call로 인한 overhead 가 발생한다. Tabulation는 bottom-up이며, recursion 에 수반되는 overhead가 없다 DP 예시 피보나치 수열 동일한 피보나치 수를 2번 계산하지 않도록 한다. recursion 만으로 풀 경우 동일한 피보나치 수를 2번 이상 계산하는 경우가 생긴다. 따라서 계산한 값을 저장해 둔다. (Memoization) 피보나치의 경우 bottom up 방식으로 풀어도 된다(bottom up 도 dp) 이항 계수 : nCk nCk = n-1Ck + n-1Ck-1 Rod Cutting Problem rod의 길이와 ..
[leetcode] 53. Maximum Subarray Maximum Subarray - LeetCode Maximum Subarray - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제설명 배열이 주어졌을 때 subarray 중에 최대 합을 구하는 문제이다. 풀이 1. 시간 복잡도 O(NlogN) 풀이 : Divide and Conque 배열의 가운데 원소를 중심으로 왼쪽 배열과 오른쪽 배열을 생각해보자. 이 때 생각해 볼 수 있는 maximum subarrya의 형태는 왼쪽 배열에만 있거나 오른쪽 배열에만 있..
[leetcode] 96. Unique Binary Trees Unique Binary Search Trees - LeetCode Unique Binary Search Trees - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제설명 노드의 갯수가 주어졌을 때 만들 수 있는 Binary Search Tree 의 갯수를 구하는 문제이다 풀이 Catalan Number에 대해 들어봤었다면 이 문제를 쉽게 풀 수 있었을 것이다. 조합론에서 나오는 개념인데, 아래와 같은 수식으로 표현된다 $$C_n=\Sigma^{n-1}_0 ..
[leetcode] 847. Shortest Path Visiting All Nodes leetcode.com/problems/shortest-path-visiting-all-nodes/ Shortest Path Visiting All Nodes - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 문제 An undirected, connected graph of N nodes (labeled 0, 1, 2, ..., N-1) is given as graph. graph.length = N, and j != i is in the list graph[i..
[leet code] Cheapest Flights Within K Stops Cheapest Flights Within K Stops - LeetCode There are n cities connected by m flights. Each flight starts from city u and arrives at v with a price w. Now given all the cities and flights, together with starting city src and the destination dst, your task is to find the cheapest price from src to dst with up to k stops. If there is no such route, output -1 . 문제 해석 출발지하고 도착점이 주어졌을 때 최대 k개의 정점들 지나서..
Quick sort,selection 정리(2) Quick Sort 분할 정복 기법 예시 시간 복잡도가 최악의 경우가 될 때를 생각해본다. 주어진 배열 [5,4,3,2,1] 을 작은 순으로 정렬한다. pivot은 배열의 마지막 원소로 설정한다 1번째 iteration : 1의 왼쪽인 5,4,3,2를 1과 비교한다. 결과 ⇒ 1의 왼쪽에는 원소가 없게 되고 오른 쪽에는 [5,4,3,2] 가 된다. ⇒[1,5,4,3,2] 2번째 iteration : 2를 피봇으로 [5,4,3,2]를 정렬한다. 결과 ⇒ 2의 왼쪽에는 원소가 없게 되고, 오른 쪽에는 [5,4,3]이 된다. ⇒ [1,2,5,4,3] 이런 식을 반복하다 보면 [1,2,3,4,5]가 얻어지고, 시간 복잡도는 O(N^2)이 된다. Quick Selection 목표 배열 내에서 K번 째로 큰 혹은 ..
Huffman Coding 문자를 인코딩할 때, 고정된 길이로 압축하는 것보다 가변길이를 선택하는 것이 좋다. 많이 등장하는 문자는 짧게, 적게 등장하는 문자는 길게 인코딩하면 압축률이 좋아질 것이다. 하지만 가변길이를 선택할 경우, 디코딩 할 때, 문제가 없도록 인코딩 규칙을 짜야된다. 즉, 어떤 인코딩된 코드도 다른 인코딩된 코드의 prefix가 되면 안된다. 1. Huffman Encoding huffman coding은 가장 작은 frequency의 문자들을 합쳐가면서 이진트리를 만드는 방식이다. huffman coding 방식에 따르면 가장 압축률이 좋은 인코딩 방식을 얻을 수 있다. 수학적 귀납법에 의해 증명이 가능하다. Proof) 2. Run Length Encoding AAABBAA => 3A2B2A 로 인코딩된다..

티스토리툴바