시간복잡도란 무엇일까요?

점근적 실행시간, 또는 big-O 시간에 대한 개념 이라고 말을 합니다. 예를 들어 데이터 전송 '알고리즘'의 실행시간을 예를 들어 보겠습니다.

온라인 전송 : O(s). 여기서 s는 파일의 크기가 된다. 즉, 파일의 크기가 증대함에 따라 전송 시간 또한 선형적으로 증가합니다.

비행기를 통한 전송 : O(1). 파일 크기에 관계없이 파일을 전송하는데 걸리는 시간이 늘어나지 않는다. 즉, 상수 시간만큼 소요된다.

간단하게 그래프로 그려 보겠습니다.

파랑 : O(1), 빨강 : O(s)

시간복잡도를 구할 때 기억할 것

  • 상수항은 무시하라
  • 지배적이지 않은 항은 무시하라

상수항은 무시하라

만든 알고리즘의 시간 복잡도가 4N+100000라는 시간이 걸린다고 생각해보자. N값의 따라 걸리는 시간이 달라진다. N의 값이 점점 커지고 여러분이 상상하는 가장 큰 숫자가 된다고 생각해보자. 뒤에 상수항은 그 숫자에 얼마나 큰 영향을 주게 되나요?

지배적이지 않은 항은 무시하라

이번에 만든 알고리즘의 시간복잡도는 N2 + N + 1000000 의 시간이 걸린다고 생각해보자. 이번에도 N의 값을 계속해서 키워나갈 때, N2의 값, N의 값, 1000000 들의 변화를 살펴보자. N2값에 비하면 N은 상수항과 비슷한 느낌을 받는다. 즉, N2값에 따라 이 알고리즘이 걸리는 시간이 결정된다. 그러므로 이 알고리즘을 big-O표기법을 사용해 표현하면 O(n2)의 시간복잡도를 가진다고 말할 수 있다.

덧셈 vs 곱셈

덧셈 수행시간 : O(A + B)

1
2
3
4
5
6
7
for(int a : arrA) {
    print(a);
}
 
for(int b : arrB) {
    print(b);
}

곰셈 수행시간 (A * B)

1
2
3
4
5
for(int a : arrA) {
    for(int b : arrB) {
        print(a + "," + b);
    }
}

알고리즘이 두 단계로 이루어져 있다고 가정하자. 어떤 경우에 수행 시간을 곱하고 어떤 경우에 더해야 할까?

  • 만약 알고리즘이 "A 일을 모두 끝마친 후에 B일을 수행"하는 형태라면 A와 B의 수행시간을 더해야한다.
  • 만약 알고리즘이 "A 일을 할 때마다 B일을 수행"하는 형태라면 A와 B의 수행시간을 곱해야 한다.

log N 수행시간

O(logN) 수행 시간을 자주 접할텐데 이 수행 시간은 어떻게 구해진걸까?

binary search(이진 탐색)을 생각해보자. 이진 탐색은 N개의 정렬된 원소가 들어있는 배열에서 원소 x를 찾을 때 사용된다. 먼저 원소 x와 배열의 중간값을 비교한다. 'x==중간값'을 만족하면 반환한다. 'x < 중간값'일 때는 배열의 왼쪽 부분을 재탐색하고 'x > 중간값'일 경우에는 배열의 오른쪽 부분을 재탐색한다.

처음에는 N개가 들어있는 배열에서 시작한다. 한 단계가 지나면 탐색해야할 원소의 개수가 N/2로 줄어들고, 다음 단계에서는 N/4로 줄어든다. 그러다 원소를 찾거나 탐색할 원소 1개가 남으면 탐색을 중지한다.

시작 N이 16이라고 가정하고 정리하면,

N = 16

N = 8

N = 4

N = 2

N = 1 의 결과로 원하는 x를 찾을 수 있다.

반대로 16에서 1로 증가하는 순서로 생각해보면 1에 2를 몇번이나 곱해야 할까?

