알고리즘 개념
-
[알고리즘 개념] 그래프알고리즘 공부/알고리즘 개념 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번의 비교로 데이터를 찾을 수 있다. 찾으려는 데이터와 중간 값을 비교하여 찾으려는 값이 중앙 값보다 작으면 왼쪽 데이터를 선택, 크다면 오른쪽 데이터를 선택하는 과정을 반복하며 데이터를 탐색한다. (중앙값) > (찾는 값) : 중앙 값 기준으로 왼쪽(작은 부분)을 탐색 (중앙값) < (찾는 값) : 중앙 값 기준으로 오른쪽(큰 부분)을 탐색 성능 이진 탐색의 성능을 계산해 보면 아..
-
[알고리즘 개념] 해시 알고리즘알고리즘 공부 2020. 8. 28. 21:27
해시 함수 어떤 길이의 데이터를 입력해도 정해진 길이의 결과를 주는 함수 여기서 정해진 길이는 256 bits로 input의 길이에 관계없이 output의 길이는 일정하다. 해시 함수의 특징 - 데이터의 입력의 길이에 제한이 없다 - 결과는 정해진 256bits의 길이를 가진다 - 결과값이 중복될 가능성이 거의 없다 - 결과값을 가지고 입력값을 유추할 수 없다 해시 알고리즘 크기가 U인 테이블 T를 생성하고 key k를 slot h(k)에 저장하는 방식이다. 이때 key의 중복은 없어야 한다. key k가 slot h(k)로 해쉬 되었다고 하며 h(k)를 key k의 해쉬 값이라고 부르고, h()가 해쉬 함수이다. slot의 크기는 무한하지 않기 때문에 h(k)의 값이 중복되어 나타날 수 있다. 이 경우..
-
[알고리즘 개념] 탐욕 알고리즘알고리즘 공부/알고리즘 개념 2020. 8. 16. 18:52
탐욕 알고리즘 탐욕 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다. 즉, 동적 프로그래밍을 보완하는 알고리즘인 것이다. 탐욕 알고리즘은 각 단계에서 조건에 맞는 최선의 선택을 하는 기법이다. 그렇기 때문에 모든 문제에 대해서 탐욕 알고리즘이 통하지 않는다. 예를 들면, 지금 선택하면 1개의 마시멜로우를 받고, 1분을 기다리면 2개의 마시멜로우를 준다고 했을 때 탐욕 알고리즘은 1개의 마시멜로우를 받는 선택을 내린다. 따라서 어떤 문제가 탐욕 알고리즘이 통하는지 잘 판단하여야 한다. 탐욕 알고리즘은 다음과 같은 과정을 거친다. 1. 해 선택 : 현재 가장 최적인 해를 구하여, 이를 부분해 집합에 추가한다. 2. 적절성 검사 : 새로운 부분해 집합이 적절한..