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 공간 복잡도

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

01 자료구조 (Data Structure) 

가) 정의

• 자료구조(Data Structure)란 자료를 컴퓨터의 기억장치 내에 저장하는 방법으로 다양한 자료를 효율적으로 표현하고 활용할 수 있도록 자료의 특성과 사용 용도를 고려하여 조직적, 체계적으로 정의한 것.
• 프로그램에서 사용할 많은 데이터를 메모리 상에서 관리하는 여러 구현방법들
• 효율적인 자료구조가 성능 좋은 알고리즘의 기반이 됨.
• 자료의 효율적인 관리는 프로그램의 수행속도와 밀접한 관련이 있음
• 여러 자료구조 중에서 구현하려는 프로그램에 맞는 최적의 자료구조를 활용해야 해 자료구조에 대한 이해가 중요

나) 분류

자료구조의 분류 : 선형구조와 비선형 구조

정적 자료구조(Static) : 프로그램 실행 중에 크기가 고정되어 있는 자료구조
- 배열은 정적 자료구조의 대표적인 예로 선언시 배열의 크기가 정해지고 이후에 변경 불가
- 미리 할당된 메모리 공간에 데이터를 저장하기 때문에 데이터 추가, 삭제, 크기 변경 등이 제한적
  
동적 자료구조(Dynamic) : 프로그램 실행 중 크기가 동적으로 조정될 수 있는 자료구조
- 필요에 따라 메모리에서 유연하게 공간을 할당하고 해제헤 데이터를 저장할 수 있어
- 데이터 추가, 삭제, 크기 변경 등이 가능함
- 대표적인 예: ArrayList, LinkedList, Queue, Stack 등이 있음

순차자료구조와 연결자료구조의 비교

**노드(Node)란**

• 자료구조에서 하나의 단위를 의미한다. 노드를 어떤 데이터를 담고 있는 상자라고 이해할 수 있다.
• 노드에는 데이터(data)와 포인터(pointer)가 있다. 포인터는 주로 연결 자료 구조에서 사용되고, 순차 자료 구조에서는 필요하지 않다.

**순차 자료 구조(Sequential Data Structure)란**

• 순차 자료 구조는 배열을 생각하면 된다. 배열, 데이터를 메모리에 차례대로 저장하는 방식. 
• 배열의 가장 큰 특징은 연속적인 공간을 사용한다는 점. 즉, 메모리에서 데이터가 연속적으로 나열되어 있다.
• 배열에서 데이터를 찾을 때는 인덱스로 접근 할 수 있어서 빠르게 찾을 수 있지만, 배열의 중간에 데이터를 삽입하거나 삭제하려면 나머지 데이터를 이동시켜야 하는 번거로움이 있다.
• 선형 리스트(Linear List)와 같은 개념

** 연결 자료 구조(Linked Data Structure)란**

• 연결 자료 구조는 배열과 달리 연속된 공간에 저장하지 않고, 각각의 노드가 서로를 가리키며 연결이 되어있다. 이때, 데이터를 담고 있는 노드가 다음 노드를 가리키는 포인터를 갖고 있다.
• 연결 자료 구조는 중간에 데이터를 쉽게 삽입하거나 삭제할 수 있지만, 특정 위치의 데이터를 찾으려면 처음부터 차례대로 노드를 따라가야 하므로 속도가 느릴 수 있다.
• 연결 리스트(Linked List)는 연결 자료 구조의 대표적인 예시

**간단한 예시:

• 배열(순차 자료 구조):
  [10, 20, 30] (연속된 메모리 공간에 데이터가 순차적으로 저장됨)
• 연결 리스트(연결 자료 구조):
  [10] → [20] → [30] (각 노드가 데이터를 가지고, 다음 노드를 가리키는 방식)

다) 스택과 큐

1) 스택(Stack)

**스택이란**

- 스택은 선형리스트(순차 자료 구조)의 하나로 데이터가 입력된 순서로 기억공간에 저장되어 후입선출하는 자료구조.

- 스택에 저장된 원소는 top으로 정한 곳에서만 접근이 가능하여 top 위치에서만 원소를 삽입하고 마지막에 삽입한 원소는 맨 위에 쌓여 있다가 가장 먼저 출력되게 됨.

- LIFO(Last In First Out) : 후입선출 구조

** 스택의 연산의 종류 **

※ 스택이 비었다는 것은?

스택이 비었다는 것은, 더 이상 스택 안에 쌓여 있는 데이터(원소)가 없다는 것을 의미합니다. 마치 그릇 안에 아무것도 들어 있지 않은 상태를 생각해보면 이해하기 쉽습니다.

stack = []
//스택에 아무것도 넣지 않은 상태