N = 1

N = 2

N = 4

N = 8

N = 16 약, 4번 2를 곱하고 결과 값을 얻을 수 있다.

즉 2k = N을 만족하는 k는 무엇인가? 이때 사용되는 것이 바로 로그(log)이다.

2k = N  ▶  log216 = 4  ▶  4

log2N = k  ▶ 2k = N

 

어떤 문제에서 원소의 개수가 절반씩 줄어든다면 그 문제의 수행 시간은 O(logN)이 될 가능성이 크다. 로그의 밑은 고려하지 않아도 된다. 밑이 다른 로그는 오직 상수항만큼만 차이가 나는데 위에서 언급했듯이 상수항은 영향이 크지 않다. 표현할 때도 logN으로 표현되며, 로그의 밑은 무시해도 된다.

 

재귀적으로 수행시간 구하기

1
2
3
4
5
6
int f(int n) {
    if (n <= 1) {
        return 1;
    }
return f(n -1) + f(n - 1);
}

재귀 함수의 수행시간은 어떻게 구해야할까? 함수 f가 두 번 호출된 것을 보고 성급하게 O(N2)이라고 결론 내린 사람은 다시 생각해보자. 수행 시간을 추측하지 말고 코드를 하나씩 읽어 나가면서 수행 시간을 계산해 보자. n = 4라고 가정하자.

f(4)는 f(3)을 두번 호출한다.

  • f(4) : f(3), f(3)

f(3)은 f(2)를 두번 호출하며 f(3)은 2개가 있다.

  • f(3) : f(2), f(2)    *  2

f(2)는 f(1)을 두번 호출하며 f(2)는 4개가 있다.

  • f(2) : f(1), f(1)    *  4

총 호출 횟수는 몇 개인가? 일일이 세지 말고 계산해보자!

f(4)

f(3)                                     f(3)

       f(2)            f(2)                   f(2)               f(2)     

 f(1)    (f1)    f(1)    f(1)           f(1)    f(1)    f(1)    f(1)

트리의 형태로 표현하면 위와 같다. 트리의 깊이가 N이고, 각 노드는 두개의 자식 노드를 갖고 있다. 따라서 깊이가 한 단계 깊어질 때마다 이전보다 두 배 더 많이 호출하게 된다. 같은 높이에 있는노드의 개수를 세어 보자.

깊이 노드의 개수 다른 표현방식 또 다른 표현방식
0 1   20
1 2 2 * 2이전 깊이 = 2 21
2 4 2 * 2이전 깊이 = 2 * 21=22 22
3 8 2 * 2이전 깊이= 2 * 22=23 23

따라서 전체 노드의 개수는 20 + 21 + 2 2 + ... + 2N(=2N+1-1)이 된다. 이 패턴을 기억하길 바란다. 다수의 호출로 이루어진 재귀 함수에서 수행시간은 보통 O(분기깊이)로 표현되곤 한다. 여기서 분기란 재귀 함수가 자신을 재호출하는 횟수를 뜻한다. 따라서 예제의 경우에 수행 시간은 O(2n)이 된다.

앞에서 언급했는데 로그의 밑은 상수항으로 취급되기 때문에 big-O표기법에서 로그의 밑은 무시해도 된다고 했었다. 하지만 지수에서는 얘기가 달라진다. 지수의 밑은 무시하면 안된다. 간단한 예로 2n과 8n을 비교해보자.

8n은 2(3)n = 23n = 22n*2n 으로 표현할 수 있다. 8n은 2n에 22n을 곱한 것과 같으므로 2n과 8n사이에는 22n만큼의 차이가 있다. 이 차이는 지수항이므로상수항과는 아주 큰 차이가 있다.

 

처음에는 big-O 시간이라는 개념이 어렵게 느껴질 수 있다. 하지만 한번 이해하면 꽤 쉽게 받아들일 수 있으니 다른 코드나 자신이 만든 코드의 시간 복잡도가 어떻게 되는지 위와 같이 계산해보길 바란다.

