[Algorithm] 알고리즘? .00

안녕하세요! 깜뭉이입니다.

해당 카테고리에서는 Algorithm에 대해 공부하고 배운 내용을 정리 및 저장 합니다.

제가 참조하는 책은 자료구조와 함께 배우는 알고리즘 입문 자바편이며, 코드는 파이썬으로 작성할 예정입니다.

저처럼 기초 알고리즘 공부를 함께 하실 분에게 도움이 되길 바라며, 그럼 시작해볼까요?

---

😵 알고리즘이란?

문제를 해결하기 위해 정해진 일련의 절차나 방법을 공식화한 형태로 표현한 것, 계산을 실행하기 위한 단계적 절차를 의미합니다. 간단한 예제와 함께 이야기 해봅시다.

 

Q. 입력한 내용을 출력해봅시다.

value = input()
print(value)

위 코드를 작성하면 값을 입력할 수 있습니다. 아무 값을 입력하고 Enter를 누르면, 입력한 값이 출력됩니다.

 

Q. 두 값을 비교해봅시다.

print("정수인 두 값을 비교합니다.")
a = int(input("A값을 입력해주세요. : "))
b = int(input("B값을 입력해주세요. : "))
if a > b:
    print("A 값이 더 큽니다.")
elif b > a:
    print("B 값이 더 큽니다.")
else:
    print("두 값이 같습니다.")

a,b에 두 값을 넣을 수 있고, 비교 되어서 결과를 알려줍니다. 프로그램을 실행하여 확인해보세요.

위처럼 값을 넣으면(input) 알고리즘을 통해 결과 값(output)이 나오게 됩니다.

지금처럼 단순한 문제 같은 경우 빠르게 답이 나오지만 수많은 값을 비교해서 결과를 내야하는 경우 시간이 더 많이 걸리겠죠? 이에 알고리즘이 효율적인지 평가하는 기준은 크게 시간복잡도, 공간복잡도로 나누며 알고리즘 문제를 풀 때 정확한 결과값 다음으로 채점 대상이 됩니다. 최근에는 기술에 발전에 따라 공간복잡도보다 시간복잡도를 척도로 판단하는 추세인 것 같습니다.

 

⏱ 시간복잡도?

시간복잡도는 얼마나 빨리 결과를 내주느냐 입니다. 그러나 절대적인 시간보다 연산들이 몇번 이루어 지는지를 숫자로 표시합니다. 시간복잡도를 표기해주는 대표적인 표기법은 빅오 표기법(big-oh notation)입니다.

 

빅오 표기법은 단순히 시간이 증가하는 비율을 나타내지만 최악의 경우를 고려합니다.

주로 자주 쓰이는 실행시간은 아래와 같습니다. 어떻게 이렇게 표시되는걸까요?

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

 

걸리는 시간은 입력 값이 얼마나 많은지에 따라 영향을 받기 때문에 아래처럼 무시할 수 있는 이유가 생깁니다. 

 

계수및 상수는 버린다. (상수항 무시합니다.) 

소요시간이 O(2n)이더라도 n이 무한대라면 결국 O(n)과 큰차이가 없기때문에 O(n)으로 표기합니다.

 

가장 높은 차수만 남긴다. (영향력이 없는 항을 무시합니다.)

소요시간이 O(n²+n)이더라도 n이 무한대라면 n²에 값에 영향을 끼치기가 어렵습니다. 따라서 O(n²)으로 표기합니다.

 

시간 복잡도 예제

def sum1(int N){
    return N*N;
}

입력 데이터에 상관 없이 언제나 일정한 시간이 걸리는 알고리즘입니다. O(1)로 표기합니다.

 

def sum2(int N){
    sum = 0;

    for i in range(1,N+1)
        sum = sum + i;
    }    

    return sum;
}

입력 데이터에 비례해 처리시간이 증가하는 알고리즘입니다.  O(n)으로 표기합니다.

 

def sum3(int N){
    sum = 0;

    for i in range(1,N+1) {
        for j in range(1,N+1) {
            sum = sum + 1;
        }
    }

    return sum;
}

입력 데이터에 비례해 처리시간이 급수적으로 증가하는 알고리즘입니다. 데이터가 10배 늘어나면 처리시간은 100배(10²) 증가합니다. O(n²)로 표기합니다.

 

 

참조.

빅오 표기법과 시간 복잡도 계산, 그리고 알고리즘 개선하기 (Big-O notation, time complexity, and algorithm

빅오 표기법 (Big-O Notation), 시간 복잡도, 공간 복잡도