알고리즘
1.[알고리즘] BFS
탐색을 할때 너비를 우선으로 하여 탐색하는 알고리즘이다.특히나 맹목적인 탐색을 하고자 할때 사용할 수 있다.최단경로를 찾고 싶을 때 사용한다.Queue를 사용하면 쉽게 찾을 수 있다.BFS를 수행하는 과정을 보자간략하게 말하자면, queue에서 pop한 수의 가장 가까
2.[알고리즘]DFS
DFS(Depth First Search, 깊이 우선 탐색) 탐색할때 깊은 것을 우선적으로 하여 탐색 맹목적으로 각 노드를 탐색할 때 이용 stack 사용 사실은 재귀만으로도 구현 가능 DFS는 다음과 같은 알고리즘에 의해 구현된다. 스택의 최상단 노드를 확
3.[알고리즘]합집합 찾기(Union-find)
합집합 찾기는 대표적인 그래프 알고리즘이다. 서로소 집합 알고리즘이라고 부르기도 한다. 구체적으로는 여러 개의 노드가 존재할 때 두 개의 노드를 선택해서 현재 이 노드가 서로 같은 그래프에 속하는지 판별하는 알고리즘 이다.예를 들어 설명해보면,1부터 8까지의 노드가 있
4.[알고리즘]크루스칼 알고리즘
크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다.즉, 최소 비용 신장 트리를 만들기 위한 알고리즘 이라고 할 수 있다.실제로, 여러개의 도시(노드)가 있을때 가장 적은 비용으로 도로를 연결하고자 할때 적용하는 알고리즘이다.노드 =
5.재귀함수 이해하기
처음에 c를 공부할때 재귀에 대해 이해하기가 매우 힘들었다.어떤 구조로 왜 작동하는지에 대해 이해하지 못했다.처음 접하는 분들을 위해 이해하기 쉽게 자세하게 설명해 보겠다.재귀함수의 정의는 정의 단계에서 자신을 재참조하는 함수를 뜻한다.예를들어물론 이런 함수는 없지만
6.Asymptotic Notations[알고리즘]
Asymptotic Notations는 알고리즘의 running time을 설명하기 위해 사용한다.예를들어, bubble sort에서는 이미 정렬되어 있을경우에는 best case 이지만거꾸로 정렬되어 있다면, worst case이다.정렬도 되어있지 않고, 거꾸로 되어
7.[알고리즘]Factorial
f(n) = n!Def: n! = 123...(n-1)(n) for $n \\ge 1$ and 0! = 1F(n)=n\*F(n-1) for n$\\ge$1; //recursive caseF(0)=1//terminae caseinput size: nbasic operat
8.[알고리즘] 하노이 퍼즐
9.[알고리즘]BinarySearch
✍️size가 n인 정렬된 array S에서 K가 있는지 찾기sorted array S0..,n-1 , key kk >= 0S=10,12,13,14,18,20,25 and k=18먼저 S를 반으로 쪼갠다.key인 18은 14보다 크므로 14보다 큰 곳의 배열만 찾으면
10.[알고리즘]MergeSort
Merge가 어떻게 이루어지는지 그림으로 보자.3,10,23,54,1,5,25,75 다음과 같은 배열이 있다.배열을 반으로 나눈다.반으로 나눈 배열을 저장할 임시 배열 A를 만든다.B와C를 비교해서 더 작은 수인 1을 A에 채운후 C의 인덱스는 1증가시킨다. B를 x
11.[알고리즘]Quicksort
그림으로 보자.1.pivot(4)을 정한다.(보통 가장 왼쪽의 인덱스)2.pivot을 제외한 인덱스들중 가장 오른쪽 인덱스에서 부터 왼쪽으로 오면서 pivot보다 작은값 하나와, 가장왼쪽 인덱스로부터 오른쪽으로 가면서 pivot보다 큰 인덱스를 교환해준다.(위 그림에서
12.[알고리즘]Floyd's Alogrithm
예를들어, 목적지까지 바로가는 항공편이 없다. 무조건 경유를 해야한다.이때 가장 빠른길로 목적지까지 가는 방법은??이럴때, 쓸 수 있는게 Floyd's algorithm이다.그래프에서 vertices를 도시, edge는 거리라고 둔다.path는 그래프에서 인접한 ver
13.[알고리즘] Optimal Binary Search Tree(OBST)
보통 OBST(Optimal Binary Search Tree)는 사전에서 단어를 찾을때 많이 사용된다.검색을 할때는 루트 노드부터 시작해서 재귀함수를 호출하면서 아래로 내려가기 때문에, 검색할 대상이 아래쪽에 있을수록 함수 호출을 해야 하는 횟수가 늘어난다. 위 그림
14.[알고리즘]branch and bound
W=16인 이 트리구조가 어떻게 나온건지 알아보자.먼저 value값은 실제적으로 넣은 값을 넣어준다. 반면 bound 값은 현재 노드 상황에서 Item들을 쪼갤 수는 없지만 무게에 맞춰 쪼개서까지 가방에 넣을수 있다고 했을때의 최대 가치 값이다. 이걸 기억하면서 접근
15.Depth First Search
DFS(Depth First Search)는 말 그대로 깊이 우선 탐색이다.바로 예시를 보자.위와 같은 순서로 노드를 탐색한다.구현 방식은 다음과 같다.어떤 문제에서 DFS를 사용하면 좋을지 백준에 나와 있는 문제를 보자.백준 2606번 링크정답 1번 컴퓨터가 바이러스