[알고리즘] 시간복잡도, Kotlin 자료형

 

Intro.

안녕하세요 Pu드로이드 입니다^^

 

취업차.. 코딩테스트 준비를 위해 1일 1백준 알고리즘 풀이를 꾸준히 하고 있는데요!

 

더 나은 문제 접근을 위해 유튜브 바킹독님의 영상으로 알고리즘 기본기를 다질 계획이며,

 

동시에 블로그 포스팅을 통해 정보를 기록하고 공유하려 합니다! 

 

궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!

 

 

 

---

 

 

 

1. 시간복잡도

시간 복잡도 : 입력값에 대해 내가 구상한 코드의 동작시간이 얼마나 걸릴지 예측할 수 있는 척도!

 

백준 문제를 풀다보면 시간 초과와 같은 상황과 마주합니다.

 

이는 주어진 문제의 제한 시간 조건 고려하지 못해 발생하는 일인데요,

 

쉽게 말해 본인이 짠 코드가 속도 측면에서 비효율적이다..! 라고 볼 수 있을것 같습니다.

 

이때, 얼마나 느리길래 이러지? 라며 문제의 조건과 본인의 코드를 확인할텐데

 

문제가 원하는 시간복잡도와 본인 코드의 시간 복잡도를 파악할 수 있다면

 

시간초과의 문제가 발생했을 때 얼른 다른 방법을 찾아 극복할 수 있습니다.

 

(다음과 같은 자료를 확인하며 대략적으로 문제와 내 코드의 시간복잡도를 비교할 수 있습니다.)

 

 

 

보통 빅오 표기법으로 시간 복잡도를 표현하며,

다음 예시로 본인 코드의 시간복잡도를 이해하면 될것같습니다.

 

예시 1)

1번 문제는 i가 N만큼 증가가 되기 때문에 O(n) 의 시간복잡도를 가집니다.

 

 

예시 2)

2번 문제는

바깥 For문안에서 i가 N만큼 돌고,

안쪽 For문안에서도 J가 N만큼 돌기 때문에

대략적으로 O(n^2)의 시간 복잡도를 가집니다.

 

 

예시 3)

3번 문제는

for 문 한개가 있으니 O(n) 아니야? 라고 생각할 수 있으나

자세히보면 i * i  의 값과 N을 비교하기 때문에

i * i = N  을  i = 루트 N 이라고 표기할 수 있습니다.

따라서 시간복잡도는 O(루트N) 입니다.

 

 

 

 

 

---

 

 

 

 

 

2. Kotlin 자료형

알고리즘 풀이를 위해 코틀린 자료형은 반드시 알고 넘어가야합니다.

 

알아야하는 이유를 다음 예시에서 볼까요?

 

https://www.acmicpc.net/problem/10757

10757번: 큰 수 A+B

 

다음과 같은 상황에서 값을 Int형으로 받을경우 범위에서 벗어나기 때문에 오류가 납니다.

ULong 타입으로 받아야 범위에 알맞아 풀리는데요!

 

이러한 이유로 자료형 숙지는 필수입니다.

 

Kotlin 자료형 크기

 

(출처 : https://enter.tistory.com/235)

 

예를들어

int형의 4바이트는 32비트죠 (1바이트 = 8비트)

 

위는 부호가 있는 자료형이기 때문에!!

맨 왼쪽의 부호 비트를 제외하고, 31비트를 사용할 수 있습니다.

 

따라서 2^31 승 즉, -2,147,483,648 ~ 2,147,483,647 의 정수형 숫자를 가질 수 있습니다.

 

양수 음수의 21억까지는 커버가 가능하다는 이야기네요!

 

부호가 없는 경우는 부호비트를 쓸 필요가 없어서

더 크게 2^32비트 통째로 써먹을 수 있습니다.

양수 범위로만 약 43억까지 커버 가능하겠네요 

 

 

 

 

위 표의 범위보다 더 큰범위의 수를 컨트롤하고 싶다면,

BigInteger 키워드를 검색해보세요! 

 

 

 

 

 

 

 

궁금한 점 질문, (정중한)조언을 매우 매우 환영하니 부담 없이 댓글 부탁드려요!