- 파이썬은 1초에 대략 2000만번의 연산이 가능하다고 전제하면 안전하다.
- 대부분 코딩테스트 문제의 제한은 시간제한이 1-5초, 메모리가 128MB-512MB정도 이다.
- 시간제한이 1초인 문제를 만났을경우(대부분) N의 범위가 500이하인경우 O(N^3)으로도 충분히 해결가능하고, 2000이하인 경우, O(N^2)인 알고리즘으로 해결 가능하며 N의 범위가 100,000이하인 경우 O(NlogN)알고리즘으로 해결 가능하고 10,000,000인 경우 O(N)알고리즘으로 해결이 가능하다.
- 경험을 토대로 N이 만단위 이하일 경우 O(N^2)알고리즘으로 충분히 해결 가능하다. 그이상은 O(NlogN)알고리즘을 1순위로 염두해두는게 좋을것 같다.
- 위는 1초가 주어졌을때 추천되는 입력 갯수에따른 알고리즘 설계이다.
- 제일좋은방법은 걸리는 시간을 직접 측정해보는 습관을 가지는것!!!!
- 문제를 풀때마다 위의 코드로 시간을 측정하여 연습하여 대략적인 감을 잡는게 좋지만,,입력의 갯수가 비약적으로 커질때마다 테스트케이스를 일일이 입력하고 있을 시간이 없을것 같기 때문에 문제를 접근하기전에 눈대중으로 메모리와 시간을 고려한 알고리즘을 생각하고 접근하는 연습을하자!
- 위는 int자료형의 원소 갯수만큼 차지하는 메모리 사용량이다.
- 파이썬에서는 메모리 사용량을 꼭 생각해주는게 좋다.
- 파이썬에서 temp=[i for i in range(100000)]이라는 코드가 있다고 가정해보자, 매 for문마다 temp=[동일한 사이즈의 다른 원소]라는 작업을 하게되면, gc에의해 기존에 잡아먹고있던 메모리공간은 버려지고 동일한 사이즈의 다른 공간이 재할당 되게 된다. 즉, 메모리 사용량은 동일하지만, 시간이 더 걸릴수 있다.(시간이 널널하면 단순히 이런식으로 계산해도 무방하다.)
- 메모리를 효율적으로 관리하는 방법으로는 슬라이딩 윈도우기법이 있다.
- 핵심개념은 더이상 필요하지않은 값을 담고있는 저장공간을 갱신시켜나간다는 것이다.
- 무의식중에 사용하고 있을가능성이 높음
- hellominchan.tistory.com/256<<sliding window기법에 대하여 잘 설명해주는것 같다.
- 즉 메모리가 어떻게 사용지에 대한 개념이 확실하면 시간도 줄일수 있다.
- 저번시간에 풀었던 LCS4문제를 보면 입력의크기가 최대 십만이므로 O(N^2)의 알고리즘으로는 무리가 있다고 판단할 수 있다. O(NlogN)의 알고리즘을 사용해야 됨을 알 수 있다.(A의 원소배치를 기준으로 B의 인덱스를 재배치해 그인덱스의 오름차순을 찾는 과정은 NlogN의 연산이다.(재배치된 인덱스들 순서대로 살펴보면서(N)*각각의 인덱스들을 이분법(logN)으로 위치를 찾아주기때문))
- 다른 LCS문제처럼 이차원 리스트를 생성하게되면 2백억개의 int형 정수를 담아야 하므로 주어진 메모리로 어림도 없음을 알 수 있다.->다른 식의 접근을 요한다.
<<결론>>
메모리와 시간을 계산하는 나만의 기준을세우자!!!!!!(반복된 연습을 통해)
끝!
'알고리즘' 카테고리의 다른 글
| algorithm study 시작!! (0) | 2020.08.20 |
|---|