오메가 : 최선의 시간을 고려
세타 : 평균의 시간을 고려
오 : 최악의 시간을 고려 (세타를 O(오)로 통합해 표현하기도 합니다)

'Algorightm' 카테고리의 다른 글

[Kotlin] 387.First Unique Character in a String [LeetCode]  (0) 2020.05.12
[Kotlin] 344.ReverseString [LeetCode]  (0) 2020.04.28
[Level1] 완주하지 못한 선수  (0) 2019.10.24
Hash Algorithm  (0) 2019.10.14


 

Chapter3 : Jailbreak 네번째 문제풀이를 하겠습니다.

 

Pattern : A man, a plan a canal: Panama

 

 

 

이번에도 어렵지않게 패턴의 규칙을 찾아낼 수 있습니다.

 

배열안의 원소들이 가운데원소를 기점으로 좌우대칭을 이룬상태인지를 확인해주면 되는 간단한 규칙입니다.

 

그럼 코드로 작성해보겠습니다. 얍!

 

 

배열의 처음부분과 끝부분에서부터 점점 배열의 위치를 가운데로 이동시켜서 비교해줍니다.

 

그렇게 모두 같으면 true를 리턴하게되고 틀린게 하나라도 있다면 false를 리턴해주게 됩니다.

 

참 쉽죠?

 

 

깔끔히 Chapter3 : Jailbreak 모두 성공했습니다. 다음에 Chapter4 로 돌아오겠습니다.

 

이상 Chapter3 : Jailbreak(4) 풀이 였습니다.

'Coding > hacked' 카테고리의 다른 글

3.hacked : Jailbreak (3)  (0) 2017.08.03
3.hacked : Jailbreak (2)  (0) 2017.08.03
3.hacked : Jailbreak (1)  (0) 2017.08.03
2.hacked : High School Hack (4)  (0) 2017.08.02
2.hacked : High School Hack (3)  (0) 2017.08.02


 

Chapter3 : Jailbreak 세번째 문제풀이를 하겠습니다.

 

Pattern : This is odd

 

 

이번 패턴도 간단합니다. 홀수일 경우에는 1을 돌려주고 짝수일경우에는 0을 돌려주면 됩니다.

 

그럼 코드로 작성해보겠습니다. 얍!

 

 

입력값이 1보다 큰동안에 반복문을 이용해서 입력값에서 2씩 계속 값을 빼줍니다.

 

참 쉽죠?

 

 

깔끔히 성공했습니다. 다음에 네번째 문제로 돌아오겠습니다.

 

이상 Chapter3 : Jailbreak(3) 풀이 였습니다.

 

'Coding > hacked' 카테고리의 다른 글

3.hacked : Jailbreak (4)  (0) 2017.08.03
3.hacked : Jailbreak (2)  (0) 2017.08.03
3.hacked : Jailbreak (1)  (0) 2017.08.03
2.hacked : High School Hack (4)  (0) 2017.08.02
2.hacked : High School Hack (3)  (0) 2017.08.02


 

Chapter3 : Jailbreak 두번째 문제풀이를 하겠습니다.

 

Pattern : Maxxxxx

 

 

이전에는 배열안에 두개밖에 없었는데 이제는 배열안에 원소들이 뒤죽박죽 난리났네요

 

그래도 배열안에서 제일 큰 수를 찾아내는 max값을 찾아내는 일이란것은 변함없습니다.

 

그럼 코드를 작성해보겠습니다. 얍!

 

 

코드도 간단합니다.

 

1번 배열의 첫번째 원소를 변수에 저장해줍니다.

2번 배열안의 모든 원소와 값을 비교해야하므로 배열의 길이만큼 반복되는 반복문을 만들어 줍니다.

