전체 글 (23) 썸네일형 리스트형 [프로그래머스/Java] Lv.1 달리기 경주 달리기 경주 문제 설명얀에서는 매년 달리기 경주가 열립니다. 해설진들은 선수들이 자기 바로 앞의 선수를 추월할 때 추월한 선수의 이름을 부릅니다. 예를 들어 1등부터 3등까지 "mumu", "soe", "poe" 선수들이 순서대로 달리고 있을 때, 해설진이 "soe"선수를 불렀다면 2등인 "soe" 선수가 1등인 "mumu" 선수를 추월했다는 것입니다. 즉 "soe" 선수가 1등, "mumu" 선수가 2등으로 바뀝니다.선수들의 이름이 1등부터 현재 등수 순서대로 담긴 문자열 배열 players와 해설진이 부른 이름을 담은 문자열 배열 callings가 매개변수로 주어질 때, 경주가 끝났을 때 선수들의 이름을 1등부터 등수 순서대로 배열에 담아 return 하는 solution 함수를 완성해주세요. 제한.. 계수 정렬(Counting Sort) 개념계수 정렬 또는 카운팅 소트(counting sort)는 컴퓨터 과학에서 정렬 알고리즘의 하나로서, 작은 양의 정수들인 키에 따라 객체를 수집하는 것, 즉 정수 정렬 알고리즘의 하나이다.(계수 정렬은 비교 정렬이 아님) 예시 시간복잡도시간 복잡도 : O(n + k) -> k는 배열에서 등장하는 최대값 참고 https://gyoogle.dev/blog/algorithm/Counting%20Sort.htmlhttps://ko.wikipedia.org/wiki/%EA%B3%84%EC%88%98_%EC%A0%95%EB%A0%AC 힙 정렬(Heap Sort) 개념힙 정렬(Heap sort)이란 최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방법으로서, 내림차순 정렬을 위해서는 최소 힙을 구성하고 오름차순 정렬을 위해서는 최대 힙을 구성하면 된다. 어떤 리스트에 값을 넣었다가 빼내려고 할 때, 우선순위가 높은 것 부터 빼내려고 한다면 정렬을 떠올리게 된다. 하지만 정렬은 숫자가 낮을 수록 우선순위가 높다고 가정할 때 매 번 새 원소가 들어올 때 마다 이미 리스트에 존재하는 원소들과 비교를 해서 정렬을 해야한다. 이렇게 하면 비효율적이기 때문에 좀 더 효율이 좋게 만들기 위하여 힙은 다음과 같은 조건이 있다. '부모 노드는 항상 자식 노드보다 우선순위가 높다.' 즉, 모든 요소들을 고려하여 우선순위를 정할 필요 없이 부모 노드는 자식노드보다 항상 우선순위가.. 기수 정렬(Radix sort) 개념기수 정렬(radix sort)은 기수 별로 비교 없이 수행하는 정렬 알고리즘이다.(비교정렬이 아니다!) 기수로는 다양한 자료를 사용할 수 있으나 크기가 유한하고 사전순으로 정렬할 수 있어야 한다. 예시 구현(Java) void countSort(int arr[], int n, int exp) { int buffer[n]; int i, count[10] = {0}; // exp의 자릿수에 해당하는 count 증가 for (i = 0; i = 0; i--) { buffer[count[(arr[i]/exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } for (i = 0; i 0; e.. 병합 정렬(Merge Sort) 개념합병 정렬 또는 병합 정렬은 비교 기반 정렬 알고리즘이다. 일반적인 방법으로 구현했을 때 이 정렬은 안정 정렬에 속하며, 분할 정복 알고리즘의 하나이다.( * 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.) 구현(Java)요소를 쪼갠 후, 다시 합병시키면서 정렬해나가는 방식mergeSortpublic void mergeSort(int[] array, int left, int right) { if(left merge()public static void merge(int[] array, int left, int mid, int right) { int[] L = A.. 퀵 정렬(Quick Sort) 개념퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다.퀵 정렬은 불안정 정렬이며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다.( * 분할 정복 알고리즘(Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이나 알고리즘이다.) 과정리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗이라고 한다.피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다.분할된 두 개의 작은 리스트에 .. 거품 정렬(Bubble Sort) 개념거품 정렬은 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘이다. 과정1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를, … , (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환한다.1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. 구현(Java)void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i .. 삽입 정렬(Insertion Sort) 개념삽입 정렬은 2번째 원소부터 시작하여 모든 요소를 차례대로 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 과정2번째 위치(index)의 값을 temp에 저장한다.temp와 이전에 있는 원소들과 비교하며 삽입해나간다.'1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다. 구현(Java)void insertionSort(int[] arr){ for(int index = 1; index = 0) && (arr[prev] > temp) ) { // 이전 위치가 음수가 아니며, 비교값이 선택값보다 크다면 arr[prev+1] = arr[prev]; // 값이 하나씩 뒤로 밀림 .. 이전 1 2 3 다음
