알고리즘 스터디 :: 알고리즘이란 ?

Algorithm 이란 어떤 문제를 해결하기 위한 여러 동작들의 모임 이다.

간단하게 이렇게 생각해보자.

학교에서 집을 갈 때 버스로 갈 수도 있고, 택시로 갈 수도 있는 상황이다.

 

 

이런 상황에서 나라면 아마 버스를 타고 갈 것이다.

왜냐면 싸니까 🫠

학교에서 집으로 가는 문제를 버스를 타는 방식으로 해결 하는 것 !

이게 바로 알고리즘 이다.

항상 어떤 문제를 해결하는 방법이 똑같은 건 아니다.

만약 치킨을 시켰는데 벌써 도착해버렸다면?

택시를 타고 빨리 집에 가는 방법을 선택할 것이다.

이런 식으로 어떤 조건이 바뀌게 되면 문제를 해결하는 방식이 달라질 수도 있다.

 

공부방법

---

1. 먼저 알고리즘이나 문제를 푸는 방법을 이해하기
   • 완벽하지 않거나 일부만 이해해도 성공~
2. 관련 문제를 풀어보기
   • 한 문제는 길어도 1~2 시간 정도만 고민
   • 모르겠으면 포기하고 정답 소스를 보거나 풀이 보기
3. 1,2번에서 이해가 가지 않는 부분이 있으면 주위에 물어보기
4. 다시 알고리즘을 이해해보고 문제 다시 풀기

 

시간 복잡도

---

시간복잡도를 이용하면 작성한 코드가 어느 정도의 시간이 걸릴지 예상할 수 있다.

최악의 경우 시간이 얼마나 걸릴지 Big O 를 이용해서 나타내기!

Big O Notation 에서 상수는 버린다.

 

Q. 아래 코드의 시간 복잡도는 ?

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

A. O(N)

 

Q. 아래 코드의 시간 복잡도는?

int sum = 0;
sum = N*(N+1)/2;

A. O(1)

 

Q. 아래 코드의 시간 복잡도는?

int sum = 0;
for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        if (i==j) {
            sum += j;
        }
    }
}

A. O(N^2)

 

대표적인 시간 복잡도들

• O(1)
• O(logN)
• O(N)
• O(NlogN)
• O(N^2)
• O(N^3)
• O(2^N)
• O(N!)

구현한 알고리즘이 문제에서 제시한 시간 범위 안에 동작 가능한지 확인해보려면

가장 큰 입력 범위를 넣었을 때, 1억 정도가 나오는지를 확인해보면 된다.

1억 정도 나오면 1초 정도라고 생각하면 됨 !

 

1초가 걸리는 입력의 크기를 보자. (대략적인 수치 !)

• O(N) : 1억
• O(NlogN) : 500만
• O(N^2) : 1만
• O(N^3) : 500
• O(2^N) : 20
• O(N!) : 10

 

⭐️ 시간 복잡도의 의미 (항상은 아니고, 대부분의 경우)

• O(1) : 단순 계산 (a+b와 같은 연산, 배열에 접근하는 연산)
• O(logN) : N 개를 절반으로 계속해서 나누는 연산 or 트리 같은 걸 사용할 때
• O(N) : 1중 for문
• O(NlogN)
• O(N^2) : 2중 for문
• O(N^3) : 3중 for문
• O(2^N) : 크기가 N인 집합의 부분 집합
  • 각각을 선택하는 경우와 선택하지 않는 경우로 나뉘기 때문 !
• O(N!) : 크기가 N인 순열

 

어떻게 구현을 해야겠다고 생각을 한 후,

시간 복잡도를 계산해본 뒤 문제의 시간제한과 비교해서 구현하기 !

코드를 작성하기 전에 시간복잡도를 계산하는 방법에 익숙해져야 한다.