알고리즘 - HackMD

# 알고리즘 **주어진 문제를 해결하기 위한 일련의 절차나 방법을 순서대로 기술한 것** - 알고리즘은 문제 해결을 위한 과정을 단계별로 나누어 표현한 것으로, 효율적인 알고리즘이 중요하다. - 알고리즘의 필요성 - 문제 해결에 있어 다양한 접근 방식과 효율성을 이해하고 평가할 수 있다. - 컴퓨터 자원을 효율적으로 사용하여 빠르고 정확한 결과를 도출한다. - 알고리즘 지식을 바탕으로 최적의 해결책을 찾아내고, 프로그래밍 역량을 향상시킨다. ## 좋은 알고리즘 - 알고리즘의 평가할 땐 **정확성**과 **효율성**이 중요시된다. - 따라서 좋은 알고리즘은 정확하고 효율적이어야 한다. > ex) 사전에서 원하는 단어를 찾아야 한다면? ## 시간복잡도와 공간복잡도 - 시간 복잡도(Time Complexity) - 알고리즘이 수행하는데 걸리는 시간을 표현한 것 - 시간 복잡도는 입력 크기에 따라 증가하는 속도로 나타낸다. - 낮은 시간 복잡도를 가진 알고리즘이 더 빠르게 문제를 해결한다. - 공간 복잡도(Space Complexity) - 알고리즘이 실행되는 동안 사용하는 메모리 공간의 양을 표현한 것 - 공간 복잡도 역시 입력 크기에 따라 증가하는 속도로 나타낸다. - 낮은 공간 복잡도를 가진 알고리즘이 더 적은 메모리 공간을 사용한다. ## Big O 표기법 - 알고리즘의 시간 복잡도와 공간 복잡도를 나타내는 표기법 - 알고리즘의 효율성을 **대략적으로** 평가할 수 있다. - 입력 크기에 따른 알고리즘의 성능 증가 속도를 표현한다. ### Big O 표기법의 예시 ![](https://i.imgur.com/6iC3i3E.png) - `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)등이 있다. - > **순서도 예시** > ![](https://i.imgur.com/TPPkytJ.png) - 자연어와 프로그래밍 언어의 형식을 섞어서 작성한 코드로, 사람이 읽을 수 있도록 단순화한 코드를 의미 - 알고리즘을 설계할 때, 복잡한 문법이나 세부 사항 없이 알고리즘의 핵심 로직을 명료하게 전달하는 목적으로 사용된다 ### 의사코드의 특징 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: `과외(하희영)`

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.