내일배움캠프 7일차 - 알고리즘

Big-O 표기법

 : "대략 이정도 속도로 늘어난다"를 간결하게 표현하는 방법

O(1) - 상수 - 입력과 무관, 한상 빠름

O(n) - 선형 - 데이터에 비례

O(n^2) - 이차 - 중첩 반복문

O(log n) - 로그 - 반씩 줄이기

예시)
반복문 1개: 처음부터 끝까지 한번 훑기 → 연산횟수 : n번 → 시간복잡도: O(n)
반복문 2개 중첩: 모든 쌍을 확인 →연산횟수:n*n = n^2 → 시간복잡도: O(n^2)

이 차이가 "1초면 끝나는 코드"와 "하루종일 돌아가는 코드"를 만든다.

 ※ Big-O에서는 알고리즘 걸리는 시간 자체를 나타내는 것이 아닌 입력값이 커질때 필요한 시간을 대략적으로 나타내는 것이다.

 예) n번실행 + n^2번 실행 = O(n^2)

클럭(Clock)

 - CPU는 클럭이라는 박자에 맞춰 일한다.
 - 메트로놈처럼 똑딱거리면서, 한 박자마다 명령을 처리한다.
 - 요즘 CPU는 보통 3GHz 이상 → 1초에 30억번 똑딱거린다는 뜻
 - 1GHz는 초당 10억 번의 신호를 처리할 수 있으나 실제 알고리즘 연산은 이보다 적은 약 1억 번 내외가 안정적이다.

1초 = 1억번 이라는 감각만 있으면
코드를 작성하기 전에
"이건 될까, 안 될까?"를 미리 판단할 수 있다.

게임 개발에서의 알고리즘 예시

매 프레임(1/60초 = 약 16ms)마다 모든 로직을 끝내야한다.
NCP 100마리 충돌체크 O(n^2) -> 10,000번 OK
NPC 1,000마리 -> 1,000,000번. 프레임 드랍발생!

웹 서비스에서의 알고리즘 예시

수백만 건 데이터에서 검색, O(n)이면 몇 초.
이진 탐색 O(log n)이면 20번이면 끝.

데이터베이스에서의 알고리즘 예시

DB 인덱스 = "탐색을 O(n)에서 O(log n)으로 줄이기"

오늘의 핵심

1) 알고리즘: 문제를 해결하는 절차. 같은 문제라도 절차에 따라 속도가 다름.

2) 시간 복잡도: 입력 크기(n)가 커질 때 연산 횟수가 어떻게 증가하는가

3) CPU 클럭 평균: 1초 = 1억번으로 이 감각으로 "될까" 를 판단할 수 있다

4) 게임에서도 매 프레임 제한된 시간 안에 처리

 -> 알고리즘 선택이 곧 성능