[Algorithm★] 알고리즘이란? 시간 복잡도 Big-O 빅오 표기법

알고리즘 문제 풀이 전에, 알고리즘이 무엇인지 부터 공부를 하기로 했다. 오늘은 코드보단 이것들이 뭔지에 대해서 개념을 공부했다. 이전에 수업을 듣긴 했지만, 어렵게 느껴져서 머리가 듣는 것을 거부한것 같다. 그래도 정리를 하고 나니 어느 정도 이해가 된다. 하지만 피보나치 수열 부분은 아직도 햇갈린다. ChatGPT를 이용해서 도움을 얻어봤다. 쉽게 알려줘 하니까 생각보다 좀 쉽게 알려준다. 이해가 안되는 부분을 좀 이용해도 좋을 것 같다. 너무 의존하면 공부가 방해 될 것 같아서 키워드를 얻는 과정이나 아주 어렵게 느껴지는 부분에 대해서 단축시켜 주는 용도로 사용할 것 같다. 아니면 코드 리뷰를 부탁해도 될지도?

알고리즘(Algorithm)

알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학(컴퓨터 프로그래밍), 전산언어학 등에서 사용되는, 

문제 해결 방법을 정의한 '일련의 단계적 절차'이자 어떠한 문제를 해결하기 위한 '동작들의 모임'이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻한다. 프로그램명령어의 집합을 의미하기도 한다.

알고리즘은 연산, 데이터 마이닝(기계 학습) 또는 자동화된 추론을 수행한다.
from. wikipedia

---

백과사전의 이야기는 너무 어렵다. 문제해결을 위한 절차, 동작들의 모임, 이런 것들은 알겠다 그래서 뭘 알고 싶은건가? 왜 알아야 하는 것인가?

https://blog.chulgil.me/algorithm/

삼성역에서 택시를 타고 강남역으로 향했는데 30분 걸렸다. 구글에서 알려주는 최단경로로 갔더라면 15분내에 도착할 것이다. 레스토랑을 예약해서 가는 경우라던지 친구와 약속시간을 잡은경우 우리에게는 시간은 항상 소중하다. 그래서 우리는 시간을 효율적으로 사용하기위한 노력을 의식적으로 하고 있다.

컴퓨터 프로그래밍에서도 시간복잡도가 가장 낮은 알고리즘을 채택해 이러한 상황을 개선하고 있다. 택시를 타고 삼성역까지 가는 절차를 알고리즘이라고 하는데 이때 수행하는 연산의 수를 시간복잡도로 나타낸다. 택시를 타고 강남역까지 가는 과정을 알고리즘으로 표현하면 아래와 같다.

function TakeTaxy(from, to) {
/*
 1. 차량에 탑승한다.
 2. from에서 to까지 최단거리 루트를 선택한다.
 3.   목적지까지 가는 루트을 설명한다.
 4.   출퇴근 시간의 경우 차가 막히는 루트는 피한다.
 5. 출발하는동안
 6.   만약 적색 신호등이면 정지한다.
 7.   만약 녹색 신호등이면 출발한다.
 8. 도착하면
 9.   요금을 정산한다.
 10. 차량에서 내린다.
*/
}​

따라서 알고리즘이란,

- 어떤 목적을 달성하거나 결과물을 만들어내기 위해 거쳐야 하는 일련의 과정들을 의미한다.
- 가는 루트는 다양하며 여러가지 상황에 따른 알고리즘은 모두 다르다.
- 따라서 시간복잡도가 가장 낮은 알고리즘을 선택하여 사용한다.

여기서 알고리즘의 실행시간은 컴퓨터가 알고리즘 코드를 실행하는 속도에 의존한다.
이 속도는 컴퓨터의 처리속도, 사용된 언어종류, 컴파일러의 속도에 달려있다.

알고리즘의 실행시간을 두 부분으로 나누면
입력값의 크기에 따라 알고리즘의 실행시간을 검증해볼 수 있다. 입력값의 크기에 따른 함수의 증가량, 우리는 이것을 성장률이라고 부른다. 이때 중요하지 않는 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중할 수있는데 이것을 점금적 표기법(Asymptotic notation)이라 부른다. 여기서, 점근적이라는 의미는 가장 큰 영향을 주는 항만 계산한다는 의미다.


점근적 표기법은 다음 세가지가 있는데 시간복잡도를 나타내는데 사용된다.

