알고리즘 기말 준비

대학교 알고리즘 강의 수업 자료를 바탕으로 정리한 글이다.

자료 구조, 알고리즘, 정렬, 객체 지향 등을 다룬다.

알고리즘

방법을 말한다.
컴퓨터 분야나 수학 등 관련 분야에서 어떤 문제를 해결하기 위해 정해진 일련의 절차 또는

알고리즘의 특징

• 정확성: 주어진 입력에 대해 올바른 해를 주어야 한다.
• 수행성: 각 단계는 컴퓨터에서 실행 가능해야 한다.
• 유한성: 일정한 시간 내에 종료되어야 한다.
• 효율성: 효율적일수록 그 가치가 높다.

자료 구조

것이다.
컴퓨터 분야에서 효율적으로 접근하고 수정할 수 있도록 자료를 구성, 관리 저장하는

단순 자료 구조

• 정수
• 실수
• 문자
• 문자열

선형 자료 구조

• 리스트
• 스택
• 큐
  선형 자료 구조에 대해 간단하게 정리한 글을 참고할 수도 있다.

비선형 자료 구조

• 트리
• 그래프

파일 자료 구조

• 순차 파일
• 직접 파일
• 색인 파일

순차 파일이란?

처리 순서에 따라 연속해서 저장한다.
연속되어 있기 때문에 추가 및 삭제할 때 시간이 오래 걸린다는 단점이 있다.

직접 파일이란?

파일 내용을 임의의 물리적 위치에 기록해 저장한다.
임의의 물리적 위치는 해시 함수를 활용해 구한다.

색인 파일이란?

순차 파일과 직접 파일의 결합된 형태를 말한다.

유클리드 최대 공약수

1. 두 수 (a, b)가 있다. (이때 a > b)
2. ((a-b), b)를 계산한다. ((두 수를 뺀 값), (둘 중 작은 수))
3. 0이 나올 때까지 반복한다.

예시

1. (8, 2)
2. ((8-2), 2) => (6, 2)
3. ((6-2), 2) => (4, 2)
4. ((4-2), 2) => (2, 2)
5. (2-2), 2) => (2, 0)
6. 8과 2의 최대 공약 수는 2이다.

알고리즘 분류

문제 해결 방식에 따른 분류

• 분할 정복 알고리즘
• 그리디 알고리즘
• 동적 계획 알고리즘
• 근사 알고리즘
• 백트래킹 알고리즘
• 분기 한정 알고리즘

문제에 기반한 알고리즘

• 정렬 알고리즘
• 그래프 알고리즘
• 기하 알고리즘

특정 환경에 따른 분류

• 병렬 알고리즘
• 분산 알고리즘
• 양자 알고리즘

시간 복잡도

최악 경우 분석

‘어떤 입력이 주어지더라도 알고리즘의 수행시간이 얼마 이상은 넘지 않는다‘라는
상한(Upper Bound)의 의미이다.

최선 경우 분석

가장 빠른 수행시간을 분석하며, 최적(Optimal) 알고리즘을 찾는데 활용된다.

평균 경우 분석

입력의 확률 분포를 가정하여 분석하는데, 일반적으로 균등분포(Uniform Distribution)를
가정하는 데 사용된다.

상각 분석

일련의 연산을 수행하여 총 연산 횟수를 합하고 이를 연산 횟수로 나누어 수행시간을 분석

O(Big-Oh)-표기

최악 경우를 의미한다.

Ω(Big-Omega)-표기

최선 경우를 의미한다.

Θ(Theta)-표기

상각 분석을 의미한다.

UML (Unified Modeling Language)

• 시각화 언어이다.
• 명세화 언어이다.
• 구축 언어이다.
• 문서화 언어이다.

객체 지향

자료 구조를 기반으로 객체를 설계한 뒤, 그들의 흐름을 설계하는 것을 뜻한다.

객체 지향의 기본 요소

• 객체: 현실에 존재하는 물리적인 요소이다.
• 클래스: 객체를 생성할 수 있는 개념적인 틀로, 클래스 자체로는 뭘 할 수 없다.
• 메시지: 생성된 객체 간의 상호작용 수단이 된다.

주요 개념

추상화

• 특정 측면을 강조한 것이다.
• 클래스를 이용하여 추상 모델을 만들 수 있다.

