▣ Dynamic-Programming(동적계획법): 동적계획법이랑 복잡한 문제를 여러 sub-problem으로 나누어 해결하는 방법이다. ->어떻게? 해당 sub-problem의 solution들을 Table(여분의 저장공간을 필요하게 된다.)에 기록 함으로써 중복계산을 피하는 방법. 장점: 중복계산을 피하기 때문에 시간적 이점을 얻을 수 있습니다.단점: 추가적인 메모리공간을 필요로 합니다. (시간과 메모리의 trade-off) example) 피보나치 함수의 계산피보나치 함수는 Fib(n) = Fib(n-1)+Fib(n-2)(Fib(0)=1, Fib(1)=1)로 정의 할 수 있습니다.원하고자 하는 피보나치 값을 계산하기 위해서는 위 그림과같은 과정을 수행하게 되며, 보다시피 여러번의 중복계산이 되어지..
03)BFS[Breadth-First Search, 너비 우선탐색]
▣Breadth-First Search(너비우선탐색) : 그래프의 모든정점을 방문하는 알고리즘 중 하나이다. -> 탐색의 기준 : 자신과 인접한 모든 간선을 우선적으로 검사하며, 그 중 visit하지 않은 정점을 찾아 순차적으로 visit해 나아간다. : 더이상 visit할 정점이 없을 때 까지 반복한다. : 인전한 간선을 우선적으로 검사하기 위하여 Queue를 이용하여 준다. 현재 visit한 정점에 인접한 모든 정점을 우선적으로 수행하기 위하여 큐에 넣어준다.example)1을 visit 하면서 인접한 정점인 2, 3 그리고 7을 큐에 넣어준다.그리고 큐에 들어간 순서대로 visit하면 반복 수행해 준다.(큐의 상태가 empty가 될 때까지 반복 됨을 알 수 있다.) Tip) BFS는 pop된 ver..
02)DFS[Depth-First Search, 깊이 우선탐색]
▣Depth-First Search(깊이우선탐색) : 그래프의 모든정점을 방문하는 알고리즘 중 하나이다. -> 탐색의 기준 : 자신과 인접한 간선을 검사하여 visit하지 않은 정점을 찾아 visit해 나아간다. : 더이상 visit할 정점이 없을 때 까지 반복한다. 1번 정점에서 시작하여 2->3->5->7->6의 순서로 visit 가능한 정점까지 진행한다.진행이 끝나면 다른 정점이 있는 곳까지 빠져나온 후 기존의 과정을 반복한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#include#i..
Queue
정의 : 먼저 넣은 데이터를 먼저 처리하는 FIFO(First In First Out)의 자료구조(일반적인 우선순위 큐에서 key값이 들어온 시간 순이라고 생각하면 우선순위 큐의 특별 케이스라고 볼 수 있다.) 큐의 형태 - (Queue size : 5)- 선형 큐 : 크기가 제한되어 있어 Out처리가 되었을 시 자료를 한 칸씩 앞으로 이동해야하는 단점이 존재 ->보다시피 배열의 크기가 정해져 있기 때문에 pop한 공간은 사용이 불가하며, 만약 사용하고 싶을 시에는 별도의 내부 value값을 옮겨주는 작업이 필요로 한다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556..