3번 배열의 원소를 [0] ~ [n]까지 모두 비교해 큰수를 변수 var_b에 넣어줍니다.

 

이것을 기반으로 만든 코드가 위와 같습니다.

 

참 쉽죠?

 

 

깔끔히 성공했습니다. 다음에 세번째 문제로 돌아오겠습니다.

 

이상 Chapter3 : Jailbreak(2) 풀이 였습니다.

 

 

'Coding > hacked' 카테고리의 다른 글

3.hacked : Jailbreak (4)  (0) 2017.08.03
3.hacked : Jailbreak (3)  (0) 2017.08.03
3.hacked : Jailbreak (1)  (0) 2017.08.03
2.hacked : High School Hack (4)  (0) 2017.08.02
2.hacked : High School Hack (3)  (0) 2017.08.02


 

이제는 Chapter3 : Jailbreak 가 열렸네요. 오늘도 문제를 다 뿌수도록 하겠습니다.

 

 

들어와보니 익숙한 느낌의 사과가 반겨주네요.

 

 

Pattern : Max

 

 

첫번째 문제의 패턴은 Max 최대값을 찾는 문제입니다.

 

배열안에 두개의 원소가 들어있고 둘 중 누가 더 큰 수인지 판별하는 간단한 패턴입니다.

 

그럼 코드로 작성해보겠습니다. 얍!

 

 

위의 코드는 간단합니다.

 

배열안에 두개의 원소밖에 없기 때문에 두개의 원소를 직접 비교해주고 큰 수를 돌려주는 간단한 문제입니다.

 

참 쉽죠?

 

 

깔끔히 성공했습니다. 다음에 두번째 문제로 돌아오겠습니다.

 

이상 Chapter3 : Jailbreak(1) 풀이 였습니다.

'Coding > hacked' 카테고리의 다른 글

3.hacked : Jailbreak (3)  (0) 2017.08.03
3.hacked : Jailbreak (2)  (0) 2017.08.03
2.hacked : High School Hack (4)  (0) 2017.08.02
2.hacked : High School Hack (3)  (0) 2017.08.02
2.hacked : High School Hack (2)  (0) 2017.08.02


 

Chapter 2 : High School Hack 네번째문제입니다.

 

바로 패턴부터 살펴보겠습니다.

 

 

이번 패턴도 어렵지 않습니다.

 

입력값으로 배열의 길이를 주면 그 길이에 맞춰 배열 안에 0부터 시작하는 양의 정수를 채워 넣으면 됩니다.

 

그럼 코드를 작성해보겠습니다. 얍!

 

 

배열을 돌려줘야 하기 때문에 배열을 먼저 선언해 줬습니다.

 

그리고 while문을 이용하여 배열안에 0부터 1씩 증가하는 값을 차례대로 채워 넣었습니다.

 

그리고 while의 반복횟수는 입력값보다 작게 반복하면 됩니다. 배열은 1부터 시작하는게 아니라 0부터 시작하기 때문입니다.

 

 

 

High School Hack (4) 의 문제풀이를 마쳤는데요 Chapter2는 네번째 문제가 마지막 문제였네요.

 

다음에는 Chapter3으로 돌아오겠습니다.

'Coding > hacked' 카테고리의 다른 글

3.hacked : Jailbreak (2)  (0) 2017.08.03
3.hacked : Jailbreak (1)  (0) 2017.08.03
2.hacked : High School Hack (3)  (0) 2017.08.02
2.hacked : High School Hack (2)  (0) 2017.08.02
2.hacked : High School Hack (1)  (0) 2017.08.02


 

Chapter 2 : High School Hack 세번째문제입니다.

 

바로 패턴부터 살펴보겠습니다.

 

 

이번 패턴도 간단해 보입니다. 

 

살펴보니 배열을 입력값으로 주면 배열의 길이를 확인해서 알려주면 될 것 같습니다.

 

그럼 코드로 작성해보겠습니다. 얍!

 

 