실체화

• 추상화된 모델을 구현하는 것이다.

캡슐화

• 데이터와 처리 담당 오퍼레이션이 묶이는 것이다.
• 캡슐화를 통해 정보 은닉이 가능하고, 독립성과 유지보수성이 증가한다.

상속

• 프로그램 확장을 돕는다.
• 정보를 공개하여 재사용할 수 있게 한다.
• 상세화: 상위 클래스의 속성을 상속 받아 하위 클래스에서 실체화하는 개념이다.
• 일반화: 하위 클래스들의 공통 속성을 추상화해 상위 클래스로 정의하는 개념이다.

다형성

• 이름은 같지만 다른 동작을 하는 함수들이다.
• 메서드 오버라이징 방식으로 구현된다.

추상 클래스

• 클래스의 명칭과 메서드는 있으나, 메서드의 처리 내용은 없는 것을 말한다.
• 상속을 통해 메서드를 구현할 수 있다.
• 추상 클래스는 추상 메서드의 일반적인 속성, 메서드를 가질 수 있다.
• 메서드의 다형성을 지원한다.

인터페이스

• 상수와 추상 메서드만 가진다.
• 다중 상속 기능을 제공한다.
• 추상 클래스와 달리, 속성을 소유할 수 없다.
• 메서드를 구현할 수 없다.

모델링

• 시스템을 구축하는 과정에서 개발자가 하는 모든 일과 과정을 뜻한다.

모델

• 모델링의 결과물이다.

모델링 방법

부치 방법론

설계 중심의 모델링 방법이다.

야콥슨의 OOSE

유스케이스를 강조한 모델링 방법으로, 행위자와의 상호작용과 요구사항을 강조한다.

럼바의 OMT(Object Modeling T echnique)

하나의 시스템을 기술하기 위해 객체 모델, 동적 모델, 기능 모델 세 가지를 사용한다.

UML

부치 방법론, OOSE, OMT를 결합한 형태의 모델링 방법이다.

사물

정적 사물

개념적, 물리적 요소를 표현하는 명사이다.

• 클래스: 동일 속성, 오퍼레이션, 관계, 의미를 공유하는 객체를 기술한다.
• 인터페이스: 클래스, 컴포넌트 서비스를 명세화하는 오퍼레이션의 모음이다.
• 통신: 서로 다른 요소와 역할이 모여 교류를 정의한다.
• 컴포넌트: 전체 시스템을 구성하는 단위이다.
• 패키지: 요소를 그룹으로 묶은 것이다. (컴포넌트는 물리적, 패키지는 개념적 존재)
• 노드: 실행할 때 존재하는 물리적 요소를 뜻한다.

동적 사물

모델의 동적인 부분을 동사로 묘사한다.

• 교류: 객체 간 주고 받는 메시지로 구성된 동작이다.
• 유스케이스: 시스템이 수행하는 활동을 순차적으로 기술한 것이다.
• 상태 머신: 외부 이벤트에 대한 객체의 상태와 변화 순서를 기술한 것이다.

주해 사물

모델링에 참여하지 않는 사물이다.

• 노트: 주석 또는 제약을 서술한 것을 의미한다.

관계

연관 관계

객체 사이의 연결 관계를 표현한다.

• 이름: 연관 관계의 의미를 설명한다.
• 역할: 연관 관계에서의 객체의 역할을 설명한다.
• 다중성: 한 객체에 몇 개의 객체가 연결되었는지를 설명한다.
• 집합 연관: 전체쪽 객체 하나가 부분쪽 객체를 소유한다.

의존 관계

두 사물 간의 의미적 관계를 표현한다.
한 사물의 명세에 따라 변경되기도 한다.
항상 반대되는 개념끼리 의존 관계이지는 않는다.

일반화 관계

일반화된 사물과 좀 더 특수화된 사물 사이의 관계를 표현한다.
예시: 버스와 택시, 트럭은 모두 자동차의 종류이다.

실체화 관계

한 객체가 다른 객체에게 오퍼레이션을 수행하도록 하는 관계이다.
예시: TV와 리모컨

다이어그램

