H-index 문제 https://programmers.co.kr/learn/courses/30/lessons/42747# 문제 설명 H-Index는 과학자의 생산성과 영향력을 나타내는 지표입니다. 어느 과학자의 H-Index를 나타내는 값인 h를 구하려고 합니다. 위키백과1에 따르면, H-Index는 다음과 같이 구합니다. 어떤 과학자가 발표한 논문 n편 중, h번 이상 인용된 논문이 h편 이상이고 나머지 논문이 h번 이하 인용되었다면 h의 최댓값이 이 과학자의 H-Index입니다. 어떤 과학자가 발표한 논문의 인용 횟수를 담은 배열 citations가 매개변수로 주어질 때, 이 과학자의 H-Index를 return 하도록 solution 함수를 작성해주세요. 제한사항 과학자가 발표한 논문의 수는 1편..

K번째 수 문제 https://programmers.co.kr/learn/courses/30/lessons/42748 문제 설명 배열 array의 i번째 숫자부터 j번째 숫자까지 자르고 정렬했을 때, k번째에 있는 수를 구하려 합니다. 예를 들어 array가 [1, 5, 2, 6, 3, 7, 4], i = 2, j = 5, k = 3이라면 array의 2번째부터 5번째까지 자르면 [5, 2, 6, 3]입니다. 1에서 나온 배열을 정렬하면 [2, 3, 5, 6]입니다. 2에서 나온 배열의 3번째 숫자는 5입니다. 배열 array, [i, j, k]를 원소로 가진 2차원 배열 commands가 매개변수로 주어질 때, commands의 모든 원소에 대해 앞서 설명한 연산을 적용했을 때 나온 결과를 배열에 담아..

퀵 정렬 개념 퀵 정렬의 세부과정은 다음과 같다. pivot이라는 요소를 선택한 후, pivot을 기준으로 왼쪽에는 pivot보다 작은 요소들을 놓고 오른쪽에는 pivot보다 큰 요소들을 놓는다. 이후 순환호출을 이용하여 재귀적으로 왼쪽, 오른쪽으로 분류해둔 요소들에 대해 전과 같은 과정을 반복한다. 위의 그림은 오른쪽 요소들에 대해 순환호출한 모습이다. 분할이 불가능할 때까지 반복하다보면 최소한의 요소로 나누어지고 이후 순서대로 결합을 진행한다. 위의 그림에서 색이 칠해져있는 요소들을 순서대로 합치면 된다. 퀵 정렬은 분할 정복 알고리즘 중 하나이다. pivot으로 2개의 부분 배열을 생성하는 분할(Divide) 과정과 부분 배열을 재귀적으로 호출하는 정복(Conquer) 과정과 정렬된 부분 배열을 합..

가장 큰 수 문제 문제 설명 0 또는 양의 정수가 주어졌을 때, 정수를 이어 붙여 만들 수 있는 가장 큰 수를 알아내 주세요. 예를 들어, 주어진 정수가 [6, 10, 2]라면 [6102, 6210, 1062, 1026, 2610, 2106]를 만들 수 있고, 이중 가장 큰 수는 6210입니다. 0 또는 양의 정수가 담긴 배열 numbers가 매개변수로 주어질 때, 순서를 재배치하여 만들 수 있는 가장 큰 수를 문자열로 바꾸어 return 하도록 solution 함수를 작성해주세요. 제한 사항 numbers의 길이는 1 이상 100,000 이하입니다. numbers의 원소는 0 이상 1,000 이하입니다. 정답이 너무 클 수 있으니 문자열로 바꾸어 return 합니다. 입출력 예 numbers retur..

선택 정렬 개념 max, min 정렬이라고도 불린다. 처음부터 끝 원소까지 훑으면서 최소나 최대를 찾아서 리스트의 처음이나 끝에 넣고 해당 원소를 제외한 다른 원소에 대해 다시 정렬을 시행하는 방법이다. 무작위로 정렬된 데이터의 처음부터 끝까지 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다. 그 후 마지막 원소를 제외한 채로 처음부터 끝까지 데이터를 탐색한 후, 가장 큰 수를 리스트의 마지막 요소와 교환한다. 구현 의사 코드는 다음과 같다. (min 정렬) for i=0 to n: a[i]부터 a[n-1]까지 차례로 비교하여 최소값이 있는 a[j]를 찾는다. a[i]와 a[j]를 바꾼다. (max 정렬) for i=0 to n: a[0]부터 a[n-i-1]까지 차례로 비교하여 최대값이 있는 ..

정렬 어떤 데이터들이 주어졌을 때 이를 정해진 순서대로 나열하는 문제가 '정렬'이다. 보통 컴퓨터에서는 탐색을 위해서 정렬을 수행한다. 탐색은 정렬을 통해 하는 것보다 더 강력한 알고리즘이 있지만, 한 번 데이터를 정렬해두면 다음부터는 이진 탐색이라는 빠른 알고리즘을 몇 번이고 사용할 수 있기 때문에 유용하다. 그래서 주어진 무작위의 데이터를 정렬하는 것에 많은 연구자들이 방법을 내놓았는데, 앞으로 설명할 6개의 정렬 알고리즘이다. 그 외에도 많은 정렬 알고리즘이 존재한다. 모든 정렬의 설명에 앞서서 예제로 설명할 데이터는 다음 그림과 같이 무작위로 배치되어있는 1~7의 데이터이다. 정렬 알고리즘의 시간 복잡도는 비교 + 이동으로 측정한다. 특성 정렬 알고리즘은 여러 기준에 따라 나뉠 수 있다. 시간 복..

힙 용도 구현 종류 연산 정렬 힙 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. partial-ordering (부분 정렬)을 만족하는 left-complete binary tree (좌측 완전 이진 트리) 이다. 부분 정렬을 만족한다는 말은 '부모 노드와 자식노드' 간에는 특정 대소관계 성립하지만, '형제노드'간에는 해당 대소관계가 성립하지 않는다는 뜻이다. 이진 탐색 트리에서는 중복된 값을 허용하지 않지만 힙 트리에서는 허용한다. 용도 힙은 추상적 자료형인 우선순위 큐를 구현하기 위해서 만들어진 자료구조이다. 배열과 연결리스트를 이용하면 삽입과 삭제 연산 중 하나가 O(n)일 수 밖에 없다. 하지만 힙을 이용하면 가장 큰 값이나 가장 작은 값을 둘 다 O(logn)만에 빠..

Quick sort '알고리즘' 전공 수업시간에 나온 과제인 '1000만개 데이터 정렬 후 해시 값 구하기'를 하면서 정리한 내용이다. 분할 정복 방법을 통해 구현되는 정렬 방법 시간 복잡도 최악 : O(n^2) 평균 : O(nlogn) 설계를 통해서 개선 가능한 부분 구현 과정 pivot을 선택한다. 위쪽 포인터가 낮은 쪽으로 가면서 피벗보다 작은 수를 찾는다. 아래쪽 포인터가 높은 쪽으로 가면서 피벗보다 큰 수를 찾는다. 두 포인터가 가리키는 요소를 교환한다. 2-4를 반복한다. 두 포인터가 교차한다면 현재 피벗과 해당 위치의 값을 교환한다. 피벗과 피벗보다 작은 section, 피벗보다 큰 section으로 나누고 각 section에 대해 1-5를 실행한다. section의 크기가 0 또는 1이면 ..