알고리즘

경북대 COMP0319 강의 기반의 정리Introduction to algorithms 참고알고리즘은 대부분의 컴퓨터학부/학과에서 전공 필수로 설정되거나 전공 필수가 아니더라도 IT업계에 취직하기 위해 혹은 개발자가 되기 위해서 '알고리즘(algorithm)'을 필수적

경북대 COMP0319 강의 기반의 정리Introduction to algorithms 3판 참고지난 시간에 이어 알고리즘의 효율성(efficiency of algorithm)에 대해 알아보자. 알고리즘의 효율성을 따지기 위해서 알고리즘을 분석해봐야 한다. 이 과정을

**경북대 COMP0319 강의 기반의 정리 Introduction to algorithms 3판 참고** Order or Growth 지난 시간에 정렬 문제를 해결하기 위해 삽입 정렬과 병합 정렬, 2개를 알아보았다. 삽입 정렬은 최악의 경우 $an^2 + bn + c$의 계산시간이, 병합 정렬은 $c1n \log n + c2n$임을 알아보았다. 병합 ...

https://youtu.be/-bm0-k7UeV8?si=cuHxR9QIKvfeizLI주니온 교수님의 강의 정리본.알고리즘의 복잡도 분석을 complexity analysis라고 한다.알고리즘의 시간 복잡도라는 것은 입력 크기 $n$에 따른 단위 연산의 수행

**경북대 COMP0319 강의 기반의 정리 Introduction to algorithms 3판 참고** Introduction 알고리즘은 문제의 크기 $n$에 의존적이라고 배웠다. 즉, $n$의 크기에 따라 알고리즘의 연산 횟수가 달라진다. 점근적 표기법으로 wo

dynamic programming은 divide-and-conquer와 같이 특정한 알고리즘이 아니라 기법이다. DP는 복잡한 문제를 재귀적인 문제로 간단한 subproblems로 나누어 해결하는 기법인데, 정의만 보았을 때는 divide-and-conquer와 동일

두 행렬의 곱은 다음과 같은 수도 코드로 계산된다는 것은 당연한 사실이다. 그런데 만약 행렬이 여러 개인 경우, 최적의 연산 횟수는 어떻게 될까? 두 행렬을 곱하는 연산 횟수를 단순히 곱한 것으로 동일할까? 만약 행렬의 크기가 제각각이라면 그렇지 않다.만약 $n$개의

두 개의 수열 $X, Y$가 주어진다. 수열 $X=\\langle x_1, \\cdots, x_m\\rangle$로 정의되고, $Y=\\langle y_1, \\cdots, y_n\\rangle$로 정의하자. 우리가 구해야하는 것은 "subsequence common

지난 시간에 동적 프로그래밍(DP)를 통해 optimal substructure가 있는 최적화 문제(optimizaiton problem)를 어떻게 효율적으로 풀 수 있는지를 배웠다. 완전 탐색(brutue force)이 가장 간단한 방법이지만, 시간 복잡도가 대부분

이전에 activity selection 문제를 풀기 위해 어떻게 풀었는지 복습해보자. 1\. optimal substurcture를 찾는다.2\. recursive solution을 어떻게 구하는지 구한다.3\. 하나의 subproblem을 풀 때, greedy ch

그래프를 표현하는 방법과 그래프를 검색하는 방법에 대해 알아보자. 그래프를 검색한다는 것은 그래프의 모든 정점을 방문하는 것으로, 효율적으로 방문하기 위한 지나가야하는 간선을 찾아야한다. 그래프를 표현하는 가장 일반적인 2가지 방법은 인접 리스트와 인접 행렬이 있고,

사이클이 존재하지 않는 방향 그래프의 위상정렬을 수행하기 위해 DFS가 사용된다. 사이클이 존재하지 않는 방향 그래프(directed acyclic graph)를 “dag”라고 하자. dag $G = (V, E)$의 위상 정렬은 그래프의 모든 vertex에 대한 선형적

우리는 앞에서 최적화 문제(optimization problem) 알고리즘들을 배웠었다. 그 중 Greedy Technique를 배웠는데, 일련의 step을 진행하며, 각 step마다 greedy한 선택을 하며 문제를 해결하는 것이었다. 만약 greedy choice

Introduction shortest-paths problem은 지도 상에 두 지점 사이의 최단 거리를 찾는 문제이다. 이때 input으로는 방향 그래프(directed graph)와 가중치 함수(weight function)가 주어진다. $$ \text{Direct

한 점에서 다른 점으로 가는 최소 경로를 찾기 위해 방향 그래프로 지도를 모델링할 수 있었다. 방향 그래프로 모델링할 수 있는 것은 이뿐만 아니라 flow network로도 모델링 가능하다. 예를 들면 어떤 물질이 source로부터 흘러들어와서 sink로 빠져나가는 배

Ford-Fulkerson Method(포드-풀커슨 방법)은 3가지 중요 아이디어에 의존한다. 앞에서 배운 잔여 네트워크(residual network) / 증강 경로(augmenting path) / cut이다. 이 3가지 개념은 Max-flow Min-cut 정리에

이때까지 flow network의 maximum flow를 구하는 방법과 핵심 아이디어가 되는 포드-풀커슨 방법과 이를 구현한 알고리즘인 에드몬드-카프 알고리즘을 배웠다. 이번에는 이를 이용해 이분 그래프(bipartite graph)가 무엇인지 배워보고 maximum

앞에서 배운 대부분의 알고리즘은 polynomial time algorithm이다. input으로 주어지는 문제의 크기가 $n$이라면, worst case에서 $O(n^k)$의 시간이 걸리는 알고리즘이다. 세상에 존재하는 모든 문제들은 polynomial time al