Algorithm
-
검색 알고리즘 - 선형 검색Algorithm 2022. 1. 20. 15:56
검색의 종류로는 배열 검색, 연결 리스트 검색, 이진 검색 트리 알고리즘이 있다. 배열 검색의 종류로는 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색을 수행한다. 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색을 수행한다. 해시법 : 추가-삭제가 자주 일어나는 데이터 집합에서 빠른 검색을 수행한다. 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법이다. 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시하는 방법이다. 선형 검색 linear search 가장 기본적인 배열 검색 방법이다. 선형으로 늘어선 배열에서 원하는 Key값을 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘이다. 즉, 선형 검색에서 배열 스캔의 종료 조건은 2가지다. 1. 검색할 값..
-
병합 정렬, 힙 정렬 (파이썬)Algorithm 2021. 6. 22. 21:33
병합 정렬 merge sort 노이만이 고안한 분할 정복 알고리즘. 퀵 정렬과 반대로 안정 정렬에 속한다. 배열을 앞부분과 뒷부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘이다. 과정 i) 리스트의 길이가 0또는 1이면 이미 정렬된 것으로 본다. ii) 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. iii) 각 부분 리스트를 재귀적으로 병합 정렬을 이용해 정렬한다. iv) 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 장점 - 안정적인 정렬 방법 - 레코드를 linked list로 구성하면, 데이터의 이동은 무시할 수 있을 정도로 작아진다. (퀵 정렬을 포함한 다른 정렬 방법보다 효율적이다.) 단점 - 레코드를 배열로 구성하면 임시 ..
-
복잡도Algorithm 2021. 3. 27. 09:34
복잡도 복잡도(complexity)는 알고리즘의 성능을 나타내는 척도다. 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다. 시간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 오래 걸리는지를 의미하고, 공간 복잡도는 특정한 크기의 입력에 대하여 알고리즘이 얼마나 많은 메모리를 차지하는지를 의미한다. 동일한 기능을 수행하는 알고리즘이 있다면 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다. 시간 복잡도 : 알고리즘을 위해 필요한 연산의 횟수 공간 복잡도 : 알고리즘을 위해 필요한 메모리의 양 효율적인 알고리즘을 사용한다고 했을 때 보통 시간 복잡도와 공간 복잡도는 일종의 거래 관계(trade-off)가 성립한다. 메모리를 조금 더 많이 사용하는 대신에 연산을 생략하거나 더 많은 정보를 관리하면서..