기본개념) 자료구조, 알고리즘, List, 선택정렬, 병합정렬

춘식이

# ⭐️ Abstract Data Type(추상적 자료형_ ADT)

'''

문제를 해결하기 위해 필요한 '자료의 형태 및 연산을 수학적으로 정의'한 모델

ex.집합, 리스트, 스택, 큐, 트리 등

vs

Data Structrue(자료 구조)

추상적 자료형에서 정의한 연산들을 '구현한' 구현체

ex. 배열, 연결 리스트 등

알고리즘

반복되는 문제를 해결하기 위한 일련의 절차나 방법

ex. 정렬, 이진 탐색 등

'''

# ⭐️ 시간 복잡도와 공간 복잡도

'''

시간 복잡도(Time Complexity)

알고리즘이 실행되는 데 소요되는 시간을 측정. 주어진 입력 크기에 따라 얼마나 빠르게 실행되는지?

주로 Big O(빅오) 표기법을 사용해서 표현하며, 알고리즘의 성능을 나타냄.

일반적으로 시간 복잡도가 작을수록 더 효율적인 알고리즘임.

공간 복잡도(Space Complexity)

알고리즘이 실행되는 데 필요한 메모리 공간의 양을 측정. 주어진 입력 크기에 따라 메모리 공간이 얼마나 더 필요한가?

공간복잡도 역시 Big O 표기법을 사용하며, 알고리즘의 메모리 사용량을 나타냄.

일반적으로 공간 복잡도도 최소화 하는 것이 바람직하나, 메모리를 사용해서 시간 복잡도를 줄일 수 있기도 하기 때문에

시간과 공간의 tradeoff를 잘 고려하는 것이 중요함.

보통 코딩테스트에서는 시간 복잡도를 중시함.

'''

# ⭐️ 2진법과 16진법

'''

2진법(Binary)

컴퓨터에서 사용되는 가장 기본적인 숫자 표기법. 0과 1 두 가지만 사용.

2진법에서 각 자리는 2의 거듭제곱으로 표현되며, 오른쪽에서부터 각 자리마다 2의 지수를 증가시킴.

ex. 0b1010은 2^3 + 2^1임. 이진수에서 0은 값이 없음, 1은 해당 위치의 값.

16진법(Hexadecimal)

16개의 숫자와 알파벳 A~F를 사용해서 숫자를 표현하는 방식. (표현식을 간결하게 만들기 위함)

16진법은 10 ~ 15를 A ~ F와 매칭하며 각 자리는 16의 거듭제곱으로 표현됨. 오른쪽에서부터 각 자리마다 16의 지수를 증가시킴.

ex. 0x1A는 1 * 16^1 + 10 * 16^0임.

2진법은 컴퓨터 시스템의 이진 연산과 디지털 회로에서 사용되고,

16진법은 메모리 주소와 데이터 표현을 간결하게 하기 위해 주로 사용됨.

'''

# ⭐️ List 자료형

'''

순열(Sequenece)라고도 불리며, '순서를 가지고 일렬로 나열한 원소들의 모임'

추상적 자료형(ADT)

이를 구현하면? (자료 구조)

List는 크게 Array, Linked List로 구현할 수 있음.

'''

# ⭐️ 정적 배열 (Static Array)

'''

배열은 선언 시 크기가 정해지고, 해당 크기 만큼의 '연속된 메모리를 할당'받아 데이터를 순차적으로 저장하는 자료구조.

ex. 만약 5개의 정수를 배열에 담으려면, Int는 4바이트(32비트)이기 때문에 총 20 바이트의 메모리 공간을 미리 할당받는다.(순차적으로)

이렇게 고정된 크기를 가지기 때문에 static array라고 부르기도 함. cf(Dynamic Array)

각 숫자의 맨 앞 메모리 주소를 통해 접근 가능함.(Random Access)

* Random Access란? 메모리에 저장된 데이터에 랜덤(임의)하게 접근하는 것.

메모리는 주소를 사용해서 데이터에 직접 접근할 수 있기 때문에 어떤 위치에 있든 데이터에 빠르게 접근할 수 있음.

(주기억 장치인 RAM, 메모리가 빠른 이유임.)

a = [1, 2, 3] 이라면, a에는 배열이 할당받은 메모리의 첫 번째 주소를 가지고 있고, 여기서 인덱싱을 통해 어떤 원소든 바로 접근 가능하다는 말.

why? 배열은 연속/순차적으로 저장되어 있기 때문에. -> O(1)

정적 배열은 데이터의 크기가 정해져 있는 경우에 매우 효율적이고 빠르다.(Random Access를 통해서, 메모리에 순차적으로 데이터가 저장되어 있기 때문에)

하지만 데이터의 크기에 변화가 생길 수 있다면? 이를 대비해서 여유 공간을 잡고 배열의 크기를 미리 크게 선언하면 메모리 낭비가 될 수 있다.

-> dynamic array를 사용하는 이유.

'''

# ⭐️ 동적 배열 (Dynamic Array)

