알고리즘

[Baekjoon] 12865 평범한 배낭 문제

https://www.acmicpc.net/problem/12865 배낭 문제는 냅색 알고리즘의 대표 문제라고 할 수 있다. 냅색 알고리즘은 다이나믹 프로그래밍에 속하는 알고리즘이다. 문제의 입력 예제를 통해 냅색 알고리즘에 대해 알아보자. 1. 먼저 넣을 수 있는 무게 크기만큼 1차원 배열을 하나 준비하자. (dy라고 하겠다) 2. 첫 번째 경우(4kg, 8원) 4kg의 가방에 8원의 가치를 가진 물건을 하나 넣을 수 있다. 5 - 7까지 모두 동일하다. 3. 두 번째 경우(5kg, 6원) 5kg의 가방에 6원의 가치를 가진 물건을 넣을 수는 있지만 이전 값인 8이 더 크므로 4kg, 8원짜리 물건을 넣는다. 4. 세 번째 경우(3kg, 2원) -> 3kg의 가방에 2원짜리 물건을 넣을 수 있다. ->..

[알고리즘] 동전 교환 알고리즘

동전 교환 알고리즘 최소의 갯수로 거스름돈을 주는 방법에 대해 알아보자. 그리디 알고리즘 동전교환 문제를 풀기 위해 그리디 알고리즘을 사용할 수 있다. 하지만 그리디 알고리즘은 가장 적은 동전 수의 최적해를 항상 찾는 것은 아니다. 예를 들어보자, 동전의 종류가 [1, 3, 4] 이렇게 존재하고 9원을 거스름돈으로 준다고 하면, 그리디 알고리즘은 4원 1개, 3원 1개, 1원 2개를 선택할 것이다. 하지만 3원 3개를 거스름돈으로 주는 방식이 가장 적은 동전의 개수를 이용한 최적해이다. 그렇다면 항상 최적해를 찾기 위해 어떤 알고리즘을 이용해야 할까? DFS DFS 알고리즘을 이용할 수 있다. 위와 같이 [1,3,4] 동전 종류가 있고, 9원을 거스름돈으로 거슬러 준다고 해보자. 각 코인마다 3개의 가지..

[알고리즘] Sliding Window 알고리즘

Sliding Window 일정한 크기의 박스(윈도우)를 유지하면서 이동하는 알고리즘 알고리즘 설명 연속된 3수의 최대값을 찾는다고 해보자. 1 ) 크기가 3인 박스를 만든다. 2 ) 한 칸씩 이동하면서 3수의 합을 계산한다. 알고리즘 구현 구현은 다음과 같다.(자바) int max = 0; for(int i = 0; i < 3; i++) { max += arr[i]; } int answer = max; for(int i = m; i < n - 3; i++) { max -= arr[i-m]; max += arr[i]; answer = Math.max(answer, max); }

[알고리즘] 소수 알고리즘(에스토스테네스 체)

에스토스테네스 체 -> 소수를 구할 때 사용하는 가장 최적화된 알고리즘이다. 알고리즘 설명 1 ) 먼저 일차원 배열을 하나 만든다. 2 ) Ch[i] == 0이면 ch[i] = 1로 바꾸고 ch[i]의 배수도 모두 1로 바꾼다. Ex ) i = 2일 때, ch[2] == 0이다. 따라서 값을 1로 바꾸고 2의 배수인 4,6,8,10,12,14도 1로 바꾼다. i = 3일 때, ch[3] == 0이다. 따라서 값을 1로 바꾸고 3의 배수인 6,9,12도 값을 1로 바꾼다. i = 4일 때, ch[4] == 1이다. 즉 소수가 아니다. 따라서 그냥 넘어간다. 구현 코드 구현은 다음과 같다.(자바) int cnt=0; int[] ch = new int[n+1]; for(int i=2; i

[알고리즘] 이분 탐색(Binary Search)

이분 탐색이란? --> 정렬되어 있는 배열에서 데이터를 찾을 때 배열의 길이를 1/2만큼 줄이면서 탐색하는 방법이다. 아래와 같이 1에서 10까지의 숫자가 있는 배열이 있다고 해보자. 여기서 8을 이분 탐색으로 찾아보자. 먼저 가운데 지점을 찾는다. 이 때 left, right값을 1과 10으로 지정한 후 찾게 된다. 가운데 값과 target값(8)의 크기를 비교한다. 만약 가운데 값이 타겟 값보다 크다면 right = mid - 1로 바꿔준다. 만약 가운데 값이 타겟 값보다 작다면 left = mid + 1로 바꿔준다. 그 다음 가운데 지점을 갱신해준 뒤 가운데 값과 타겟 값을 비교한다. int binary_search(int target, int n) { int result = 0; int left ..