요약

1. 진행한 것
2. 새로 알게 된 점
3. 개선할 점

1. 진행한 것

알고리즘 문제 풀이를 진행 한 것은 마찬가지인데 지금까지와는 조금 달랐다.

요세푸스 문제0 - https://www.acmicpc.net/problem/11866
최소 힙 - https://www.acmicpc.net/problem/1927
약수 - https://www.acmicpc.net/problem/1037

항해99 측에서 매일 푸는 문제 수가 너무 많은 것 같다며 3문제로 줄였다. 그래서 오늘부터는 지금까지 풀었던 문제의 복습과 제대로 이해가 안 되고 넘어갔던 개념들을 복습할 수 있었다.

2. 새로 알게 된 점

Heap 구조에 대해 알게 됐고 배열을 Heap 구조처럼 사용해서 우선순위 큐를 직접 구현해봤다.

위 그림과 같이 배열의 인덱스를 노드들의 부모 자식 관계를 확인하는데 이용한다.
부모의 인덱스x2나 (인덱스x2+1)이 해당 노드의 자식 노드들이 된다.

push를 할 때는 배열의 가장 마지막 인덱스의 뒤에 넣고 부모 노드와 크기 비교 후 자식이 더 크면 바꾸는 것을 반복한다.

poll을 할 때는 1번 데이터를 빼낸다. 그 후 마지막 데이터를 1번 인덱스에 넣고 자식들 중 우선순위가 높은 녀석과 비교해서 바꾸는 것을 반복한다. 이 방식을 사용해야 완전 이진 트리 구조가 유지된다.

3. 개선할 점

앞으로 알고리즘 문제를 풀면서 시간복잡도를 계산해보면서 풀어보면 좋을 것 같다.