자료구조와 알고리즘

Data Structure

• 데이터 집합 ⇒ 컨테이너
• 기능 ⇒ 삽입, 삭제, 조회
• Array, List, Queue, Stack, Tree, Graph 

데이터의 배치에 따라 선형적, 비선형적인 형태로 나눌 수 있다

선형적인 자료구조로는 배열과 리스트(더 나아가 스택과 큐)가 있음

비선형적인 자료구조의 대표적인 예로는 Tree와 Graph가 있음

Algorithm

• 문제 해결을 목적으로 하는 절차 공식
• 목적 ⇒ 탐색, 정렬, 최단 경로
  • 순차 탐색, 이진 탐색, …
  • 선택 정렬, 힙 정렬, …
  • BFS, Dijkstra Algorithm

알고리즘의 조건

• 입력 : 0개 이상의 입력 값
  ⇒ 입력 값은 없을 수 있다
• 출력 : 1개 이상의 출력, 입력에 따라 2가지 이상의 서로 다른 결과
  ⇒ 입력에 따라 2가지 이상의 다른 결과를 출력해야 한다
• 명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성
  ⇒ 입력 값이 같은데 출력이 다르면 안 된다
• 유한성 : 유한 번의 명령어를 수행 후 유한 시간 내에 종료
  ⇒ 무한 루프 등으로 처리가 끝나지 않으면 안 된다
• 효율성 : 모든 과정은 명백하게 실행 가능(검증 가능)한 것이어야 함
  ⇒ 알고리즘의 성능은 시간 복잡도와 공간 복잡도로 표현한다

알고리즘의 성능

알고리즘의 성능은 시간 복잡도와 공간 복잡도로  표현한다. 

• 시간 복잡도(CPU)
  임의 값의 개수와 알고리즘의 실행수행 시간과의 상관관계를 표현한 말이다. 
  입력 데이터의 양이 많아짐에 따라 처리 속도가 어떻게 변하는지를 
  수학의 기호를 빌려 표현하는 방식이다.
• 공간 복잡도(메모리)
  알고리즘의 메모리 사용량의 변화를 비교하는 것이다.

수학의 기호를 빌려 표현하는 방식

시간복잡도를 나타내는데 되는 표기법

• 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
• 평균의 경우 : 세타 표기법 (Big-θ Notation)
• 최악의 경우 : 빅오 표기법 (Big-O Notation)

평균인 세타 표기를 하면 가장 정확하고 좋겠지만 평가하기가 까다롭다.

그래서 최악의 경우인 빅오를 사용하는데 알고리즘이 최악일 때의 경우를 판단하면

평균과 가까운 성능으로 예측하기 쉽기 때문이다.

 

자료구조와 알고리즘의 성능 평가는 
가상 컴퓨터 위에서 가상 언어를 이용한 가상 코드를 이용해서 진행한다

(Pseudocode라고 한다)

알고리즘의 수행 시간 ⇒ 효율성

점근 표기법(asymptotic notation)은 어떤 함수의 증가 양상을
다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다
by 위키백과

점근 표기법에서는 다음과 같은 원칙을 따른다

1. 상수항 무시
   • (2N) -> O(N)
   • O(N² + 2) -> O(N²)
2. 영향력 없는 항 무시
   • O(N² + N) -> O(N²)

시간 복잡도 예시

유클리드 호제법(Euclidean Algorithm)

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은
2개의 자연수 또는 정식(整式)의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘이다.
이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다.
by 위키피디아, 나무위키

유클리드 알고리즘을 직관적으로 설명한 그림

브루트 포스

brute: 무식한, force: 힘 --> 무식한 힘으로 해석

완전 탐색 알고리즘. 즉, 가능한 모든 경우의 수를 모두 탐색하면서 요구 조건에 충족되는 결과를 가져온다.
이 알고리즘의 강력한 점은 예외 없이 100%의 확률로 정답을 출력한다.

일반적 방법으로 문제를 해결하기 위해서는 모든 자료를 탐색해야 하기 때문에

특정한 구조를 전체적으로 탐색할 수 있는 방법을 필요로 한다.

알고리즘 설계의 가장 기본적인 접근 방법은 해가 존재할 것으로 예상되는 모든 영역을 전체 탐색하는 방법이다.

난수

C/C++에서 간단하게 srand()와 rand()로 난수를 생성할 수 있지만,

하지만 퀄리티 좋은 난수 생성을 위해 주로 사용되는 것은 메르센 트위스터이다

메르센 트위스터(Mersenne Twister)는 1997년에 마츠모토 마코토와 니시무라 다쿠지가 개발한 의사난수 생성기이다. 기존 생성기들의 문제점들을 피하면서 매우 질이 좋은 난수를 빠르게 생성할 수 있도록 설계되었기 때문에
점점 많은 곳에서 채택되고 있으며, 흔히 주기가 2^19937-1인 MT19937을 사용한다.

 

균등 분포: 특정 값에 근접하는 모양

정규 분포: 평균 값을 중심으로 언덕 모양

/// <summary>
/// 시드값을 얻기 위한 random_device 생성
///   Random Device는 운영체제가 제공하는 진짜 난수를 사용할 수 있다
///   단, 진짜 난수는 생성 속도가 매우 느리기 때문에 주로 시드 값으로 사용한다
/// </summary>
random_device rd;
/// <summary>
/// random_device에서 얻은 객체(진짜 난수)로 의사 난수 생성 엔진의 객체를 정의
///   mt19937는 메르센 트위스터 알고리즘을 사용하는 엔진으로 양질의 의사 난수를 생성한다
///   (단, 객체 크기가 2KB 이상이므로, 메모리가 부족할 경우는 minstd_rand가 적합할 수 있음)
/// </summary>
mt19937 gen(rd());
/// <summary>
/// 0 부터 99 까지 균등하게 나타나는 난수열을 생성하기 위해 균등 분포 정의
/// </summary>
uniform_real_distribution<> dist(0, 1);

int main()
{
    // 랜덤 수 구하기
    double tmp = dist(gen);
}

 

SSS