[컴퓨터과학 개론] 5강 - 알고리즘(1)

✅ 1. 알고리즘의 개념

(1) 알고리즘의 정의

• 주어진 문제를 풀기 위한 명령어들을 단계적으로 나열한 것을 의미 ( 주어진 문제에 대한 풀이 방법 및 절차 )
• 입출력: 0개 이상의 외부 입력, 1개 이상의 출력 생성
• 명확성: 각 명령은 모호하지 않고 단순 명확해야 함
• 유한성: 한정된 수의 단계를 거친 후에는 반드시 종료해야 함
• 유효성: 모든 명령은 컴퓨터에서 실행할 수 있어야 함
• 알고리즘을 충족하기 위해서는 이와 같이 4가지 조건을 만족해야함.
• 알고리즘은 주어진 문제에 대한 효율적인 알고리즘을 구현하는 것을 목표로 하고 있음. ( 실용적 측면에서 효율적이어야 함 )

(2) 알고리즘 생성 단계

• (1) 설계: 문제를 해결하는 아이디어를 구체화하여 알고리즘 형태로 만드는 단계
• (2) 표현/기술: 설계된 알고리즘을 수도 코드, 순서도 또는 특정 프로그래밍 언어로 작성 단계
• (3) 정확성 검증: 알고리즘이 모든 유효한 입력에 대해 올바른 결과를 내는지 논리적으로 증명하거나 테스트하는 단계
• (4) 효율성 분석: 알고리즘이 문제를 해결하는 데 필요한 시간과 공간 자원의 양을 분석하여 효율성을 평가하는 단계
• 이렇게 총 4가지 단계를 거쳐서 알고리즘 구현을 하게 된다.

(3) 자료구조와 알고리즘의 관계

[ 자료구조 ]

• 데이터 사이의 논리적 관계를 표현하고 조직화하는 방법
• 기본적/대표적 종류로는 배열, 연결 리스트, 스택, 큐, 트리, 그래프 등이 있다.

[ 효율적인 프로그램 ]

• 자료구조에 대한 고려 없는 효율적인 알고리즘의 선택은 무의미함.
• 알고리즘에 대한 고려 없는 효율적인 자료구조의 선택은 무의미함.
• 즉, 적절한 자료구조와 알고리즘이 적절히 합쳐져 조화를 이루면 효율적인 프로그램(알고리즘)을 만들 수 있음.

---

✅ 2. 알고리즘의 설계

• 효율적인 알고리즘을 만들기 위한 첫 번째 단계이다.

(1) 최대값을 찾기 - 알고리즘 예시

• 해당 알고리즘은 최소/최대값 찾기에 해당하기 때문에 모든 원소를 순차적으로 확인해야 하는 문제이다.
• 모든 데이터를 한 번씩 확인해야 하는 문제에서는 n개의 데이터가 주어질 때 n-1 번의 연산을 수행하는 알고리즘이 가장 효율적인 즉, 최소한의 연산 횟수가 된다.
• 알고리즘 1과 2는 각각 7번의 연산으로 동일한 효율성을 나타내고 있다.

(2) 뒤섞인 카드 중에서 원하는 카드 찾기 - 알고리즘 예시

• 순차 탐색: 배열이나 연결 리스트와 같은 선형 자료 구조에서 특정한 값을 찾는 가장 기본적인 탐색 알고리즘이다.
• 정렬되지 않은 카드 더미에서 원하는 카드를 찾는 가장 직관적이고 현실적인 방법임.
• 즉, 정렬이 되어있다면 다른 탐색 방법이 더 효율적일 수 있음.

(3) 순서대로 나열된 카드 중에서 찾기 - 알고리즘 예시

