알고리즘

🔐 문제 길이가 같은 두 개의 큐가 주어집니다. 하나의 큐를 골라 원소를 추출(pop)하고, 추출된 원소를 다른 큐에 집어넣는(insert) 작업을 통해 각 큐의 원소 합이 같도록 만들려고 합니다. 이때 필요한 작업의 최소 횟수를 구하고자 합니다. 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주합니다. 큐는 먼저 집어넣은 원소가 먼저 나오는 구조입니다. 이 문제에서는 큐를 배열로 표현하며, 원소가 배열 앞쪽에 있을수록 먼저 집어넣은 원소임을 의미합니다. 즉, pop을 하면 배열의 첫 번째 원소가 추출되며, insert를 하면 배열의 끝에 원소가 추가됩니다. 예를 들어 큐 [1, 2, 3, 4]가 주어졌을 때, pop을 하면 맨 앞에 있는 원소 1이 추출되어 [2, 3, 4..

지금 까지 했던 merge 퀵, 선택, 삽입, 흡 등 비교 정렬은 아무리 빨리도 nlogn의 수행시간이 나온다. 계수 정렬 알고리즘은 카운트 베열이 필요하다. 무슨 숫자가 몇개 있는지 확인 하기 위해 계수 정렬의 특징 - 입력 후에도 배열이 유지된다. 기수정렬

Dicide-and-Conquer qaradigm을 사용 즉 풀기 어려운 정렬을 계산하기 쉽게 나누어 진행하는것 partition을 이용 Pivot을 정해서 작은것은 왼쪽 큰것은 오른쪽으로 위치시킨다. 재귀호출을 통해 계속 반복한는것 퀵 정렬의 수행시간은 Pivot을 어떨게 설정하냐에 따라 달라진다. Merge sort 는 nlogn이지만 공간은 사용해야 한다는 단점이 있다. HeapSort는 max-heap구조를 만들어야 한다는 어려움이 있다. Quicksort는 nlogn이지만 최악의 경우 시간이 많이 늘어난다.

힙 정정 (Heap Sort) - 힙 구조의 특성을 이용한 정렬 - 수행시간은 합병정렬과 동일한 O(nlon) - 삽입정렬과 동일한 제자리 정렬 (Sort in Place) 힙의 형태 (The chape of a heap) - 완전 이진 트리(Complete binary tree)에 가까운 형태 (트리는 부모노드와 자식 노드로 구성되어있는 그래프) - 이진트리(Binary tree)는 각 노드의 자식수가 2 이하인 경우 - 완전 이진트리는 Root노드부터 Leaf노드까지 빠짐없이 채워져 있는 트리 최대힙 특성 (Max-Heap Property) - 부모 노드의 값은 항상 자식 노드의 값보다 크거나 같다. - 따라서 전체 트리의 Root 노드값이 가장크다. - 또한 각 하위 트리 구조의 Root 노드가 가..

정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명할 수 있다. 문제정의, 알고리즘 설명, 정확성 증명, 성능 분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3......... an) - 출력 (output) 입력된 숫자 위 배열이 오름차순 조건을 만족하도록 재 배열하는 것 합병 정렬(Merge Sort) - 합병을 이용한 정렬 알고리즘 - 두 개의 정렬된 배열이 주어졌을 때, 정렬된 하나의 배열로 합병 - 각 배열의 가장 왼쪽에 있는 값을 비교해보면 가장 작은 수를 알 수 있다. 정렬을 하기에는 너무 큰 배열을 쪼개어 정렬한 후 합병한다. 이를 위해 합병 정렬을 필요한 것이다. A divide-and-conquer approach 크기가 커서 풀기 어려운 하나의..

정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명 할 수있다. 문제정의, 알고리즘 설명, 정확성증명, 성능분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3 ......... an) - 출력 (output) 입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것 선택정렬 알고리즘 선택정렬(Selection sort) - 선택하여 정렬하는 알고리즘 - 최소값 선택 정렬 (Min-Selection sort) 가장 작은 값을 선택(오름차순) - 최대값 선택 정렬 (Max-Selection sort) 가장 큰 값을 선택(내림차순) - 정확성 증명 수학적 귀납법을 이용 i번쨰 선택한 숫자가 i번째로 작은(혹은 큰) 숫자인지를 증명 - 성능분석 최선 최악의 경우 수행..

정렬문제(sorting problem) 알고리즘은 4단계에 걸쳐서 설명 할 수있다. 문제정의, 알고리즘 설명, 정확성증명, 성능분석 - 입력 (input) n개의 숫자들의 배열 (a1, a2, a3 ......... an) - 출력 (output) 입력된 숫자위 배열이 오름차순 조건을 만족하도록 재 배열하는것 삽입정렬(Insertion sort) - 삽입을 이용한 정렬 알고리즘 Key 값과 정렬된 리스트가 주어졌을 때 , Key 값을 정렬된 리스트의 알맞는 위치에 삽입 Key가 3이고 정렬된 배열이 일때 키를 알맞은 위치에 삽입한 배열은 이다.

선택정렬 가장 작은 값은 찾는다. (첫 번째 값과 두 번째 값을 비교해서 작은 값을 찾고 그 값과 3번째 값과 또 비교하고 이렇게 차례차례 비교해서 가장 앞에 가장 작은 수를 넣는다.) 무조건 모든 것을 비교해 봐야 한다. 즉 최선과 최악의 경우의 수행 시간이 같음 따라서 선택 정렬은 전체의 배열에서 최솟값을 찾아 맨 앞에 위치시키고 인덱스를 하나씩 증가시켜 그다음 작은 값을 위치시킨다. - 최선 최악 경우 시간 : 무조건 n^2 삽입 정렬 - 삽입을 이용한 정렬 알고리즘 - Key 값과 정렬된 리스트가 주어졌을 때, Key값을 정렬된 리스트에 알맞은 위치에 삽입 key 값을 정렬된 배열에 넣으면서 정렬 배열을 하나씩 늘려가는 정렬 방식 최선과 최악의 경우가 다르다. for문 2개가 아닌 while 문을..