[C++] HackerRank : 누적합 / 이분 탐색 / 힙 / 투포인터

 

코딩테스트 대비를 위해

해커랭크에서 누적합 / 이분 탐색 / 힙 / 투 포인터 관련 알고리즘

연습하기..!

 

---

 

1. The Maximum Subarray (Normal)

 

 

 

📌 문제 요약

주어진 배열로 만들 수 있는 부분 배열 중

연속적인 원소들의 최대 합과 단순 최대 합을 구하라.

 

구현 코드

vector<int> maxSubarray(vector<int> arr) {
    vector<int> answer;
    int addNum[100001];
    fill(addNum, addNum+arr.size()+1, 0);
    
    addNum[0] = arr[0];
    for(int i=1; i<arr.size(); i++) addNum[i] = max(addNum[i-1]+arr[i], arr[i]);
    answer.push_back(*max_element(addNum, addNum+arr.size()));
    
    int positive = 0;
    for(int num : arr) if(num>0) positive += num;
    if(positive == 0) positive = *max_element(arr.begin(), arr.end());
    
    answer.push_back(positive);
    return answer;
}

 

 

💡 알고리즘 요약

연속적인 원소들의 부분 배열의 합은

누적합 테이블을 현재 값 vs 누적 값 갱신을 통한

최대 값으로 구해준다.

(카데인 알고리즘)

 

 

구현 팁

현재 값과 누적 값을 비교하며 갱신한다.

 

---

 

2. Pairs (Normal)

 

 

📌 문제 요약

두 값의 차이가 k인 쌍의 개수를 구하라

 

구현 코드

int pairs(int k, vector<int> arr) {
    int result = 0;
    sort(arr.begin(), arr.end());
    
    for(int i=0; i<arr.size()-1; i++){
        for(int j=i+1; j<arr.size(); j++){
            if(arr[j] > arr[i]+k) break;
            else if(arr[j] == arr[i]+k){
                result++;
                break;
            }  
        }
    }
    return result;
}

 

💡 알고리즘 요약

정렬 후 이분 탐색 또는

완전 탐색을 사용한다.

 

 

구현 팁

중복 제거 필요 시 set 를 고려할 것.

 

---

 

3. Find the Running Median (Hard)

 

 

 

📌 문제 요약

입력 값이 주어짐에 따라

실시간 중앙값을 계산한다.

 

 

구현 코드

vector<double> runningMedian(vector<int> a) {
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;
    vector<double> result;
    
    for(int i=0; i<a.size(); i++){
        if(right.empty() || a[i] >= right.top())
            right.push(a[i]);
        else {
            left.push(a[i]);
        }
        
        if(right.size()> 1+left.size()){
            left.push(right.top());
            right.pop();
        }
        else if(left.size()> 1+right.size()){
            right.push(left.top());
            left.pop();
        }
        
        if(right.size() > left.size()) result.push_back(right.top());
        else if(right.size() < left.size()) result.push_back(left.top());
        else result.push_back((right.top() + left.top()) / 2.0);
    }
    return result;
}

 

💡 알고리즘 요약

좌측 / 우측 Heap을 구성하여

중앙값 보다 작은 값(maxHeap), 보다 큰 값(minHeap)의

top 값으로 median을 구성해준다.

 

 

구현 팁

원소 삽입 후 항상 크기 균형을 조절해야 한다.

 

---

 

4. The Longest Increasing Subsequence (Hard)

 

 

📌 문제 요약

증가 수열 중 가장 긴 길이의

최장 증가 수열를 구하라

 

 

구현 코드

int longestIncreasingSubsequence(vector<int> arr) {
    vector<int> lis;
    
    for(int num : arr){
        auto pos = lower_bound(lis.begin(), lis.end(), num);
        
        if(pos == lis.end()) lis.push_back(num);
        else *pos = num;
    }
    
    return lis.size();
}

 

💡 알고리즘 요약

이분 탐색 기반 LIS,

DP로 풀고자 할 때엔 배열의 길이가 크면

시간 복잡도가 n^2 이므로 부적합하다. 

 

 

구현 팁

배열의 크기가 10^4 보다 크다면

이분 탐색을 이용하자.

 

---

 

5. Find the Town Judge (Easy)

 

 

📌 문제 요약

마을 판사는 판사를 제외한 모든 마을사람들에게

신뢰를 받는다.

신뢰 관계를 통해 누가 판사인지 찾아라.

 

 

구현 코드

class Solution {
public:
    int findJudge(int n, vector<vector<int>>& trust) {
        if(n==1) return 1;

        unordered_map<int, int> atob;
        unordered_map<int, int> btoa;

        for(vector<int> relationship : trust){
            atob[relationship[1]]++;
            btoa[relationship[0]]++;
        }

        for(auto value : atob)
            if((value.second == (n-1)) && (btoa[value.first] == 0)) return value.first;

        return -1;
    }
};

 

💡 알고리즘 요약

진입차수와 출차수를 비교하여

판사를 찾아내자. 

 

 

구현 팁

vector<int>로 진입과 출차를 비교하는 것이

가장 효과적인 방법

 

---

 

끝!