• 이진 탐색: 절반씩 잘라가면서 원하는 값을 찾아나가는 방식이다. 정렬된 자료에서만 사용이 가능함.
• 즉, 정렬된 자료의 개수(n)가 많아질수록 순차 탐색보다 훨씬 빠르고 효율적이게 된다.
• 예시에서 순서대로 나열된 경우를 보면 이진 탐색을 쓰게 되면 가운데 7을 보고 왼쪽은 제외 할 수 있게 되며, 오른쪽 가운데를 보고 마지막 왼쪽에 10이 있다는 것을 알 수 있게됨. 즉, 3번만에 찾을 수 있어 매우 효율적임.

(4) 알고리즘 설계에 적용할 방법

[ 어떤 알고리즘이 좋은가? ]

• 어떤 알고리즘이 좋은가? 는 문제에 따라 다르고, 해당 문제는 무수히 많기 때문에 방법 또한 매우 다양함.
• 그래서 주어진 문제와 그에 따른 조건등이 매우 다양하므로 해당 문제에 필요한 알고리즘을 직접 설계해야함.
• 즉, 일반적이고 범용적인 설계 기법은 사실상 존재하지 않음.
• 그렇지만 모든 문제는 아니지만 많은 문제에 적용될 수 있는 대표적인 설계 기법이 존재함.

[ 대표적인 설계 기법 ]

• 분할정복(divide-and-conquer) 방법
• 동적 프로그래밍(dynamic programming) 방법
• 욕심쟁이(greedy) 방법

(5) 분할정복 방법 ( 대표적인 알고리즘 설계 기법 )

• 순환적(재귀)으로 문제를 푸는 방법으로 복잡한 문제를 작은 부분 문제로 나누어 해결하는 알고리즘 설계 패러다임이다.
• 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제로 순환적으로 분할하고, 분할된 문제들을 각각 해결한 후 이들의 해를 결합하여 원래 문제의 해를 구하는 하향식 접근 방법이다.

[ 특징 ]

• 분할된 작은 문제는 원래 문제와 동일, 단 입력 크기만 작아짐
• 분할된 작은 문제는 서로 독립적임.

(6) 동적 프로그래밍 방법 ( 대표적인 알고리즘 설계 기법 )

동적 프로그래밍 대표적 예시

• 최적화 문제의 해(최댓값, 최솟값)를 구하기 위한 상향식 접근 방법이다.
• 문제의 크기가 작은 소문제에 대한 해를 구해서 테이블에 저장해 놓고, 이를 이용하여 크기가 보다 큰 문제의 해를 점진적으로 만들어 가는 방법이다. ( 소문제들이 서로 독립일 필요 없음 )
• 문제를 분할 정복처럼 쪼개어보니 겹치는 부분 문제들이 존재할 경우 사용 할 수 있는 방법이다. ( 핵심 키워드: 재사용 )

(7) 욕심쟁이 방법 ( 대표적인 알고리즘 설계 기법 )

욕심쟁이 방법 예시

• 해를 구하는 일련의 선택 과정마다 전후 단계의 선택과는 상관없이 각 단계에서 '가장 최선'이라고 여겨지는 국부적인 최적해를 선택해 나가면 결과적으로 전체적인 최적해를 얻을 수 있을것이라고 희망하는 방법 ( 각 단계 마다 최선의 대한 욕심 )
• 희망하다 라고 하기 때문에, 각 단계의 최적해를 통해 전체적인 최적해를 만들어 내지 못할 수 있음.
• 욕심쟁이 방법에서 "가장 좋아 보이는 것"이라는 표현은 종종 **'최댓값' 또는 '최솟값'**과 같은 최적의 값을 의미한다.

(8) 대표적 알고리즘 설계 기법 정리

• 분할 정복, 동적 프로그래밍, 욕심쟁이 방법 세 가지 방법은 문제를 해결하기 위한 설계자의 마음가짐에 가까움
• 분할 정복: 큰 문제를 감당할 수 없으니, 여러 개로 쪼개서 각자 해결하자.
• 동적 프로그래밍: 풀다 보니 똑같은 문제가 자꾸 나오네? 한 번 푼 답은 잘 적어뒀다가 다시 써먹어야겟다.
• 욕심쟁이 방법: 다른 건 생각하지 말고, 지금 당장 가장 좋은 선택만 계속하자

