[SWEA] 7. 힙

이번 시간에는 힙에 관한 내용이었다. 저번 학기 알고리즘 수업 때 힙을 되게 많이 다루어서 힙에는 자신감이 있었다. 수업을 듣기 전에는 힙을 이름만 알고 잘 몰랐지만 학기 중에 여러 번 구현하면서 잘하는 줄 알았지만 아니었다! 수업 때 강의자료에 있는 adjust() 코드를 항상 옆에 참조해서 풀어서 그런가 보다. 수업 때 배운 adjust는 미리 수의 배열이 있고 마지막 부모 노드부터 자식 노드들을 확인하며 자신 아래의 트리가 힙의 원칙에 맞는지 판단하는 방식으로 O(n)의 시간이 걸렸고 heap에서 꺼내어 정렬하는데 O(nlogn)의 시간이 걸려 총 O(nlogn)의 시간이 걸린다.

이번 강에서 배운 내용은 숫자가 주어질 때 heap에 push와 pop을 하는 방법이었다. 처음에 adjust를 사용하려다가 이 내용과 살짝 다르다는 것을 알기 전까지 헤맸다.

 

No31. 기초 Partial Sort 연습 (SWEA 12372)

힙을 배워서 힙 구조를 연습할 겸 힙 자료구조를 활용해서 문제를 풀었다. 하지만 힙을 잘 써보지 않아서 인지 굉장히 오래 걸렸다. 여러 가지 실수를 했는데

1. 반복문을 부모가 0이상일때 멈춰야 했는데 자신이 0 이상일 때 멈춰 힙이 이상해졌다.

2. heap의 제일 마지막 원소가 제일 우선순위가 작은 원소가 아니다. 결괏값을 넘길 때 우선순위가 높은 원소를 넘겨야 해서 max heap을 구현하고 제일 작은 원소를 임계값으로 두기 위해 10번째 원소를 최솟값으로 설정했는데 그러면 안 되고 제일 작은 값을 찾아야 했다.

3. 우선순위를 비교하는 것을 함수로 만들어 활용하였는데 최솟값을 찾을 때 활용하지 않았다.

오후 내내 이 문제만 풀었다. 이런 기초 문제는 보통 main.cpp 가 user.cpp로 나뉘어있는데 input 값을 해석하는 게 너무 힘들다. 

 

No32. 힙 (SWEA 2930)

힙 자료구조를 수현 하는 문제였는데 문제에 친절하게 C++에서는 PQ 가 힙과 같다고 적혀있길래 전 문제에서 힙 구현을 했으니 간단하게 PQ를 활용해서 문제를 풀었다. STL이 좋긴 하다!

 

No 33. 보급로 (SWEA 1249)

그래프 탐색으로 최선의 경로를 구하는 문제였다. SWEA는 스택 영역이 충분하지 않아 BFS + DP로 문제를 풀었다. 오랜만에 최적의 경로를 찾는 문제여서 살짝 버벅거려서 굉장히 자신감이 떨어졌지만 그래도 이내 풀어내 조금은 복구할 수 있었다.

 

No34. 중간 값 구하기 (SWEA 3000)

처음에 숫자 한 개가 주어지고 2개씩 추가되면서 중간값들을 더해나가는 문제이다. 처음에는 PQ를 쓰려니 큐 중간의 원소는 확인이 되지 않아 pop을 하면서 중간값을 찾고 큐를 복원시켜주었더니 시간 초과가 났다. 나중에 문제를 다시 풀 때도 방법이 생각나지 않아 구글링을 했다. 문제의 포인트는 왼쪽 값과 오른쪽 값들을 PQ로 보관하고 있다가 2 숫자를 추가해주고 평형을 맞춰나가는 방식으로 풀면 되는 것이었다.

 

No35. 수 만들기 (SWEA 10806)

할 수 있는 연산들(곱셈과 덧셈)로 특정 수를 구하는 문제였다. 나는 정직하게 0에서 부터 해당 연산들을 이용하여 K 값을 찾아나갔다. 그랬더니 수가 커질수록 시간이 굉장히 오래걸리는데 문제는 테스트케이스 100개가 1초의 제한시간을 가지고 있어 다른 방법이 있다 싶었다. 하지만 고민을 해도 알 수가 없어 결국 알아보니 역연산을 활용해서 K 값에서 0을 먼저 도달하는 방법을 사용하면 문제가 금방 풀리는 것이었다! 이런 수학 문제들을 잘 안풀다 보니 접근 방식이 서툴렀던 것 같다. 다음에 문제를 찾아 풀때 힙 문제와 수학 문제를 조금 더 접해보아야겠다고 생각했다.

 

---

문제를 풀면서 PQ 의 사용법에 대해 많이 알게 되었다.

PQ는 기본적으로 내림차순으로 정렬이 되는데 이는

priority_queue <int> pq;
priority_queue <int,vector<int> ,less<int> > pq2;

와 같이 표현할 수 있으며 오름 차순으로 정렬을 하고 싶으면 음수화를 할 수도 있지만

priority_queue <int, vector<int>, greater<int> > pq;

로 사용할 수 있다.

이외에도 구조체를 사용해서 특정 변수를 키값으로 내림차순으로 만들고 싶다면

struct elem {
    int other;
    int value;
};

struct cmp {
    bool operator()(elem t, elem u) {
        return t.value < u.value; // 기본적 PQ 의 내림차순. 오름차순은 >
    }
};
priority_queue <elem, vector<elem>, cmp> pq;

와 같이 cmp 클래스에 연산자를 만들고 PQ에 오버 로딩하는 방식으로 구현할 수 도 있고

struct elem{
	int other;
    int value;
};
 
bool operator<(elem t, elem u){
    return t.value < u.value;
}
 
priority_queue<elem> pq;

 으로 < 연산자 오버 로딩을 이용할 수도 있다고 한다.