(C++) 코딩테스트 1. 시간복잡도와 디버깅 / 2. 자료구조(1/2)

참고도서 : Do it! 알고리즘 코딩테스트 C++편 . 김종관 .  이지스퍼블리싱 . 2022 
참고도서 : 파이썬 알고리즘 인터뷰 . 박상길 .  책만 . 2020

---

시간복잡도

보통의 시간복잡도는 빅오 표기법을 기준으로 수행시간을 계산해야합니다. 보통 여러 시간복잡도 유형중에서 빅오가 가장 최악의경우일때를 나타낸다고 보시면됩니다.

빅오는 점근적 실행 시간(시간복잡도)을 표기할 때 가장 널리 쓰이는 수학적 표기법입니다. (입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기법이다)

빅오의 경우는 시간복잡도를 항상 최고차항만 표기합니다. 

O(1) : 입력값이 아무리 커도 실행시간이 일정한 경우
O(logn) : 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편
O(n) : 입력값만큼 시간에 영향을 받으며 알고리즘을 수행하는데, 걸리는 시간은 입력값에 비례한다.
O(nlogn) : 병합정렬같이 효율좋은 알고리즘이 이에 해당된다. 
O(n^2) 버블정렬 같이 비효율적인 정렬 알고리즘이 이에 해당된다.
O(2^n) : 피보나치 수를 재귀로 계산하는 경우 이에 해당한다.
O(n!) : 브루트 포스로 문제를 풀이하는 경우가 이에 해당한다.

일단은 간단하게, 시간복잡도는 for문의 개수가 적을 수록 좋다고 생각하면서 넘어가겠습니다. 

보통 시간복잡도를 계산하는 방법은 for 문 안에서 변수의 크기를 계속 늘려가면 된다고 합니다. 

 

디버깅

디버깅은 다음과 같은 순서를 따릅니다.
1. 코드에서 디버깅하고자 하는 줄에 중단점을 설정합니다. 중단점은 여러개 설정할 수 있습니다.
2. IDE의 디버깅 기능을 설정해서 코드를 1줄씩 실행하거나 중단점까지 실행합니다. 
3. 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 피할 수 있습니다.

 

 

자료구조 

배열
1. 인덱스를 통해 값에 바로 접근이 가능
2. 값을 삽입하거나 삭제가 어려움
3. 배열의 크기는 고정됨
4. 구조가 간단함

리스트
1. 인덱스가 없어 첫번째 노드부터 접근해야함
2. 포인터로 연결되어, 삽입이나 삭제하는 속도가 빠르다.
3. 리스트의 크기를 따로 설정하지 않아도된다.
4. 배열보다 구조가 복잡함

벡터
1. 크기를 자동으로 늘릴 수 있다.
2. 중간에 데이터를 삽입할때 배열과 같은 동작을 한다.
3. 배열과 마찬가지로 인덱스를 통해 접근한다.

 

관련 문제 풀어보기
11720번: 숫자의 합 (acmicpc.net)

11720번: 숫자의 합

첫번째에 숫자의 개수를 적고, 두번째에 공백없이 숫자들을 입력합니다. 그리고 이 숫자들을 모두 더하면됩니다.

간단하게, 풀자면 벡터를 사용할 수도 있지만, 굳이 벡터를 사용할 필요가 없다고 생각하는게, 일단 string형태로 받아온 다음에 0부터 N까지의 합을 구하면 될 것 같습니다.

#include<iostream>

int main() {
	std::string str;
	int sum = 0;
	int t; std::cin >> t;
	std::cin >> str;

	for (auto i : str) {
		sum += int(i) - '0';
	}

	std::cout << sum;
}

정답이군요...

여기서 중요한 포인트는 stoi , stol, stod, stof 와 같이 string에서 다른 자료형(앞글자)로 가는 것이며 반대는 to_string이 있습니다. 그러나 for문을 돌면 string 형태가 아니라 char 형태입니다. int형으로 변환을 해주면 아스키코드의 값이기 때문에 '0' 의 값을 빼주면 됩니다. 

 

1546번: 평균 (acmicpc.net)

1546번: 평균

과목의 개수를 적고, 과목 중에서 가장 높은 점수로 평균을 구한다 아니아니 100대신에 가장 높은 점수로 나눈다. 이걸 뭐라 설명해야해 (SUM)/MAX * 100 을 구해라... 이런 문제인거 같습니다.

벡터를 사용해야하는 문제입니다. 왜냐하면, 과목의 개수가 정해져 있지 않기 때문입니다. 그리고 평균값은 double 자료형을 주어야합니다.

#include<iostream>
#include<vector>

int main() {
	int book; int MAX = 0;
	std::vector<int> v;

	int t; std::cin >> t;
	while (t--) {
		std::cin >> book;
		v.push_back(book);
		if (MAX < book)
			MAX = book;
	}

	double sum = 0;
	for (auto i : v) {
		sum += (double)i / MAX * 100;
	}

	std::cout << sum / v.size();
}

딱히 어려움은 없는 문제였습니다. 

아.. 현재 제 코드는 각 과목에서 계산을 한 번씩 했지만 그럴 필요가 없습니다. 수학적으로 접근하면.. 각각 과목에 MAX값을 나눈다는 것은 결국 모두 MAX로 나눈다는 것입니다. 그러니 vector를 사용할 필요도 없었네요. 다시 풀면 이렇습니다.

#include<iostream>

int main() {
	int book; int sum = 0; int MAX = 0;

	int t; std::cin >> t;
	int size = t;
	while (t--) {
		std::cin >> book;
		sum += book;
		if (MAX < book)
			MAX = book;
	}

	std::cout << (double)sum / MAX / size * 100;

}

코드가 굉장히 짧아지는 군요..

 

구간합