---

✅ 3. 알고리즘의 분석

• 설계가 된 알고리즘을 분석하는 것을 의미함.

(1) 정확성 분석 ( 복잡하고 어렵기 때문에 잘 다루지 않는 내용이 됨. )

• 유효한 입력과 유한한 시간내에 내가 원하는 정확한 결과가 생성 되는가를 판단함.
• 이러한 확인하는 과정은 다양한 수학적 기법을 사용한 이론적 증명을 하는 과정임.
• 정확성 분석이 이미 된 알고리즘을 보통 효율성 분석을 함 우린.

(2) 효율성 분석 ( 대부분 이걸 사용 )

• 알고리즘 수행에 필요한 컴퓨터 자원의 양을 측정하고 평가하는 것을 의미함. ( 핵심은 메모리, CPU 임 )
• 공간 복잡도: 메모리의 양 = 정적 공간 + 동적 공간 ( 메모리 공간을 얼마나 사용하는지 따짐 )
• 시간 복잡도: CPU와 관련해서 알고리즘의 수행 시간이 얼마나 걸리느냐를 따지는 것을 의미함.

(3) 시간 복잡도

[ 시간 복잡도의 핵심 원리 ]

• 시간 복잡도는 알고리즘의 효율성을 객관적으로 평가하기 위한 기준임.
• 컴퓨터의 속도, 언어 등 외부 요인에 따라 달라지는 **실제 시간(초 단위)**이 아니라, **알고리즘의 '연산 횟수'**를 측정한다.
• 이는 알고리즘 자체의 순수한 성능을 비교하는 데 목적이 있음.
• 즉, 시간 복잡도에서 말하는 '수행 시간'은 실제로 걸리는 초 단위의 시간이 아니라, 알고리즘의 연산 횟수를 의미함.
• 핵심은 알고리즘이 문제를 해결하기 위해 수행하는 계산, 비교, 대입 등의 기본적인 연산이 몇 번 일어나는지를 세는 것임.

[ 시간 복잡도를 나타내는 두 가지 기준 ]

• [ 1. 입력 크기의 함수 ]
• 알고리즘의 연산 횟수를 입력 데이터의 크기(N)에 대한 함수로 표현합니다. 
• 즉, 데이터가 N개일 때 연산이 몇 번 발생하는지 (T(N))를 나타내는 것입니다. 
• 예를 들어, 데이터가 2배 늘어나면 연산 횟수도 2배 늘어나는 관계를 O(N)으로 표현합니다.
• [ 2. 최악 수행 시간 ]
• 입력 데이터의 상태에 따라 알고리즘의 성능이 달라질 수 있기 때문에, 가장 느리게 동작하는 최악의 경우를 기준으로 성능을 평가합니다. 
• 최악의 경우를 파악하면, "이 알고리즘은 아무리 나쁜 상황이 와도 이 시간(연산 횟수)을 넘지 않는다"라는 성능의 상한선을 보장할 수 있어 가장 안전한 기준이 됩니다.

(4) 점근성능

• 점근성능이란 입력 크기 n이 매우 커질 때 알고리즘이 어떻게 동작하는지, 즉 성장률을 중심으로 한 성능을 의미한다.
• 실제 실행 시간이나 메모리 사용량을 정확히 측정하는 것이 아니라, 입력이 커질수록 증가하는 속도를 분석한다.
• 주로 Big-O, Big-Ω, Big-Θ 같은 점근적 표기법으로 표현을 한다.

• 작은 n에서는 B 알고리즘이 느릴 수 있지만, n이 충분히 커지면 n^2인 A가 더 느리다는 것을 점근성능 분석으로 알 수 있음.
• 점근성능은 알고리즘의 수행시간이 다항식으로 표현이 되었을 때, 해당 다항식의 최고차항을 이용해서 표기하는것을 의미함.

