본문 바로가기

Algorithm20

[Level 2] H-Index - 정렬 | C++ [문제] 함수의 인자로 논문의 인용 횟수가 담긴 배열이 주어지는데, 여기서 H-index를 구해 반환하는 것이 문제이다. H-Index란 주어진 논문들 중 인용 횟수가 h번 이상인 논문이 h개 이상 존재하고, 나머지 논문은 h번 이하 인용된 것 중 가장 큰 h 값을 말한다. 말이 좀 어려운데 쉽게 설명해서 배열 [0, 0, 3, 6, 8, 10]이 주어졌다면, 6편의 논문들 중 h 이상의 값을 가지고 그것들이 h편 이상이면 된다. h가 0이라면 0 이상의 값을 0편 이상 가지고 있으므로 만족한다. 1이여도 만족하고 2여도 만족하고 3이여도 만족한다. 4는 4보다 크거나 같은 값이 3개밖에 없으므로 만족하지 않는다. 따라서 0,1,2,3 중 가장 큰 3이 H-Index가 된다. [풀이] 내 풀이 방법은 간.. 2020. 5. 24.
[Level 3] 베스트 앨범 - 해시 | C++ [문제] 문제 설명이 더 헷갈리게 만들어서 예제를 보고 풀었다. 문제는 간단하게 설명해보면 일단 장르와 플레이 횟수가 저장된 벡터가 인자로 주어지는데, 두 벡터의 각 요소는 쌍이다. 무슨 뜻이냐면, 위 예제에서 classic 장르의 어떤 곡의 플레이 횟수가 500, pop 장르의 어떤 곡의 플레이 횟수가 600 이런 식으로 곡의 장르와 플레이 횟수를 두 벡터에 나눠 저장해둔 것이다. 따라서 두 벡터는 크기가 동일하다. 한마디로 위 예제는 클래식 장르 3곡과 pop 장르 2곡이 담긴 리스트다. 여기서 각 장르 내에서 가장 많이 플레이된 두 곡의 인덱스(고유번호)를 차례대로 배열에 담아 반환하는 것이 문제이다. 또한 가장 많이 플레이 된 장르 순으로 저장되어야 한다. 예를 들어 A 장르의 플레이 횟수 합이 .. 2020. 5. 23.
[Easy] Leetcode | 101. Symmetric Tree | TREE BFS DFS - 문제 주어진 이진 트리가 중심을 기준으로 대칭인지 판별한다. - 풀이 다른 여러가지 방법이 있겠지만, 내가 풀이한 방법은 다음과 같다. 1. root 노드를 기준으로 왼쪽 서브트리는 전위 순회(preorder)를 한 결과를 vector에 순서대로 저장한다. 2. root 노드를 기준으로 오른쪽 서브트리는 root-right-left 노드 순으로 순회한 결과를 vector에 순서대로 저장한다. 3. 위에서 구한 두 vector의 요소를 서로 비교하여 다른 요소가 있다면 false를 반환, 모두 같으면 true를 반환한다. 아래 코드에서 1번 예제인 [1, 2, 2, 3, 4, 4, 3] 트리를 예를 들어 위 방법을 적용해보면 다음과 같다. 1. leftSubTree: [2, 3, 4] 2. rightS.. 2020. 4. 24.
[Easy] Leetcode | 70. Climbing Stairs | Dynamic programming - 문제 계단을 오르는 데 정상까지 오르려면 n번의 step을 거쳐야 한다. 한 번에 오를 수 있는 계단의 수는 1 또는 2 step이다. 정상까지 오를 수 있는 방법의 수는? Note: n은 양의 정수로 주어진다. - 풀이 n을 1부터 조금씩 나열해보면 규칙이 보인다. n=1) 1 n=2) 2 n=3) 3 n=4) 5 n=5) 8 n=6) 13 ... 피보나치 수열이다. 즉, 위의 각 결과가 f의 함수의 결과라고 했을 때 각 결과는 다음과 같다. n=1) 1 n=2) 2 n=3) f(2) + f(1) n=4) f(3) + f(2) n=5) f(4) + f(3) n=6) f(5) + f(4) ... 재귀 함수로 구현하면 시간 복잡도는 지수 시간의 복잡도를 가진다. O(2^n) 이 경우 시간 초과로 테스트.. 2020. 4. 20.
[Easy] Leetcode | 53. Maximum Subarray | dynamic programming - 문제 integer 배열이 nums로 주어지는데, nums의 연속적인 부분 배열의 합 중 최댓값을 찾아 반환해주는 함수를 작성하는 문제이다. (부분 배열은 최소 1개의 요소를 가짐) - 풀이 연속적인 부분 배열의 최대합을 구하기 위해 다음과 같은 계획을 세웁니다. 다른 풀이 방법은 더 빠른 시간 복잡도를 가질 수 있지만, 해당 방법은 선형 시간(O(n))의 복잡도를 가진다. 1. 각 요소를 마지막 요소로 가지는 부분 배열들의 합(sum) 중 가장 큰 값을 벡터(subArrayMaxSum)에 저장한다. => 즉, subArrayMaxSum라는 벡터의 [i]번 째 요소엔 nums[i]를 마지막 요소로 가지는 부분 배열의 합 중 가장 큰 합이 들어있다. 2. subArrayMaxSum의 요소 중 가장 큰 .. 2020. 4. 18.
[Easy] Leetcode | 21. Merge Two Sorted Lists | Linked list - 문제 연결 리스트를 이용하여 주어진 정렬된 두 리스트를 병합시켜 새 리스트를 만들어 반환하는 문제이다. 노드 구조체는 문제에 주어진다. - 풀이 우선 주어진 리스트가 NULL일 경우는 나머지 리스트를 그대로 반환해준다. l1과 l2를 가리키는 리스트를 first, second로 선언한다. head라는 더미노드를 만들고 head->next에 반환할 리스트의 첫 노드를 생성한다. 즉 병합된 리스트의 첫 노드는 head->next 노드이다. curNode를 생성해 새로 노드가 추가될 곳을 가리키도록 한다. tempList는 루프를 진행하며 l1과 l2중 크기가 작은 노드를 가리키도록 하며 curNode->next에 tempList->val을 val로 갖는 노드를 생성한다.첫 루프는 둘 중 하나의 리스트가 .. 2020. 2. 1.

티스토리툴바