예시를 보자.

stack = [1, 2, 3]  # 스택에 원소가 있음

if not stack:  # 스택이 비었는지 확인
    print("스택이 비었습니다.")  # 이 메시지는 출력되지 않음
else:
    print("스택에 원소가 있습니다.")  # 스택에 원소가 있으니 이 메시지가 출력됨

2) 큐(Queue)

** 큐(Queue)란 **

- 스택과 유사하게 삽입과 삭제의 위치가 제한되어 있지만 스택과는 달리 데이터가 삽입되는 곳과 삭제되는 곳이 다른 자료구조.

- 큐는 뒤에서만 삽입되고 앞에서는 삭제만 할 수 있는 구조로 삽입된 순서대로 원소가 나열되어 가장 먼저 삽입한 원소는 맨 앞에 있다가 가장 먼저 삭제된다. 

- FIFO (First In First Out) 선입선출 구조

** 큐의 연산 종류 **

3) 스택과 큐 연산 비교

라) 트리와 그래프 

1. 트리 (Tree)

- 원소들 간에 계층관계를 가지는 계층형 자료구조로 상위 원소에서 하위 원소로 내려가면서 확장되는 나무 모양의 구조를 가지고 있으며 원소들 간에 1:다 관계를 가진다.

- 트리의 시작노드를 루트노드(root node)라고 하고 노드를 연결하는 선을 간선(edge)이라고 한다. 같은 부모 노드를 가진 자식 노드들을 형제노드(sibling node)라고 하고 부모노드와 연결된 간선을 끊었을 때 생성되는 트리를 서브트리(subtree)라고 한다.

2. 그래프 (Graph)

연결되어 있는 원소 사이의 다:다 관계를 표현하는 자료구조로 객체를 나타내는 정점(vertex)과 객체를 연결하는 간선(edge)의 집합이다. 그래프 자료구조는 전기회로분석, 인공지능 등과 같이 여러가지 복잡한 문제들을 그래프로 나타내어 그래프이론을 기반으로 문제를 해결하는 경우가 많다.

마) 자료구조의 선택 기준

• 자료의 처리 시간
• 자료의 크기
• 자료의 활용 빈도
• 자료의 갱신 정도
• 프로그램의 용이성

바) 자료구조의 활용

02 알고리즘(Algorithm)

가) 알고리즘 개요

1) 알고리즘의 정의

- 주어진 문제를 해결하기 위한 일련의 처리 절차를 단계적으로 기술한 것. 문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서이다.

- 알고리즘의 목표 : 단순히 원하는 결과를 얻을 수 있는 알고리즘이 아닌, 처리시간이나 기억장소 사용 측면에서 효율적인 알고리즘을 개발하는 것이다.

2) 알고리즘의 조건

입력, 출력, 명확성, 유한성, 효과성

나) 알고리즘 분석 기준

정확성, 작업량, 기억 장소 사용량, 최적성, 단순성

다) 알고리즘 표현 방법

라) 알고리즘 성능 분석

1) 공간 복잡도

• 고정 공간량 : 프로그램, 변수 및 상수들과 같이 프로그램의 크기나 입출력 횟수에 상관없이 고정적으로 필요한 저장 공간
• 가변 공간량 : 프로그램의 수행과정에서 사용하는 자료와 변수들을 저장하는 공간과 함수 실행에 관련된 정보를 저장하는 공간

2) 시간 복잡도

• 컴파일 시간 : 프로그램 특성과 관련이 적은 고정적인 시간으로 일단 컴파일이 되면 프로그램의 수정이 일어나지 않는 한 일정하게 유지
• 실행 시간 : 프로그램의 실행시간으로 컴퓨터의 성능 등에 의존하므로 실제 정확한 실행 시간을 측정하기 보다는 명령문의 실행 빈도수를 구하여 계산

알고리즘 간의 비교 시에는 주로 실행 시간을 사용하여 시간 복잡도를 나타낼 빅-오(Big Oh) 표기법을 사용하여 O(n)로 표기한다. 알고리즘에 따라 logn, n, nlogn, n^2, n^3, 2^n 등의 실행 시간 함수가 있다. 

가장 작은 값의 시간 복잡도를 가지는 알고리즘을 선택하는 것이 좋다.

마) 정렬 알고리즘

1) 정렬의 분류

• 정렬 장소에 따라 내부정렬(Internal Sort)과 외부정렬(External Sort)로 분류할 수 있다.
• 정렬 방법은 사용하는 시스템의 특성, 데이터의 양과 상태, 정렬에 필요한 기억 공간 및 실행 시간 등의 조건을 고려하여 선택한다.

2) 내부 정렬 알고리즘의 분류