[내일배움캠프 Spring_3기] 알고리즘

알고리즘

알고리즘이란?

알고리즘(Algorithm)은 문제를 해결하기 위한 단계적 절차나 규칙을 의미

• 마치 요리 레시피처럼 시작부터 끝까지 어떤 순서로 무엇을 해야 하는지를 정확하게 적어놓은 것이라고 생각하면 됨

알고리즘의 중요성

1. 논리적 사고력 향상

• 문제를 해결하는 과정에서 체계적이고 논리적인 사고방식을 기를 수 있음

2. 효율적인 문제 해결

• 알고리즘 학습을 통해 더 빠르고 효율적인 코드를 작성할 수 있게 되며, 복잡한 문제를 분석하고 해결하는 능력을 향상시킬 수 있음

3. 취업에서의 중요성

알고리즘의 표현 방법

알고리즘을 다른 사람에게 전달하거나 구현하려면, 그 과정을 명확하고 간결하게 표현하는 것이 중요

• 이를 위해 자주 사용하는 대표적인 방법이 의사코드(Pseudocode)와 자연어 표기법

의사코드(Pseudocode)란?

의사코드는 프로그래밍 언어와 유사하지만 더 자유로운 형태의 표현 방식

특징

• 특정 프로그래밍 언어의 문법을 엄격히 지키지 않아도 됨
• 단계별 논리 흐름(조건, 반복 등)을 구조적으로 표현하기에 좋음
• 실제 코드로 옮기기 수월

예시) 최댓값 찾기 알고리즘

FUNCTION findMax(numbers):
    max ← numbers[0]
    FOR i = 1 TO length(numbers) - 1
        IF numbers[i] > max THEN
            max ← numbers[i]
        END IF
    END FOR
    RETURN max
END FUNCTION

자연어 표기법이란?

자연어 표기법은 일상적인 언어를 사용하여 알고리즘을 설명하는 방식

특징

• 비전문가도 쉽게 이해할 수 있음
• 전체적인 흐름이나 핵심 아이디어를 빠르게 전달하기 좋음
• 다만, 문장이 모호해질 수 있으므로 정확한 표현에 신경 써야함

예시) 최댓값 찾기 알고리즘

1. 첫 번째 숫자를 최댓값으로 저장한다.
2. 두 번째 숫자부터 마지막 숫자까지 순서대로 확인한다.
   - 현재 숫자가 저장된 최댓값보다 크면, 현재 숫자를 최댓값으로 갱신한다.
3. 모든 숫자를 확인한 후, 최댓값을 반환한다.

---

좋은 알고리즘의 조건

1. 정확성: 알고리즘이 정확하게 동작하는가?

• 입력한 값에 대해 올바른 결과가 나와야 함
• 정해진 단계를 따라 실행되고, 반드시 멈추는 시점이 있어야 함
• 같은 입력값이면 항상 같은 결과가 나와야함

2. 효율성: 알고리즘이 효율적인가?

• 시간 복잡도: 실행 시간이 너무 오래 걸리지 않아야 함
• 공간 복잡도: 컴퓨터의 메모리를 적절하게 사용해야 함

3. 명확성: 알고리즘이 이해하기 쉬운가?

• 각 단계가 명확하고 이해하기 쉬워야 함
• 다른 사람도 읽고 이해할 수 있어야 함
• 필요한 경우 주석으로 설명을 추가하면 좋음

4. 확장성: 알고리즘이 실용적이고 관리하기 좋은가?

• 다양한 상황에서 사용할 수 있어야 함
• 나중에 수정하거나 개선하기 쉬워야 함
• 문제가 생겼을 때 어디가 잘못됐는지 찾기 쉬워야 함

---

알고리즘 성능 분석

알고리즘 성능 분석이란?

알고리즘이 얼마나 효율적으로 동작하는지를 측정하는 방법
주로 시간(실행 속도)과 공간(메모리 사용량)을 기준으로 평가함

알고리즘의 성능을 분석할 때 가장 중요하게 살펴보아야 할 것이 바로 시간 복잡도!
-> 시간 복잡도는 알고리즘이 문제를 해결하는데 얼마나 많은 시간이 필요한지를 표현하는 방법
주로 빅오(Big-O) 표기법을 사용하여 나타냄

• 시간 복잡도는 프로그램의 응답 시간과 직결됨
• 반면 공간복잡도(메모리 사용)는 사용자가 직접 체감하기 어려움

빅오(Big-O) 표기법이란?

빅오 표기법은 알고리즘의 시간 복잡도를 수학적으로 표현한 방법
주로 입력 데이터의 크기가 늘어날 때 알고리즘의 실행 시간이 어떤 비율로 증가하는지를 표현함.
즉, 정확한 실행 시간이 아닌, 입력 데이터의 크기에 따라서 실행 시간의 증가 추세를 표현함

시간 복잡도 구하기

1. 명령문 개수 계산

