컴공생의 다이어리

[프로그래머스] K번째수 - 파이썬(Python) def solution(array, commands): answer = [] for i, j, k in commands: answer.append(sorted(array[i - 1:j])[k - 1]) return answer https://programmers.co.kr/learn/courses/30/lessons/42748 코딩테스트 연습 - K번째수 [1, 5, 2, 6, 3, 7, 4] [[2, 5, 3], [4, 4, 1], [1, 7, 3]] [5, 6, 3] programmers.co.kr

계수 정렬(Counting Sort) 계수 정렬은 특정한 조건이 부합될 때만 사용할 수 있지만 데이터 수가 많더라도 중복된 값이 많이 분포돼있는 배열을 정렬할 때 효과적이고 빠른 정렬 알고리즘이다. 최대, 최소 값 차이가 100만 이하일 경우 효과적이다. 카운팅 정렬이라고 하기도 한다. 선택, 삽입, 퀵 정렬처럼 데이터를 비교하며 위치를 변경하는 비교 기반의 정렬 알고리즘이 아니다. 계수 정렬의 조건은 아래와 같다. 데이터의 크기 범위가 제한된 경우 ex) 0 ~ 100 까지의 점수를 정렬하는 경우 데이터가 양의 정수인 경우 데이터가 실수인 경우 무한의 범위를 가질 수 있으므로 1번 조건에 부합하지 못함 가장 큰 데이터와 가장 작은 데이터의 차이가 1,000,000(백만)을 넘지 않는 경우 필수적인 조건..

병합 정렬(Merge Sort) 병합 정렬은 분할 정복 알고리즘의 하나로 합병 정렬이라고도 한다. 불안정 정렬인 퀵 정렬과 달리, 병합 정렬은 안정 정렬에 속한다. 전체 데이터를 가장 작은 단위로 분할한 후 분할한 데이터를 다시 병합하면서 정렬하는 재귀용법을 활용한 정렬 알고리즘이다. 퀵 정렬과 비교했을 때, 차이점은 아래와 같다. 퀵 정렬 - 각 요소를 피벗과 비교하여 요소를 정렬 - 피벗을 통해 정렬(partition) → 영역을 쪼갬(quick sort) 병합 정렬 - 배열을 하나의 요소가 남을 때까지 두 개의 하위 배열 (n / 2)로 반복하여 나눔 - 영역을 쪼갤 수 있을 만큼 쪼갬(merge sort) → 정렬(merge) 정렬 과정 분할(Divide) 단계 리스트를 절반으로 나누어 비슷한 크..

퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 합병 정렬(Merge Sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다. 퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 하나의 리스트를 피벗(pivot)을 기준으로 피벗보다 작은 데이터와 큰 데이터를 두 개의 부분 리스트로 나눈 다음, 각 부분 리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법이다. 정렬 과정 배열 가운데서 하나의 원소를 선택(→ 이 원소가 피벗) 피벗을 기준으로 피벗보다 작은 원소들은 피벗 앞(왼쪽)으로 오고, 피벗보다 큰 원소들은 피벗 뒤(오른쪽)로 이동 피벗을 제외하고 나뉘게 된 두 배열은 앞 ..

삽입 정렬(Insertion Sort) 삽입 정렬은 손안의 카드를 정렬하는 방법(새로운 카드를 기존의 정렬된 카드 사이에 올바른 위치에 삽입)과 유사하다. 또한 삽입 정렬은 선택 정렬과 유사하지만, 좀 더 효율적인 정렬 알고리즘이다. 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 정렬 과정 2번째 위치(index)의 값부터 정렬을 시작한다. 해당 인덱스(key 값) 앞에 있는 데이터(B)부터 비교해서 key 값이 더 작으면, B값을 뒤 인덱스로 복사 이를 key 값이 더 큰 데이터를 만날 때까지 반복 큰 데이터를 만난 위치 바로 뒤에 key 값을 이동 파이썬 코드 def insertion_sort(arr): ..

선택 정렬(Selection Sort) 선택 정렬은 버블 정렬(Bubble Sort)과 유사한 알고리즘이다. 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 정렬 과정 1. 우선, 위치(index)를 선택한다. 2. i+1번째 원소부터 선택한 위치(index)의 값과 비교를 시작 3. 오름차순이므로 현재 선택한 자리에 있는 값보다 순회하고 있는 값이 작다면, 위치(index)를 갱신 4. 2번 반복문이 끝난 뒤에는 min_index에 1번에서 선택한 위치(index)에 들어가야 하는 값의 위치(index)를 갖고 있으므로 서로 교환(swap) 파이썬 코드 def selection_sort(arr): for i in range(len(arr)-1): min_i..

거품 정렬(Bubble Sort) 거품 정렬은 버블 정렬이라고도 불리는 알고리즘이다. 거품 정렬은 두 인접한 데이터의 대소를 비교해서, 앞에 있는 데이터가 뒤에 있는 데이터보다 크면, 자리를 바꾸는 정렬 알고리즘이다. 이름의 유래로는 정렬 과정에서 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어졌다고 한다. 정렬 과정 1회전에 첫번째 원소와 두번째 원소를 비교, 두번째 원소와 세번째 원소를 비교, ... (마지막-1)번째 원소와 마지막 원소의 대소를 비교하며 정렬 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동한다. 따라서 2회전에서는 맨 마지막 원소를 제외하고 1번 과정을 다시 수행하여 두번째로 큰 수를 맨 뒤에서 두번째로 정렬한다. 이렇게 정렬을 1회전씩 수행하다 보면 모..

문제 네 가지 기능(배열의 정보 추가, 삭제, 검색 및 정렬)이있는 프로그램을 작성하시오. 배열은 크기 2 * 6 (행 * 열) 정수 유형의 2 차원 배열이다. 첫 번째 열에는 학생 ID가 포함되고 두 번째 행에는 해당 수학 점수가 포함된다. 프로그램이 시작되면 배열이 비어 있다. 사용자의 명령에 따라 반복적으로 수행되는 기능으로 'End'를 입력하면 프로그램이 종료된다. 네 가지 기능 각각에 대한 기능을 만드시오. Append(추가) : 사용자가 입력한 학생 ID와 수학 점수 쌍을 배열 끝에 추가한다. 추가하고 나서 배열을 2차원 모양으로 인쇄한다. Delete(삭제) : 사용자가 입력한 학생 ID와 일치하는 학생ID와 수학 점수 쌍을 삭제한다. 삭제 한후 배열을 2차원 모양으로 인쇄한다. Search..