- 최상의 경우 : 오메가 표기법 (Big-Ω Notation)
- 평균의 경우 : 세타 표기법 (Big-θ Notation)
- 최악의 경우 : 빅오 표기법 (Big-O Notation)
평균인 세타 표기를 하면 가장 정확하고 좋겠지만 평가하기가 까다롭다.
그래서 최악의 경우인 빅오를 사용하는데 알고리즘이 최악일때의 경우를 판단하면 평균과 가까운 성능으로 예측하기 쉽기때문이다.

이 개발자분의 블로그를 통해서 빅-오를 왜 사용하는지 간단 명료하게 알게 되었다. 전에 알고리즘 초기에 빅-오를 배우긴했는데 이게뭔지, 갑자기 이론을 시작했다가, 눈떠보니 갑자기 연습 문제를 풀더니 이론과 코드와 무슨 관계인지 연결이 안되던 것이 문제였다. 이번엔 왜 빅-오를 선택해서 사용하는지, 내가 짜는 코드가 어떤 부분인지 for가 관련이있고 중첩 for도관계가 있고 연계되어 기억도나면서 퍼즐이 맞춰지고 있다. 예제를 통해서 좀 더 정확하게 구분해야겠다. 이런 개발자분이 선배면 좋겠다..

 

Big-O

알고리즘의 로직을 코드로 구현할 때, 시간 복잡도를 고려한다는 것은
‘입력값(n==데이터==input)의 변화에 따라 연산을 실행할 때, 연산 횟수에 비해 시간이 얼마만큼 걸리는가?’라는 말이다.
효율적인 알고리즘을 구현한다는 것은 바꾸어 말해 입력값이 커짐에 따라 증가하는 시간의 비율을 최소화한 알고리즘을 구성했다 라고 말할 수 있다. 이 시간 복잡도는 주로 Big-O 표기법을 사용한다.

Big-O 표기법은 최악의 경우를 고려하므로, 프로그램이 실행되는 과정에서 소요되는 최악의 시간까지 고려할 수 있기 때문이다. “최소한 특정 시간 이상이 걸린다” 혹은 “이 정도 시간이 걸린다”를 고려하는 것보다 “이 정도 시간까지 걸릴 수 있다”를 고려해야 그에 맞는 대응이 가능하다.

프로그래밍에서 최악을 고려하는 이유로는 예로 100개의 사람이 있고 "홍길동"씨를 찾아야 한다. 한명씩 이름표를 봐야 할 때, 운이 좋으면 첫번째에 찾겠지만 보통 운인 경우 30~70번째에 찾을 수도 있다. 하지만 최악의 경우 마지막인 100번째에서 찾을 수 있다. 그럼 내가 "홍길동"을 찾아내는 이름표를 검사하는 방법은 최악의 경우인 100번째까지 고려해야 하는 것이다. 그리고 찾는 방법을 개선하기 위해서 그 최악의 시간을 일단 파악하고 동일한 "홍길동"을 찾는 목적으로 다른 방법이 있다면 적용 시키기 위한 목적이 있다.

---

1. 표기법으로 보는 시간 복잡도(Time Complexity)의 종류와 예제 코드의 형태

O(1) : constant time 상수 시간
일정한 시간이 소요됨
데이터(==n==input)가 늘어나더라도, 직접 idx를 지정하고 있기 때문에 배열을 읽고 print까지 하는 로직의 수행 시간은 일정하다.

        int[] constArr = {0, 10, 20, 30};
        System.out.println(constArr[0]);
        System.out.println(constArr[3]);

 

O(n) : linear time 선형 시간
입력 데이터 크기에 비례해서 처리 시간이 소요됨
아래 Arr에 데이터(==n==input=={element})가 추가 될 수록 정비례로 for문이 돌아야 할 바퀴수가 배열의 크기(length)에 의해 결정되므로 배열에 element를 추가 할 때마다 n과 arr.length는 정비례로 늘어나고 이는 곧 정비례로 수행 시간이 늘어 날 것이다.

        int[] linearArr = {0, 10, 20, 30};
        for (int i = 0; i < linearArr.length; i++) {
            System.out.println(linearArr[i]);
        }​

