알고리즘 공부/알고리즘 개념
-
[알고리즘 개념] 그래프알고리즘 공부/알고리즘 개념 2020. 9. 1. 19:40
그래프 정점(노드)와 간선(엣지)로 이루어진 자료구조 간선의 방향 유무에 따라 단방향 그래프와 무방향 그래프로 나뉜다. 그래프의 표현 인접 행렬 그래프 : 모든 정점에 대해 연결 유무를 표시한다. 직관적이며 쉽게 구현이 가능하지만, 불필요한 정보의 저장이 많으며 메모리 차지가 크다 인접 리스트 그래프 : 간선이 존재하는 곳만 표시한다. 필요한 정보만 저장하기 때문에 메모리 차지는 적지만, 구현이 어렵다. 그래프 탐색 BFS/DFS https://validming99.tistory.com/74 [알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS) 그래프 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종이다. G = (V,E) 세 가지 그림 모두 그래프이다. 트..
-
[알고리즘 개념] 이분 탐색 (Binary Search)알고리즘 공부/알고리즘 개념 2020. 9. 1. 15:20
이진 탐색 탐색이란 원하는 데이터를 배열 내에서 찾는 것이다. 이진 탐색은 정렬된 배열을 전제로 탐색하는 방법으로 한 번 비교할 때마다 절반의 데이터를 제외시킨다. 이러한 방법으로 엄청난 속도로 탐색을 완료할 수 있다. 예를 들어 70억 개의 데이터에 대해 순차 탐색은 평균적으로 35억 번을 비교하지만, 이진 탐색은 최대 33번의 비교로 데이터를 찾을 수 있다. 찾으려는 데이터와 중간 값을 비교하여 찾으려는 값이 중앙 값보다 작으면 왼쪽 데이터를 선택, 크다면 오른쪽 데이터를 선택하는 과정을 반복하며 데이터를 탐색한다. (중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색 (중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색 성능 이진 탐색의 성능을 계산해 보면 아..
-
[알고리즘 개념] 깊이 우선 탐색(DFS)와 너비우선 탐색(BFS)알고리즘 공부/알고리즘 개념 2020. 8. 25. 12:03
그래프 정점(node)과 그 정점을 연결하는 간선(edge)으로 이루어진 자료구조의 일종이다. G = (V,E) 세 가지 그림 모두 그래프이다. 트리 또한 그래프 중 하나이며 정점과 간선의 관계에 따라 세부적으로 구분할 수 있다. 그래프 탐색 그래프를 탐색한다는 것은 하나의 정점으로부터 시작해 차례대로 모든 정점들을 한 번씩 방문하는 것이다. 깊이 우선 탐색과 너비 우선 탐색은 그래프를 탐색하는 방법 중 하나이다. 깊이 우선 탐색 : DFS (Depth-First Search) 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 옆으로 이동. 루트 노드에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방식을 말한다. 모든 노드를 방문하고자 하는 경우 깊이 우선 탐색이 적합하다..
-
[알고리즘 개념] 동적계획법알고리즘 공부/알고리즘 개념 2020. 8. 22. 17:54
동적 계획법 영어로 하면 Dynamic Programming이다. 큰 문제를 작은 문제로 나누어 푸는 문제를 일컬어 동저계획법이라고 한다. 이 점에서 분할 정복과 비슷하지만, 가장 큰 차이점은 동적 계획법에서는 쪼개진 작은 문제가 중복되지만, 분할 정복은 절대로 중복될 수가 없다는 점이다. 따라서 동적 계획법은 작은 문제의 결과를 저장해둔다. 이미 계산한 값을 저장해 두는 메모리를 캐시라고 하며 같은 문제가 다시 등장하였을 때 이를 이용하여 문제 해결 속도를 향상할 수 있다. 조건 작은 문제의 반복이 일어나는 경우. 단, 이 작은 문제의 결과는 같아야 한다. 즉, 어떤 문제가 여러 개의 부분 문제로 쪼개어질 수 있어야 하며 이 부분 문제는 같은 부분 문제이거나 재귀 알고리즘을 통해 해결되어야 한다. 피보..
-
[알고리즘 개념] 탐욕 알고리즘알고리즘 공부/알고리즘 개념 2020. 8. 16. 18:52
탐욕 알고리즘 탐욕 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 즉, 동적 프로그래밍을 보완하는 알고리즘인 것이다. 탐욕 알고리즘은 각 단계에서 조건에 맞는 최선의 선택을 하는 기법이다. 그렇기 때문에 모든 문제에 대해서 탐욕 알고리즘이 통하지 않는다. 예를 들면, 지금 선택하면 1개의 마시멜로우를 받고, 1분을 기다리면 2개의 마시멜로우를 준다고 했을 때 탐욕 알고리즘은 1개의 마시멜로우를 받는 선택을 내린다. 따라서 어떤 문제가 탐욕 알고리즘이 통하는지 잘 판단하여야 한다. 탐욕 알고리즘은 다음과 같은 과정을 거친다. 1. 해 선택 : 현재 가장 최적인 해를 구하여, 이를 부분해 집합에 추가한다. 2. 적절성 검사 : 새로운 부분해 집합이 적절한..
-
[알고리즘 개념] 완전 탐색알고리즘 공부/알고리즘 개념 2020. 8. 14. 19:51
완전 탐색 컴퓨터의 순기능을 이용하여, 모든 경우의 수를 탐색하는 방법이다. 모든 경우를 살펴보기 때문에 무조건 답을 찾을 수 있다는 장점이 있지만, 답을 찾는데 시간이 효율적이지 못하다는 단점이 있다. 따라서, 탐색할 요소가 적거나 N제한이 작은 경우에 완전 탐색을 사용한다. 구현 방법 1. 반복문 이용 - for문과 if문을 이용하여 코드를 작성한다. 재귀를 이용하는 것보다 코드 작성이 쉽지만, 중첩이 많이 일어난다는 단점이 있다. for(int i = 0 ; i < n ; i++) for(int j = i + 1; j < n; j++) for(int k = j + 1; k < n; k++) for(int l = k + 1; l < n; l++) cout
-
[알고리즘 개념] 힙 (heap)알고리즘 공부/알고리즘 개념 2020. 8. 11. 15:55
이진트리 : 모든 노드의 자식 노드가 2개 이하인 트리 구조 완전 이진트리 이진트리와 다르게 데이터가 루트 노드부터 시작하여 자식 노드가 왼쪽, 오른쪽 자식 노드 순서로 쌓이게 되는 트리를 말한다. 이진트리는 중간에 노드가 비어있을 수 있지만, 완전 이진 트리는 중간 노드가 비어있을 수 없는 형태이다. 힙 힙은 최대 힙과 최소 힙이 있다. 최대 힙은 구성하는 모든 노드가 '부모 노드가 자식 노드보다 크다'라는 규칙을 가진 것이다. 최소 힙은 반대로 구성하는 모든 노드에 대해 부모 노드가 자식 노드보다 작다는 규칙을 가진 것이다. 따라서 힙의 루트는 최댓값이나 최솟값이다. 따라서 힙은 최댓값과 최솟값을 쉽게 찾을 수 있는 자료 구조이다. 배열의 인덱스를 활용하여 자식 노드와 부모 노드를 찾기 쉽기 때문에 ..
-
[알고리즘 개념] 스택/큐알고리즘 공부/알고리즘 개념 2020. 8. 9. 12:07
스택 그림을 보면 알 수 있듯, 스택은 LIFO(Last In Frist Out) 후입 선출 구조이다. 즉, 밑이 막힌 구조로 마지막으로 넣은 것이 먼저 나온다는 것이다. 쉽게 생각하면 쌓아 올린 접시를 생각하면 된다. 실생활에서는 컴퓨터의 뒤로 가기 기능이 스택을 이용하여 구현되었다. 페이지 뒤로 가기, 실행 취소 (Ctrl + Z)와 같은 기능은 스택의 대표 예제이다. 데이터를 삽입할 때는 push 데이터를 삭제할 때는 pop이라는 용어를 사용한다. 스택에서는 마지막 데이터 위치를 기억하기 위해 top이라는 변수를 사용하여 구현하게 된다. 스택 구현은 배열과 연결 리스트를 통해 구현할 수 있다. 배열의 장점은 구현이 쉽고, 원하는 데이터의 접근 속도가 빠르다는 것이다. 하지만, 배열의 크기가 정해져 ..