[알고리즘] 1강 - 알고리즘 소개(1)

✅ 1. 알고리즘 소개

(1) 알고리즘 이란?

• 알고리즘이란, 문제를 해결하기 위해 정해진 일련의 절차나 규칙을 의미한다.
• 이러한 알고리즘을 통해 만들어진 절차나 규칙이 프로그래밍 언어로써 구현이 되면 그때 프로그램이 된다.
• 이후, 이러한 프로그램은 컴퓨터에서 데이터를 받아 처리되어 정보로 가공이 되는 역할을 한다.

---

✅ 2. 기본 개념

• 컴퓨터를 활용해서 주어진 문제를 해결하기 위한 학문이 컴퓨터 과학임.
• 알고리즘: 위와 같은 문제를 해결하기 위한 풀이 방법 또는 절차를 의미한다.
• 또한, 효율적인 알고리즘을 만드는것이 핵심 목표임.

(1) 알고리즘 정의

• 위와 같은 정의는 해당 문제를 이론적으로 컴퓨터를 통해서 해결할 수 있느냐 없느냐를 따지는 중요한 조건임.

(2) 알고리즘 생성 단계

• 효율적인 알고리즘을 만들기 위해서는 위와같은 생성 단계가 필요함.

(3) 알고리즘의 표현/기술 방법

• 알고리즘 설계 이후 의사코드를 통해서 표현/기술을 할 수 있음.

• 의사 코드 뿐 아니라 순서도로 표현/기술을 할 수 있음.

---

✅ 3. 알고리즘 설계

(1) 최솟값 찾기 알고리즘

• 최솟값을 찾는 알고리즘은 위와같이 여러가지 방식이 존재하며, 핵심은 둘 중 어떤것이 더 효율적인 알고리즘인가를 찾는것임.
• 결론은 둘 다 비교횟수는 7번으로 동일함.

(2) 탐색 알고리즘 - 순차 탐색

• 순차 탐색: 앞에서부터 하나씩 찾아가는 방식의 탐색 알고리즘을 순차 탐색이라고 함.

(3) 탐색 알고리즘 - 이진 탐색

• 이진 탐색: 가운데 숫자를 파악하면서 왼쪽 작은 값 오른쪽 큰 값을 기준으로 찾아나가는 탐색 방식이다.
• ** 이진 탐색은 순차 탐색보다 비교 횟수가 적어 찾는 속도가 빠르지만, 정렬된 데이터만 찾을 수 있다는 문제가 있음. **

• 알고리즘은 주어진 문제와 조건등이 매우 다양하기 때문에, 일반적/범용적인 설계 기법은 존재하지 않음.
• ** 하지만, 주로 많이 사용이 되는 설계 기법은 존재함. ( 욕심쟁이, 분할정복, 동적 프로그래밍 ) **

(4) 욕심쟁이 방법

• ** 문제를 해결하는데 필요한 각 단계마다 가장 최선이라고 여겨지는 선택을 해나가는 방식임 ( 매우 욕심쟁이임. ) **
• ** 하지만, 항상 최적해를 보장해주지는 못하는 한계가 존재함. **

• 쉽게말해, 가장 멋진 바지, 가장 멋진 넥타이, 가장 멋진 자켓 각각은 그 카테고리에서 1등일지 몰라도, 이걸 한꺼번에 입은 멋쟁이씨는 패션 테러리스트에 가까울 수 있음.
• ** 이와 같이 각각의 최적해를 구했지만 각각의 아이템들이 얼마나 잘 어우러지느냐에 결정되기 때문에 욕심쟁이 방법으로는 전체 최적해를 구할 수 없을 가능성이 매우 높음. **
• 국부적 최적해: 현재 위치에서 가장 최선이라고 여겨지는 선택을 하는 것임.
• 전체 최적해: 전체적으로 봤을 때 각 선택들에 대한 해가 모여 만들어진 최적인 해를 의미함.

(5) 욕심쟁이 방법 - 거스름돈 문제

• 쉽게말해, 1000원으로 220원짜리 물건을 샀다고 가정하면, 거스름돈으로 780 원을 받아야 함.
• ** 이 과정에서 780원 거스름돈의 동전 개수를 최소로 하면서 받게 되면, 500(1), 100(2), 50(1), 10(3) 으로 전체 최적해를 구할 수 있음. **

• 하지만, 이와 같이 동전의 단위가 120원과 같이 추가가 된다면 욕심쟁이 방법으로는 문제를 해결할 수 없다는 한계가 존재함.
• ** 650원 = 500(1), 120(1), 10(3) = 총 5개 / 최적해 = 500(1), 100(1), 50(1) = 총 3개 **

(6) 욕심쟁이 방법 - 배낭 문제

• 쉽게말해, 배낭에는 10만큼의 물체를 넣을 수 있으며, p 는 이익을 나타내며, w 는 무게를 나타낸다.
• 이때, 배낭에 물체를 넣을 때 배낭의 무게를 초과하지 않으며, 이익이 가장 큰 경우를 구하는 문제임.
• 조건: 물체는 쪼갤 수 있음.
• 해결: 단위 무게당 이익이 가장 큰 물체부터 최대한 넣는 과정을 반복하면 됨.

• 물체당 이익과 무게를 나누면 단위 무게당 이익을 구할 수 있게 됨.
• ** 해당 이익 중 가장 큰 단위 무게당 이익을 순서대로 넣게 되면 문제는 해결 됨. **

• ** 이전의 배낭 문제와는 다르게 물체를 쪼갤 수 없는 형태의 배낭 문제의 경우에는 욕심쟁이 방법으로 해결이 불가능함. **

(7) 분할정복 방법

• 분할정복 방법: 더 이상 나눌 수 없을 때까지 문제를 쪼개고, 쪼갠 문제를 해결 한 뒤 다시 결합하여 해를 구하는 방식이다.

• 분할, 정복, 결합 단계를 내부적으로 수행하는 과정을 거치게 되며, 대표적으로 퀵 정렬, 합병 절렬, 이진 탐색 등이 있다.

(8) 분할정복 방법 - 이진 탐색

• 이진 탐색 알고리즘은 분할정복 방법을 구현한 알고리즘으로 볼 수 있음.

(9) 동적프로그래밍 방법

• 동일한 작은 문제들이 반복해서 나타나는 경우와 부분 문제의 최적 결과가 전체 문제의 최적 결과를 구성하는 경우 사용됨.