(4) 점근성능의 표기법

• 점근성능을 분석하면 입력 크기 𝑛 이 커질 때 알고리즘이 어떻게 동작하는지 알 수 있고, 이를 수학적으로 표현한 대표적인 성능 지표가 점근적 상한(Big-O), 점근적 하한(Big-Ω), 점근적 상하한(Big-Θ) 세 가지이다.

[ 점근적 상한 (Big-oh) ]

• 입력 함수 𝑓(𝑛) 이 𝑐𝑔(𝑛) 보다 항상 작거나 같아지는 순간부터, 우리는 𝑓(𝑛) 의 점근적 상한을 𝑔(𝑛) 이라고 정의함.
• 𝑓(𝑛) : 입력 n을 넣으면 수행량이 얼마인지 알려주는 함수입니다.
• 𝑔(𝑛) : 성장을 비교할 기준이 되는 함수임. 흔히 알고리즘의 복잡도를 나타낼 때 쓰이는 표준 함수 (예: 𝑛, 𝑛^2 , log 𝑛)
• 𝑐 : f(n)과 g(n) 사이의 크기 차이를 조정하는 상수이다.
• 𝑛0​ : 충분히 큰 입력 크기
• 최대 성장률을 나타내는 개념이다.
• 알고리즘이 최악의 경우 얼마나 느려질 수 있는지 상한선을 제공한다.
• 실제 실행 시간보다는 입력 크기 증가에 따른 증가 속도를 보는 데 초점이 있음.

[ 점근적 하한 (Big-omega) ]

• 입력 함수 𝑓(𝑛)이 𝑐𝑔(𝑛) 보다 항상 크거나 같아지는 순간부터, 우리는 𝑓(𝑛) 의 점근적 하한을 𝑔(𝑛) 이라고 정의함.

[ 점근적 상하한 (Big-theta) ]

• 점근적 상한(Big-O)은 함수 𝑓(𝑛)이 기준 함수 𝑔(𝑛)보다 충분히 큰 입력에서 위로 넘어가지 않는 최대 성장률, 점근적 하한(Big-Ω)은 𝑓(𝑛) 이 𝑔(𝑛) 보다 충분히 큰 입력에서 아래로 내려가지 않는 최소 성장률, 점근적 상하한(Big-Θ)은 𝑓(𝑛) 이 𝑔(𝑛) 과 같은 성장 속도로 상한과 하한 사이에 끼어 있는 경우를 의미한다.

[ 점근성능 표기 다항식 표기 ]

---

✅ 4. 정렬 알고리즘: 선택 정렬, 버블 정렬, 삽입 정렬

(1) 정렬(sort) 이란?

• 주어진 데이터를 어떤 기준(순서)에 따라 재배열하는 과정을 의미한다.
• 컴퓨터에서 가장 많이 사용되는 연산 중 하나임.
• 정렬 수행 시점에 데이터가 저장되는 곳에 따라서 내부정렬, 외부정렬로 나뉜다.
• 내부정렬: 모든 데이터를 주기억장치에 적재한 후 정렬하는 방식을 의미함. ( 모든 데이터가 메모리에 들어갈 수 있을 때 가능 )
• 외부정렬: 모든 데이터를 주기억장치에 저장할 수 없는 경우(즉, 데이터가 큰 경우) 전체 데이터를 보조기억장치에 저장하고 그 중의 일부 데이터를 번갈아 가면서 주기억장치로 적재해서 정렬하는 방식을 의미함.

(2) 내부정렬

