본문 바로가기

Study for Backend/Algorithm

 (17)
[Algorithm 기초] 투 포인터 Two Pointer (투 포인터) - 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 선형 구조 알고리즘 - 포인터 배치 방법 --> 같은 방향에서 시작 : 첫 번째 원소에 둘 다 배치 --> 서로 다른 방향에서 시작 : 첫 번째 원소와 마지막 원소에 배치 - 한 번의 반복으로 모든 요소를 처리하기에 효율적이며 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있음 알고리즘 복잡도 : O(n) 투 포인터의 종류 1. 고정 길이 슬라이딩 윈도우 - 고정된 길이의 윈도우를 사용하여 배열이나 리스트를 탐색 - 윈도우의 크기를 일정하게 유지하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행 - 부분 배열의 합이나 평균을 계산하는 등의 문제에 사용 2. 가변 길이 슬라이..
[Algoritm 기초연습] 백준 1920 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net //이진탐색 scanner 사용 버전 public class binarySearchPractice06 { public static int binarySearch(int[] array, int target){ if (array == null || array.length == 0){ return -1; } int left = 0; int right = ..
[Algorithm 기초] 이진 탐색 이진 탐색 (Binary Search) - 정렬된 상태의 데이터에서 특정값을 빠르게 탐색하는 방법 - 찾고자 하는 값과 데이터 중앙에 있는 값과 비교 - 찾고자 하는 값이 더 작으면 데이터 왼쪽 부분에서 이진 탐색 - 찾고자 하는 값이 더 크면 데이터 오른쪽 부분에서 이진 탐색 알고리즘 복잡도 : O(logn) //이진탐색 사용예제01 //20240224 알고리즘 - 이진 탐색 public class binarySearch { //반복문 구조 버전 public static int binarySearch(int arr[] , int target){ int left = 0; int right = arr.length - 1; while (left right){ return -1; } int mid = (lef..
[Algorithm 기초] 기수 정렬, 계수 정렬, 셀 정렬 기수 정렬 (Radix Sort) 낮은 자리수 부터 정렬하는 방식. 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블(queue)을 위한 메모리 필요 알고리즘 복잡도 : O(dn) 기수정렬구현 의사코드 (Pseudocode) RadixSort(a[], n): // Finding the maximum element max=a[0] For (i=1 to n-1): If (a[i]>max): max=a[i] // Calling countingSort for // k times using For loop. For (div=1 to max/div>0): countingSort(a, n, div) div=div*10 계수 정렬(Counting Sort) 숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방..
[Algorithm 기초연습] 백준 2750 수 정렬하기 https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net //버전01 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int cnt = sc.nextInt(); int[] arr = new int[cnt]; for(int i = 0; i < cnt; i++){ arr[i] = sc.nextInt(); }..
[Algorithm기초] 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬 합병 정렬 (Merge Sort) 배열을 계속 분할해서 길이가 1이 되도록 만들고 인접한 부분끼리 정렬하면서 합병 알고리즘 복잡도 : O(nlogn) 합병정렬구현 의사코드 (Pseudocode) mergeSort(A[], p, r) ▷ A[p...r]을 정렬한다{ if (p < r) then { q ← (p+q)/2; ----------------- ① ▷ p, q의 중간 지점 계산 mergeSort(A, p, q); ---------- ② ▷ 전반부 정렬 mergeSort(A, q+1, r); -------- ③ ▷ 후반부 정렬 merge(A, p, q, r);------------ ④ ▷ 합병 } } merge(A[], p, q, r){ 정렬되어 있는 두 배열 A[p...q]와 A[q+1...r]을 ..
[Algorithm기초] 버블 정렬, 삽입 정렬, 선택 정렬 정렬 특정 값을 기준으로 데이터를 순서대로 배치하는 방법 정렬의 종류 1. 구현 난이도는 쉽지만 속도는 느린 알고리즘 - 버블 정렬, 삽입 정렬, 선택 정렬 2. 구현 난이도는 조금 더 어렵지만, 속도는 빠른 알고리즘 - 합병 정렬, 힙 정렬, 퀵 정렬, 트리 정렬 3. 하이브리드 정렬 - 팀 정렬, 블록 병합 정렬, 인트로 정렬 4. 기타 정렬 알고리즘 - 기수 정렬, 카운팅 정렬, 셸 정렬, 보고 정렬 버블 정렬 (Bubble Sort) 인접한 데이터를 비교하며 자리를 바꾸는 방식. 값을 비교하고 작은 수가 앞쪽으로 자리교체 알고리즘 복잡도 : O(n제곱) = n(n-1)/2 버블정렬구현 의사코드 (Pseudocode) *스도코드 : 알고리즘 flow 파악용 코드이며 실제 돌아가지 않음 bubbleS..

티스토리툴바