배열을 통해 시간복잡도를 줄이는 방법입니다. 배열이 하나 있다고 할 때, 이 배열의 합을 배열로 가지고 있는 합배열이 있다고 합시다.

S[0] = A[0]
S[1] = S[0] + A[1] =  A[0] + A[1]
S[2] = S[1] + A[2] =  A[0] + A[1] + A[2]
와 같은 배열입니다.

그러면 이런 경우입니다.  A[3] + A[4] + A[5]  를 구하려한다고 합니다. 그러면 합배열을 사용하면 다음과 같습니다.
S[5] - S[1] = A[0] + A[1] + A[2] + A[3] + A[4] + A[5]   -  A[0] + A[1]
그러므로 S[i] - S[j-1]  입니다.

 

관련문제 풀이

11659번: 구간 합 구하기 4 (acmicpc.net) 

11659번: 구간 합 구하기 4

문제는 간단합니다. 1 2 3 4 5 가 주어지면 2와 4 이러면 2 3 4 까지 더한 값을 리턴하면됩니다. 그러면 앞서 배운 구간합을 사용해봅시다.

합배열만 있으면 되는 문제니, 우선은 Vector는 하나만 사용하고 이를 합배열로 사용합시다. 그리고 앞서 설명한 S[i] - S[j-1] 공식을 사용하도록 합시다.

#include<iostream>
#include<vector>

int main() {
	std::vector<int> v; int su; int sum = 0;
	int size; int t;
	
	v.push_back(sum);
	std::cin >> size >> t;
	while (size--) {
		std::cin >> su;
		sum += su;
		v.push_back(sum);
	}

	int front; int back;

	while (t--) {
		std::cin >> front >> back;
		std::cout << v[back] - v[front - 1] << "\n";
	}
}

 

결과는 맞게 나오는데, 시간초과가 나온다.. 어떤 이유일까..  

#include<iostream>
#include<vector>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::vector<int> v; int su; int sum = 0;
	int size; int t;
	
	v.push_back(sum);
	std::cin >> size >> t;
	while (size--) {
		std::cin >> su;
		sum += su;
		v.push_back(sum);
	}

	int front; int back;

	while (t--) {
		std::cin >> front >> back;
		std::cout << v[back] - v[front - 1] << "\n";
	}
}

진짜 만약 코딩테스트 문제에서 

std::ios::sync_with_stdio(false);
std::cin.tie(NULL);
std::cout.tie(NULL);

std::endl 대신에 "\n" 를 사용할 것

이거 3줄로 시간초과냐 아니냐가 갈리면 욕나올듯 아무리 시간을 타이트하게 잡았다고 해도, 이런 편법을 아냐 모르냐로 정답이냐 아니냐를 판단하게 하는게 맞는가 싶기도 하다.

 

11660번: 구간 합 구하기 5 (acmicpc.net)

11660번: 구간 합 구하기 5

 

저는 문제를 잘못 접근하고 있었는데, 그냥 x1, y1 에서 x2,y2 까지 영역을 모두 더하면 되는 문제입니다.

이런 느낌입니다. 앞서 풀어본바와 같이 구간합을 사용해서 접근을 해봅시다.

#include<iostream>
#include<vector>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::vector<std::vector<int>> v; 
	std::vector<int> temp;
	int su; int sum = 0;
	int size; int t;
	
	std::cin >> size >> t;
	
	for (int i = 0; i < size; i++) {
		for (int j = 0; j < size; j++) {
			std::cin >> su;
			sum += su;
			temp.push_back(sum);
		}
		v.push_back(temp);
		temp.clear();
	}

우선 2차원 벡터를 사용했고, 다음처럼 표시합니다. 그러면 이제 이를 활용해야하는데, 저는 그냥 각 행별로 구간합을 빼자 생각했습니다.

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::vector<std::vector<int>> v; 
	std::vector<int> temp;
	int su; int sum = 0;
	int size; int t;
	
	std::cin >> size >> t;
	
	for (int i = 0; i < size; i++) {
		temp.push_back(sum);
		for (int j = 0; j < size; j++) {
			std::cin >> su;
			sum += su;
			temp.push_back(sum);
		}
		v.push_back(temp);
		temp.clear();
	}

일단 sum이 맨 처음일때 값을 알고있어야하기 때문에 sum 값을 하나 더 추가합니다.

#include<iostream>
#include<vector>

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::vector<std::vector<int>> v; 
	std::vector<int> temp;
	int su; int sum = 0;
	int size; int t;
	
	std::cin >> size >> t;
	
	for (int i = 0; i < size; i++) {
		temp.push_back(sum);
		for (int j = 0; j < size; j++) {
			std::cin >> su;
			sum += su;
			temp.push_back(sum);
		}
		v.push_back(temp);
		temp.clear();
	}

	int s_x, s_y, e_x, e_y;
	while (t--) {
		sum = 0;
		std::cin >> s_x >> s_y >> e_x >> e_y;
		for (int i = s_x; i <= e_x; i++) {
			sum += v[i - 1][e_y] - v[i - 1][s_y-1];
		}
		std::cout << sum << "\n";
	}
}

그러면 다음처럼 나오게 되고

후.. 어려웠다.. 

 

제 방법은 

위와 같은 방법이지만, 정석풀이는 이게 아닌 것 같습니다. vector를 두개 써서 숫자를 하나 저장하고, 하나는 구간합을 저장합니다. 그 후에 

전체의 구간합을 구한 후에 초록부분의 구간합을 빼고, 주황색부분을 한 번 더해주면 빨간영역을 쉽게 구할 수 있다고 합니다.  아무래도 for문이 줄어들어 더 빠른 것 같습니다. 

책에 언급된 마지막 문제는 난이도가 높은 문제이기 때문에 나중에 따로 모아서 풀이합니다.