✅ 시간복잡도

문제마다 시간 제한이라는 게 주어진다.

시간 제한 안에 돌지 못 하는 알고리즘 → 시간 초과(탈락!)

📖시간 복잡도 표기법 알아보기

시간 복잡도 : 주어진 문제 해결을 위한 연산 횟수

(**1억 번의 연산 → 1초의 수행 시간**)

• 빅-오메가 (최선의 경우)
• 빅-세타 (보통의 경우)
• 빅-오 (최악의 경우)

e.g.

→ for문 내에서 0-99 사이의 무작위 값에서 0이 나오면 for문 탈출

빅-오메가 → 한 번 만에 0이 나옴 (시간 복잡도 1번)

빅-세타 → 50번 만에 0이 나옴 (시간 복잡도 N/2)

빅-오 → 100번 만에 0이 나옴 (시간 복잡도 N)

코테에서는 **빅-오 표기법**기준으로 수행 시간 계산하는 게 좋다.

알고리즘 선택의 기준으로 사용하기

버블 정렬의 시간 복잡도 → O(n^2)

병합 정렬의 시간 복잡도 → O(nlogn)

문제000

시간 제한 2초

→ 2억번 연산이 가능한 것. (2억번 이하의 연산이 되는 알고리즘을 선택해야 함)

💡 연산 횟수 계산 방법
연산 횟수 = 알고리즘 시간 복잡도 n값에 데이터 최대 크기 대입

(알고리즘 적합성 평가)
버블 정렬 ⇒ 부적합

$1,000,000^2$

→ 1,000,000,000,000 > 200,000,000

병합 정렬 ⇒ 적합

$1,000,000log_2(1,000,000)$

→ 약 20,000,000 < 200,000,000

우리가 어떤 알고리즘으로 풀어야 하는가의 기준이 되는 것이 바로 시간 복잡도

코드 로직 개선 ← 시간 복잡도 활용

시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 제외
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨

for(int i = 0; i < N; i++){
	cout << "연산 횟수" << cnt++ << "\n";
}
for(int i = 0; i < N; i++){
	cout << "연산 횟수" << cnt++ << "\n";
}
for(int i = 0; i < N; i++){
	cout << "연산 횟수" << cnt++ << "\n";
}

일반 for문 3개 ⇒ 시간 복잡도 not 3N , yes N

for(int i = 0; i < N; i++){
	for(int i = 0; i < N; i++){
		cout << "연산 횟수" << cnt++ << "\n";
	}
}

이중 for문 → N^2

(정리)

1. 시간복잡도는 최악의 케이스를 고려하는 것
2. 시간 복잡도 도출 시
   1. 상수는 무시한다.
   2. 가장 많이 중첩된 반복문을 기준으로 한다.
3. 시간 복잡도는
   1. 알고리즘 선택 기준
   2. 시간 초과시 내 비효율적 코드가 어디인지 판단 기준

✅ 디버깅

논리 오류를 찾는 가장 좋은 방법

📖 **디버깅**

문법 오류/논리 오류 찾아 바로잡는 과정

• 문법 오류는 컴파일러가 체크해줘 문제가 되지 않는데,
• 논리 오류는 코드가 사용자의 의도와 다르게 “동작”하는 것

? 특정 코테에선 디버깅 못 하는데 공부해야 하나요?

→ 중요하다. 많이 해보면 컴퓨터스럽게, 컴퓨터의 process대로 어떻게 동작하는 지에 대한 이해가 높아지고, 코드를 읽는 실력이 늘게 됨

→ 알고리즘의 동작 원리를 이해하는 데 도움이 된다.

재귀함수 등

디버깅 하는 법

1. 디버깅 하고자 하는 줄에 중단점 설정(여러 개 설정 가능)
2. 코드 한 줄씩 실행 or 다음 중단점
3. 수식 입력해 논리 오류도 파악 가능

vs → local, auto, 조사식(watch) 창 활용 가능

오류 1. 변수 초기화 오류

변수 초기화를 제대로 하지 않은 경우. 코드가 복잡해지면 놓칠 가능성이 높음

오류 2. 인덱스 범위 지정 오류

반복문에서 반복 범위 잘못 지정 or 비교 연산자 잘못 사용함

배열 인덱스 0부터 시작. N까지 반복해야하는데 N-1까지 설정하거나..

오류 3. 잘못된 변수 사용 오류

자료형 오류가 가장 많이 발생함

int 오버플로우 등..

의도치 않게 정답으로 음수 출력시 변수 범위 초과 의심하기

✅ 배열과 리스트 그리고 벡터

📖 배열

메모리의 연속 공간에 값이 채워져 있는 형태의 자료구조

• 인덱스 통해 바로 접근 가능
• 선언한 자료형의 값만 저장 가능
• 새로운 값 삽입/특정 인덱스 값 삭제 어려움. → 해당 인덱스 주변 값 이동시켜야 할 정도임
• 크기 선언할 때 지정. 한 번 선언 시 늘리/줄이기 불가
• 구조 간단. 코테에서 많이 사용

📖 리스트

값, 포인터를 묶은 노드를 포인터로 연결한 자료구조

• 노드 : 값. 포인터를 쌍으로 갖는 기초 단위
• 인덱스 없음 → head포인터부터 순서대로 접근해야 함 → 속도가 느리다
• 포인터로 연결. 데이터 삽입/삭제 연산 속도가 빠르다
• 선언 시 배열처럼 크기를 지정하지 않아도 된다
• 포인터 저장할 공간 필요. 배열보다 구조가 복잡하다

📖 c++(코딩테스트)에서는 벡터가 가장 많이 쓰인다

• 동적으로 원소 추가 가능
• 맨 마지막 위치 데이터 삽입/삭제는 문제 없음
  • 중간 데이터 삽입 삭제는 배열과 같은 메커니즘
• 인덱스 이용해 각 데이터에 직접 접근 가능하다

벡터의 기본 사용법 → #include <vector> 필요!

vector<자료형> name;

**name.size()** : 벡터에 저장된 데이터 개수 반환
name.at(i) : at에 인자로 넘어온 정수 : 벡터 내부 인덱스.
name.front() : 벡터의 첫 번째 데이터 설정/가져올 때 사용하는 함수
name.back() : 벡터의 마지막 데이터를 설정/가져올 때 사용하는 함수
name.empty() : 벡터가 비어 있는지 알려주는 함수 (비어있다면 true 반환)
name.swap(name2) : 벡터 데이터를 서로 바꿈

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    vector<int> A;
    A.push_back(10);
    A.push_back(30);
    A.push_back(5);
    A.push_back(8);
    A.push_back(6);

    A.push_back(1);
    A.insert(A.begin(), 7);
    A.insert(A.begin() + 2, 7);

    A[4] = -5;

    A.pop_back();
    A.erase(A.begin() + 3);

    cout << A.size() << endl;
    cout << A.front() << endl;
    cout << A.back() << endl;
    cout << A[3] << endl;
    cout << A.at(5) << endl;

    A.clear();

    return 0;
}