• 클래스 다이어그램: 클래스, 인터페이스, 통신과 함께 그들의 관계를 표현한다.
• 컴포넌트 다이어그램: 컴포넌트 사이의 구성 및 의존을 표현한다.
• 배치 다이어그램: 실행 시 처리하는 노드와 그 노드에 있는 컴포넌트의 구성을
  표현한다.
• 유스케이스 다이어그램: 유스케이스와 액터의 관계를 구조적으로 표현한다.
• 순차/통신 다이어그램: 교류 다이어그램의 일종이다.
• 활동 다이어그램: 시스템 내부의 활동 흐름을 표현한다.
• 상태 다이어그램: 시스템의 동적 뷰를 표현한다.

UML 뷰

유스케이스 뷰 (요구사항 뷰)

시스템 기능의 요구사항을 정의, 표현한다.

설계 뷰 (분석)

프로세스 뷰 (설계)

구현 뷰 (설계)

배치 뷰 (설계)

분할 정복 알고리즘

주어진 문제를 부분 문제로 분할한 뒤, 부분 해를 구하여 취합을 통해 전체 문제를 해결하는
알고리즘이다.
문제가 a개로 분할되고, 부분 문제의 크기가 1/b로 감소하는 알고리즘이다.

• a = b = 2: 합병 정렬, 최근접 점의 쌍 찾기, 공제선 문제
• a = 3, b = 2 && a = 4, b = 2: 큰 정수의 곱셈
• a = 7, b = 2: 스토라센의 행렬 곱셈 알고리즘
• 문제가 2개로 분할, 부분 문제의 크기가 일정하지 않음: 퀵 정렬
• 문제가 2개로 분할, 부분 문제 1개가 의미 없음: 이진 탐색
• 문제가 2개로 분할, 부분 문제 1개가 의미 없고, 크기가 일정하지 않음: 선택 문제
• 부분 문제의 크기가 1, 2개씩 감소: 삽입 정렬, 피보나치의 수 계산

합병 정렬

문제가 2개로 분할되고 크기가 1/2로 감소하는 정렬 알고리즘이다.
메모리와 공간 차지가 단점이다.
퀵 정렬, 힙 정렬보다 효율적이다.
응용: 정렬 알고리즘의 병렬화 수행
복잡도

• 시간 복잡도: O(n log n)
• 공간 복잡도: O(n)

퀵 정렬

배열의 수 중 하나를 피봇으로 지정하여 정렬을 수행하는 정렬 알고리즘이다.

• 배열의 수 중 하나를 피봇으로 지정한다.
• 피봇보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 이동시킨다.
• 이동한 왼쪽 배열, 오른쪽 배열에서 다시 피봇을 각각 지정하여 이동을 수행한다.
  (재귀적 수행)
• 모든 배열이 이동하면, 모든 배열을 취합하여 정렬을 마무리한다.
  복잡도
• 최선, 평균: O(n log n)
• 최악: O(n^2)
  부분 문제의 크기가 작아지면 삽입 정렬 사용을 통해 성능을 향상시킬 수 있다.
  퀵 정렬은 그 크기가 클수록 효율적이다.
  응용: 특정 유전자를 빠르게 찾는 데에 접미 배열과 함께 사용

선택 문제

k번째로 작은 수를 찾는 문제이다.
간단하게 요약 설명하면 퀵정렬을 하다가 원하는 k번째 수를 찾으면 그만 두는 것이다.
퀵 정렬은 중간 값에 가까운 값을 피봇으로 선정할수록 좋다. (good 분할)

최근접 점의 쌍 찾기

• x좌표로 정렬 / 반으로 나눠서 비교한다.
• 나눠진 부분끼리도 확인이 필요하다. (나눠진 점의 쌍이 최근접일 수도)
  응용: 컴퓨터 그래픽스 및 비전, 지리 정보, 분자 모델링, 마케팅

피보나치 수

• f(0) = 0
• f(1) = 1
• f(n) = f(n-1) + f(n-2)

분할 정복 주의사항

• 분할 + 취합 둘 다 중요하다.
• 분할이 항상 효율적인 알고리즘을 위한 정답은 아니다.

그리디 알고리즘

욕심내어 최대/최소의 값만 선택하는 알고리즘이다.

동전 거스름돈 문제

거스름돈으로 줘야 하는 최소한의 동전 개수를 구하는 문제이다.
단위가 가장 큰 동전부터 줄 수 있는 최대한의 개수를 준다.

