시간복잡도와 공간복잡도


성능 분석의 기준

프로그램의 성능을 측정하는데 기준은 무엇일까? 아래의 예시를 보고 한번 생각해보도록 하겠습니다.

A군은 특정 데이터 집단을 분석하여 모델링하는 알고리즘 a,b를 개발하였다
A군의 컴퓨터에서 a 알고리즘과 b 알고리즘을 수행하였더니, 각각 20분, 40분의 시간이 소요 되었다
A군은 또 다른 테스트를 하기 위해 B서버와 C서버에서 각 알고리즘을 수행하였더니 40분, 30분의 시간이 소요 되었다

위의 예시를 보면 A군이 개발한 a,b 알고리즘 중 어느것이 더 뛰어나다고 단정할 수 있을까?
아쉽지만 기준이 모호하기 때문에 어느것이 뛰어나다고 단정할 수 없습니다.
그렇다면 우리는 알고리즘의 성능을 측정하는데 어떠한 기준을 적용하는 것일까? 답은 바로 아래에 나와 있습니다.

  • 시간복잡도
  • 공간복잡도

컴퓨터 공학을 전공하였다면, 한번쯤은 들어봤을 개념입니다. 들어보지 않았다면, 이번 기회에 정리하는 시간을 갖도록 합시다!!
시간복잡도는 cpu, 공간복잡도는 memory와 관련 되어 있다는 것만 짚고 넘어가고, 자세한건 밑에서 알아보도록 하겠습니다.


시간복잡도

시간복잡도란 무엇일까?

"In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm."

시간 복잡도(Time Complexity)란 특정 알고리즘이 문제를 해결하는데 걸리는 시간을 의미합니다.
같은 문제를 해결하는데 접근 방법이나 알고리즘에 따라 걸리는 시간이 달라질 수 있습니다.
따라서, 우리는 같은 문제를 해결하는데 더 적은 시간이 걸리는 알고리즘을 선택해야 합니다.

시간복잡도 표기법

시간복잡도를 표현하는 방법은 아래와 같이 3가지가 있습니다. 간단히 각 표기법에 대하여 알아보도록 하겠습니다.

  • O (빅오,Big-O)
    • 최악의 경우를 나타냅니다. 즉, 최대로 걸릴 수 있는 시간(상한 시간)을 의미합니다
  • Ω (빅오메가,Big-Omega)
    • 최선의 경우를 나타냅니다. 즉, 최소로 걸릴 수 있는 시간(하한 시간)을 의미합니다
  • θ (빅세타,Big-Theta)
    • 최선과 최악의 중간을 나타냅니다. 즉 평균적인 복잡도를 의미합니다

3가지의 표기법을 제시하지만 알고리즘의 성능 측정 지표로 주로 사용되는 것은 빅오 표기법입니다.
그 이유인 즉슨 '아무리 최악의 상황이라도 상한시간의 성능을 보장할 수 있다'라는 것이기 때문이다.


Big-O

위에서 간단히 시간복잡도를 측정하는 표기법에 대하여 알아보았습니다.
빅오표기법은, 문제 해결시 최대로 걸리는 시간 (최악의 시간)을 구하는데 사용됩니다.
주로 사용되는 시간복잡도에 대하여 간략히 알아보고 계산법에 대하여 예시를 통해 알아보도록 하겠습니다.

시간복잡도 표기법에 대해서 알아보도록 하겠습니다.

T(n) = 10 = O(1)
T(n) = 2n^3 + 2n + 5 = O(n^3)
T(n) = 5n^4 + 2n^2 + 10 = O(n^4) 

시간복잡도는 가장 큰 영향력을 주는 항에 대해서만 빅오로 표기합니다. 다음은 코드로 보며 시간복잡도를 계산해보도록 하겠습니다.


예제 1)

public void constant() {
    int constant = 100;
}

한번만 수행되기 때문에 위 함수의 시간복잡도는 O(1)입니다.

예제 2)

public void forTimeComplexity(int n) {
    int sum = 0;   
    for (int i = 0; i < n; i++) { // n + 1
        // 실행
    }
}

시간 복잡도는 O(n)입니다.

예제 3)

