한국방송통신대 알고리즘 강의 1강 정리노트입니다.
시작하며
💡 알고리즘 과학
데이터를 컴퓨터에 입력하고, 정보를 만드는 과정에서, 프로그램은 데이터를 처리해 결과를 만드는 도구다. 프로그램은 알고리즘을 기반으로 동작한다.
컴퓨터과학은 컴퓨터 + 데이터 + 프로그램 + 알고리즘의 결합이다.
🎯 학습 목표
- 컴퓨터를 이용해 문제 해결 방법에 대해 체계적으로 생각하는 훈련을 한다.
- 문제 해결을 위한 지적 추상화 능력 및 통찰력을 향상시킨다.
- 문제 풀이 절차와 방법을 통해 효율적인 알고리즘을 만든다.
알고리즘
👉 주어진 문제를 해결하거나 함수를 계산하기 위해 따라야할 명령어를 단계적으로 나열한 것
- 입출력: 0개 이상의 외부 입력과, 1개 이상의 출력 생성
- 명확성: 각 명령은 모호하지 않고 단순 명확해야 한다.
- 유한성: 한정된 수의 단계를 거친 후에 반드시 종료
- 유효성: 모든 명령은 컴퓨터에서 수행할 수 있어야 한다.
알고리즘이 존재하면 컴퓨터를 통해 해결할 수 있다.
다만 실용적 관점에서, 알고리즘은 효율적이어야 한다.
📌 예시: 문제의 규칙 찾기
최소값 찾기
- 첫 번째 데이터를 최솟값으로 저장
- 다음 숫자를 읽고, 이것과 저장된 최솟값을 비교
- 비교 후 더 작은 숫자를 최솟값으로 다시 저장
- 다음에 처리할 데이터가 있으면 2로
- 저장된 최소값을 결과로 출력
오일러 경로 문제: 퀘닉스 버그 다리
- 그래프의 모든 간선을 단 1번만 지나가는 경로의 존재 여부
- 각 정점의 차수가 홀수인 정점이 0개 혹은 2개
- 홀수점이 2개인 경우, 홀수점에서 시작한다.
최단경로 찾기
- 단일 출발점 최단 경로
- 다익스트라 알고리즘
알고리즘 생성
- 설계: 상향식, 하향식 설계
- 표현: 일상 언어, 순서도 flow chart, 의사 코드, 프로그래밍 언어
- 검증: 수학적 증명
- 분석: 시간 복잡도, 공간 복잡도
알고리즘 설계
적용 가능한 풀이 방식 중 더 효율적인 방식을 찾는다.
효율성의 기준: 시간 복잡도/공간 복잡도아래는 알고리즘 설계에 대한 예시이다.
📌 탐색 알고리즘
정렬된 배열에서 이진 탐색 O(log n)은 순차 탐색 O(n) 보다 효율적이다.
하지만 정렬되지 않은 배열에서 이진 탐색은 사용할 수 없다.
👉 특정 알고리즘이 다른 알고리즘보다 무조건 좋지는 않다. 문제의 조건에 맞는 알고리즘을 사용한다.
📌 탐욕 알고리즘(greedy, 욕심쟁이)
해를 구하는 일련의 선택 과정에서, 전후 단계의 선택과는 상관없이, 가장 최선이라고 여겨지는 국부적인 최적해를 선택해, 결과적으로 전체적인 최적해를 구할 수 있을 것이라는 희망적인 전략이다.
단점: 국부적인 최적해들이 전체 최적해를 보장하지 않을 수 있다.- 거스름돈, 베낭
- 최소 신장 트리: 크루스칼, 프림 알고리즘
- 단일 출발점 최단 경로: 다익스트라 알고리즘
📝 거스름돈 문제
돌려줄 거스름돈 T가 있을 때, 고객이 받을 동전의 개수를 최소로 하기
- 액면가가 큰 순부터 가장 최선의 해를 구함
- 가장 큰 동전부터 선택하면 동전 개수가 최소가 될 것을 가정한 풀이법
탐욕 알고리즘을 사용했을 때, 만약 동전의 종류가 [500, 120, 100, 50, 10]이라면 650원의 값을 구하기 위해 실제 최적해 3개가 아닌, 5개의 결과를 도출하게 된다.
👉 동전의 단위가 서로 배수 관계일 때, 탐욕 알고리즘이 잘 동작한다.
👉 탐욕적 선택이 최적해를 보장하지 못하는 경우, DP와 같은 다른 방식을 사용한다.
📝 베낭 문제
- 최대 용량 M인 1개의 베날과, n개의 물체가 있다고 가정
- 각 물체 i는 무게 (w_i), 이익 (p_i)를 가짐
A. 물체를 쪼개서 넣을 수 있는 경우
베낭의 용량을 초과하지 않는 범위에서, 베낭의 물체 이익의 합이 최대가 되도록 물체를 넣는 방법
테스트 케이스에서 베낭 용량이 10이고, 물체가 4개, w=[3, 5, 3, 4], p=[15, 20, 9, 4]인 경우, 단위 무게(w) 당 이익은 [5, 4, 3, 3.5]으로, 물체는 0, 1, 3, 2 순으로 이득이다.
물체를 단위 무게 당 이익이 높은 순부터 순차적으로 베낭에 넣는다면
첫 번째 물체 0(w=3)을 넣으면 베낭의 남은 용량은 7이 된다.
두 번째 물체 1(w=5)를 넣으면 베낭의 남은 용량은 2가 된다.
세 번째 물체 3(w=4)를 남은 용량(2)만큼 넣으면 베낭의 남은 용량은 0이 된다.
최대 이익은 15 + 20 + 14/2 = 42가 된다.
B. 물체를 쪼갤 수 없는 경우: 0/1 베낭 문제
0/1 베낭 문제의 가정은 물체를 부분적으로 넣을 수 없는 경우이다. (물체의 삽입은 false/true)
만약 탐욕 알고리즘을 사용하여 문제를 풀이할 경우, 세 번째 물체를 넣을 수 없으므로 4의 용량이 남게 되어, 최대 이익은 35가 된다.
하지만 실제 최대 이익은 베낭에 10의 용량만큼 0, 2, 3번째 물건을 넣어서 나오는 38이다.
👉 따라서 0/1 베낭 문제는 탐욕 알고리즘으로 해결할 수 없다. (MP 완전, 근사 알고리즘)
📌 분할정복
하향식 접근 top-down
퀵 정렬, 합병 정렬, 이진 탐색
주어진 문제의 입력을 더 이상 나눌 수 없을 때까지 2개 이상의 작은 문제들로 순환적으로 분할하고, 분할한 작은 문제들을 각각 해결한 뒤, 해를 결합하여 원래 문제의 해를 구하는 방식
특징
- 분할된 작은 문제는 원래의 문제와 동일하다: 입력의 크기만 작아짐
- 분할된 문제는 서로 독립적이다: 순환적인 분할 및 결과의 결합
순환 호출 시, 작업 수행
- 분할: 주어진 문제의 입력을 여러 작은 문제로 분할한다.
- 정복: 작은 문제들을 순환적으로 분할한다. 만약 작은 문제가 더 분할되지 않을 정도로 크기가 작다면, 순환 호출 없이 작은 문제에 대한 해를 구한다.
- 결합: 작은 문제에 대해 정복된 해를 결합하여 원래 문제의 해를 구한다.
📝 이진 탐색
정렬된 데이터에서 목표값을 찾기 위해서 이진 탐색을 실행한다.
[10, 15, 20, 25, 30, 35, 40, 45, 50]에서 목표값 20을 찾기 위해서 이진 탐색을 실행하면 Mid를 4, 1, 2로 이동하여 3번 탐색만에 20의 위치인 인덱스 2를 반환할 수 있다.
- 분할: 배열의 가운데 원소를 기준으로 왼쪽 배열과 오른쪽 배열으로 분할한다. 탐색 키(목표값) Mid가 같다면 인덱스를 반환하고 종료한다.
- 정복: 탐색 키가 가운데 원소보다 작으면 왼쪽 배열을 대상으로 이진 탐색을 순환 호출하고, 아니라면 오른쪽 배열을 대상으로 이진 탐색을 순환 호출한다.
- 결합: x, 부분 배열에 대한 탐색 결과가 직접 반환되므로 결합이 불필요
동적 프로그래밍 Dynamic Programming: 상향식 접근 bottom-up
플로이드 알고리즘(모든 정점 쌍 간 최단 경로), 행렬의 연쇄적 곱셈, 최장 공통 부분 수열
입력의 크기가 가장 작은 부분문제부터 해를 구하여 테이블에 저장해놓고, 이를 이용하여 입력 크기가 보다 큰 문제의 해를 점진적으로 만들어가는 방식
특징
- 각각의 작은 문제는 원래의 문제와 동일하다: 입력의 크기만 작아짐
- 작은 문제는 서로 독립적일 필요가 없다: 문제가 겹쳐질 수 있음, 중복 계산을 막기 위해 테이블에 메모이제이션 한다.
