hyoriyam

Simple Sort Algorithm

데이터를 오름차순 또는 내림차순으로 정렬하는 기본적인 알고리즘

종류 : 버블 정렬(Bubble Sort), 삽입 정렬(Insertion Sort), 선택 정렬(Selection Sort) 등

1. 버블 정렬 (Bubble Sort)

버블 정렬은 서로 인접한 두 요소를 비교하여 잘못된 순서라면 위치를 바꾸는 방식으로 동작합니다. 이 과정을 반복하여 가장 큰 값이 리스트의 끝으로 "버블"처럼 이동합니다. 

동작 방식:

• 리스트의 처음부터 시작하여 인접한 두 개의 값을 비교합니다.
• 잘못된 순서라면 두 값을 교환합니다.
• 이 과정을 리스트 끝까지 반복한 후, 가장 큰 값이 맨 끝에 위치하게 됩니다.
• 나머지 요소들에 대해 같은 과정을 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [2, 5, 1, 5, 6, 9]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

2. 삽입 정렬 (Insertion Sort)

삽입 정렬은 리스트를 순차적으로 탐색하며, 각 요소를 이미 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식입니다.

동작 방식:

• 두 번째 요소부터 시작하여 그 요소를 앞의 정렬된 리스트와 비교합니다.
• 적절한 위치에 삽입하여 정렬된 부분을 확장해 나갑니다.
• 리스트 끝까지 이 과정을 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [2, 5, 9, 1, 5, 6]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

3. 선택 정렬 (Selection Sort)

선택 정렬은 매번 남아 있는 리스트 중에서 가장 작은(또는 큰) 값을 선택하여 앞쪽부터 차례대로 위치를 정렬해 나가는 방식입니다.

동작 방식:

• 리스트에서 가장 작은 값을 찾아 첫 번째 요소와 교환합니다.
• 다음으로 두 번째 작은 값을 찾아 두 번째 위치와 교환합니다.
• 이 과정을 리스트의 끝까지 반복합니다.

예시:

정렬 전: [5, 2, 9, 1, 5, 6]
첫 번째 단계 후: [1, 2, 9, 5, 5, 6]
최종 정렬 후: [1, 2, 5, 5, 6, 9]

요약:

• 버블 정렬: 인접한 요소끼리 비교하며 정렬.
• 삽입 정렬: 이미 정렬된 부분에 새로운 요소를 삽입하며 정렬.
• 선택 정렬: 남은 요소 중 가장 작은 것을 찾아 차례대로 정렬.

이 알고리즘들은 구조가 단순하고 구현이 쉬워서 학습용으로 적합하지만, 시간 복잡도가 O(n2)O(n^2)O(n2)이기 때문에 큰 데이터 세트에는 비효율적일 수 있습니다.

< 학습목표 >

• 개념: 불안정한 짝(unstable pair)와 안정적인 매칭(stable matching)의 개념을 이해하고,
• 구현: Gale-Shapley 알고리즘이 어떻게 불안정한 짝을 피하고 안정성을 보장하는지 알고,
• 응용: 실제 문제나 응용 사례에서 이 알고리즘을 적용할 수 있어야 합니다.

Stable matching

Def. A stable matching is a perfect matching with no unstable pairs.

Stable Matching 문제의 핵심은 이미 형성된 매칭이 있고, 그 매칭이 불안정한지 또는 안정적인지를 판단하는 것이에요.

Perfect matching

Def. A matching M is a set of ordered pairs h-s with h ∈ H and s ∈ S s.t.

- Each hoshpital h ∈ H appears in at most one pair of M.

Unstable pair

Def. Given a perfect matching M, hospital h and student s form an unstable pair if both.

Key point. An unstable pair h-s could each improve by joint action.

Gale-Shapley deferred acceptance algorithm for Stable Matching Marriage

The Gale-Shapley algorithm, solves the stable matching problem, where you have an equal number of men and women, and each person ranks the people of the opposite gender by their preferences.

The goal if to find a stable matching - a situation where no pair of individuals would both prefer to be with each other over their current partners.

예제 )

Males: 

Adam, Ben, Cian, David, Ethan

Females:

Tina, Wendy, Xena, Yasmine, Zara

선호도 조사가 다음과 같다고 하자. (선호하는 순서대로 적음)

(A, T), (B, W), (C,X), (D,Z), (E, Y)

Meaning of Algorithms

- a set of instructions for solving a problem

Why we use algorithms?

• Algorithms are especially important to computers because computers are general purpose machines for solving problems.
• In order for a computer to be useful, we must give it a problem to solve and a technique for solving the problem.
• Through the use of algorithms, we can make computers intelligent by programming them with various algorithms to solve problems.

Algorithms' Characteristics

• Name
• Description
• Input (입력) : Algorithm receives input
  외부에서 제공되는 자료가 0개 이상 있어야 한다. (입력할 수 없는 경우도 있음.)
• Output (출력) : Produces output
  적어도 1개 이상의 결과를 만들어야 한다.
• Generality(일반성) : The algorithm applies to set of inputs
  같은 유형의 문제에 대해 항상 적용될 수 있어야 합니다.
  