최소 신장 트리

반복되는 사이클 없이 연결된 점들의 가중치 합이 최소인 트리를 구하는 알고리즘이다.
알파벳으로 구성된 점과 점끼리 연결하는 선분의 가중치의 합을 최소로 구한다.
크루스칼 알고리즘과 프림 알고리즘, 두 가지 방법으로 구할 수 있다.

크루스칼 알고리즘

1. 현재 표시된 가중치 중 가장 낮은 가중치를 고른다.
2. 그 다음으로 낮은 가중치를 가진 선분을 찾아 고른다.
3. 이때, 동일한 가중치를 가진 선분이 있다면 알파벳 순으로 선택한다.
4. 또한 선택한 선분 때문에 사이클이 생성되는 경우, 선택하지 않고 넘어간다.
5. 사이클 없이 모든 점을 연결한다.

프림 알고리즘

1. 랜덤한 점을 선택한다.
2. 선택한 점을 방문한 점 집합에 추가한다.
3. 방문한 점들에서 연결된 간선 중 가중치가 가장 낮은 간섬을 선택한다.
4. 선택한 간선이 아직 방문하지 않은 점과 연결되어 있다면, 그 정점을 방문한 점
   집합에 추가한다.
5. 모든 정점을 연결할 때까지 반복하여 연결한다.

크루스칼 VS 프림

1. 크루스칼과 달리 프림은 랜덤한 위치(점)에서 시작할 수 있다.
2. 크루스칼과 달리 프림은 사이클 검사가 필요없다.
3. 크루스칼은 간선 중심이지만, 프림은 정점 중심이다.

최단 경로 찾기

다익스트라(Dijkstra) 최단 경로 알고리즘을 사용한다.
현재 위치한 점에서 가장 가까운 다른 점을 골라 선택한다.

• 프림은 방문했던 모든 점에서 각 가까운 점을 고르지만, 다익스트라는 현재 위치한
  점에서만 고려한다.
  시간 복잡도: O(n^2)
  응용: 지도 서비스, 네비게이션, 네트워크, 통신, 교통 공학

부분 배낭 문제

가장 가치가 높게 짐을 넣는 문제이다.

• 가치 / 무게로 나눈 값을 기준으로 높은 것부터 최대로 가방에 넣는다.

집합 커버 문제

응용: 도시 계획, 경비 시스템, 컴퓨터 바이러스 찾기

작업 스케줄링

응용: 강의실 배정, 공장 가동 등

허프만 압축

빈도수가 높은 문자부터 이진수로 구성된 값을 할당하여 용량을 줄이는 알고리즘이다.

동적 계획 알고리즘

플로이드

모든 길을 계산하여 간단하다.

다익스트라

현재 점에서 계산한다.

응용

지도, 내비게이션, 네트워크 통신

동적 계획에서의 동전 거스름돈 문제

줘야되는 거스름돈이 20원인데 만약 16원짜리 동전이 있다면?

그리디 알고리즘

가장 큰 단위부터 최대로 가지기 때문에 16원 1개와 1원 4개로 총 5개의 동전을 줘야한다.

동적 계획 알고리즘

동적 계획에서는 효율성을 고려하기 때문에 10원 2개로 총 2개의 동전을 줄 수 있다.

정렬 알고리즘

내부 정렬

입력 크기가 주기억 장치보다 작은 경우 사용된다.

• 버블 정렬: 이웃하는 숫자를 비교하여 작은 수를 점진적으로 앞으로 이동시킨다.
• 선택 정렬: 가장 작은 값과 끝 값을 교환하여 점진적으로 정렬한다.
• 삽입 정렬: 비교 후 적절한 순서로 교환하여 정렬한다.

힙 정렬

• 배열의 앞에서부터 트리로 구성하여 정렬한다.
• 큰 수와 트리 맨 위에 있는 수를 교환한다.
• 트리 맨 위에 있는 가장 큰 수를 정렬한 배열의 마지막으로 이동시킨다.
• 그 다음 큰 수를 비어있는 맨 위로 이동시키고 배열로 이동시킨다.
• 트리에서 큰 순서대로 하나씩 제거하여 정렬된 배열로 이동시킨다.