'''

(파이썬의 List는 Dynamic Array로 구현되어 있음. Swift의 array도 데이터가 추가되면 동적으로 리사이징 됨.)

정적 배열은 선언할 때 크기가 정해지기 때문에 이후에 크기 변경이 불가능하다.

동적 배열에 데이터를 담다가, 만약 자리가 모자라면?

더 커다란 배열을 메모리에 할당해서 기존 데이터들을 옮겨 담은 후에 새로운 데이터를 추가한다. (Resizing) 그리고 기존 배열은 삭제한다.

기존 요소들을 하나 하나 옮기기 때문에 리사이징은 O(n) 시간 복잡도를 가진다.

but 대부분 요소를 추가하는 경우에는 O(1)이고, 리사이징이 필요한 경우만 O(n)이기 때문에 분할상환기법(amortized)에 따라 O(1)로 표기할 수 있음.

그럼 새로운 배열의 크기는 어떻게 정하는가? 보통은 기존 배열 사이즈 * 2의 크기를 가지게 됨. (Doubling)

why? 리사이징은 O(n), 즉 시간이 오래 걸리는 작업이기 때문에, 조금씩 늘리는 것보다 여유롭게 큰 사이즈를 할당하는 것이 효율적이기 때문.

다이나믹 어레이는 선언 할 때 배열의 크기를 정하지 않아도 되기 때문에 편하다. 코테 문제에서 배열을 사용할 때는 list를 사용하면 됨.

선언 - O(n)

접근, 변경, append, pop - O(1)

중간 삽입 - O(n) 배열은 순차적으로 저장되어 있기 때문에, 중간에 데이터를 넣으려면 나머지 요소들을 한 칸 씩 거의 n개에 가깝게 이동시키기 때문

중간 삭제 - 중간 삽입과 마찬가지로 O(n) 한 칸 씩 거의 n개를 땡겨줘야 하기 때문

'''

# 정렬 알고리즘이란?

'''

Sorting Algorithm

주어진 데이터를 일정한 기준에 따라 정렬하는 알고리즘.

정렬은 데이터를 조직화하고 검색이나 다른 작업을 수행하기 쉽게 만들어줌.

정렬 알고리즘에는 다양한 방법이 존재함(선택, 삽입, 버블, 병합, 퀵, 힙, 계수, 기수) 각 알고리즘은 특징과 성능이 다름.

'''

# 정렬 알고리즘의 안정성(Stable, Unstable)

'''

정렬 알고리즘에서 안정성은 '정렬된 요소들의 상대적인 순서가 유지되는지' 여부를 나타낸다.

Stable(안정적) 정렬 알고리즘

동일한 값 또는 동일한 키 값을 가진 요소들의 '순서를 유지함'.

정렬 전과 동일한 순서를 가지는 요소들이 정렬된 후에도 동일한 순서를 유지함.

안정적 정렬 알고리즘은 입력 데이터에 따라 상대적인 순서가 중요한 경우 유용함.

-> 정렬된 데이터에서 중복된 값이 있는 경우 안정적 정렬 알고리즘을 사용하면 중복된 값들의 순서가 유지되기 때문에

이후 정렬된 데이터를 다른 기준으로 다시 정렬할 때 유용할 수 있음.

Unstable(불안정) 정렬 알고리즘

동일한 값 또는 동일한 키 값을 가진 요소들의 '순서를 보장하지 않음'

정렬 후에 동일한 값 또는 동일한 키 값을 가지는 요소들의 상대적인 순서가 바뀔 수 있음.

불안정적 정렬 알고리즘은 상대적인 순서가 중요하지 않거나, 성능이 더 중요한 경우에 사용될 수 있음.

-> 추가적인 작업 없이 더 빠른 정렬 속도를 제공할 수 있음.

'''

# Selection Sort(선택 정렬)

'''

Unstable 정렬 알고리즘

[b, B, a, c] 배열이 있을 때 (a < b < c) (b == B)

선택 정렬을 하면 [ a, B, b, c]가 된다. 즉 같은 값이지만 처음 순서가 유지되지 않기 때문에 불안정 정렬임.

시간 복잡도 - O(n^2)

배열을 순회하면서 최솟값을 선택해서 맨 앞으로 이동시키는 과정을 반복.

배열의 길이가 n이면, n번의 비교 및 교환 작업이 필요하기 때문

선택 정렬은 주어진 배열에서 '가장 작은 값을 찾아 첫 번째 위치로 옮기고', 그 다음으로 작은 값을 두 번째 위치로 옮기는 과정을 반복함.

맨 왼쪽부터 마킹하고, 더 작은 값이 나오면 다시 마킹하고 끝까지 본 다음에 자리를 바꿈. https://visualgo.net/en/sorting

선택 정렬은 구현이 간단하지만, 데이터 세트가 큰 경우 성능이 떨어질 수 있음.

'''

# Merge Sort(병합 정렬)

'''

Stable 정렬 알고리즘

시간 복잡도 - O(n log n)

병합 정렬은 분할 정복(divide and conquer) 알고리즘의 일종임

병합 정렬은 배열을 반으로 나눈 뒤 각각을 재귀적으로 정렬한 후, 정렬된 배열을 병합해서 최종적으로 정렬된 배열을 얻는 방식

병합 정렬은 일반적으로 안정적이며 성능도 좋지만 추가적인 메모리 공간이 필요하다는 단점도 있음.

정렬된 부분 배열을 병합할 때도 안정적인 방식으로 병합됨. (순서 유지)
https://visualgo.net/en/sorting

https://www.youtube.com/watch?v=FCAtxryNgq4

'''