알고리즘 1-7주차

데이터분석/CS 기초

알고리즘 1-7주차

neonii 2025. 2. 21. 09:51

728x90

알고리즘: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것
문제를 알고리즘으로 작성하는 과정
특성
- 입력과 출력은 반드시 필요함
- 유한성: 일정한 시간 내에 종료되어야 함 (i.e. 알고리즘 수행이 끝나지 않거나 매우 오래 걸리면 해를 얻을 수 없음)
- 정확성: 주어진 문제에 대한 정확한 출력 값을 만들어야 함
- 일반성: 같은 유형의 문제에 모두 적용 가능해야 함
표현 방법
- 순서도 flow chart: 문제 해결 과정을 기호와 도형을 사용하여 표현
- 의사 코드 pseudocode: 프로그램 명령문 형식을 취하고 각 명령을 사람이 이해하기 쉬운 단어로 나타냄
- 자연어 natural language
성능 평가
- 바람직한 알고리즘은 명확하고 효율적이어야 함
  따라서 알고리즘을 설계하고 나서 이 알고리즘이 자원을 얼마나 소모하는지 분석하는 과정은 중요함
  이때 자원은 소요 시간, 메모리, 통신 대역 등이 될 수 있음
- 성능 측정: 실제 구현 필요, 구체적으로 실행해 시간을 확인
- 성능 분석: 실제 구현 불필요
  - 시간 복잡도
    - 구체적인 실행 시간은 하드웨어, 운영체제, 언어, 컴파일러 등 실행 환경에 따라 달라짐
      따라서 실행 시간을 측정하는 대신 연산의 실행 횟수를 세는 것
      연산의 실행 횟수는 입력 데이터의 크기에 관한 함수로 표현
    - 점근적 분석: 입력 데이터의 크기 n이 무한대로 커질 때의 복잡도를 간단히 표현하기 위해 사용,
      최고차항의 차수 만으로 표시
      - Big-O 표기법: 최악의 경우 worst case analysis
      - Big-Omega 표기법: 최선의 경우 best case analysis
      - Big-Theta 표기법: 최악의 경우와 최선의 경우 모두 적용
  - 공간 복잡도: 메모리가 많이 저렴해져서 공간 복잡도보다는 시간 복잡도가 더 중요함

점화식 Recurrence Relation

점화식: 수열의 특정 항을 이전 항 또는 몇 개의 이전 항을 사용하여 표현한 식
점근적 분석 방법
- 반복 대치 repeated substitution: 더 작은 문제에 대한 함수로 반복해서 대치
- 추정 후 증명: 결론을 추정하고 참이라 가정한 후, 수학적 귀납법을 이용하여 증명
- 마스터 정리: 형식에 맞는 점화식의 복잡도는 복잡한 계산이나 증명 없이 바로 알 수 있음

정렬 알고리즘

내부 정렬: 데이터 양이 적을 때 주기억 장치 내에 저장한 자료를 대상으로 정렬하는 방법
(e.g. 선택 정렬, 버블 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬 등)
외부 정렬: 입력의 크기가 주기억 장치 공간보다 큰 경우, 보조기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어들인 후, 정렬하여 보조기억 장치에 다시 저장하는 과정을 반복

선택 정렬 selection sort

하나의 원소만 남을 때까지 반복: 최대 원소를 찾음 → 최대 원소와 맨 오른쪽 원소를 교환 → 맨 오른쪽 원소를 제외
특징: 입력에 민감하지 않은 input insensitive 알고리즘
(i.e. 입력이 정렬되어 있는 정도와 무관하게 항상 일정한 시간 복잡도를 나타냄)

버블 정렬 bubble sort

이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복

삽입 정렬 insertion sort

새로운 데이터를 정렬된 데이터에 삽입하는 과정을 반복
특징: 입력의 상태에 따라 수행시간이 달라질 수 있음 (i.e. 어느 정도 정렬이 되어있을 때 효과적!)

병합 정렬 merge sort

정렬할 데이터들을 2개로 나누고 각각 정렬한 다음, 다시 합병하여 하나의 정렬된 데이터로 완성하는 방법

쉘 정렬 shell sort

