본문 바로가기

Algorithm (Java)6

[Algorithm] 구간 합 (Prefix Sum) 구간 합 (Prefix Sum) ■ 정의 - 수들의 나열에서 특정 구간의 합을 의미 - 보통 1차원 배열에서 인덱스 사이의 값들의 합을 구하는데 사용 ■ 구간 합 알고리즘 - 구간 합 공식: sum[j] - sum[i - 1] // i에서 j까지의 구간 합 - 합 배열(P)을 미리 계산해 두면 구간 합은 한 번에 계산 가능 - 알고리즘의 시간복잡도: O(1) ■ Code import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class No11659 { public static void main(String[] args) .. 2023. 5. 1.
[Algorithm] 힙 정렬 (Heap Sort) 힙 정렬 (Heap Sort) ■ 정의 - 최솟값 또는 최댓값을 빠르게 찾아내기 위해 완전이진트리 형태로 만들어진 자료구조 - 힙(heap)을 사용하여 정렬하는 알고리즘 · 힙(heap)이란?: '부모값이 자식값보다 항상 크다' 조건을 만족하는 완전이진트리 · 최대힙: 부모노드 값(key 값) ≤ 자식노드 값 (key 값) · 최소힙: 부모노드 값(key 값) ≥ 자식노드 값 (key 값) ■ 인덱스 관계 - 부모노드 인덱스: a[(i-1) / 2] - 왼쪽 자식노드 인덱스: a[i * 2 + 1] - 오른쪽 자식노드 인덱스: a[i * 2 + 2] ■ 힙 정렬 과정 Step 1. 최대 힙의 루트 노드를 마지막 배열 값과 교환, 가장 큰 값을 마지막 배열에 저장 후 힙에서 제거 Step 2. 다시 힙을 .. 2023. 4. 8.
[Algorithm] 탐욕 알고리즘 (Greedy Algorithm) 탐욕 알고리즘 (Greedy Algorithm) ■ 정의 다음 그림에서 최댓값을 구하려면 그림1과 같이 5 + 7 + 9 = 21로 구할 것이다. 하지만 탐욕 알고리즘은 그 순간마다 최적의 선택을 하기 때문에 그림2와 같이 5 + 10 + 4 = 19를 구할 것이다. 이처럼 탐욕 알고리즘은 지금 당장 좋은 것만을 고르며, 현재 선택이 나중에 미칠 영향은 고려하지 않는다. 따라서 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 따라서, 탐욕 알고리즘 해법은 그 정당성 분석이 중요하다. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토한다. 거스름 돈, 활동 선택, 최.. 2023. 4. 3.
[Algorithm] 버블 정렬(Bubble Sort) 버블 정렬 (Bubble Sort) ■ 정의 버블 정렬은 이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬(straight exchange sort)이라고도 함 ■ 사용 예 - 총 3번의 Pass를 통해 [1, 3, 4, 6, 7]로 오름차순 정렬을 만들 수 있음 - 사진에서는 모든 비교과정을 표시하였지만, 이미 정렬된 수와의 비교는 굳이 진행하지 않아도 됨 ■ 장점 - 구현이 매우 간단하고, 소스코드가 직관적 - 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 => 제자리 정렬(in-place sorting) - 안정 정렬(Stable Sort) ■ 단점 - 시간복잡도가 최악, 최선, 평균 모두 O(n^2)으로, 굉장.. 2023. 3. 9.
[Algorithm] 이진검색 (Binary search) 이진검색 (Binary search) ■ 정의 - 이진검색은 요소가 오름차순으로 정렬된 배열인 상태에서 검색하는 알고리즘 - 오름차순으로 정렬된 정수의 리스트를 같은 크기의 두 부분 리스트로 나누고 필요한 부분에서만 탐색 - 리스트의 중간 부분에 찾는 원소가 있는지 확인, 없으면 위쪽에 있는지 아래쪽에 있는지 판단하여 맨 앞부터 검색 하거나 중간부터 검색 ■ 사용 예 - 39를 찾는 과정 1. index 0과 10을 기준으로 2로 나눈 값 index 5를 살펴본다. 2. index 5의 값이 찾으려는 39보다 작으므로 index 5 이하는 더 이상 살피지 않는다. 3. index 6과 10을 기준으로 2로 나눈 값 index 8을 살펴본다. 4. index 8의 값이 찾으려는 39보다 크므로 index .. 2023. 2. 14.
[Algorithm] 선형검색(Linear search) / 보초법(Sentinel method) 선형 검색 (Linear search) ■ 정의 - 요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키 값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색하는 기법 ■ 사용 예 - 찾으려는 값이 2일 경우 - 찾으려는 값이 7일 경우 - 찾는 값이 3으로 존재하는 경우 앞에서부터 순차적으로 검색 후 index 값이 3에서 탐색을 종료 함 - 찾는 값이 7로 존재하지 않는 경우 마지막까지 검색 후 -1을 return 후 종료 함 ■ Code - while문으로 작성한 선형검색 public class SeqSearch { static int seqSearch(int[] a, int n, int key){ int i = 0; while(true){ if(i == n) return -1; if(a.. 2023. 2. 13.

티스토리툴바