[Coding test] (바킹독 실전 알고리즘) 기초 코드 작성 요령 I : 시간복잡도, 공간복잡도 (feat. Python)

INTRO

KEY POINT

시간 복잡도 공간복잡도를 문제를 보고 빠르게 파악하자!

 

강의에대한 내용정리는 바킹독님께서 친절하게 텍스트까지 남겨주시며 최고의 강의를 해주고 있으시니 이 블로그에서는 문제 풀이를 파이썬으로 풀어보기만 하도록 하겠습니다. 개념이나 내용이 궁금하다면 아래 링크에서 바킹독님의 강의를 듣는 것을 추천합니다.

 

기초 1주차 강의에서 시간복잡도, 공간복잡도 코딩테스트 문제 풀이 입니다.

https://blog.encrypted.gg/922

[실전 알고리즘] 0x01강 - 기초 코드 작성 요령 I

 

시간 복잡도 표

항상 문제를 풀이하기전에 시간복잡도를 대충 계산하고 문제를 푸는 것이 좋다는 것을 이 강의를 통해 알았습니다.

앞으로 문제를 풀이 할때마다 이 시간 복잡도 표를 자주 보게 될 것 같아서 따로 캡처 해뒀습니다.

 

문제풀이

강의자인 바킹독님꼐서는 c++언어로 문제를 풀이 하셨기 때문에 저는 파이썬으로 알고리즘을 풀어보려 합니다.

문제에 대한 설명은 바킹독님의 설명을 거의 그대로 가져온 것입니다. 

문제 1

for문에서 i가 1부터 N까지 돌며 3으로 나누어지는지, 5로 나누어지는지 확인합니다.

 

그러므로 시간복잡도는 O(N)입니다.

 

My solution

**시간 복잡도 : o(N)**

 

문제 2

I가 0일 때 N-1개의 수에 대해 합을 100과 비교하고, i가 1일 때 N-2개의 수에 대해 합을 100과 비교하고, 이런식으로 쭉쭉쭉 가다가 i가 N-2일 때 1개의 수에 대해 합을 100과 비교하니 다 더하면 연산은 (N²-N)/2번 일어나고, 이걸 빅오표기법으로 나타내기 위해 상수 떼고 더 낮은 항을 없애고나면 O(N²)인걸 알 수 있습니다.

My solution

**시간 복잡도 : o(N)**

 

문제 3

 i가 1부터 올라가면서 1의 제곱이 N과 일치하는지 확인하고 2의 제곱이 N과 일치하는지 확인하고 계속 가다가 N과 일치하는 순간이 있으면 N이 제곱수이니 1을 반환하고, 일치하는 순간이 없이 i의 제곱이 N보다 커져 for문을 탈출하게 되었다면 제곱수가 아니니 0을 반환하면 됩니다.

 

이 방식의 시간복잡도는 i가 1부터 2, 3 이렇게 가다가 최대 √N까지 올라갈테니 시간복잡도는 O(√N)이 됩니다. 이렇게 시간복잡도에 루트가 들어갈 수도 있습니다.

 

My solution

**시간복잡도 O(√N)**

 

문제 4

코드에서 val은 2의 거듭제곱이 저장되는 변수입니다. 맨 처음에는 1로 시작해서 2, 4, 8, ··· 이렇게 커지다가 val을 2배했을 때 N보다 커지게 되는 순간에 while문을 탈출해서 val을 반환하면 문제에서 요구하는 답을 구할 수 있게 됩니다.

 

이 방식의 시간복잡도는 N이 2k 이상 2k+1 미만이라고 할 때 while문 안에서 val은 최대 k번만 2배로 커집니다. 그러고나면 val은 2k가 되고, 이후 2*val <= N이 거짓이 되기 때문입니다. 그러니까 N이 2k 이상 2k+1 미만이라고 할 때 시간복잡도가 O(k)이고 로그의 정의에 입각해서 생각할 때 k는 lgN이니 결국 시간복잡도는 O(lgN)이 됩니다.

My solution

**시간복잡도는 O(lgN)**

 

 

여기까지가 기초강의 01강 파이썬 문제풀이 였습니다. 이 후 공간복잡도 관련한 개념이 있지만 문제는 없는 관계로 생략하도록 하겠습니다. 개념관련해서는 바킹독님의 강의를 듣고 같이 문제를 풀고 파이썬 언어를 사용하시는 분들은 정답을 비교 해주시는 용도로 활용해주시면 될 것 같습니다.

 

항상 데이터만 다루고 모델링만하다가 코딩테스트를 하려니까 헷갈리는 부분이나 연산식도 까먹은게 되게 많네요...

바킹독님의 강의를 듣고 문제를 풀면서 끝까지 강의를 끝내보도록 하겠습니다.

 

다음 강의도 화이팅..!