들어가며

시간 복잡도(Time Complexity)란 특정 알고리즘이 문제를 해결하는데 걸리는 시간을 의미하고,
통상적으로 최악의 경우(빅오, ‘O’)를 구해서 표기합니다

 

이전 포스팅 에서 시간복잡도에 대해 알아보았는데요,
이번 포스팅에서는 순차탐색과 이진탐색에 대하여 알아보고
간단한 leetcode (릿코드) 예제와 함께 시간복잡도를 계산해 보도록 하겠습니다


Leetcode 문제 이해하기

Search Insert Position - LeetCode ‘EASY’ 난이도인 문제입니다

이진탐색을 공부하기에 좋은 예제라 생각하여 가져왔습니다 👀

  • 배열의 인덱스는 0부터 시작합니다
  • 오름차순으로 정렬된 array와, 타겟이 Input으로 제공됩니다
  • Output으로 타겟이 위치할 인덱스 위치를 return 하여 줍니다

1번 예제에서는 목표값 '5'가 배열에서 2에 위치한 것을 알 수 있습니다

4번 예제에서는 목표값 '0'이 배열에서 0번째 위치해야 하는 것을 알 수 있습니다


순차탐색 풀이 & 시간복잡도

순차 탐색의 경우, 처음부터 비교하여 비교가 끝날때까지 차례로 훑어보게 됩니다

  • Example1, 목표값 5 에서는 탐색 3번 [1, 3, 5]
  • Example2, 목표값 2 에서는 탐색 2번 [1, 3]
  • Example3, 목표값 7 에서는 탐색 4번 [1, 3, 5, 6]
  • Example4, 목표값 0 에서는 탐색 1번 [1]
  • Example5, 목표값 0 에서는 탐색 1번 [1]

최악의 경우 마지막 끝까지 4번 훑어보게 됩니다.

public int searchInsert(int[] nums, int target) {
    int length = nums.length;
    for (int i = 0; i < length; i++) {
        if (nums[i] == target) {
            return i;
        }

        if (target < nums[i]) {
            return i;
        }
    }
    return length;
}

즉, 최악의 경우인 n번까지 훑어보게 됨으로 시간복잡도는 O(n)을 가지게 됩니다.


이진탐색 풀이 & 시간복잡도

이진탐색의 경우 업&앤 다운으로 숫자맞추기를 한다고 보면 됩니다.

“1부터 100까지 숫자가 정렬되어 있을때 내가 생각하고 있는 숫자를 맞춰봐” (답은 43)
50 땡! -> 다운
25 땡 -> 업
36 땡 -> 업
43 정답

만약 순차탐색으로 숫자를 맞추게 된다면 1부터 43까지 차례로 확인을 하겠죠?

그러나 이진탐색은 위와 같이 4번의 질의로 정답을 맞추었습니다.

 

즉, 이진탐색은 순차탐색보다 효율적으로 숫자를 탐색하고 있습니다.

마찬가지로 leetcode 문제를 살펴보겠습니다

 

  • Example1, 목표값 5 에서는 탐색 1번 [5]
  • Example2, 목표값 2 에서는 탐색 2번 [3, 1]
  • Example3, 목표값 7 에서는 탐색 3번 [3, 5, 6]
  • Example4, 목표값 0 에서는 탐색 2번  [3, 1]
  • Example5, 목표값 0 에서는 탐색 1번  [1] 
public static int searchInsert(int[] nums, int target) {
    int first = 0;
    int last = nums.length - 1;

    while (first <= last) {
        int mid = (first + last) / 2;
        if (nums[mid] == target) {
            return mid;
        } else if (nums[mid] < target) {
            first = mid + 1;
        } else {
            last = mid - 1;
        }
    }
    return first;
}

이진탐색에서는 중앙값과 목표값을 비교하여 인덱스의 위치를 계속 조절하고 있습니다!!

이제 이진탐색의 시간복잡도를 구해보도록 하겠습니다.

  • 먼저 숫자 N이 주어집니다
  • 첫 탐색을 하게 되면 N/2 만큼 남게됩니다
  • 두번째 탐색을 하게 되면 1/2 * N/2 만큼 남게 됩니다
  • 세번째 탐색을 하게 되면 1/2 * 1/2 * N/2 만큼 남게 됩니다
  • k번째 탐색을 하게 된다면 (1/2)^k * N 만큼 남게됩니다
  • ‘(1/2)^k * N = 1’ 이 성립하기에 양변에 2^k을 곱하여 줍니다
  • N = 2^k가 되어 k 값을 구하게 되면 k = log2N 이 됩니다

시간복잡도는 상수를 제거하여 표현하기에 이진탐색의 시간복잡도는 logN으로 표현할 수 있습니다

주의, 이진탐색의 경우 숫자가 정렬되어 있어야 합니다 (오름차순, 내림차순)


출처

Search Insert Position - LeetCode
이진 탐색과 시간 복잡도 분석 (Binary Search and its Time Complexity Analysis)

블로그 이미지

사용자 yhmane

댓글을 달아 주세요

시간복잡도와 공간복잡도


성능 분석의 기준

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

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

댓글을 달아 주세요