public void forTimeComplexity(int n) {
    int sum = 0;                        
    for (int i = 0; i < n; i++) {       // n + 1
        for (int j = 0; j < n; j++) {   // n + 1
            // 실행
        }
    }
}

n^2 + 2n + 1이지만 가장 영향력을 많이 주는 n^2 항으로 계산하면 O(n^2)입니다.

간단한 예시로 시간복잡도를 계산해 보아는데요,
다음 정렬 포스팅에서 더욱 자세히 알아보도록 하겠습니다!!


공간복잡도

공간 복잡도(Space Complexity) 프로그램을 실행 후 완료하는 데 필요로 하는 자원의 양을 말합니다.
다만 최근에는 컴퓨터의 발달로 인해 충분한 메모리를 확보할 수 있기 때문에 공간복잡도의 중요성이 예전에 비해서 많이 낮아졌습니다.


int get_factorial(int n) {
    int i = 0;
    int result = 1;

    for(i = 1; i <= n; i++)
    {
        result = result * i;
    }
    return result;
}

변수 i, result만 사용하므로 공간복잡도는 O(1)입니다.

int get_factorial(int n) {
    if(n > 1) return n * factorial(n - 1);
    else return 1;
}

위와 같은 팩토리얼이지만, 재귀를 이용하고 있습니다. n부터 1까지 호출되어 스택에 쌓이므로 O(n)입니다.
가변공간을 잘 활용하고 재귀보다는 for문으로 풀어 주면 공간을 효율적으로 사용할 수 있는 것을 확인하였습니다.


정리

시간복잡도는 '얼마나 빠르게 수행되느냐?' 공간복잡도는 '얼마나 많은 자원을 사용하느냐'로 정리할 수 있습니다.
이전과는 달리 하드웨어의 급속한 발전으로 인해 어느정도의 시간복잡도만 보장해준다면 공간복잡도는 이해해주고 있습니다!!

다음 포스팅에서는 정렬 알고리즘에 대하여 알아보도록 하겠습니다!!


참조

블로그 이미지

사용자 yhmane

댓글을 달아 주세요

팩토리얼

Factorial

계승 또는 팩터리얼이라 하며 자연수 n이 주어졌을 때 그 수보다 작거나 같은 모든 양의 정수의 곱이다.

3! = 3 * 2 * 1 = 6
5! = 5 * 4 * 3 * 2 * 1 = 120
  • 알고리즘에서는 반복과 재귀의 형태로 풀 수 있다
public class Factorial {

    // 반복문
    public int factorial(int number) {
        int result = 1;
        for (int i =1; i <= number; i++) {
            result = result * i;
        }

        return result;
    }

    // 재귀
    public int recursiveFactorial(int number) {
        if (number == 1) {
            return 1;
        }
        return number * recursiveFactorial(number - 1);
    }
}

참조

yhmane github

블로그 이미지

사용자 yhmane

댓글을 달아 주세요

피보나치 수열

Fibonacci sequence

수학에서 다루는 수열. 이 수열의 항들은 피보나치 수(Fibonacci number)라 부른다. 다음과 같은 점화식으로 피보나치 수열을 정의할 수 있다.

F0 = 0
F1 = 1
Fn+2 = Fn+1 + Fn
  • 제 0항을 0, 제1항을 1로 두고, 둘째 번 항부터는 바로 앞의 두 수를 더한 수로 둔다
  • 0항부터 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987 이러한 형태로 이어진다
  • 알고리즘에서는 반복과 재귀의 형태로 풀 수 있다

코드

점화식을 세우면 간단히 풀 수 있는 문제이다

package fibonacci;

public class Fibonacci {

    // 반복문
    public int fibonacci(int number) {
        if (number == 0) {
            return 0;
        } else if (number == 1) {
            return 1;
        }

        int result = 0;
        int number1 = 0;
        int number2 = 1;

        for (int i = 2; i <= number; i++) {
            result = number1 + number2;
            number1 = number2;
            number2 = result;

        }
        return result;
    }

    // 재귀
    public int recursiveFibonacci(int number) {
        if (number == 0) {
            return 0;
        } else if (number == 1) {
            return 1;
        }
        return recursiveFibonacci(number - 1) + recursiveFibonacci(number - 2);
    }
}