• 반복문, 조건문, 대입문 등 각각의 명령문이 실행되는 횟수를 계산
• 각 줄의 실행 횟수를 더하여 전체 실행 횟수를 구함

2. 가장 큰 항만 남기기

   빅오 표기법에서는 가장 영향력이 큰 항만 고려하는 이유

   • 입력 크기(n)가 매우 커질 때는 작은 항들의 영향력이 미미해지기 때문
   • 상수항은 실제 실행 환경에 따라 달라질 수 있어서 제외
   • 증가 추세를 파악하는 것이 목적이므로 정확한 횟수보다는 전체적인 증가 패턴이 중요

   예시) 입력 데이터 크기가 n일 때 명령어 실행횟수가 T(n)인 경우 시간복잡도 계산

   T(n) = 5n³ + 100n² + 200n + 1000
   
   단순화 과정
   1. 최고차항 선택: 5n³
   2. 계수 제거: n³
   3. 다른 항 제거: n², n, 상수항 제거
   4. 최종 표기: O(n³)

시간 복잡도 비교 차트 및 실행시간 비교표

---

알고리즘 풀이 방법

알고리즘 문제 해결 5단계

1. 문제 이해 및 요구사항 분석하기

• 문제를 천천히 정독
• 예제 입출력을 통해 문제의 의도 파악
• 주어진 입력과 출력 형식을 정확히 파악
• 제약 조건과 요구사항 규칙 정리

2. 접근 방법 구상하기

• 비슷한 유형의 문제 생각하기
• 어떠한 유형의 알고리즘을 사용할지 정하기
• 문제를 해결하기 위한 기본 아이디어 고안 혹은 문제 해결 절차에 대해 단계별로 나누기 및 도식화

3. 세부 구현 설계 및 검토하기

• 문제 해결 절차의 각 단계를 의사코드로 표현하기
• 발생할 수 있는 예외 상황 찾아보기
• 극단적인 케이스 고려하기
• 시간 복잡도 분석하기

4. 코드 작성 및 구현하기

• 세부 구현으로 표현된 아이디어를 실제 코드로 작성하기
• 구현 과정에서 변수명, 함수명을 명확하게 작성하기

5. 테스트와 디버깅

• 다양한 테스트 케이스를 통해 코드의 정확성을 검증하기
• 오류가 발생하면 디버깅하기
• 시간 초과의 경우 아이디어 수정 및 코드 최적화하기

---

알고리즘 유형

구현(Implementation) & 시뮬레이션(Simulation)

특징

• 코딩 테스트에서 가장 기본이 되는 문제 유형
• 알고리즘적 난이도보다는 구현의 정확성이 중요
• 요구사항을 빠짐없이 코드로 옮기는 것이 핵심
• 문제의 조건과 제약을 정확히 이해하고 처리해야 함

• 구현 과정에서 자잘한 실수(인덱스 범위, 예외 상황 처리 등)를 하기 쉽기 때문에 꼼꼼함이 중요
• 디버깅을 통한 중간 결과 검증이 매우 중요

구현 및 시뮬레이션의 주요 유형
1. 단순 구현: 주어진 알고리즘이나 규칙을 그대로 코드로 옮기는 문제

• 예) 날짜/시간 계산, 진법 변환, 문자열 처리 등

2. 완전 시뮬레이션: 문제에서 제시된 과정을 처음부터 끝까지 실행하여 결과를 도출하는 문제

• 예) 주사위 게임, 카드 게임, 보드 게임 시뮬레이션 등

3. 상태 변화 시뮬레이션: 특정 조건에 따라 시스템의 상태가 변화하는 과정을 구현하는 문제

• 예) 로봇 이동, 뱀 게임, 벽돌 깨기 게임 등

4. 규칙 찾기 및 구현: 문제의 숨겨진 규칙을 찾아 이를 코드로 구현하는 문제

• 예) 달팽이 배열, 소용돌이 수, 패턴 인식 등

완전 탐색(Brute Force)

모든 경우의 수를 빠짐없이 조사하여 정답을 찾는 바업ㅂ

특징

• 모든 경우를 시도하므로, 정답을 놓칠 가능성이 없음
• 입력 규모가 작을 때 유리하며, 구현이 비교적 간단

구현 방법
1. 반복문을 이용한 구현
2. 재귀 함수를 이용한 구현

대표적인 문제 유형
1. 순열/조합 계산

• 예) N개 중 K개를 고르는 모든 조합, N개 전부를 나열하는 모든 순열 등

2. 부분집합 계산

• 예) 부분집합의 합으로 특정 값을 만드는 모든 경우 확인

3. 그래프 전체 탐색

• 예) 모든 경로 찾기, 모든 노드 방문 시뮬레이션, DFS/BFS를 통한 모든 가능성 확인

그리디(Greedy) 알고리즘

매 순간 가장 최선의 선택을 함으로써 전체 최적해를 구하는 방식

특징

• 다른 알고리즘(예: 완전탐색, 동적 계획법 등)보다 일반적으로 구현이 간단하고, 빠른 시간 안에 결과를 얻을 수 있음

