# 알고리즘
**주어진 문제를 해결하기 위한 일련의 절차나 방법을 순서대로 기술한 것**
- 알고리즘은 문제 해결을 위한 과정을 단계별로 나누어 표현한 것으로, 효율적인 알고리즘이 중요하다.
- 알고리즘의 필요성
- 문제 해결에 있어 다양한 접근 방식과 효율성을 이해하고 평가할 수 있다.
- 컴퓨터 자원을 효율적으로 사용하여 빠르고 정확한 결과를 도출한다.
- 알고리즘 지식을 바탕으로 최적의 해결책을 찾아내고, 프로그래밍 역량을 향상시킨다.
## 좋은 알고리즘
- 알고리즘의 평가할 땐 **정확성**과 **효율성**이 중요시된다.
- 따라서 좋은 알고리즘은 정확하고 효율적이어야 한다.
> ex) 사전에서 원하는 단어를 찾아야 한다면?
## 시간복잡도와 공간복잡도
- 시간 복잡도(Time Complexity)
- 알고리즘이 수행하는데 걸리는 시간을 표현한 것
- 시간 복잡도는 입력 크기에 따라 증가하는 속도로 나타낸다.
- 낮은 시간 복잡도를 가진 알고리즘이 더 빠르게 문제를 해결한다.
- 공간 복잡도(Space Complexity)
- 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 표현한 것
- 공간 복잡도 역시 입력 크기에 따라 증가하는 속도로 나타낸다.
- 낮은 공간 복잡도를 가진 알고리즘이 더 적은 메모리 공간을 사용한다.
## Big O 표기법
- 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 표기법
- 알고리즘의 효율성을 **대략적으로** 평가할 수 있다.
- 입력 크기에 따른 알고리즘의 성능 증가 속도를 표현한다.
### Big O 표기법의 예시
- `O(1)`
- `O(log n)`
- `O(n)`
- `O(n log n)`
- `O(n^2)`
- `O(n^3)`
- `O(2^n)`
- `O(n!)`
## 알고리즘의 조건
- 입력 - 알고리즘은 0 또는 그 이상의 외부에서 제공된 자료가 존재해야한다.
- 출력 - 알고리즘은 최소 1개 이상의 결과를 가져야한다.
- 명확성 - 알고리즘의 각 단계는 명확하여 애매함이 없어야 한다.
- 유한성 - 알고리즘은 단계들을 유한한 횟수로 거친 후 문제를 해결하고 종료해야 한다.
- 효과성(수행가능성) - 알고리즘의 모든 연산들은 사람이 종이와 연필을 이용하여 유한한 시간 안에 정확하게 수행할 수 있을 정도로 충분히 단순해야 한다.
## 알고리즘 설계 방법의 종류
컴퓨터의 많은 알고리즘은 모두 기발안 아이디어에 기반하고 있지만. 큰 틀의 관점에서 다음의 알고리즘 설계 방법을 배워본다.
- 브루트 포스: 가능한 모든 경우의 수를 탐색하여 최적의 해를 찾는 방법. (비효율적일 수 있으나 확실한 해결책을 제공한다)
- 그리디 알고리즘: 각 단계에서 최적의 선택을 하여 전체 문제의 해를 찾는 방법. (항상 최적의 해를 보장하지는 않는다)
- 재귀 알고리즘: 함수가 자기 자신을 호출하여 문제를 더 작은 단위로 나누어 해결하는 방법
- 분할 정복: 문제를 작은 하위 문제로 분할한 후, 각 하위 문제를 해결하고 결과를 결합하여 원래 문제의 해를 찾는 방법
- 백트래킹: 가능한 모든 해를 탐색하되, 어떤 조건을 만족하지 않는 해는 더 이상 탐색하지 않고 되돌아가는 방법
- 동적 계획법: 작은 문제의 해를 저장하고 이를 활용하여 큰 문제의 해를 찾는 방법으로 중복 계산을 줄이고 효율성을 높이는 방법
---
# 의사코드
- 알고리즘의 표현 방법중 하나
- 대표적인 알고리즘 표현 방법으로는, 자연어(natural language), 의사 코드(Pseudocode), 순서도(flowchart)등이 있다.
- > **순서도 예시**
> 
- 자연어와 프로그래밍 언어의 형식을 섞어서 작성한 코드로, 사람이 읽을 수 있도록 단순화한 코드를 의미
- 알고리즘을 설계할 때, 복잡한 문법이나 세부 사항 없이 알고리즘의 핵심 로직을 명료하게 전달하는 목적으로 사용된다
### 의사코드의 특징
1. 자연어와 프로그래밍 언어의 중간 형태를 가진다
2. 복잡한 문법이나 세부 사항을 최소화하여 알고리즘의 핵심 로직을 쉽게 이해할 수 있다
3. 의사코드는 일반적인 프로그래밍 언어와 달리 표준화되지 않았기 때문에 작성 방식이 작성자마다 다를 수 있다
4. 알고리즘 설계 및 문서화 과정에서 효과적이다
- 설계 단계에서 미리 오류를 확인하고 수정할 수 있다
- 코드 검토가 쉬워진다
> 건물을 지을 때 설계를 하고, 설계에 따라 뼈대를 튼튼하게 하는 것이 중요하듯이, 프로그래밍할 때도 그 구조를 잘 구성하는 것이 매우 중요하다.
### 의사코드 예시
- 텍스트 파일에서 "foo"라는 단어를 찾아 전부 bar라는 단어로 바꾸어 주는 프로그램을 만든다고 하자.
```
Begin
Input A
Input B
Compute SUM = A + B
Print SUM
END
```
---
```
파일을 연다.
파일의 각 행(line)에 대해서 "cat" 이라는 단어를 찾는다.
"cat" 단어를 지운다.
"cat" 단어를 지운 자리에 "bat"이라는 새로운 단어를 넣는다.
파일을 닫는다.
```
---
```
FOR each index of string
IF string(index) is equals to hash
RETURN "Hash Found"
END IF
END FOR
```
---
```
let n = 0
for each person in room
set n = n + 1
```
---
- 의사코드에서 반드시 따라야 하는 규칙은 없다
- 의사코드를 어떻게 작성해야 하는지를 정의한 문법은 없다
- 의사코드는 목적이 무엇인가에 따라 의사 코드가 더 자세할 수도 있다
- **이전에 배웠던 정렬 알고리즘을 수도코드로 작성해보자**
- [정렬 알고리즘](https://hackmd.io/xsoa9K0xTtKtXB8_60eMQQ?view#%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%AC-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC)
---
# 브루트 포스 알고리즘 (Brute force)
## 브루트 포스란?
- 가능한 **모든 경우의 수를 탐색**하여 문제를 해결하는 방식
- 더 효율적인 알고리즘이 존재하는 경우에는 해당 알고리즘을 사용하는 것이 좋다
- 암호학에서 종종 사용된다
- 장점
- 알고리즘을 설계하고 구현하기 매우 쉽다
- 거의 완벽하게 병렬 작업이 가능하다는 특징이 있다
- 항상 정확도 100%를 보장한다
- 단점
- 경우의 수가 많아질수록 시간 복잡도가 높아져 비효율적일 수 있다
- 문제가 조금만 복잡해져도 매우 비효율적인 알고리즘이 될 수 있다
- 예시
- 배열에서 최대값과 최소값 찾기
- 완전수 찾기
> 완전수 : 자기 자신을 제외한 약수를 더했을 때 자기 자신이 되는 양의 정수. (ex: 28 = 1 + 2 + 4 + 7 + 14)
- 비밀번호 크래킹 (4자리 휴대전화의 비밀번호 찾기)
- 4색정리 (수학계에서 완전히 부르트포스만으로 문제를 해결한 경우)
- 선택 정렬, 버블 정렬, 삽입 정렬도 브루트포스 알고리즘의 일종으로 간주할 수 있다.
- 복습 ! [정렬 알고리즘](https://hackmd.io/xsoa9K0xTtKtXB8_60eMQQ?view#%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%84%A0%ED%83%9D-%EC%A0%95%EB%A0%AC-%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%AC-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC)
## 브루트 포스 예시
1. 블랙잭
- 숫자 카드들 중에서 3장을 선택하여 그 합이 최대한 가까워지는 경우의 합을 구하는 문제
2. 분해합
- 주어진 숫자 N의 가장 작은 생성자를 구하는 문제
3. 다음 순열
- 주어진 순열의 다음 순열을 구하는 문제
4. 비밀지도
- 두 개의 지도를 겹쳤을 때, 지도의 각 위치에서의 값이 0일 경우에는 공백을, 1일 경우에는 #을 출력하는 문제
5. 암호 만들기
- 길이가 L인 암호를 만드는 문제
> 더 효율적인 알고리즘이 존재하는 경우 오답으로 간주되기 때문에 언제 브루트 포스를 써야하는지 판단하는 것이 중요하다.
> 일반적으로 다음과 같은 경우 부르트 포스 알고리즘을 고려해볼 수 있다.
> - 탐색 공간이 작은 경우
> - 문제의 구조가 단순한 경우
> - 최적해를 찾기 위한 고급 기법이 필요하지 않은 경우
### 블랙잭
- 백준 알고리즘 2798번 ==[링크](https://www.acmicpc.net/problem/2798)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자
---
#### 수도코드 해답 예
```
1. 카드 리스트를 입력받는다.
2. M 값을 입력받는다.
3. 가장 M과 가까운 합을 찾기 위한 변수를 초기화한다 (예: closestSum = 0).
4. 3개의 카드를 선택하는 모든 조합에 대해 다음을 수행한다.
a. 선택한 카드의 합을 구한다.
b. 카드의 합이 M보다 작거나 같고, closestSum보다 크다면 closestSum을 업데이트한다.
5. closestSum을 출력한다.
```
#### 소스코드 해답 예
``` java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt(); // 카드의 개수 입력
int M = sc.nextInt(); // 목표값 입력
int[] cards = new int[N];
for (int i = 0; i < N; i++) {
cards[i] = sc.nextInt(); // 카드값 입력
}
int closestSum = 0;
for (int i = 0; i < N - 2; i++) {
for (int j = i + 1; j < N - 1; j++) {
for (int k = j + 1; k < N; k++) {
int sum = cards[i] + cards[j] + cards[k];
if (sum <= M && sum > closestSum) {
closestSum = sum;
}
}
}
}
System.out.println(closestSum); // 가장 M에 가까운 합 출력
}
}
```
---
# 그리디 알고리즘(Greedy)
## 그리디 알고리즘이란?
- 최적해를 구하기 위해 선택할 때마다 그 순간에 가장 좋은 선택을 하는 알고리즘
- 각 단계에서의 최적해가 전체 문제의 최적해인 경우에 사용할 수 있는 알고리즘으로, 최적화 문제를 해결하는데 사용된다
- 원리
1. 문제를 부분 문제로 분할한다
2. 각 단계에서 최적해를 선택한다
3. 선택한 최적해를 현재의 부분 문제에 대한 해답에 추가한다
4. 부분 문제가 해결될 때까지 반복한다
- 장점
- 실행 속도가 빠르며, 구현이 간단하다
- 일부 문제에서는 최적해를 항상 보장하며, 이 경우 다른 알고리즘에 비해 더욱 효율적이다
- 대부분의 경우 그리디 알고리즘은 근사해(Approximate Solution)를 구하는 용도로 사용될 수 있다
- 단점
- 그리디 알고리즘은 항상 최적해를 보장하지 않는다. (각 단계에서 선택한 선택지가 다음 단계에서 선택할 수 있는 최선의 선택이라는 보장이 없기 때문)
- 그리디 알고리즘은 전체적인 상황을 고려하지 않고 각 단계에서 가장 좋은 선택을 하는 알고리즘이기 때문에, 전체적인 최적해와는 상충될 수 있다
## 그리디 알고리즘 예시
1. 거스름돈 문제
- 손님이 지불한 돈과 물건의 가격이 주어졌을 때, 거스름돈으로 사용할 동전의 최소 개수를 구하는 문제
2. 회의실 배정 문제
- 여러 개의 회의가 있을 때, 각 회의의 시작시간과 종료시간이 주어졌을 때, 가장 많은 회의를 할 수 있는 경우의 수를 구하는 문제
3. 탐욕적 배낭 문제
- 가방에 넣을 수 있는 무게의 한계와 각 물건의 가치와 무게가 주어졌을 때, 가방에 넣을 수 있는 물건의 최대 가치를 구하는 문제
4. 크러스컬 알고리즘 (Kruskal Algorithm)
- 최소 비용 신장 트리(Minimum Spanning Tree)를 구하는 알고리즘으로, 간선의 가중치가 작은 순서대로 연결하는 그리디 알고리즘
5. 다익스트라 알고리즘 (Dijkstra Algorithm)
- 최단 경로를 구하는 알고리즘으로, 시작점에서부터 가장 짧은 거리에 있는 정점을 선택해가며 최단 경로를 찾아가는 그리디 알고리즘
> 현재 상태에서 최적이라고 생각되는 선택을 하면서 전역 최적해를 찾을 수 있는지 확인해야한다.
### 거스름돈 문제
- 백준 알고리즘 5585번 ==[링크](https://www.acmicpc.net/problem/5585)==
- 위 문제를 보고 수도코드 작성 및 풀이를 해보자
#### 수도코드 해답 예
```
1. 지불 금액을 입력받는다.
2. 거스름돈 총액을 계산한다 (1000 - 지불 금액).
3. 화폐 단위 배열을 정의한다 (예: {500, 100, 50, 10, 5, 1}).
4. 거슬러 줄 동전 개수를 초기화한다 (예: coinCount = 0).
5. 각 화폐 단위에 대해 다음을 수행한다.
a. 거스름돈 총액에서 해당 화폐로 거슬러 줄 수 있는 최대 동전 개수를 누적한다.
b. 거스름돈 총액을 업데이트한다.
6. 거슬러 줄 동전 개수를 출력한다.
```
#### 소스코드 해답 예
``` java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int payment = sc.nextInt(); // 지불 금액 입력
int change = 1000 - payment; // 거스름돈 총액 계산
int[] coins = {500, 100, 50, 10, 5, 1}; // 화폐 단위 배열
int coinCount = 0; // 거슬러줄 동전 개수
for (int coin : coins) {
coinCount += change / coin; // 해당 화폐로 거슬러 줄 수 있는 최대 동전 개수 누적
change %= coin; // 남은 거스름돈 갱신
if (change == 0) break; // 거스름돈이 없으면 종료
}
System.out.println(coinCount); // 거슬러 줄 동전 개수 출력
}
}
```
---
## 과제 : 백준 알고리즘 풀어보기
- https://www.acmicpc.net/problem/2798
- https://www.acmicpc.net/problem/5585
---
## 과제 : 야구 게임
**요구사항**
- 1~9 사이의 중복되지 않는 3개의 정수를 생성한다.
- 사용자는 3개의 숫자를 입력한다.
- 생성된 3개의 숫자를 맞추는데 위치까지 정확히 맞춰야 한다.
- 숫자와 숫자의 위치까지 일치하면 strike 로 판정한다.
- 숫자는 맞지만 위치가 틀렸다면 ball 로 판정한다.
- 숫자3개가 모두 일치하지 않으면 out 으로 판정한다.
- 3 strike 가 되면 유저가 이기고 게임이 종료된다.
- 유저가 10번 안에 맞추지 못하면 패배하고 게임이 종료한다
---
## 과제 : 제네릭 이진 트리 구현
목표: 자바로 이진 트리(Binary Tree)를 구현한다.
**요구사항**
- 제네릭 클래스를 사용하여 다양한 데이터 타입을 저장할 수 있는 이진 트리(`BinaryTree`) 클래스를 구현한다.
- 제네릭은 Comparable을 상속받은 대상으로 한정한다 (`<T extends Comparable<T>>`)
- `BinaryTree` 클래스는 다음의 메소드를 포함해야 한다
- `public void insert(T data)`: 트리에 새로운 노드를 삽입한다.
- `public boolean contains(T data)`: 트리에서 지정된 데이터를 가진 노드가 있는지 확인한다.
- `public void delete(T data)`: 트리에서 지정된 데이터를 가진 노드를 삭제한다.
- `public void preOrderTraversal()`: 전위 순회(pre-order traversal)를 사용하여 트리의 모든 노드를 출력한다.
- `public void inOrderTraversal()`: 중위 순회(in-order traversal)를 사용하여 트리의 모든 노드를 출력한다.
- `public void postOrderTraversal()`: 후위 순회(post-order traversal)를 사용하여 트리의 모든 노드를 출력한다.
---
###### tags: `과외(하희영)`
Sign in with Wallet
Connect another wallet