참조

yhmane github

블로그 이미지

사용자 yhmane

댓글을 달아 주세요

문제


boj.kr/1463



풀이 & 코드

 

- 우선 어떤 유형의 문제인지 파악이 필요합니다

여기서는 동적 프로그래밍 (dynamic programming)의 문제입니다. 즉, 큰 문제를 작은 문제로 나누어 푸는 것 입니다.

작은 문제들이 반복되고, 작은 문제들의 값이 같을때 이를 동적 프로그래밍이라고 하는데 메모제이션 이라는 기법으로 문제를 접근합니다.


작은 문제들의 결과값은 항상 같기에 이 결과를 어떤 곳에 저장하여 놓는 것입니다.


- 이쯤 1463번 문제의 유형을 알았으니 동적프로그래밍의 해결방법을 찾습니다.

Bottom-up, Top-Down 방식이 있습니다. 어떤 것이 무조건 좋다는 답은 없고, 그때 그때 상황에 맞춰 적용하면 됩니다.


- 여기서는 Bottom-up 방식으로 풀었습니다.




/**
* dp
* bottom-up 방식
* 점화식 solve
*/

Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int[] dp = new int[n + 1];

dp[1] = 0;
for (int i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + 1;

    if (i % 3 == 0) { dp[i] = Math.min(dp[i], dp[i / 3] + 1); }

    if (i % 2 == 0) { dp[i] = Math.min(dp[i], dp[i / 2] + 1); }
}
System.out.println(dp[n]);

- 1) 3으로 나누어 떨어질 경우 : D[N] = D[N/3] + 1

- 2) 2로 나누어 떨어질 경우 : D[N] = D[N/2] + 1

- 3) 1 뺀다 : D[N] = D[N-1] + 1


다음 규칙의 최솟값을 메모제이션하여 결과값을 출력하여 줍니다.


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

문제


boj.kr/10818



풀이 & 코드

 

값을 입력 받을때마다 최소/최대값과 비교하여 줍니다

int max = -1000001;
int min = 1000001;
for (int i = 0; i < cnt; i++) {
int num = scanner.nextInt();
if (max < num) {
max = num;
}
if (min > num) {
min = num;
}
}

System.out.println(min + " " + max);


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

문제


boj.kr/10951



풀이 & 코드

 

입력이 없을때까지 체크하여 준다

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

String input;
while ((input = br.readLine()) != null) {
String[] nums = input.split(" ");
System.out.println(Integer.parseInt(nums[0]) + Integer.parseInt(nums[1]));
}
}


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

링크


문제링크



풀이 & 코드



먼저, 첫번째 테스트 케이스를 분석해보자


입력 값으로


7과 3 1 3 7 3 4 6 숫자들이 들어 왔다.


이 숫자를 배열로 생각하여 나열해 보면

1 2 3 4 5 6 7  번째 사람


3 1 3 7 3 4 6  지목한 사람



2 -> 1 -> 3 -> 3


5 -> 3 -> 3


4 -> 7 -> 6 -> 4 


가리키는 방향으로 부터 사이클이 생성 되고, 팀이 생성되는 것일 확인 할 수 있다.


1번째 (3), 2번째 (4, 7, 6) 팀 X ( 2, 1, 5 )



이렇게 사이클이 생성될 경우 팀이 생성 된다는 것을 알 수 있고


우리가 많이 풀었던 그래프 문제라는 것을 인지 할 수 있다.



package hwang;

import java.util.*;
import java.io.*;

public class Hwang9466 {

private static int[] graph;
private static int count = 0;
private static boolean[] visited;
private static boolean[] finished;

public static void main(String[] args) throws Exception {

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;

int T = Integer.parseInt(br.readLine());

while(T-- > 0) {

int N = Integer.parseInt(br.readLine());
graph = new int[N + 1];
visited = new boolean[N + 1];
finished = new boolean[N + 1];
count = 0;

st = new StringTokenizer(br.readLine());
for (int i = 1; i<= N; i++) {
graph[i] = Integer.parseInt(st.nextToken());
}

for (int i = 1; i<= N; i++) {
dfs(i);
}

System.out.println(N - count);
}
}

private static void dfs(int now) {

if (visited[now]) {
return;
}

visited[now] = true;
int next = graph[now];

if (!visited[next]) {
dfs(next);
} else {
if (!finished[next]) {
count++;
for (int i = next; i != now; i = graph[i]) {
count++;
}
}
}

finished[now] = true;
}
}


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