그리디 알고리즘의 적용 조건
1. 탐욕 선택 속성(Greedy Choice Property)

• 매 순간의 최선의 선택이 전체 문제의 최적해가 되어야 함

2. 최적 부분 구조(Optimal Substructure)

• 부분 문제의 최적해들을 결합해 전체 문제의 최적해를 구할 수 있어야 함

대표적인 문제 유형
1. 거스름돈 계산

• 동전 단위가 특정 조건(예: 배수 관계)에 부합할 때, 큰 단위 동전부터 먼저 사용

2. 회의실 배정 문제

• 종료 시간이 빠른 회의부터 배정하는 방식으로 최대 개수를 찾는 문제

3. 최소 신장 트리(MST)

• 크루스칼(Kruskal), 프림(Prim) 알고리즘

백트래킹(Backtracking)

완전 탐색을 기반으로 하되, 유망하지 않은 경우(조건 불만족)는 미리 배제(가지치기) 하여 탐색 효율을 높이는 기법

특징

• 조건을 만족할 수 없는 상황을 빠르게 배제할 수 있어, 탐색 범위를 크게 축소할 수 있음
• 대부분 재귀 함수로 구현

백트래킹의 적용 조건
1. 상태 공간 트리 구성 가능성

• 문제의 해결 과정을 트리 형태로 구조화할 수 있어야함
• 각 단계별 선택지를 명확하게 정의할 수 있어야함

2. 유망성 판단 기준(Promising)

• 현재 상태에서 더 진행할 가치가 있는지 판단할 수 있는 명확한 기준이 있어야 함

3. 가지치기 효율성

• 유망하지 않은 경우를 제외했을 때 탐색 범위가 충분히 줄어들어야 함
• 가지치기 조건 검사가 너무 복잡하지 않아야함

대표적인 문제 유형
1. N-Queen 문제
2. 스도쿠 풀이
3. 부분집합의 합

분할 정복(Divide and Conquer)

문제를 작거나 유사한 하위 문제로 분할하고, 각 문제를 해결한 뒤 결과를 합쳐 최종 해를 구하는 방식

특징

• 분할 -> 정복(해결) -> 병합 단계를 거침
• 분할된 각 부분 문제는 서로 독립적이어야 함

분할 정복의 적용 조건
1. 분할 가능성(Divisibility)

• 문제가 동일한 유형의 더 작은 하위 문제들로 나눠질 수 있어야 함
• 분할된 문제는 원래 문제와 같은 성질을 가져야 함

2. 하위 문제의 독립성(Independence)

• 분할된 하위 문제들은 서로 독립적이어야 함
• 어떤 하위 문제의 해결이 다른 하위 문제의 해결에 영향을 주지 않아야 함

3. 병합 가능성(Mergeability)

• 하위 문제들의 해답을 병합하여 원래 문제의 해답을 만들 수 있어야 함

대표적인 문제 유형
1. 병합 정렬(Merge Sort)

• 배열을 반으로 나눈 뒤 각각 정렬 후 병합

2. 퀵 정렬(Quick Sort)

• 피벗(Pivot)을 기준으로 왼쪽은 피벗보다 작은 요소들, 오른쪽은 큰 요소들로 재귀적 정렬

3. 이진 탐색(Binary Search)

• 검색 구간을 절반씩 줄여가며 원하는 값을 찾는 방법

동적 계획법(Dynamic Programming, DP)

큰 문제를 작은 부분 문제들로 나누고, 각 부분 문제의 해를 저장(메모이제이션)하여 재활용함으로써 전체 문제의 최적 해를 구하는 알고리즘 설계 기법

특징

• 중복 계산을 획기적으로 줄일 수 있어, 지수 시간이 걸리는 문제도 다항 시간 안에 풀 수 있는 경우가 많음
• Top-Down 방식(메모이제이션) 또는 Bottom-up 방식(타뷸레이션)으로 구현함
• 점화식을 올바르게 세우는 것이 핵심

동적 계획법의 적용 조건
1. 최적 부분 구조(Optimal Substructure)

• 작은 부분 문제들의 최적 해들을 조합하여 큰 문제의 최적 해를 구할 수 있어야 함

2. 중복되는 부분 문제(Overlapping Subproblems)

• 동일한 작은 문제들이 반복적으로 나타나야 함
• 이러한 중복 문제들의 해를 저장해두고 재활용할 수 있어야 함

대표적인 문제 유형
1. 수열 문제

• 피보나치 수열: f(n) = f(n-1) + f(n-2)

2. 최적화 문제

• 배낭 문제(Knapsack Problem): 무게 제한이 있는 배낭에 물건들을 넣을 때, 가치의 합이 최대가 되도록 물건을 고르는 문제
• 최장 증가 부분 수열(LIS: Longest Increasing Subsequence): 주어진 수열에서 증가하는 부분 수열 중 가장 긴 길이 찾기

3. 경로 문제

• 미로 찾기(최단 경로)