패스트캠퍼스 챌린지 30일차
[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.
1. 백준 1927번 문제
최소 힙을 구현하는 문제이다. 시간 제한은 1초이고 입력 데이터는 N = 100,000, X = 약 2,000,000,000이다. 시간 제한에 따라 구현하기 위해서는 O(N log X)이며 이는 3,100,000번 내 연산으로 해결 가능하다. 이를 위해 다음과 같이 힙 정렬을 구현해보았다.
힙 정렬을 구현할 수 있긴 하지만 삭제할 때마다 모든 원소를 확인해서 최악의 경우 시간 복잡도는 O(N) 시간이 소요될 수 있다.
어떤 방법을 쓰더라도 시간 초과가 나와서 이건 무슨 경우지? 하고 있다가 위와 같은 내용을 확인하게 되었다.(참고)
일반적으로 O(log N)의 효율을 갖지만 최악의 경우를 고려할 경우 더 느려질 수 있다는 것이다. 그래서 파이썬에서 기본으로 제공해주는 heapq 라이브러리를 활용하면 좋다고 한다. 그래도 궁금한 것을 못참는 성격이라 짬내서 개선시킬 수 있는 방법에 대해서 알아봐야겠다.
그리고 다시 라이브러리를 사용해서 문제를 풀어봤다. 런타임을 제외하고 아래에서부터 3개까지는 PyPy3로 사용했는데 메모리가 많이 사용되었고 시간 또한 Python3로 실행시킨 것보다 오래 걸린 것을 알 수 있다. 그리고 반복문에 sys 라이브러리의 readline을 사용해서 시간을 단축시켰다.
특정 경우에 PyPy3가 또는 Python3 유리할 때가 달랐기에 이번 기회에 Python3와 PyPy3의 차이에 대해서도 조금 더 알아보았다.(참고)
2. 백준 1715번 문제
각 카드의 묶음을 섞을 때의 최솟값을 구하는 문제이다. 시간 제한은 2초이고, 데이터는 N = 100,000과 N개의 줄에 최대 1,000의 묶음으로 구성된다. 최악의 경우에는 100,000 * 1,000개로 1억번의 연산이 필요하며 시간 제한 안에 풀기 위해서는 O(N log 1000)으로 약 100만번 내의 연산으로 풀어야한다.
이를 위해 접근 방법은 다음과 같다.
1. 카드 묶음을 묶어 나갈 때 최소화된 카드 묶음에서부터 묶어나간다. -> 그리디
2. 이를 위해 입력된 카드 묶음 수에서 최소화된 카드 묶음을 뽑는다. -> 최소 힙 정렬
3. 뽑은 카드 묶음을 더해 최소값을 출력한다. -> 반복문
복기
1. Python3과 PyPy3를 비교해보면 PyPy3가 성능이 좋다. 단순한 코드에 반복 수가 많아서 그런 것일까? 계속 비교하면서 알아봐야겠다.
2. 문제를 해석하고 풀이 방법까지 잘 적용했으나 더 깊이 이해하지 못해서 좀 헤맸다. 문제 해석 능력은 필수적이다.
3. 그리디와 힙 정렬의 조합을 막강했다!
3. 백준 1715번 문제
풀 문제의 순서를 구하는 문제이다. 문제는 1번부터 N번까지 있고 오름차순으로 난이도가 올라간다. 그리고 문제와 조합에 따라 더 쉬워질 수 있기 때문에 우선 순위도 고려해야한다.
데이터는 N = 32,000, M = 100,000으로 총 3,200,000,000개의 데이터를 다루게 된다. 이를 위해 O(N log M)으로 32,000 * 17 = 544,000번의 연산이 가능하므로 제한 시간 내에 풀이할 수 있다.
여기에서는 위상 정렬(Topology Sort) 알고리즘을 사용할 수 있는데, 이 알고리즘은 강의에 나와있지 않아 블로그 참고하여 구현 및 학습 후 진행하였다.(참고)
3 - 1. 기본 알고리즘 학습
알고리즘을 구현하는 과정에서 블로그에 나와 있는 코드(좌)로는 입력된 정점과 간선을 기준으로 진입 차수와 그래프를 생성했기 때문에 제한된 조건(연속된 수)에 한해 위상정렬 알고리즘을 사용할 수 있어 우측과 같이 보완하였다. 시간 복잡도는 O(V + E)
3 - 2. 문제 풀이 적용
1차 시도에서는 앞서 기본 알고리즘 학습에서 보완했던 코드 + heapq 자료구조를 사용하였다. heapq를 사용했던 것은 문제 번호(난이도)가 작은 것부터 풀어야하는 조건이 있었기 때문에 최소 힙 알고리즘을 적용하기 위해서다. 하지만 틀렸다.
여기서 간과했던 것은 1번 문제에서부터 N번 문제까지 있던 것이었는데, 기존 코드의 그래프 생성에서 보면 입력된 값들에 한해서만 그래프와 진입차수를 생성해준다. 하지만 문제에서는 먼저 푸는 것이 좋은 문제(입력된 값)가 몇몇 문제에 한정되어 있는 것을 알 수 있다.
2차 시도에서는 이를 보완해서 모든 값을 초기화 시켜주는 코드를 추가로 작성하였고 마침내 풀이에 성공했다.
Python3와 PyPy3 비교
1. PyPy3는 Python3의 실행 속도를 개선하기 위해 JIT 컴파일 방식을 도입했다.(참고)
JIT compiler는 인터프리터 방식으로 실행하다가도 시점에 따라 바이트 코드 전체를 컴파일해서 네이티브 코드로 변경하고 캐시에 보관한다. 이로 인해 해당 메소드는 더이상 인터프리팅하지 않고 저장된 네이티브 코드로 직접 실행하기 때문에 코드를 빠르게 수행하게 된다.
2. PyPy3는 자주 쓰이는 코드를 캐싱하는 기능이 있다. 이로 인해 메모리를 더 많이 사용해서 자주 쓰이는 코드를 저장하고 이를 통해 실행 속도를 개선할 수 있다.
따라서 간단한 코드라면 Python3를, 특정 코드가 반복되는 코드라면 PyPy3를 쓰는 것이 효율적인 것을 알 수 있다.
패스트캠퍼스 [직장인 실무교육]
fastcampus.co.kr
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.