문제 링크


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



코드 & 풀이


입력된 간선을 보고 연결 요소 (Connected Component)를 구해야 합니다.


연결요소란?


그래프 G에서 노드와 엣지가 서로 겹치지 않는(independent) 부그래프를 G 요소(component)라고 합니다. 

이들 요소 가운데 요소 모든 노드쌍에 대해 경로가 존재하는 부그래프 S G 연결요소(connected component)라고 합니다.


예제1)


1-2-5 / 3-4-6 // 2개의 연결요소


예제2)

1-2-3-4-5-6  // 1개의 연결요소




만약 연결요소가 잘 이해되지 않는 다면 정점과 간선을 직접 그려보는 것이 좋습니다.



package hwang;

import java.io.*;
import java.util.StringTokenizer;

public class Hwang11724 {

private static int visit[];
private static int [][]graph;
private static int N, M;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());

visit = new int[N+1];
graph = new int[N+1][N+1];

for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int x = Integer.parseInt(st.nextToken());
int y = Integer.parseInt(st.nextToken());

// 무방향 간선
graph[x][y] = graph[y][x] = 1;
}

// cc 갯수
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (visit[i] == 0) {
cnt++;
dfs(i);
}
}
System.out.println(cnt);
}

private static void dfs(int node) {
visit[node] = 1;

for (int i = 1; i <= N; i++) {
if (graph[node][i] == 1 && visit[i] == 0) {
dfs(i);
}
}
}
}

dfs로 탐색을 하며, 연결요소가 생성될 때마다 갯수를 증가시켜 주면 됩니다.




블로그 이미지

사용자 yhmane

댓글을 달아 주세요


문제


[링크]

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


풀이 & 코드


우선 아래와 같이 예제 입력이 들어 왔다.


()(((()())(())()))(())


여기서는 3가지 경우만 체크하면 풀수가 있다.


1) '(' 여는 괄호 -> 스택에 넣어주면 된다.


*  ')' 닫는 괄호

닫는 괄호는 두가지 경우로 나뉜다.

2) 레이저 절단  

- 스택의 사이즈를 구한다.  

3) 막대의 끝

-  막대 갯수를 더한다. (+1)

() 레이저 절단 .. 하지만 막대의 시작과 끝이 없기 때문에 조각이 생기지 않는다