• Order of Operations (명령어의 순서) : Exact order of steps to perform
  설명: 알고리즘은 단계별로 순서가 정확하게 정의되어 있어야 합니다. 이 순서가 바뀌면 원하는 결과를 얻지 못할 수 있기 때문에 명령어의 순서는 매우 중요합니다.
  예시: 버블 정렬에서 인접한 두 수를 비교하고, 그 결과에 따라 위치를 바꾸는 과정이 순차적으로 이루어져야 합니다. 만약 순서가 잘못되면 정렬이 되지 않습니다.
  
• Precision(정확성) : The steps are precisely stated
  설명: 알고리즘의 단계는 명확하고 구체적이어야 하며, 애매하거나 불확실한 명령은 없어야 합니다. 알고리즘을 수행하는 사람이든 컴퓨터든, 각 단계를 정확하게 수행할 수 있어야 합니다.
  예시: "숫자를 비교한다"는 구체적인 단계입니다. 반면 "필요한 작업을 수행한다"는 모호한 지시입니다. 정확한 단계가 없으면 알고리즘이 제대로 실행될 수 없습니다.
  
• Finiteness (유한성) : The algorith terminates
  알고리즘은 유한한 단계를 거쳐 실행이 종료되어야 한다. 모든 명령문은 유한한 시간 내에 실행되어야 하고, 무한 루프같은 무한한 반복을 피해야 한다. 알고리즘은 모든 입력에 대해 종료되어야 하므로 무한히 실행되거나 중단되어서는 안된다.
• Correctness(정확성) : The output produced by algorithm is correct
  입력을 이용한 문제 해결 과정과 출력은 논리적이고 정확해야 합니다. 오류가 없어야 함.
  

※ 알고리즘과 자료구조와의 관계 
알고리즘의 성능은 자료구조에 의해 결정된다.

성능이란, '얼만큼 빨리 수행되느냐.'이다.

같은 자료라고 해도 어떻게 표현되고 저장되느냐에 따라 사용가능한 알고리즘이 달라지기 때문이다.

자료구조의 기본적인 연산을 구현하기 위해서 알고리즘을 사용한다.

※ 알고리즘 분석 기준

복잡도란,

1. 알고리즘의 성능, 효율성을 나타내는 척도. 즉. 어떤 알고리즘이 효율적인지 판단하는 척도.
2. 크게 Time Complextity와 Space Complexity로 나눌 수 있음.
3. 각 알고리즘이 주어진 특정 크기의 입력(n)을 기준으로 수행시간(연산) 혹은 사용 공간이 얼마나 되는지 객관적으로 비교할 수 있는 기준을 제시함.
4. 복잡도를 나타내는 방법 : 점근 표기법으로 O(빅오), Ω(오메가), Θ(세타) 등이 있고, 주로 빅오와 세타 표기법이 많이 사용됨.

알고리즘을 평가할 때는 주로 수행 시간과 메모리 사용량을 기준으로 둔다.

1) 시간 복잡도 (Time Complexity)
- 특정 크기의 입력을 기준으로 할 때 필요한 연산의 횟수를 나타낸다.
- 실행 시간이 아닌, 연산 횟수를 센다. 

- 알고리즘의 성능 평가 Case 분류

• 최선의 경우 (Best Case)
  최적의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 적은 경우
• 최악의 경우 (Worst Case)
  최악의 입력을 한 상태에서, 작업을 완료하는 데 가장 연산 횟수가 많은 경우
• 평균의 경우 (Average Case)
  여러 경우의 수를 고려하여, 총 연산 횟수를 계산하고 시행 횟수로 나눈 경우

알고리즘 분석 시 평균의 경우와 최악의 경우가 가장 많이 활용되며, 알고리즘이 복잡해질수록 Average를 구하기 어려워 Worst Case로 Algorithm Perfomance를 파악한다.

2) 공간 복잡도 (Space Complexity)
- 메모리(저장공간)가 적게 드는 것을 의미한다.

- 프로그램 실행과 완료에 얼마나 많은 공간이 필요한지를 나타낸다.

- 알고리즘을 실행시키기 위해 필요한 공간(space)은 두 가지로 분류한다.

• 고정 공간(Fixed Space), 알고리즘과 무관한 공간
  - 코드가 저장되는 공간
  - 알고리즘 실행을 위해 시스템이 필요로 하는 공간 
• 가변 공간(Variable Space), 알고리즘과 밀접한 공간
  - 문제를 해결하기 위해 알고리즘이 필요로 하는 공간
  - 변수를 저장하는 공간. 순환 프로그램의 경우 순환 스택(recursion stack) 등

3) 시간 복잡도 VS 공간 복잡도

- 시간 복잡도는 얼마나 빠르게 실행되는지, 공간 복잡도는 얼마나 많은 자원(메모리 공간)이 필요한지를 판단한다.
- 시간 복잡도와 공간 복잡도는 반비례하는 경향이 있어, 보통 알고리즘의 성능을 파악할 때는 시간 복잡도를 위주로 파악한다.