주어진 입력 데이터를 적당한 매개 변수의 값만큼 떨어진 데이터들과 비교하여 교환하는 과정을 반복
임베디드 시스템에서 주로 활용: 메모리와 연산 능력이 제한적인 임베디드 시스템에서 쉘 정렬을 사용하면, 큰 데이터를 한번에 다루지 않아도 되고 각 그룹을 동시에 정렬할 수 있어 병렬 처리가 가능하며 간단한 알고리즘이라 하드웨어 명령어로도 쉽게 실행할 수 있음

퀵 정렬 quick sort

기준 키를 기준으로 작거나 같은 값은 앞으로, 큰 값은 뒤로 가도록 분리하여 정렬
현장에서 가장 많이 쓰는 정렬 알고리즘!

힙 정렬 heap sort

주어진 배열을 힙으로 만든 다음 차례로 하나씩 힙에서 제거
힙 heap: 완전 이진 트리 (i.e. 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 채워져 있음),
각 노드의 값은 자식의 값보다 작거나 같음

기수 정렬 radix sort

제한적인 범위 내에 있는 숫자에 대해서 각 자릿수 별로 정렬하는 알고리즘
기 radix: 특정 진수를 나타내는 숫자들 (e.g. 10진수의 기는 0, 1, ..., 9)
특징: 입력이 모두 k자릿수 이하의 자연수인 특수한 경우에만 사용할 수 있음! 비교 정렬이 아님!
안정성 정렬 stable sort: 값이 같은 원소끼리는 정렬 후에도 원래의 순서가 바뀌지 않는 성질을 가짐

계수 정렬 counting sort

각 데이터가 등장한 횟수를 세서 그 기준으로 정렬하는 방법
특징: 범위 조건이 있는 경우 굉장히 빠른 알고리즘, 비교 정렬이 아님!

정렬 알고리즘 효율성 비교

	worst case	average case
선택 정렬	n^2	n^2
버블 정렬	n^2	n^2
삽입 정렬	n^2	n^2
병합 정렬	nlogn	nlogn
퀵 정렬	n^2	nlogn
힙 정렬	nlogn	nlogn
기수 정렬	n	n
계수 정렬	n	n

탐색 알고리즘

저장 중인 데이터 중에서 원하는 정보를 찾아내는 작업
데이터를 저장하는 효율적인 자료구조가 개발되기 전에는 데이터가 들어오는 대로 쌓는 방법밖에 없었는데, 이는 데이터를 저장하기는 쉽지만 검색은 번거로움
레코드 record: 개체에 대해 수집된 모든 정보를 포함하고 있는 저장 단위
필드 field: 레코드의 각각의 정보를 나타내는 부분
탐색 키 search key: 다른 레코드와 중복되지 않도록 각 레코드를 대표, 하나 이상의 필드로 구성할 수도 있음

순차 탐색 sequential search = 선형 탐색 linear search

첫 번째 데이터부터 차례로 비교
시간 복잡도: O(n), 데이터 정렬 여부와 관계 없이 하나씩 비교해가며 원하는 값을 찾기 때문에 비효율적

자기 구성 순차 탐색 self-organizing sequential search

자주 사용되는 항목을 데이터 집합의 앞쪽에 배치하여 순차 탐색의 검색 효율을 높임
전진 이동법 move to front: 탐색된 항목을 데이터 집합의 가장 앞으로 이동
전위법 transpose: 탐색된 항목을 바로 이전 항목과 교환, 자주 사용될수록 점진적으로 앞쪽으로 이동시키는 것
빈도 계수법 frequency count: 각 항목이 탐색된 횟수를 별도의 공간에 저장해두고 탐색된 횟수가 높은 순으로 데이터 집합을 재구성

이진 탐색 binary search

정렬된 데이터 집합을 이분화하면서 탐색
(i.e. 시작과 끝의 인덱스를 설정하고 그 중간값을 구한 후, 키와 중간값을 계속 비교함. 탐색 키가 중간값보다 작으면 왼쪽, 크면 오른쪽을 탐색함)
시간 복잡도: O(logn)

효율적인 탐색을 위한 자료구조

탐색 트리 search tree