( ) ( ( ( ( ) 레이저 절단이 이루어 진다. 3단으로 쌓아 올렸기 때문에 스택에 남아 있는 '(((' 3조각이 생긴다              

( ) ( ( (   ( ) ( ) 또다시 레이저 절단이 이루어 진다. 마찬가지로 스택엔 3조각이 남아 있기에  3조각이 더 생긴다 

( ) ( ( (   ( ) ( ) ) 3층의 막대기 끝나는 지점이다. 1조각이 생긴다

( ) ( (    ( ( ) ( ) ) ( ( )  다시 1개의 층을 쌓고 레이저로 절단하였다. 3조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) )  3층의 막대기 끝나는 지점이다. 1조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) ) ( ) 2층의 막대기를 레이저로 절단하였다. 2조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) ) ( ) ) ) 2층과 1층의 막대기가 끝나는 지점이다. 1조각씩  총 2조각이 생긴다

( ) ( (    ( ( ) ( ) ( ( ) ) ( ) ) ) ( ( ) ) 마지막 막대기를 레이저로 잘라 2조각이 더 생긴다

이렇게 해서 예제는 총 17 조각이 생긴다.


스택으로 풀면 쉬운 문제이지만,

처음엔 이해가 잘 안될 수도 있다.

그런 경우에는 위의 방법 처럼 직접 써보면서 갯수를 구해보는 것이 좋다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
 
public class Main {
 
    public static void main(String[] args) throws IOException {
 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String input  = br.readLine();
        int    len    = input.length();
        int    result = 0;
 
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < len; i++) {
            char value = input.charAt(i);
            if (value == '(') stack.push(value);
            else {
                stack.pop();
                // 레이저
                if (input.charAt(i-1== '(') result += stack.size();
                // 파이프 끝
                else result++;
            }
        }
 
        System.out.println(result);
    }
}
cs


블로그 이미지

사용자 yhmane

댓글을 달아 주세요

링크


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


BOJ 10844 문제 링크입니다



풀이


먼저, 문제를 풀 때 어떠한 문제인지 알면 50프로는 알고 들어가는 것 입니다.


마찬가지로, 이 문제는 n자리의 계단수를 구하면 되는 것인데



1자리, 2자리, 3자리 까지는 직접 구할 수 있지만 4자리, 5자리, 6자리 ... 로 가게 되면 직접 구할 수 없습니다.

이렬 경우에는 규칙성을 찾아서 점화식을 찾아야 하는데요, 이러한 계산을 bottom-up 또는 top-down 방식으로 풀게 된다면

다이나믹 프로그래밍의 분류라 생각 하시면 됩니다.




서론이 길었는데 저만의 문제 풀이를 해보겠습니다.

(문제에선 0으로 시작하는 수는 없다고 하였습니다!!)



먼저 1자리의 경우

1, 2, 3, 4, 5 ,6 , 7, 8, 9  가 각 1로         1자리 수의 경우 9


2자리

10,11/ 21,23 / 32,34 / 43, 45/ 54, 56 / 65,67 / 76,78 / 87,89/ 98        2자리 수의 경우 17


3자리

101, 121, 123 / 210,212, 232, 234/ 321, 323, 343, 345/ 432, 434, 454, 456 / 543, 545, 565, 567 / 

654, 656, 676, 678 / 765, 767,  787, 789 / 876, 878, 898 / 987, 989            3자리 수의 경우 32가지가 나옵니다



 

 1로 시작

 2로 시작

 3으로 시작

 4로 시작

 5로 시작

 6으로 시작

 7로 시작

 8로 시작

9로 시작

 1자리의 수

 1

 1

 1

 1

 1

 1

 1

 1

 1

 2자리의 수

 2

 2

 2

 2

 2

 2

 2

 2

 1

 3자리의 수

 3

 4

 4

 4

 4

 4

 4

 3

 2


자 위의 숫자들을 표로 정리하여 보았습니다. 여기서 규칙성을 찾아야 합니다 ..

규칙성이 보이시나여? 

규칙성을 보려고 하면 4자리 수까지 보아야 잘 보이지만,, dp 문제를 많이 풀다 보면 '아 이건 이거겠넹 ㅋㅋ' 라는게 머리속을 스쳐 지나가실 겁니다 .,..하하


1의 경우 dp[i-1][j+1] + dp[i-2][j]                     dp[3][1] = dp[2][2] + dp[1][1]  = 2+ 1

9의 경우 dp[i-1][j-1]                                        dp[3][9] = dp[2][8] = 2

그 이외의 경우 dp[i-1][j-1] + dp[i-1][j+1]          dp[3][2] = dp[2][1] + dp[2][3] = 2 + 2 , dp[3][8] = dp[2][7] + dp[2][9] = 2 + 1


코드

import java.io.*;

public class Main {

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int n = Integer.parseInt(br.readLine());
int[][] dp = new int[101][10];
Long result = 0l;

for (int i=1; i<10; i++) {
dp[1][i] = 1;

if (i==9) {
dp[2][i] = 1;
} else {
dp[2][i] = 2;
}
}

for (int i=3; i<=n; i++) {
for (int j=1; j<10; j++) {
if (j==1) {
dp[i][j] = (dp[i-1][j+1] + dp[i-2][j])%1000000000;
} else if (j==9) {
dp[i][j] = (dp[i-1][j-1])%1000000000;
} else {
dp[i][j] = (dp[i-1][j-1] + dp[i-1][j+1])%1000000000;
}
}
}

for (int i=1; i<10; i++) {
result += dp[n][i];
}

System.out.println(result%1000000000);
}

}


블로그 이미지

사용자 yhmane

댓글을 달아 주세요