• 모든 데이터를 주기억장치에 저잭한 후 정렬하는 방식
• 정렬 방식에 따라 크게 비교기반, 분포기반 두 가지로 나뉨.
• 비교 기반: 어떤 데이터를 정렬할 때 두 값을 비교해서 크거나 같다 이러한 조건에 따라 정렬을 수행하는 것
• 분포 기반: 데이터가 어떤식으로 분포하고 있다라는 정보를 사전에 미리 알아서 그 정보를 바탕으로 정렬을 수행하는 것

[ 비교 기반 ]

• 선택(selection) 정렬 - O(n^2)
• 버블(bubble) 정렬  - O(n^2)
• 삽입(insertion) 정렬  - O(n^2)
• 퀵(quick) 정렬 - O(nlogn)
• 합병(merge) 정렬  - O(nlogn)

[ 분포 기반 ]

• 계수(countion) 정렬 - O(n)
• 기수(radix) 정렬  - O(n)
• 사전에 이미 알고 있는 정보를 활용하기 때문에 단순히 성능면에서는 분포기반이 우월함.

(3) 정렬을 위한 기본 가정

(3) 선택정렬

• 정렬되지 않은 데이터 중에서 가장 작은(또는 큰) 값을 선택해 앞에서부터 차례대로 자리 바꾸는 정렬 방법
• 이름 그대로 “선택” + “정렬”이에요.
• 위와 같이 정렬을 위한 기본 가정에서 선택 정렬을 하게 될 경우

• 선택정렬 알고리즘에 따라서 해당 방식으로 정렬이 되게 된다.

• 데이터 개수만큼 반복을 하면 정렬을 할 수 있게 된다.
• 최소값을 반복적으로 찾아서 정렬을 해주는 방식이 될 수 있다.
• 즉, 데이터 n개가 주어질 때 n-1 번의 비교가 필요하게 될 것이고, 이후 다음 최소값 또한 n - 1의 n - 2번의 비교가 필요해진다.
• 즉, 수식을 정리하면 결과는 O(n^2) 이 된다.
• 결과적으로 언제나 동일한 수행 시간을 갖게된다.

(4) 버블정렬

• 인접한 두 원소를 비교해서 큰 값을 뒤로 보내는 정렬임. 이름 그대로 거품처럼 큰 값이 위로 올라가는 모습에서 유래됨.
• 위와 같이 정렬을 위한 기본 가정에서 버블 정렬을 하게 될 경우

 

• 왼쪽 오른쪽 비교를 통해서 오른쪽으로 큰 값을 밀어줌을 반복하다보면 정렬이 됨.

[ 버블 정렬의 특징 ]

• 원하는 순서로 이미 정렬이 되어 있는 경우에는 비교가 없이 바로 수행이 되기 때문에 매우 빠를 수 있음.
• 하지만, 역순으로 정렬되어 있는 경우에는 최악의 경우 O(n^)이 될 수 있음.

(5) 삽입 정렬

• 주어진 데이터를 하나씩 뽑은 후, 나열된 데이터들이 항상 정렬된 형태를 가지도록 뽑은 데이터를 바른 위치에 삽입해서 나열하는 방식이다.
• 입력 배열을 정렬 부분과 미정렬 부분으로 구분하고
• 미정렬 부분의 가장 왼쪽에 있는 데이터(첫 번째 데이터)를 뽑은 후 정렬된 부분에서 제자리를 찾아서 삽입하는 과정을 반복\
• 이미지의 원리는 맨 앞 부분의 데이터인 20을 가장 근접한 40과 비교 후 앞으로 옮기고, 이후 다음 30과 비교후 앞으로 옮김 그리고 10과 비교후 본인이 더 크다면 그 뒤에 배치가 됨. ( 즉, 본인 보다 작으면 그 뒤에 삽입이 됨. )
• 핵심은 정렬되지 않은 부분의 첫 번째 부분과 정렬된 오른쪽 끝부터 비교하면서 넣게됨.

• 이미 정렬이 되어있는 경우가 최선의 경우, 역순으로 정렬된 경우를 삽입 정렬에선 최악의 경우로 본다.