[알고리즘/코딩테스트👩‍💻] Do it! 알고리즘 코딩테스트 C++ 1~2강 코딩테스트 준비하기

2학년 겨울방학이 된 지금부터는 이전보다 더욱 본격적으로 알고리즘 실력을 쌓고 코딩테스트 준비를 하려고 합니다. 코딩테스트 언어를 Java와  C++ 중 고민하다가 C++을 선택하게 되었습니다. 
 
교내 학회 ALGOS에서도 C++로 알고리즘을 공부하고 백준을 풀고 있지만, 제 개인적으로도 공부를 해야 할 필요성을 느껴서 이지스퍼블리싱의 교재를 방학 중에 1회독해보려고 합니다. 전반적으로 문제들을 봤는데 많이 어려워서 먼저 "알고리즘에 익숙해지겠다"는 목표로 1회독을 하고, n회독 때는 온전히 제 힘으로만 풀어볼 생각입니다.
 
교재 : Do it! 알고리즘 코딩테스트 c++ (김종관, 이지스퍼블리싱)
공부 깃허브 : https://github.com/yeonjae02/algorithmStudy_cpp

GitHub - yeonjae02/algorithmStudy_cpp: Do it! 알고리즘 코딩테스트 C++ 을 공부하며 작성한 코드 저장소

 

---

 

Chap01. 어떤 알고리즘으로 풀어야 할까?

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

- C++에서는 1억 번의 연산을 1초의 수행 시간으로 예측 가능
- 시간 복잡도 유형

• 빅-오메가(Ω(n)) : 최선일 때(best case)의 연산 횟수를 나타낸 표기법
• 빅-세타(θ(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
• 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법

- 코딩테스트에서는 빅-오 표기법을 기준으로 수행시간을 계산해야 함.
 

1.2 시간 복잡도 활용하기

- 문제 : 백준 2750
https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

• 코드 

#include <iostream>
#include <vector>
using namespace std;

// BOJ 2750

void swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int main()
{
	int n;
	cin >> n;
	vector<int> v(n);

	for (int i = 0; i < n; i++) cin >> v[i];

	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n - 1 - i; j++)
			if (v[j] > v[j + 1]) swap(&v[j], &v[j + 1]);
	}

	for (int i = 0; i < n; i++) cout << v[i] << "\n";
	return 0;
}

 
- 시간 복잡도를 바탕으로 코드 로직 개선하기 : 시간 복잡도 도출 기준

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

 

Chap02. 코드의 논리 오류를 어떻게 잡을까?

2.1 디버깅은 왜 중요할까?

- 디버깅(debugging) : 프로그램에서 발생하는 문법오류나 논리오류를 찾아 바로잡는 과정
-디버깅하는 법

1. 코드에서 디버깅하고자 하는 줄에 중단점을 설정한다. (중단점은 여러 개 설정 가능)
2. IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행 가능하고 추적할 변숫값도 지정할 수있다. (변숫값이 의도대로 바뀌는지 파악)
3. 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있다.

 

2.2 디버깅 활용 사례 살펴보기

- 실수하기 쉬운 4가지 오류

• 변수 초기화 오류
• 반복문에서 인덱스 범위 지정 오류
• 잘못된 변수 사용 오류
• 자료형 범위 오류
  • 음수가 될 수 없는 값이 음수가 된다면 자료형을 int가 아닌 long, long long으로 변경하기