C++ Tip

SW Expert Academy (Samsung) Pro 레벨 테스트 대비 tip 정리

부분문자열의 suffix 사전 순 배열

suffix로 시작하는 str의 부분 문자열의 사전 순으로 배열 하는 문제인데…

strcmp(str1, str2) 이 <0 인 경우가 사전 배열임!!

(생각지도 못했음..)

#include <string.h>
#include <algorithm>
using namespace std;

char str[400];
int suffix[400]; // 접두어의 idx

bool compare(const int& a, const int& b) {
    return strcmp(str + a, str + b) < 0; // 사전 순 배열
}

int main()
{
  int strLen = strlen(str);
  for (int i=0; i<strLen; i++)
    suffix[i] = i;
    
  sort(suffix, suffix + strLen, compare); // suffix를 사전 순으로 배열해줌
}

dijkstra 알고리즘과 priority_queue

Heap은 에서 `priority_queue<>` 과 같이 선언 할 수 있다.

이때, 기본이 내림차순이므로 top()할 때 가장 큰 수로 나오는 것을 유의해야한다.

따라서, 우선 순위 큐를 뒤집어 주어야하는데 방법이 좀 까다롭다.

pair를 안 쓰면 priority_queue<int, vector<int>, greater<int> > pq;로 나름 간단하지만,

pair를 쓰게 되면 아래와 같이 struct 설정하여 연산자 오버로딩을 해야한다.

혹은 비교를 원하는 거리를 pair의 first에 놓고 greater<pair<int, int> > 추가해도 됨.

#include <vector>
#include <queue>

struct cmp{

    bool operator()(pair<int, int>&a, pair<int, int>&b) {
        return a.second > b.second;
    }
};

priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq; // heap

이렇게 우선순위큐를 구성을 하면 아래와 같이 dijkstra를 구현 할 수 있다.

void dijkstra(int start)
{
    d[start] = 0;
    priority_queue<pair<int, int>, vector<pair<int, int> >, cmp> pq; // heap
    pq.emplace(make_pair(start, 0));

    while(!pq.empty()) {
        int current = pq.top().first;
        int distance = pq.top().second;
        pq.pop();

        printf("current : %d\n", current);

        if(d[current] < distance) continue;
        for (int i=0; i < a[current].size(); i++) {
            int next = a[current][i].first;
            int nextDistance = distance + a[current][i].second;
            if (nextDistance < d[next]) {
                d[next] = nextDistance;
                pq.emplace(make_pair(next, nextDistance));
            }
        }

    }
}

이때, push보다는 emplace가 대부분 효율적이라고 한다..

dijkstra 알고리즘과 최적화

Lazy version vs Eager version

• Lazy version

  node relaxing 될 때, 기본 priority queue에 해당 node의 값이 있어도 업데이트 하지 않는다.

  나중에 해당 queue 차례가 될 때, dist[idx] < minValue가 자연스럽게 형성 되어 continue 처리한다.

• Eager version

  반면에, Eager version은 애초에 key-value로 priority queue에 넣어서

  relaxing 될 때 queue안에 key 값이 있는지 확인하고 있다면 ‘수정’, 없다면 ‘추가’ 한다.

또한, end node가 정해져 있다면 idx == end 일 때 바로 break 하면 시간을 줄 일 수 있다.

visit을 이미 한 노드는 더 이상 진행해봤자 dist는 고정되어 버리기 때문이다.