각 노드가 키를 하나씩 가지고 있으며, 이를 통해 레코드의 저장 위치를 파악함
내부 탐색 트리: 메인 메모리에 전체 키를 수용할 수 있어, 탐색 트리가 메인 메모리 내에 존재함
외부 탐색 트리: 메인 메모리가 전체 키를 수용할 수 없어, 탐색 트리가 디스크 등 외부 저장소에 존재함

이진 탐색 트리 binary search tree

이진 트리(왼쪽 자식 < 부모 < 오른쪽 자식)이면서 같은 값을 갖는 노드가 없어야 함
좌우 균형이 잘 맞으면 탐색의 효율이 높음 (i.e. 효율은 트리의 깊이와 밀접한 관련이 있음)
데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적임
- 시간 복잡도: O(h) 이때 h는 트리의 높이, 최악의 경우 (사향이진트리) O(n)
데이터의 탐색
- 루트 노드부터 시작
- 루트 노드와 찾으려는 데이터가 같으면 탐색은 성공적으로 종료됨
  루트 노드가 찾으려는 데이터보다 작으면 루트 노드의 오른쪽 서브 트리를 탐색하고
  루트 노드가 찾으려는 데이터보다 크면 루트 노드의 왼쪽 서브 트리를 탐색해 감
데이터의 삽입
- 탐색에 성공하면 삽입은 실패함, 같은 데이터를 갖는 노드가 있을 수 없기 때문
- 루트 노드부터 시작해 삽입할 데이터가 루트 노드보다 작으면 왼쪽 서브 트리로, 크면 오른쪽 서브 트리로 이동함
데이터의 삭제
- 삭제하고자 하는 노드가 리프 노드인 경우: 그냥 삭제하고자 하는 노드 삭제
- 삭제하고자 하는 노드의 자식 노드가 한 개인 경우: 삭제하고자 하는 노드의 부모가 삭제하고자 하는 노드의 자식을 직접 가리키도록 함
- 삭제하고자 하는 노드의 자식 노드가 두 개인 경우: 삭제하고자 하는 노드의 오른쪽 서브 트리의 최소 원소 노드를 삭제하고, 삭제한 노드를 삭제하고자 하는 노드의 자리에 놓음
- 첫 번째 두 번째는 상수 시간이 들지만, 세 번째는 삭제하고자 하는 노드의 직후 원소를 찾는 데 최악의 경우 트리의 높이에 비례하는 시간이 소요됨

균형 트리 balanced tree

삽입과 삭제 시 필요하면 스스로 균형을 유지함
항상 O(logn)의 탐색 성능, 이때 n은 트리의 원소 개수

레드 블랙 트리

이진 탐색 트리에 균형을 맞추는 기능을 추가한 트리
- 각 노드는 레드나 블랙
- 루트는 블랙
- 모든 리프는 블랙
- 레드 노드는 연속적으로 나타나지 않음
- 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같음
데이터의 탐색: 탐색은 트리의 내용을 건드리지 않으므로, 이진 탐색 트리에서의 탐색과 동일함
데이터의 삽입
- 삽입 후 레드 블랙 특성을 위반하는 경우, 색 변환과 최대 2회의 트리 회전이 필요함
  단번에 해결되거나, 위반 내용이 트리 위쪽으로 이동하게 됨. 최악의 경우 이것이 루트까지 올라가서 루트를 블랙으로 바꿔야만 해결됨. 그래도, 시간 복잡도는 트리의 높이를 초과하지 않기 때문에, 트리의 높이에 비례하는 시간인 O(logn)임
  1. 이진 탐색 트리의 삽입 알고리즘에 따라 삽입한 후, 삽입된 새 노드를 레드로 색칠함
  2. 만일 삽입된 새 노드의 부모 노드가
    - 블랙이라면 아무 문제 없음
    - 레드라면 레드 블랙 특성이 깨짐
      - s가 레드라면
      - s가 블랙이라면

데이터의 삭제
- 삭제 후 레드 블랙 특성을 위반하는 경우, 색 변환과 최대 3회의 트리 회전이 필요함
  1. 이진 탐색 트리의 삭제 알고리즘에 따라 삭제
  2. 만약 삭제된 노드가
    - 레드라면 아무 문제 없음
    - 블랙이라면
      - 위로 올라온 자식 노드가 레드라면 블랙으로 바꾸면 아무 문제 없음
      - 위로 올라온 자식 노드가 블랙이라면 블랙 노드 개수가 한 개 모자라 레드 블랙 특성이 깨짐

