avatar
Steady

[Algorithm] 알고리즘에 대해

Algorithm
3 months ago
·
6 min read

알고리즘을 모르면 개발을 못하나?


선배 개발자들의 의견이 다를지 모르겠지만, 내 생각은 NO다.

그간 개발을 해오면서 단순히 어떤 변수를 처리해서 전달하고 결과값을 얻어내는 기능을 만들어 내는 데에 어떤 알고리즘을 아냐 모르냐는 큰 영향을 끼치지 않았다.

그래서 나는 이 재미없는 알고리즘을 굳이 배워야 하나라는 생각을 머리 한켠에 가지고 있었다.

그럼 알고리즘을 어디에 쓰나?


알고리즘은 효율적인 코딩을 위해 쓴다.

똑같은 동작을 하는데 어떤 코드가 더 빨리 수행되고 메모리를 덜 쓴다면 그게 효율적인 코드라고 할 수 있겠다.

나는 단순히 어떤 기능을 빨리만 만들어 내는 것보다 어떤 코드를 어떻게 효율적으로 만들거나 수정했는지가 스스로에게 더 보람차고 면접관의 눈에도 더 가치 있는 경험이 된다고 확신한다.
(내가 이미 실패 해봤으니까)

복잡도?


알고리즘을 얘기할때 자주 내용인 복잡도는 알고리즘이 수행될때 걸리는 시간이나 메모리의 양을 나타내는 수치이다. 따라서 복잡도가 클수록 비효율적이라고 할수있다.

빅오 표기법

: 복잡도를 설명할때 사용하는 표기법이다.

O는 'Order of' 의 약자로 알고리즘의 성능이 입력 크기에 따라 어떻게 변화하는 지 나타낸다.

O(입력 크기) 와 같이 표기하며 가장 최악의 경우를 가정한다.

시간 복잡도

: 알고리즘이 수행되는 데 걸리는 시간에 따라 결정된다.

  • 주요 복잡도

    • O(1) (상수 시간): 어떤 값을 입력 받던지 실행 시간이 늘 일정한 경우

      • 이미 만들어지 변수의 값에 접근하는 경우.

    • O(log n) (로그 시간): 입력 크기에 따라 실행 시간이 로그 비율로 증가하는 경우

      • 이진 검색 알고리즘

    • O(n) (선형 시간): 입력 크기에 비례하여 실행 시간이 증가하는 경우

      • 배열 내의 모든 값을 조회하는 경우

    • O(n log n): 입력 크기에 따라 로그 비율로 연산을 여러번 하는 경우

      • 퀵 정렬, 병합 정렬

    • O(n²) (이차 시간): 입력 크기에 따라 실행 시간이 제곱으로 증가하는 경우

      • 버블 정렬

    • O(2ⁿ): 입력 값의 모든 경우의 수를 계산하는 경우

      • 피보나치 수열을 재귀적으로 계산할 경우

공간 복잡도

: 알고리즘이 수행되는 데 걸리는 메모리의 양에 따라 결정된다.

  • 주요 복잡도

    • O(1) (상수 공간): 어떤 값을 입력 받던지 고정된 양의 메모리를 사용하는 경우

      • 하나의 변수를 이용할때 데이터를 저장하는 경우

    • O(n) (선형 공간): 입력 크기에 따라 비례하여 메모리를 사용하는 경우

      • 1차원 배열을 이용해 데이터를 저장하는 경우

    • O(n²) (이차 공간): 입력 크기에 따라 메모리 사용량이 제곱 비례하는 경우

      • 2차원 배열이나 그래프로 데이터를 저장하는 경우'

정리하자면


코드를 효율적으로 작성하려면 알고리즘을 공부하자.

시공간 복잡도가 낮을 수록 효율적인 알고리즘이다.

복잡도는 표기법 별로 아래 순서대로 좋고 나쁨을 구분한다.
O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

다음엔 알고리즘 별 처리 방법과 복잡도 차이를 적어보며 공부하겠다.







여기서는 꾸준해보자