알고리즘이란 무엇인가?
📌 알고리즘이란 본질적으로 무엇인가?
컴퓨터공학을 전공하고 있는 학생이라면, 지금쯤 알고리즘이란 무엇인가라고 정의 내릴 수 있을 것이다.
교수님에 따라, 전공책에 따라 약간의 차이는 있겠지만, 일반적으로 우리는 어떤 문제를 해결하기 위한 명확한 절차(과정)나 규칙, 명령어들의 집합을 알고리즘이라고 일컫는다.
그리고 모든 알고리즘들은 5가지의 규칙을 반드시 따라야한다!
1️⃣ 입력(Input ≥ 0)
알고리즘은 하나 이상의 입력값을 가져야 한다.
입력값은 0개 이상일 수 있으며, 적절한 범위를 가져야 한다.
예를 들어, 정렬 알고리즘이라면 정렬할 리스트가 입력값이 됨
2️⃣ 출력(Output > 0)
알고리즘은 최소한 하나 이상의 출력을 반환해야 한다.
출력값은 유효한 결과여야 하며, 알고리즘이 수행된 후 의미 있는 값을 반환해야 함.
단순히 print()만 하는 것이 아니라, 논리적인 연산 결과가 나와야 함.
3️⃣ 명확성(Definiteness)
알고리즘의 모든 단계는 명확해야 한다.
각 단계는 애매모호함이 없어야 하고, 특정한 작업을 수행해야 한다.
같은 입력을 주었을 때 항상 같은 동작을 해야 한다.
4️⃣ 유한성(Finiteness)
알고리즘은 반드시 유한한 단계를 거쳐 종료되어야 한다.
무한 루프에 빠지면 안 되며, 일정한 시간이 지나면 결과를 출력해야 함.
5️⃣ 효과성(Effectiveness)
각 단계는 충분히 단순하고, 기계적으로 수행할 수 있어야 한다.
사람이 이해하기 어려운 절차가 아니라, 명확한 연산으로 표현되어야 함.
즉, 실제로 실행 가능한 명령어들로 구성되어야 한다.
📌 How algorithms work
알고리즘은 데이터를 초기화하고, 수정하고, 삭제하는 등의 작업을 수행한다.
즉, 대부분의 알고리즘은 어떤 형태로든 데이터를 처리하는 과정을 거친다는 것이다.
🤔 그렇다면 무한히 많은 입력 리스트를 일일이 확인하지 않고도, 알고리즘이 항상 올바르게 작동한다는 것을 증명할 방법이 있을까?
-
당신은 시간 빌게이츠인가?, 알고리즘이 모든 경우에 대해 올바르게 동작하는지 일일이 검증하는 것은 불가능하다!!
-
따라서, 수학적 증명 방법을 사용해야 한다. (예: 귀납법, 불변식 사용)
🔑 핵심 통찰 (Key Insight): 알고리즘의 동작을 분석할 때, 변하지 않는 것(불변식, invariant)을 찾으면 도움이 된다.
-
알고리즘을 검증하는 핵심적인 방법 중 하나는 불변식(Invariant)을 찾는 것!
-
불변식이란 알고리즘이 실행되는 동안 변하지 않는 성질을 의미해.
-
예를 들어, 정렬 알고리즘에서 "이미 정렬된 부분은 항상 정렬 상태를 유지한다"라는 것이 불변식이 될 수 있음.
📝 정리하자면
-
알고리즘을 모든 경우에 대해 검증하는 것은 비효율적이므로, 변하지 않는 속성(불변식)을 찾는 것이 중요하다는것이 핵심이다.
-
또한 이러한 불변식은 알고리즘이 올바르게 동작하는지 검증하는 데 사용될 수 있다.
📌 Proving Correctness (정확성 증명)
🔹 Loop Invariant (반복문 불변식)란?
- 반복문이 실행되기 전과 실행된 후에도 항상 참인 조건을 의미한다.
🔹 알고리즘의 정확성을 증명하는 3가지 단계
1️⃣ 초기조건 (Initialization)
반복문이 처음 실행되기 전에 불변식이 참임을 보여야 함.
2️⃣ 유지조건 (Maintenance)
만약 반복문이 한 번 실행되기 전 불변식이 참이라면, 실행 후에도 참이어야 함.
3️⃣ 종료조건 (Termination)
반복문이 종료될 때 불변식이 알고리즘의 정당성을 보장해야 함.
🔥 즉, 알고리즘을 분석할 때 "뭐가 변하는가?"보다는
"뭐가 변하지 않는가?"를 찾는 것이 중요한 전략이라는 것이다! 🔥
그럼 말 나온김에 sorting 알고리즘에 대해 알아보도록 하자.
📌 Sorting
sorting, 즉 정렬은 가장 기본적인 알고리즘이다.
n개의 숫자가 랜덤하게 나열되어있을때, 이를 순서대로(오름차순, 내림차순)등으로 재배열한는 것을 의미한다.
Sorting의 종류는 크게 Insertion(삽입) Sort, Shell sort, Quick Sort, Merge(병합) Sort, Heap Sort 등이 있다.
가장 먼저 제일 난이도가 낮은 Insertion Sort부터 알아보자!
📌 Insertion Sort
🚀 삽입 정렬이란?
삽입 정렬(Insertion Sort)은 데이터를 하나씩 확인하면서 적절한 위치에 삽입하는 방식의 정렬 알고리즘이다. 이미 정렬된 부분과 그렇지 않은 부분을 나누고, 정렬되지 않은 데이터를 하나씩 가져와 적절한 위치에 삽입하는 방식으로 동작하는 특징을 가진다.
이는 마치 "카드 게임에서 손에 카드를 하나씩 정리하는 방식"과 같다!
🛠 삽입 정렬 알고리즘 (코드)
Insertion-SORT(A)
for j=2 to A.length
key = A[j]
i = j -1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key삽입정렬을 의사코드로 나타내면 위와 같다.
이 코드를 통해서 우리는 삽입 정렬의 동작 원리를 요약할 수 있다!
🎮 삽입 정렬의 동작 원리
- 첫번째 데이터는 이미 정렬된 것으로 간주하고 넘어간다.
- 두 번째 데이터부터 시작하여, 이전 값들과 비교하면서 적절한 위치를 찾는다.
- 적절한 위치를 찾으면 데이터를 삽입하고, 나머지 값들을 밀어서 정렬한다.
- 이 과정을 마지막 데이터까지 반복한다.
🤔 의문점 1. 이 알고리즘은 그럼 제대로 작동하는가?
👉 숫자 카드 4,3,1,5,2를 정렬한다고 생각해보자.
1️⃣ 처음엔 4 혼자 있어서 정렬된 상태
→ 4, 3, 1, 5, 2
2️⃣ 3을 뽑아 4보다 앞에 둔다
→ 3, 4, 1, 5, 2
3️⃣ 1을 뽑아 3보다 앞에 둔다
→ 1, 3, 4, 5, 2
4️⃣ 5는 이미 올바른 위치에 있으므로 그대로 둔다
→ 1, 3, 4, 5, 2
5️⃣ 2를 뽑아 1과 3 사이에 둔다
→ 1,2,3,4,5
✅ 정렬 완료!
📌 삽입 정렬의 정확성 증명
위에서 학습했던 정확성 증명의 3가지 단계를 거쳐 삽입 정렬이 항상 올바르게 동작함을 수학적으로 증명해보자.
증명에 앞서, 정확성 증명에서 제일 강조했던 Loop Invariant를 정의해볼 것이다.
🔹 삽입 정렬에서의 Loop Invariant
"반복문의 j 번째 반복이 시작될 때, 배열 A[1..j-1]은 항상 정렬된 상태이다."
- 즉, 매 반복마다 정렬된 부분 리스트가 유지되며, 새로운 원소 A[j]를 적절한 위치에 삽입하는 방식이 계속된다는 것이다.
1️⃣ 초기 조건 (Initialization)
j = 2일 때, A[1..j-1]는 단 하나의 원소 A[1]만 포함하고 있음.
하나의 원소는 자동으로 정렬된 상태이므로, 초기 조건이 만족됨.
2️⃣ 유지 조건 (Maintenance)
반복문의 각 단계에서 새로운 원소 A[j]를 삽입하기 위해, 기존 원소 A[j-1], A[j-2], ...를 하나씩 오른쪽으로 이동시켜 올바른 위치를 찾는다.
이렇게 하면 A[1..j]는 항상 정렬된 상태를 유지하며, j를 1 증가시키면, 새로운 A[1..j-1]이 정렬된 상태가 되어 불변식이 유지됨.
3️⃣ 종료 조건 (Termination)
마지막 반복(j = n)이 끝나면, A[1..n]이 정렬된 상태가 됨.
위 과정을 토대로 우리는 삽입 정렬이 항상 올바르게 동작함을 증명할 수 있다!
무튼, 이제 이 삽입정렬이 잘 작동한다는 것은 지겨울 정도로 증명했다.
그럼 그 다음으로 알고리즘에서 중요한 요소인 시간복잡도로 넘어가보자.