B트리

외부 탐색 트리: 디스크에 한 번 접근하는 시간은 수십 만 명령어의 처리 시간과 맞먹기 때문에, 디스크 접근 횟수가 효율을 좌우함
다진 검색 트리: 대용량의 파일을 검색할 수 있도록 하기 위해, 루트를 제외한 모든 노드가 k/2개 이상 k개 이하의 key를 가짐
- key가 k개 있으면 k+1개의 자식을 가짐
- 모든 리프 노드는 같은 깊이를 가짐
데이터의 탐색: key는 정렬된 상태로 저장되어 있으므로, 찾으려는 데이터 값과 비교하여 데이터가 포함된 범위를 결정함
(e.g. key가 10, 20, 30인 경우 내가 찾는 값이 25라면 20과 30 사이의 자식 노드로 내려감)
데이터의 삽입
1. x를 삽입할 리프 노드 r을 찾음
2. 노드 r에 공간의 여유가 있으면 key를 삽입하고 끝
  노드 r에 공간의 여유가 없다면 형제 노드를 살핌
3. 형제 노드에 공간의 여유가 있다면 형제 노드에 key를 하나 넘긴 후 삽입하고 끝
  형제 노드에 공간의 여유가 없다면 가운데 key를 부모 노드로 넘기고 노드를 두 개로 분리
데이터의 삭제
1. x를 key로 가지고 있는 노드를 찾음
2. 노드가 리프 노드가 아니라면 x의 직후 원소 y를 가진 리프 노드 r을 찾아 x와 y를 바꿈
3. 리프 노드에서 x를 제거
4. x 제거 후 노드에 underflow가 발생하면 우선 key를 가져올 수 있는 형제 노드가 있는지 확인
5. key를 가져올 형제 노드가 있다면 가져다 채우고 끝
  그렇지 않다면 형제 노드와 병합

해시 테이블

저장된 자료와 비교하여 자리를 찾지 않고 단 한 번의 계산으로 자리를 찾음 (i.e. 원소가 저장될 자리가 원소의 값에 의해 결정됨)
- 삽입과 삭제가 빈번한 자료에 적합함
- 최소 원소를 찾는 것과 같은 작업은 지원하지 않음
시간 복잡도: 평균 O(1), 매우 빠른 응답을 요하는 응용에 유용
해싱 hashing: 해시 함수를 이용해 레코드가 저장되어 있는 주소를 직접 구하는 것, 계산된 값은 해시 값 또는 해시 주소라고 함
해시 테이블 hash table: 레코드를 한 개 이상 보관하는 버킷들의 집합
- 해시 테이블에 원소가 차 있는 비율인 적재율은 해시 테이블 성능에 매우 중요한 영향을 미침
해시 함수 hash function: 하나의 문자열을 보다 빨리 찾을 수 있도록 주소에 직접 접근할 수 있는 짧은 길이의 값이나 키로 변환하는 알고리즘을 수식으로 표현한 것
- 입력 원소가 해시 테이블에 골고루 저장될 수 있도록 해야 함 (i.e. 서로 다른 두 원소가 한 주소를 놓고 충돌할 확률이 낮아짐)
- 계산이 간단해야 함
- 가장 대표적인 방법:
  - 나누기 방법 division method: h(x) = x mod (해시 테이블 사이즈)
  - 곱하기 방법 multiplication method: h(x) = (xA mod 1) * (해시 테이블 사이즈), 이때 A는 0<A<1인 상수
  - 중간 제곱법 mid-square: 키 값을 제곱한 후에 그 결과의 중간에 있는 적당한 수의 비트를 취하여 버켓 주소로 하는 것
  - 접지법 folding: 종이를 접듯이 숫자를 접어 일정한 크기 이하의 수로 만드는 방법
    - shift folding: 최하위 비트가 일치하도록 맞추고 더하는 방법
    - folding at the boundary: 각 부분을 종이 접듯이 경계에서 겹친 다음 같은 자리에 위치한 수들을 더하는 방법

728x90