algorithm

탐욕법(Greedy)

탐욕법은 말그대로 탐욕적으로 눈앞에 보이는 상황에서 가장 좋은 상황(최선의 선택)을 고르는 것을 말한다. 탐욕법은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다고 한다. 탐욕법 사용 가능 조건 Local minimum과 Global minimum이 같을 경우 sub-problem의 solution으로 큰 problem의 solution을 구할 수 있을 경우 ( 동적계획법과 동일) Problem들의 solution들이 서로 영향을 주면 안된다 탐욕법 예제 탐욕법의 가장 대표적인 예시는 coin change이다 예를 들어 760원을 [10,50,100,500]의 동전으로 주는데 동전을 최소로 주는 방법을 구하는 것이다. 이 때는 가장 큰 500원 부터 차례..

해쉬(Hash)

해쉬 테이블은 key-value system을 이용하여 자료를 정리하는 구조이다. 이 구조는 사전과 같은 의미라고 볼 수 있다. 만약 사전에서 단어를 찾는다면 해당 단어를 찾고 그 단어의 해석을 확인할 것이다. 이 때 해당 단어가 key이고, 단어의 해설이 value이다. 해쉬 테이블을 사용하는 이유는 무엇일까? 바로 효율성 때문이다. 아래는 배열과 해쉬에서 하나의 데이터를 찾는 과정이다. 배열 위에서 보이는 배열에서 원하는 메뉴를 찾는다고 가정하자. 만약 pizza의 가격을 찾는다면 위에서부터 선형 탐색(Linear Search)을 진행한다. 이렇게 선형 탐색을 하게되면 매우 시간이 오래 걸리게 된다. 해쉬 테이블 위 해쉬 테이블에서 같은 pizza의 가격을 찾는다면 간단하게 pizza를 호출하면 된다..

BFS/DFS(Breadth/Depth First Search)

BFS와 DFS는 그래프를 그려 그래프 안을 돌아다니며 알맞는 경우를 찾을 때 사용되는 알고리즘이다. 이 알고리즘들은 하나의 저장장소와 visited 저장 장소를 이용하여 그래프의 규칙을 찾게 된다. BFS BFS는 Breadth Frist Search의 약자로 말 그대로 너비 우선 탐색을 하는 알고리즘이다. BFS는 Queue를 사용하여 경우의 수를 저장한다. 해당 queue에서 shift를 이용하여 얕은 깊이의 요소들을 우선적으로 계산을 진행한다. 이를 통하여 시작 지점에서 너비 우선적으로 반환하는 프로그램을 작성할 수 있다. 아래 그림을 보자 A지점에서 BFS 방식으로 Graph Traversals을 해보자 BFS는 queue에 저장을 하며 경우가 완료 되면 pop을 해주고, 방문하거나 접촉한 배열..

동적계획법(Dynamic Programming)

동적 계획법이란? 하나의 문제는 단 한 번만 풀도록 하는 알고리즘입니다. 일반적으로 상당수 분할 정복 기법은 동일한 문제를 다시 푼다는 단점을 가지고 있습니다. 단순 분할 정복으로 풀게 되면 심각한 비효율성을 낳는 대표적인 예시로는 피보나치 수열이 있습니다. 동적 계획법을 사용할 수 있는 조건 Problem가 더 작은 sub-problem으로 쪼개질 경우 이 작은 sub-problem의 solution으로 큰 problem의 solution을 구할 수 있을 경우 sub-problem이 겹칠 경우 피보나치 수열 위 공식에서 Fn은 Fn-1과 Fn-2로 쪼개지면서 조건 1을 만족시킨다. 그리고 fn-1과 fn-2로 fn의 값을 구할 수 있으므로 조건 2를 만족시킨다. 마지막으로 중복의 fn을 가지므로 조건 ..