전체 글
-
Greedy Algorithm알고리즘 2020. 3. 17. 16:04
Greedy Algorithm 탐욕 알고리즘개념 : 최적해를 구하는 데에 사용되는 근사적인 방법. 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. (미래를 생각하지 않고 각 단계에서 최선의 선택을 함)그리디 알고리즘으로 최적의 해를 구할 수 있는 문제가 많지는 않다.그리디 알고리즘이 사용되는 경우 -> 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우 (DP보다 수행시간 훨씬 빠르므로 유용) 예시 문제 ① : 동전 개수 10원, 50원, 100원, 500원짜리 동전들을 이용하여 어떤 금액을 표현하자. 이때 각 동전은 무수히 많은 대신 동전 개수를 최소로 사용해야 한다. 풀이>> 무조건 사용할 수 있는 한..
-
Floyd-Warshall알고리즘 2020. 3. 17. 15:29
그래프에서 정점끼리의 최단 경로를구하는 문제 중다익스트라에 이어 플로이드 워셜 알고리즘에 대해 알아보도록 하자. Floyd-Warshall Algorithm 플로이드 워셜 알고리즘개념 : 모든 정점끼리의 최단 거리를 구하는 알고리즘(다익스트라가 한 정점에서 다른 정점들까지였다면, 플로이드는 모든 정점들을 다 구하는 방법이다.)(각 정점을 시작점으로 다익스트라 알고리즘을 반복하여도 되지만, 플로이드는 단 한번의 시행으로 모든 쌍을 구할 수 있다.)속성 Optimal substructure - 최단 경로의 부분경로는 역시 최단 경로다. (특정 경로 안에 무수히 많은 경로가 있을 때, 중간 정점들이 각각 최단이 된다면 이를 모두 이은 경로 또한 최단이 된다는 개념)작동 방식- 정점(1,2, … , k) 이 있..
-
Dijkstra알고리즘 2020. 3. 17. 15:02
그래프에서 정점끼리의 최단 경로를 구하는 알고리즘에는 다익스트라, 벨만-포드, 플로이드가 존재한다.이번에는 다익스트라에 대해서 알아보도록 한다. Dijkstra algorithm 다익스트라 알고리즘개념 : 하나의 정점에서 다른 모든 정점들의 최단 경로를 구하는 방법구현 방식 : priority queue 사용 (priority queue는 내림차순으로 정렬해줌을 주의)작동 방식첫 정점을 기준으로 연결되있는 정점들을 추가하며, 최단 거리를 갱신한다.(거리를 저장하는 배열의 초기값은 무한대 값으로 저장한다.) 그림 예시 (파란색은 각 정점 사이의 가중치를 뜻한다.)정점이 7개 있을때의 그래프 1을 중심으로 다른 정점들까지의 최단 거리를 구한다고 하면, 거리 배열은이런 모습으로 만들어진다.만약, 다른 정점으로..
-
Binary Serach알고리즘 2020. 3. 16. 20:57
Binary Search 이진탐색순차 탐색 : 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 방법.이진 탐색 : 탐색 범위를 절반씩 줄어가며 값을 찾는 방법. 탐색 전, 배열이 미리 정렬되어 있어야한다. 배열의 크기가 N이라고 할때, 순차탐색 이진탐색 시간복잡도 O(N) O(log N) 탐색 방법 크기가 N인 배열 arr에서, target을 찾는다고 가정 시start = 0, end = N-1 로 초기화 한다.mid = (start + end) / 2 로 초기화 한다.target과 arr[mid]의 값을 비교한다. 값이 같을 시, 탐색을 종료 같지 않을시, target data[mid] 이면 star..
-
자료형잡다한 지식 2020. 3. 16. 20:08
문제를 풀다보면, int 자료형 혹은 float만 사용하는 것이 아닌데 일일히 찾아보기 힘들어서 정리해둔다. 자료형 자료형 크기 범위 char 1Byte, 8bit -128 ~ 127 short 2Byte, 16bit -32,768 ~ 32,767 unsigned short 0 ~ 65,535 int 4Byte, 32bit -2,147,483,648 ~ 2,147,483,647 unsigned int 0 ~ 4,294,967,295 long long 8Byte, 64bit -9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 unsigned long long 0 ~ 18,446,744,073,709,551,615 bool 1Byte, 8bit True or F..
-
DP알고리즘 2020. 3. 16. 19:34
DP (Dynamic Programming) 동적계획법 개념 : 큰 문제를 작은 문제로 나누어서 푸는 문제 작은 문제들을 계산한 값을 여러 번 사용하기 때문에 Memoization (메모이제이션)이 필요하다. Memoization? 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해, 매번 다시 계산하지 않도록 하여 전체적인 실행 속도를 빠르게 하는 기술 → 즉, 계산된 결과를 배열에 저장한 뒤, 다음 계산에서 필요하면 저장된 값을 불러옴. 시간 복잡도가 훨씬 줄어든다. 구현 방식 : Bottom-up 방식과 Top-down 방식 Bottom-up 방식 : 작은 문제부터 계산해 나가는 방식, for문 이용해서 처음 값부터 다음 값을 계산해 나가는 방식 Top-down 방식 : 큰 문제를 풀 ..
-
DFS & BFS알고리즘 2020. 3. 16. 16:50
들어가기 전, 그래프의 탐색이란? 어떤 정점에서 출발하여 그래프의 모든 정점을 방문하는 것 깊이를 우선으로 하는 깊이 우선 탐색과 너비를 우선으로 하는 너비 우선 탐색이 있다. 1. DFS (Depth First Search) 깊이 우선 탐색 개념? 현재 정점에서 이동할 수 있는 점들까지 들어가면서 탐색하는 방법 모든 정점(혹은 노드라고도 부름)를 방문하고자 하는 경우에 사용 다른 정점으로 이동할 수 없을때, 이전 정점으로 돌아가야하므로 거쳐온 정점들을 모두 저장해 주어야 한다. 구현 방법? 스택 또는 재귀함수로 구현, 즉 후입선출(LIFO) 원칙으로 탐색 어떤 정점을 방문했는지의 여부를 반드시 검사해야한다. *검사안할 경우 무한루프에 빠질 수 있다.* (ex) 2. BFS (Breadth Frist S..