이번에 foreach 가 새로 생겨서 foreach를 이용해서 만들었습니다. 먼저 foreach가 어떤건지 예를 들어 보겠습니다.

처음 봤다면 당황하지 마세요. 전혀 어렵지 않습니다.

 

var_a;     //변수 선언

var_b = [1,2,3,];    //배열 초기화

 

위처럼 배열과 변수가 있을 때 간단한 코드를 써 보겠습니다.

 

foreach var_a in var_b {

var_c++ ;

retrun var_c;

 

이렇게 되면 처음 foreach 문을 들어오게 되었을 때 var_a 에 var_b의 첫번째 인수인 1이 들어가게됩니다.

그리고 중괄호 안의 내용을 실행하게 되는데요 var_c의 값이 1증가합니다.

 

var_b에 아직 배열에 원소가 남아있으므로 다시 var_a에 var_b의 두번째 인수가 들어갑니다. 그리고 중괄호 안의 코드가 실행됩니다.

이렇게 배열의 마지막 인수까지 실행이 된 후 foreach가 끝나게 됩니다.

 

그럼 var_b에는 3개의 인수가 들어있으므로 var_c의 값은 1씩 3번 증가했으니 var_c의 값은 3이 됩니다.

 

이렇게 foreach문을 이용해서 배열의 길이를 알 수 있었습니다. 참 쉽죠?

 

 

High School Hack (3) 의 문제풀이를 마치겠습니다.

'Coding > hacked' 카테고리의 다른 글

3.hacked : Jailbreak (1)  (0) 2017.08.03
2.hacked : High School Hack (4)  (0) 2017.08.02
2.hacked : High School Hack (2)  (0) 2017.08.02
2.hacked : High School Hack (1)  (0) 2017.08.02
1.hacked : The Hackpad (4)  (0) 2017.08.01


 

Chapter 2 : High School Hack 두번째문제입니다.

 

바로 패턴부터 살펴보겠습니다.

 

 

첫번째 문제와 같은 패턴이네요. 입력값의 제곱수를 돌려주면 되는 간단한 패턴이네요.

 

바로 코드로 작성해보겠습니다. 얍!

 

 

저번 문제를 풀고 새롭게 생긴 pow라는 함수를 이용해서 한줄로 만들었습니다.

 

pow(a,b); 라는 함수는 a를 b의 크기만큼 제곱하는 함수입니다.

 

간단한 예를 들어보면은   pow(3,5); 라면 3의 5승이 되는 겁니다. 즉 3*3*3*3*3 이 되는거죠. 참 쉽죠?

 

 

High School Hack (2) 의 문제풀이를 마치겠습니다.


 

'Coding > hacked' 카테고리의 다른 글

2.hacked : High School Hack (4)  (0) 2017.08.02
2.hacked : High School Hack (3)  (0) 2017.08.02
2.hacked : High School Hack (1)  (0) 2017.08.02
1.hacked : The Hackpad (4)  (0) 2017.08.01
1.hacked : The Hackpad (3)  (0) 2017.08.01


 

Chapter1 을 다 풀었더니 Chapter2가 열렸네요

 

그럼 Chapter 2 : High School Hack 을 시작해 봅시다.


 

음.... 네 High School Hack을 뭐라고 알려주네요. 읽고싶으신 분들은 천천히 읽어보시길 바랍니다.

 

 

다음으로 넘기니 패턴을 보여주네요.

 

이번 패턴 Power 간단하네요.

 

in  ->  out

2   ->  4 

3   ->  9

4   ->  16

 

입력한 값들을 제곱된 수로 돌려주면 될 것 같네요. 패턴을 알았으니 코드를 작성하러 가보겠습니다.

 

 

코드는 간단히 while을 이용해 반복문을 만들겠습니다.

 

곱하기는 결국 덧셈이란것을 이용해서 코드를 작성하겠습니다. 이해를 돕기위해 코드 작성전에 간단히 예를 들어 보겠습니다.

 

2*3 = 2+2+2  2를 3번 더한겁니다.

3*8 = 3+3+3+3+3+3+3+3  3을 8번 더한겁니다. 참 쉽죠?

 

그럼 2가 입력되면 2의 2승 //  3은 3의 3승 //  4는 4의 4승

 

그럼 input의 크기만큼 반복해서 input의 값을 더해주면 간단히 코드를 완성할 수 있습니다.

 

그럼 코드를 작성해 보겠습니다. 얍!

 

 

참 쉽죠?

 

이상 백자까였습니다.

'Coding > hacked' 카테고리의 다른 글

2.hacked : High School Hack (3)  (0) 2017.08.02
2.hacked : High School Hack (2)  (0) 2017.08.02
1.hacked : The Hackpad (4)  (0) 2017.08.01
1.hacked : The Hackpad (3)  (0) 2017.08.01
1.hacked : The Hackpad (2)  (0) 2017.08.01

.

 

오늘은 helloworld를 알아볼까 합니다.

 

프로그래밍을 해보신분이라면 helloworld를 들어 보셨을거라고 생각합니다.

 

런데 오늘은 프로그래밍에서 처음 배우는 helloworld가 아니라 웹사이트를 알려드릴까합니다.

 

먼저 홈페이지를 들어가 보겠습니다.

 

 

홈페이지를 들어오시면 이런화면을 보실 수 있습니다. 들어오면 먼저 추천 알고리즘 문제가 눈에 띄는데 하나하나 살펴 보겠습니다.

 

먼저 모든 코스로 들어가 보겠습니다.

 

 

모든 코스를 들어오면은 여러 프로그래밍과 관련된 강의를 무료! 로 배울 수 있습니다. 그리고 각 강의를 몇명이 공부 중인지도 알려주는데요

 

7,6111명이 공부중이라는 파이썬을 직접 들어가 보겠습니다.

 

 

들어와서 시작하기를 눌러봤는데요 이렇게 동영상강의를 볼 수 있습니다. 동영상 강의는 15분정도로 길지 않습니다.

 

그리고 자신이 강의를 어디까지 들었는지도 체크를 해주기도 해서 강의를 듣고 어디까지 들었었는지 헷갈리지 않을 수 있어 좋은 것 같습니다.

 

혹시 프로그래밍 공부가 필요한데 어떻게 공부해야 할 지 막막했다면 이 곳에서 강의를 들어보는 것도 좋을 것 같습니다.

 

다음은 알고리즘 문제로 들어가 보겠습니다.

 

 

들어오면 레벨별 문제를 풀어볼 수 있습니다.

 

문제의 레벨은 1 ~ 8 까지 나눠져 있고 알고리즘을 만들 프로그래밍 언어는 파이썬,자바,C++ 등의 언어로 풀 수 있습니다.

 

그럼 자신감을 챙기고 풀어보러 들어가보겠습니다.

 

 

왼쪽에는 문제가 나오고 오른쪽에는 코딩을 하면 되는데요 처음이라 레벨1의 간단한 문제를 풀어보러 들어왔습니다.

 

간단한 알고리즘을 동작시키는 함수를 작성하면 되는데 풀어보겠습니다.

 

얍!

 

레벨1이라 어렵지 않게 풀어 볼 수 있었습니다.

 

파이썬을 배워 본 적이 없어 배열의 선언방법과 반복문의 사용방법 등을 검색해서 푸느라 시간이 조금 걸렸지만 어렵지 않게 풀 수 있었습니다.

 

간단한 문제이니 모두 풀어 볼 수 있을 것이라 생각됩니다.

 

여기가지 helloworld를 알아보았습니다. 다음엔 알고리즘 문제와 공부한 것들을 가지고 돌아오겠습니다.

 

helloworld ====>  http://tryhelloworld.co.kr/

 

+ Recent posts