하지만 잘못생각하면, 2개의 for문이 겹치지 않고 아래 코드처럼 단순히 별도로 존재해도, 단순히 2개니까 2n이지 않을까? 생각 할 수 있지만, 각각 별개의 로직을 수행하고 있기 때문에 각각 O(n)으로 봐야 한다. 마치 이것은 신제품 차량이 나와서 속도 테스트를 하는데, 하필 같은 서킷에서 함께 테스트를 한 것이다. 하지만 서로 다른 기종인 것이다. 포르쉐와 페라리가 각각 달린다고해서 두개 속도 테스트를 합쳐서 보지는 않는다. 포르쉐의 속도는 O(n)이었고, 페라리의 속도는 O(n)이었다고 설명해야 하는 것 처럼 별도로 생각해야 한다. 위 저점금적 표기법의 조건인 상수와 계수들을 제거하면 알고리즘의 실행시간에서 중요한 성장률에 집중하기 위함이다.

        int[] linearArr = {0, 10, 20, 30};
        for (int i = 0; i < linearArr.length; i++) {
            System.out.println(linearArr[i]);
        }
        //아래와 같이 for문이 하나 더 있더라도 중첩되어 있지 않고 별개로 수행되기 때문에,
        //0(n)으로 일정하다.
        for (int j = 0; j < linearArr.length; j++) {
            System.out.println(linearArr[j]);
        }

O(n^2) : quadratic time 번역하면 이차라는 뜻
이차라는 말에서 예상할 수 있듯이 데이터의 양이 증가함에 따라 제곱 꼴로 증가해가는 시간 복잡도이다. 더 알기 쉽게는 for 등 반복문이 2개가 중첩되어 있는 경우이다.

       //반복문이 두번 있는 케이스
        int[][] quadArr = {
                {10, 20},
                {10, 20, 30, 40},
                {10}
        };
        // 조회해보자.
        for(int i=0;i<quadArr.length;i++){
            for(int j=0;j<quadArr[i].length;j++){
                System.out.println(quadArr[i][j]);
            }
        }

O(2^n) : 대표적인 fibonacci 수열
피보나치 수열은 앞의 두 숫자를 더하여 다음 숫자를 만들어내는 수열로,
0과 1로 시작한다. 자바로 피보나치 수열을 구현하는 방법은 여러 가지가 있지만,
가장 기본적인 방법(재귀함수)과 메모이제이션(Memoization)을 활용한 방법

1) 재귀 함수
재귀 함수는 반드시 기본 조건을 정의
기본 조건은 함수가 무한히 호출되지 않고 종료되는 지점을 정의하는 것
보통 피보나치 수열에서는 n이 0이나 1일 때 결과가 고정되어 있기 때문에 이를 기본 조건으로 사용

함수 내에서 자기 자신을 호출하는 것으로,
피보나치 수열의 특성상 이전 두 숫자를 더해 다음 숫자를 구해야 하므로
재귀적으로 이전 두 숫자를 구하는 방법을 사용

package Algorithm;


public class Prac01 {
    // 1) 기본적인 재귀 방법(함수 구현 부분)
    public static int fibonacci(int n) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    public static void main(String[] args) {
    
		// 1) 기본적인 재귀 방법
        //기본적인 재귀 방법은 성능이 좋지 않기 때문에, 입력값이 크면 계산이 오래 걸릴 수 있다.
        //구현 부분은 좀 더 복습 할 것.
        int n = 10; // 원하는 피보나치 수열의 인덱스 입력
        int result = fibonacci(n);
        System.out.println("인덱스 " + n + "의 피보나치 수는: " + result);
	}

}

2) 메모이제이션
메모이제이션은 중복 계산을 피하기 위해
이전에 계산한 결과를 저장하여 재사용하는 방법으로,
피보나치 수열을 효율적으로 계산할 수 있다.
구현 부분은 좀 더 복습 할 것.

package Algorithm;

import java.util.HashMap;
import java.util.Map;

public class Prac01 {
    // 2) Memoization 활용 방법(함수 구현 부분)
    public static int fibonacciMemoization(int n, Map<Integer, Integer> memo) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        } else if (memo.containsKey(n)) {
            return memo.get(n);
        } else {
            int result = fibonacciMemoization(n - 1, memo) + fibonacciMemoization(n - 2, memo);
            memo.put(n, result);
            return result;
        }
    }
    
    public static void main(String[] args) {
            // 2) Memoization 활용 방법
        Map<Integer, Integer> memo = new HashMap<>();
        result = fibonacciMemoization(n, memo);
        System.out.println("Memoization을 사용하여 인덱스 " + n + "의 피보나치 수는: " + result);
    }
}