욤미의 개발일지

컴퓨터는 연산 속도에 한계가 있고 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 이러한 문제를 해결하기 위해서는 연산 속도와 메모리 공간을최대한 활용할 수 있는 효율적인 알고리즘을 작성해야 한다. ＊ 해결하기 어려운 문제에 대해서 깊게 다루는 분야로는 P-NP 문제를 다루는 계산 복잡도 이론이 있다. 다이나믹 프로그래밍(동적 계획법) 메모리를 약간 더 사용하여 수행 시간 효율성을 비약적으로 향상시키는 대표적인 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일방적으로 두가지 방식(탑다운-하향식과 보텀업-상향식)으로 구성된다. 일반적인 프로그래밍 분야에서의 동적 할당(Dynamic All..

탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘 순차 탐색(Seqeuntial Search) 기본적인 탐색 방법으로 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법 보통 정렬되지 않은 리스트에서 데이터를 찾아야할 때 사용(정렬 여부와 상관없이 가장 앞에서 부터 비 데이터가 아무리 많아도 시간만 충분하면 항상 원하는 원소(데이터)를 찾을 수 있다. 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메소드도 내부에서는 순차탐색이 수행된다. 데이터 개수가 N개 일 때 최대 N번의 비교 연산 수행 → 시간 복잡도 O(N) 이진 탐색(Binary Search) 배열의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘 탐색 범위를 반으로 좁혀..

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯 하여 붙여진 명칭 동작 과정 크게 보면 뒤에서 부터 앞으로 정렬을 해나가는 구조이기 때문에 후반으로 갈수록 정렬 범위가 하나씩 줄어든다. 가장 큰 값을 맨 뒤로 먼저 보낸다. 마지막 요소는 정렬이 끝났기 때문에 한개를 제외하고 그 앞에만 다시 정렬 이 과정을 반복하여 정렬한다. 시간 복잡도 먼저 반복문을 통해 모든 인덱스에 접근해야 하기 때문에 O(N)을 시간을 소모하며, 하나의 루프에서는 인접한 값들의 대소 비교 와 자리 교환를 위해서 O(N)을 시간이 필요하다. (n-1) + (n-2) + (n-3) + .... + 2 + 1 = n(n-1) / 2이..

4. 계수 정렬 특정 조건이 부합할 때만 사용할 수 있지만 매우 빠른 정렬 알고리즘 이다. 모든 데이터가 양의 정수일 때, 데이터의 개수가 N 데이터 중 최댓값이 K일 때, 계수 정렬은 최악의 경우에도 수행 시간 O(K+N)을 보장한다. 계수 정렬은 데이터의 크기가 제한되어 있을 때에 한해서 데이터 개수가 많더라도 매우 빠르게 동작하며 원리 또한 간단하다. 다만, 계수 정렬은 '데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때'만 사용할 수 있다. 계수 정렬이 효과적인 경우 일반적으로 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000을 넘지 않을 때 c.f) 0 이상 100 이하인 성적 데이터를 정렬할 때 계수 정렬을 사용할 수 없는 경우 데이터의 값이 무한한 범위를 가질 수 있..

3. 퀵 정렬 기준을 설정하고 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다. 정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이다. 책 에서는 다루지 않지만 퀵 정렬만큼 빠른 알고리즘으로 병합 정렬이 있다. 이 두 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이기도 하다. 특징 큰 숫자와 작은 숫자를 교환할때, 교환하기 위한 기준을 피벗(Pivot)이라고 한다. 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지 미리 명시해야한다. 피벗을 설정하고 리스트를 분할하는 방법에 따라서 여러 가지 방식으로 퀵 정렬을 구분한다. 여기서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 설명한다. 동작 예시 - 호어 분..

2. 삽입 정렬 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입 하는 정렬 알고리즘 선택 정렬에 비해 구현 난이도가 높지만, 일반적으로 더 효율적으로 동작한다. (선택 정렬에 비해 실행 시간 측면에서 더 효율적) 선택 정렬은 현재 데이터 상태와는 상관없이 무조건 모든 원소를 비교하고 위치를 바꾸는 반면, 삽입 정렬은 필요할 때만 위치를 바꾸므로 '데이터가 거의 정렬 되어 있을 때' 훨씬 효율적이다. 특징 특정한 데이터가 적절한 위치에 들어가기 이전에 그 앞까지의 데이터는 이미 정렬되어 있다고 가정한다. 정렬되어 있는 데이터 리스트에서 적절한 위치를 찾은 뒤에, 그 위치에 삽입된다. 두 번째 데이터부터 시작한다. 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단. 동작 예시 초기 데이터: 7 5 9..