나의 알고리즘 공부 여정5 - 시간 복잡도, 코드 효율화

 

20210312_TIL

 

• 알고리즘 개념 학습 기간이 끝났다. 이제 하~중 난이도의 알고리즘 문제들을 양치기(?) 하는 기간이다. 오늘은 어제, 그제 풀었던 문제 대비 쉬운 문제들을 풀었다. 대신, 지난주 하루 평균 3~4문제들을 푼 것과 달리 오늘은 7문제나 풀었다. 지난 주에 학습을 완료한 개념들을 많이 많이 응용해보는 기간이라 생각하면 될 듯하다. 기본이 되는 개념학습이 거의 완료되어 있어서 그런지, 지난 주 대비 난이도 하 알고리즘 문제를 푸는 시간이 매우매우 단축되었다.

 

• 그러다 보니 자연스럽게 코드 효율화에 대한 고민이 깊어졌다. 이제 난이도 하 문제는 답을 못맞출 일은 없다. 이 다음에 필요한 것은 효율화다. 어떻게 하면 시간복잡도를 줄일 수 있는지, for 문 중첩을 최대한 안쓸 수 있는지에 대한 고민들을 시작했다. 

 

• 코드 효율화를 위한 노력은 다음과 같다. 알고리즘 문제 풀이 공유 시간에, 팀원들의 코드와 내 코드를 비교해가며 각각 시간복잡도를 계산해보았다. 내 풀이보다 시간복잡도가 낮은 풀이가 있다면 내가 쓴 코드와 꼼꼼히 비교했다. 그리고 풀이를 참조하여 내 코드 로직을 변경하지 않는 선에서 시간 복잡도를 최대한 줄이려는 시도를 했다. 효율화를 마치고서는 백준 사이트에 코드를 다시 제출해 걸리는 시간을 체크했다!

 

 

코드 효율화 예시

 

베르트랑 공준 4948번

 

4948번: 베르트랑 공준

 

코드 효율화 전과 후의 코드를 먼저 비교해보자

 

 

 

 

왼쪽이 코드 효율화 전, 오른쪽이 코드 효율화 후의 코드다. 기본 로직은 하나도 변한게 없다. 기본 로직을 바꾸지 않고도 코드를 효율화 할 수 있다는 것을 배웠다.

 

 

왼쪽 코드는 python3 기준 시간초과, pypy 기준 472ms 이 소요된다. 하지만 오른쪽 코드는 python3 기준 176ms, pypy 기준 152ms 이 소요된다. 자 그럼 어떻게 효율화가 진행되었는지 살펴보자.

 

 

1. while문으로 입력값을 받아야 하는 상황에서, while문안에 입력값과 출력값 뿐 아니라 모든 연산을 넣어놓은 것이 치명적이었다. 왼쪽 코드는 while문으로 입력값을 받고, 받은 입력값으로 연산을 돌렸다. 덕분에 while, for, while 이렇게 반복연산이 세개나 중첩되어 버렸다. 

 

-> 해결책: 주요 연산은 따로 완료한 다음에, 그 값을 가져와 마지막에 while문으로 입력값을 받고 연산된 값을 가져와 출력하는 식으로 구현했다. 여기서 반복문 중첩이 한번 풀렸다. 시간 복잡도를 엄청나게 줄였다! 반복문을 중첩할 때에는 정말 많은 고민을 해야 하겠다...!

 

 

2. 이 문제는 True 인 값이 몇 개나 되는지를 물어보는 문제였다. 이 경우에는 True를 1로 표현할 수 있으니까 1로 표현하고 나중에 1로 표현된 값을 더해주기만 하면 되는 멋진 방법이 있었다. 나는 True, False 대로 구현하고 나중에 그걸 따로 세 주느라 for 반복문을 한번 더 사용했다. 문제에서 물어보는게 무엇인지에 따라 Boolean 값을 숫자로 설정하는 게 훨씬 효율적일 때가 있다! 항상 출력 형태를 고민하면서 변수 표현형태를 고르자.

 

 

3. 배수를 좀 더 간단하게 표현하는 법이 있었다. 알아두면 다른 문제에서 시간 복잡도를 줄여줄 수도 있을 듯하다! 

 

100까지의 2의 배수를 구할 때

for i in range(2, 101, 2):

  result = i

 

이렇게 표현이 가능하다. range 괄호 안의 맨 끝 숫자가 증가분이니 저렇게 쓰면 배수 형태를 구현할 수 있다.

 

 

4. 마지막으로 n개의 요소가 동일한 값을 가진 리스트 만들기! 이를 처음 코드에서는

 

array = [True for i in range (n)] 라고 표현했는데

array = [1]*n 으로 표현해도 동일하다!

 

for문 한번 더 쓰는건 다른 연산에서 for문이 필요해서 쓴 상황에서는 시간 복잡도에 큰 영향을 주지는 않는다. 그래도 모든 코드들을 효율화 하는 방식을 생각해보는 것은 추후 분명히 도움이 될 것이다.

 

 

---

 

덧붙여, 실전 문제풀이도 좋지만 전체적인 개념 구조를 잡고 개념의 빈 공간들을 채워 나가야 한다는 생각이다. 실전 알고리즘 문제풀이 주차에 알고리즘 개념 책도 한권 읽을 예정이다.

 

book.naver.com/bookdb/book_detail.nhn?bid=16419115

Do it! 자료구조와 함께 배우는 알고리즘 입문

일단 딱 400 페이지로 구성되어 있다. 오늘 기준으로 50 페이지 읽었는데, 기왕이면 알고리즘 주차에 맞춰서 다 읽는 것을 목표로 하고 있다!