0주 차 강의를 수강하고 올린 글에서도 언급했다시피
코딩 테스트 강의를 제대로 수강하는 것은 처음이라 굳이 이렇게까지 적는다고? 할 정도로 정리할 예정이다.
내가 글을 올리는 목적이 누군가한테 보여주기식이 아니라, 나중에 내가 복습하기 위한 목적이기 때문!
아무 생각 없이 받아쓰는 것과, 무슨 의미인지 생각하면서 타이핑하는 것은 분명 다르다 생각한다.
다만 강의는 C++ 책이 기준이므로, 코드 관련한 부분은 생략하겠다.
(파이썬 편 책이 있으므로, 코드 부분은 필요하다면 추가 예정, 하지만 C++도 이해 가능하므로 강의자료로는 첨부)
▶ 강의 목차
- 알고리즘이란?
- 알고리즘 성능측정법 및 시간 복잡도 개념
- 시간 복잡도를 빅오 표기법으로 표기하기
- 코딩 테스트에서 꼭 알아둬야 할 시간 복잡도
- 실전 예시
- 그래서 '알고리즘'이란 뭘까?
- 어떤 문제를 해결하기 위한, 일련의 규칙이나 절차를 말함
- 어떠한 입력값을 통해 출력값을 도출해 내는 일반화된 작업을 정의
- 알고리즘의 특성?
- 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 함
- ex) 요리 레시피와 같이 각 단계가 명확해야 함. 올바르게 동작하기 위해
- 유일성 : 각 단계마다 명확한 다음 단계를 거쳐야 함
- 혼동이 없고, 다음단계로 확실히 넘어가기 위함
- 타당성 : 구현할 수 있고, 실용적이어야 함
- 아무리 이론적으로 완벽해도, 사용할 수 없으면 무용지물
- 입력 : 정의된 입력을 받아들일 수 있어야 함
- 출력: 답으로 출력을 내보낼 수 있어야 함
- 유한성 : 특정 수의 작업 이후에 정지해야 함
- 무한루프에 빠지지 않고 종료가 되어야 함, 일정한 시간 내에 결과를 도출해야 함
- 일반성 : 정의된 입력들에 일반적으로 적용할 수 있어야 함
- ex) 코테 문제를 풀었음. 예시 입력과 출력이 주어짐.
- 예시 입력에 대해서는 예시 출력을 잘 출력함. 근데 내 코드를 제출하면 정답 x.
- 예시 입력은 일부분이므로, 다른 입력값에 대해서는 올바르지 못한 결과값을 도출
- 정밀성 : 변하지 않는 명확한 작업 단계를 가져야 함
- 알고리즘의 성능은 어떻게 측정할 것인가?
- 보통 문제를 보면 입력값이 있고, 입력값을 통해 도출해야 할 출력값이 있음
- 우리가 구현한 코드로 출력값이 나옴
- 구현된 코드가 동작할 때 절대시간 측정과, 연산 횟수 측정으로 성능을 측정함
- 알고리즘 성능은 어떻게 측정할 것인가? (절대시간 측정)
- 입력값을 주고 출력값이 나올 때까지의 시간을 측정하는 것일까? (과연?)
- PC에서 코드가 수행된 시간이 짧을수록 좋은 성능이다라고 정의해 보자
- 동일한 코드를 수행할 때, 두 개의 PC에서 결과가 같게 나올까?
- 알고리즘 성능 측정을 위해서는 환경에 제약을 받지 않는 기준이 있어야 함
- 일반화시킬 수 없는 알고리즘 측정법임. 그렇다고 안 좋은 건 아니고...
- 알고리즘의 성능은 어떻게 측정할 것인가? (연산 횟수 측정 1)
- 코드가 동일하면 연산 횟수는 모두 동일하므로 객관적 지표로 사용 가능
- 어떠한 코드에서, 입력값이 N일 때 연산 횟수는 N^2 + 3N + 5로 정의할 수 있음
- 특정 코드의 경우 연산 횟수가 입력에 따라 변경될 수도 있는 이 경우는??
- 입력값이 1일 때와, 2일 때의 연산 횟수가 달라질 수 있다.
- 연산 횟수는 환경 영향을 받지 않으나, 입력값에 따라 달라질 수 있으므로 기준이 필요
- 알고리즘의 성능은 어떻게 측정할 것인가? (연산 횟수 측정 2)
- 입력값에 따른 연산 횟수가 일정하지 않은 경우
- 연산 횟수를 구하면, N이 짝수일 때는 N^2, N이 홀수일 때는 N
- 입력값에 따라서 연산 횟수가 달라짐
- 코테에서는 제한시간 내에 수행될 수 있는지 확인이 중요함!
- 코테에서는 최악의 경우를 기준으로 연산 횟수를 정하는 게 합리적으로 보임
- 입력값에 따라 연산 횟수가 달라지면 이렇게 봐야 함
#include <iostream>
using namespace std;
void solution(int n) {
if (n % 2 == 0) { // If the number is even
for (int i = 0; i < n * n; ++i) {
cout << i << endl;
}
} else { // If the number is odd
for (int i = 0; i <= n; ++i) {
cout << i << endl;
}
}
}
- 알고리즘의 성능은 어떻게 측정할 것인가? (지금까지 내용 정리)
- 코딩테스트에서 알고리즘의 성능은 연산 횟수로 측정
- 입력값에 따라 연산 횟수가 상이하다면, 가장 최악의 경우를 기준으로 연산 횟수를 측정
- 입력값에 따른 연산 횟수를 측정해서 알고리즘의 성능을 지표로 나타내는 것을 시간 복잡도 라고 함
- 조금 더 알아보는 시간!
- 코딩테스트에서 이렇게 정밀한 연산 횟수를 매번 측정해야 하나요? (측정 1 예시처럼)
- 답을 먼저 이야기하면 NO.
- 정밀한 연산 횟수를 측정하기보다는, 점근적 표기법으로 표기함(이후 배울 예정)
- 그래서 코딩테스트에 시간복잡도를 어떻게 활용해야 하나요?
- 입력값이 100만까지 들어올 수 있다고 가정해 보자
- 연산 횟수가 N^2이면 TLE(시간초과)이 나겠네?
- 연산 횟수가 logN이면 Pass겠네? (log의 성능을 만족하는 자료구조, 알고리즘을 아마 내가 쓸 거임)
- 이런 식으로 내가 구현한 코드가 문제에서 요구하는 성능을 만족하는지 확인할 수 있는 게 시간복잡도
- 정밀한 표기보다 엄밀하게 표기하는 것이 점근적 표기법
- 입력값을 기준으로 내가 사용할 수 있는 자료 구조 및 알고리즘 고려 가능
- 코딩테스트에서 이렇게 정밀한 연산 횟수를 매번 측정해야 하나요? (측정 1 예시처럼)
- 점근적 표기법(정의를 알아보기 전)
- 이전에 봤던 N^2 + 3N + 5의 각 항의 그래프를 따로 그려보자
- N이 커질수록 격차가 커짐
- N이 무한이라면??
- 3N은 N^2에 비해 무시할 정도로 적은 값이 된다
- 5는 3N에 비해 무시할 정도로 적은 값이 된다
- N이 크게 되면 앞에 있는 3은 크게 의미가 없음
- 특정 시점부터는 3N은 5보다 항상 큼
- 특정 시점부터 N^2은 3N보다 항상 큼
- 코딩테스트는 연산 횟수를 측정하는 시험이 아님! X
- 어느 정도 복잡한지 대략적으로 알면 충분함
- N^2 + 3N + 5 대신 N^2이라고 (시간복잡도를 표기) 해도 무리가 없음
- 점근전 표기법(정의)
- 정확한 연산 횟수가 아닌, 연산 횟수의 추이를 활용해서 시간복잡도를 표기하는 방법
- 이때 최악의 경우를 고려해서 접근적 표기법으로 나타내는 것을 빅오표기라고 함
- 빅오표기? 큰 원을 쳐서 연산 횟수를 적으면 된다. O(N^2) : 빅오 N 제곱인 성능이다.
- 방법은 아래와 같이 아주 간단
- 다항식에서 가장 많이 영향을 미치는 항을 남기고 제거
- 마지막 남은 항의 계수를 제거
- 점근적 표기법(최고차항 구하고 빅오표기법으로 표기하기)
- 번호가 커질수록 그래프가 누움
- 어? 근데 x가 1이라면, x! 보다 2^x가 더 크지 않나요?
- 시간 복잡도에서는 x가 충분히 큰 상태에서 비교한다고 생각하면 됩니다!!!
- 점근전 표기법(자주 보이는 복잡도 1)
- 직관적이라서 딱히 설명은 x
- 점근전 표기법(자주 보이는 복잡도 2)
- 이진 탐색 트리에서 원소 탐색 O(log N)
- 트리의 높이를 구하는 것
- 1 + 2 + 2^2 + · · · + 2^k = N (등비수열)
- 등비수열 합계산 r =2, a = 1, a(r^n-1)/(r-1) = 2^(k-1) -1 = N
- k와 N이 엄청 커지면, 2^k = N → k = log N (지수는 무시할 수 있음)
- 높이가 logN이 된다
- 트리 이야기가 나오면 lgoN이라는 이야기가 많이 나오는데, 트리의 높이라고 보면 된다!
(아래와 같이 매번 탐색대상이 반절로 줄어드는 경우 O(logN)이 된다. (머지정렬의 머지, 이진탐색 등)
- 점근전 표기법(자주 보이는 복잡도 3)
- 동전의 앞뒤면을 확인하는 것
- 동전 N개를 던졌을 때 경우의 수 = O(2^N)
- 예시 : 동전 2개를 던졌을 대 경우의 수 = 2의 제곱
- 앞앞
- 앞뒤
- 뒤앞
- 뒤뒤
- 총 4개. 2 x 2 x 2 · · · · 2(N번째 동전). N개를 더하면 2^N
- 점근적 표기법(코딩테스트에 활용하기)
- 입력값의 크기를 통해 어느 정도 시간복잡도까지 허용되는지 추측 가능
- 구현시 알고리즘/자료구조 선택을 명확히 할 수 있음
- 본인이 구현한 코드가 시간초과(TLE) 발생할 것인지 미리 파악 가능
- 대략 초당 1,000~2,000만 정도 연산을 한다고 가정하면 됨
- 정확한 연산 횟수는 중요하지 않음. 대략적으로 파악하면 된다.
- 문제에서 요구하는 성능을 만족할 경우 모두 정답처리가 되어야 하므로, 충분히 여유 있게 출제가 된다.
- O(N), O(2*N) 둘 다 정답
- 입력값의 크기를 통해 어느 정도 시간복잡도까지 허용되는지 추측 가능
- 점근적 표기법(메서드의 시간 복잡도 파악)
- 동일한 동작을 하는 것처럼 보이나, 시간복잡도가 다른 경우 존재
- 기본 컨테이너 vs unordered 컨테이너
- vector와 dictionart/set 에서 특정 key 존재유무 확인
- vector와 list에서 특정위치 원소 가져오기
- 동일한 코드처럼 보이나, 코딩테스트 당락을 결정할 수 있는 중요한 부분
- 직접 코드를 수행해서 확인
- 저자님이 올리신 성능확인 github
- 동일한 동작을 하는 것처럼 보이나, 시간복잡도가 다른 경우 존재
- 점근적 표기법(실전 예시 - 책 참고)
- 문제 11 [짝지어 제거하기★]
- 문자열의 길이 : 1,000,000 이하의 자연수
- 문자열의 길이만큼 이중 반복문을 돌리려고 하는 순간! FAIL...
- 이런 생각을 아예 하지 말아야 함
- 문제 62 [배열 회전하기★★]
- 회전 횟수 n은 자연수이며 1~4입니다.
- 2차원 배열의 행과 열의 크기는 같고, 행의 크기는 10을 넘지 않습니다.
- 이 말은 성능은 고려할게 아니라, 로직만 정확히 짠다면 정답처리
▶ 강의 후기
- 낮은 레벨의 코딩테스트 문제만 풀어봤지만, 가끔 제출했을 때 TLE 발생한 적이 있었다.
- 시간 복잡도라는 개념을 몰랐고, 바로 위에 있는 이중 반복문을 돌리려고 한 게 바로 나...ㅠ
- 입력조건이 내가 작성하는 코드에 그렇게 큰 영향을 미칠 것이라 생각하지 않고 로직만 잘 작성하면 된다고 생각했다.
- 이렇게 하면 완전 FAIL...
- 문제에 주어지는 입력값을 보고 사용가능한 알고리즘을 추정하고 문제를 풀어야겠다는 생각이 든다.
- 시간 복잡도라는 개념을 인지하면서 책에 있는 문제들을 풀어봐야겠다.
▶ 궁금한 점
- 이론적인 부분에서는 아직 없음
- 문제를 풀면서 궁금한 점이 생길 것으로 예상
'코딩테스트 > 코테 스터디(코딩테스트 합격자 되기 C++)' 카테고리의 다른 글
| 코테 스터디 3주차 [해시] (1) | 2024.10.16 |
|---|---|
| 혼자 읽기 아쉬운 저자님의 당부사항 (1) | 2024.10.16 |
| 코테 스터디 2주차 [스택/큐] (3) | 2024.10.15 |
| 코테 스터디 0주차 [효율적으로 코딩 테스트 공부하기] (3) | 2024.10.02 |