알고리즘/유형정리

[알고리즘] 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 ..