본문 바로가기

Algorithm

 (12)
[알고리즘] 파라메트릭 서치(Parametric Search) 알고리즘 Parametric Search(파라메트릭 서치)는 최적화 문제를 해결하는 기법으로, 이분 검색(Binary Search)을 확장하여 사용한다. 일반적으로 특정 조건을 만족하는 값의 범위를 찾거나, 최대 또는 최소 값을 구하는 데 사용된다.주요 개념최적화 문제를 결정 문제로 변환예: "최대값을 구하라" → "특정 값이 가능한가?"라는 결정 문제(Decision Problem)로 변환.이분 검색을 활용가능한 값의 범위를 이분 검색으로 좁혀가며, 최적의 값을 탐색.조건 함수 작성특정 조건을 만족하는지 여부를 판단하는 함수(결정 함수)가 필요.사용 사례최적의 분배예: 작업을 최소 시간 안에 나누는 문제(예: 블루레이 디스크 분할 문제).최대/최소 경로그래프에서 특정 조건을 만족하는 최소 또는 최대 경로 찾기...
[알고리즘] 이분 검색 알고리즘 (Binary Search) 이분 검색(Binary Search)은 정렬된 배열에서 특정 값을 효율적으로 찾기 위한 알고리즘이다.배열을 반복적으로 반으로 나누어 원하는 값을 탐색하므로 시간 복잡도가 O(log ⁡n)이다.이분 검색 알고리즘의 동작 원리정렬된 배열을 전제 조건으로 사용이분 검색은 데이터가 정렬된 상태여야 동작한다.중간값 선택탐색 범위의 중간값을 선택한다.값 비교중간값과 목표 값을 비교한다.같다면 값을 찾은 것이므로 인덱스를 반환한다.작다면 오른쪽 절반에서 탐색을 계속한다.크다면 왼쪽 절반에서 탐색을 계속한다.반복 또는 재귀 호출위 과정을 반복하거나 재귀적으로 호출하며 탐색 범위를 줄여 나간다.종료 조건값이 발견되면 해당 인덱스를 반환하고, 탐색 범위가 비게 되면 검색 실패를 의미하는 값을 반환한다.이분 검색 Java ..
[알고리즘] 삽입 정렬 (Insertion Sort) 삽입 정렬은 현재 정렬할 요소를 그 앞의 정렬된 부분과 비교하여 적절한 위치에 삽입하는 방식이다.정렬된 부분이 점차 커지며, 새로운 요소를 앞에서부터 차례대로 삽입하여 정렬을 완성한다.일반적으로 데이터가 거의 정렬되어 있을 때 효율적인 방식이다.동작 과정두 번째 요소부터 시작하여 앞의 요소와 비교해 적절한 위치에 삽입합니다.이를 반복하여 정렬된 배열의 범위를 한 단계씩 늘려가면서 진행합니다.구현 코드public static void insertionSort(int[] arr){ int n = arr.length; for(int i = 1; i = 0; j--){ if(arr[j] > temp){ arr[j+1] = arr[j]; }e..
[알고리즘] 버블 정렬 (Bubble Sort) 버블 정렬은 인접한 두 요소를 비교하여 크기가 맞지 않으면 서로 교환하는 방식으로 동작한다. 이렇게 하면 큰 값이 배열의 끝으로 "거품"처럼 이동하는 모습이라 해서 버블 정렬이라 부른다.동작 과정배열의 첫 번째 요소부터 인접한 두 요소를 비교하여, 만약 앞 요소가 뒤 요소보다 크면 교환합니다.배열의 끝까지 반복하여 가장 큰 값이 맨 뒤로 이동하게 만듭니다.이런 과정을 배열의 크기만큼 반복하면서 정렬을 완성합니다.구현 코드public static void bubbleSort(int[] arr){ int n = arr.length; for (int i = 0; i arr[j+1]){ //인접 요소 교환 int temp = arr[j]; ..
[알고리즘] 선택 정렬 (Selection Sort) 선택 정렬은 배열에서 가장 작은 요소를 선택하여 맨 앞의 요소와 교환하는 과정을 반복하는 방식이다. 전체 배열에서 최소값을 찾아 앞쪽부터 하나씩 정렬해 나가는 방식이라 간단하다. 정렬할 데이터가 많을 경우에는 비효율적이다.동작 과정배열에서 최소값을 찾아 첫 번째 요소와 교환합니다.다음 단계에서는 두 번째 요소부터 끝까지의 최소값을 찾아 두 번째 요소와 교환합니다.이러한 과정을 반복하여 배열이 모두 정렬될 때까지 진행합니다.구현코드public static void selectionSort(int[] arr) { int n = arr.length; for (int i = 0; i
[알고리즘] 배열 합치기 오늘 포스팅에서는 배열 합치기에 대해서 알아보자. 2 Pointers 알고리즘을 통해 구현해보려고 하는데, 이는 단순히 반복문을 통해 배열을 합치는 것 보다 시간복잡도 측면에서 이점이 있다.  바로 예제를 통해서 확인해보자.오름차순으로 정렬되어 있는 배열 2개 A, B가 있을 때 2개의 배열을 합쳐서 오름차순 하여라. (A, B의 원소는 int 범위 내에 있다.)  ex) A = [1, 2, 3, 5], B = [2, 4, 5, 8, 9] 라면 최종 배열은 C = [1, 2, 3, 4, 5, 5, 8, 9] 가 되어야 한다.public ArrayList example(int[] arr, int[] arr2){ // 2 Pointers 알고리즘 ArrayList answer = n..

티스토리툴바