문제풀이 고려사항
1. 제한된 메모리와 시간
2. 알고리즘
시간복잡도
문제에서 제시된 입력의 크기와 프로그램의 수행시간과의 관계를 나타내는 함수
Big-O(빅-오) : 상한 점근 (가장 느리게 실행될 때)을 이용해서 시간복잡도 표현
간단하게 생각하면 최고차항의 차수 또는 지수의 밑이 중요하다
1초 = 10^9
Bruteforcing
모든 경우의 수를 확인해보는 방법
빠른 입출력
- main 아래에 구문 적기
cin.tie(nullptr);
cout.tie(nullptr);
ios::sync_with_stdio(false);- 이 경우 scanf, printf 혼용 X cin, cout만 사용하기
- endl(버퍼를 비운다)대신 개행문자 '\n' 사용하기
1) 블랙잭 BOJ 2798
주어진 배열에서 M을 넘지 않으면서 최대한 가까운 세 수의 합을 구하기
- for문을 세번돌려 값을 구하는 풀이 [O(n^3)]
2) 일곱 난쟁이 BOJ 2309
아홉 난쟁이의 키가 주어졌을 때, 합이 100이 되는 7명의 난쟁이 찾기
- 아홉명 난쟁이 키의 합을 구한 후 100을 뺀 값을 x라고 하면,
x를 만족하는 두명의 난쟁이를 제외시키는 풀이 [O(n^2)]
3) 분해합 BOJ 2231
분해합은 N과 N을 이루는 각 자리수의 합, 수가 주어질 때 그 수의 가장 작은 N을 구하기
여기서 N <= 10^6
ex) 198+1+9+8 = 216
- for문(작은수부터)을 돌려 하나씩 분해합을 구한 후 비교하는 방법 [O(n)]
Q. 왜 시간복잡도가 O(nlogn)이지?
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
//use '\n'
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
string n;
cin >> n;
int low = 0;
int sum = 0;
low = stoi(n) - (9 * n.size()); //하한값을 구한다 셋다 999일경우 가장 작은 숫자가 나온다
for (int i = low; i < stoi(n); i++) { //하한값부터 하나씩 증가시킨다
sum += i;
int temp = i;
for (int j = n.size()-1; j >= 0; j--) { //분해합을 구하는 과정
sum += temp / (int)(pow(10.0, j));
temp = temp % (int)(pow(10.0, j));
}
if (stoi(n) == sum) { //답이라면
cout << i << '\n';
// 출력하고 빠져나간다
//(하한값부터 시작했기 때문에 답을 찾는 것 = 가장 작은 생성자를 찾은 것)
break;
}
sum = 0;
}
if (stoi(n) != sum)
cout << 0;
return 0;
}
풀고나서 보니, 분해합을 구하는 과정은
while (temp != 0) {
sum += temp % 10;
temp /= 10;
}아래와 같이 적용시키는게 더 편하다는 것을 알았다
4) 분해합2 BOJ 12348
여기서 N <= 10^18
- N - (9X자릿수의 개수) = 그 수의 가장 작은 N [O(1)]
분해합2도 위 분해합 풀이처럼 풀었지만, 런타임 에러가 발생했다
Q. Strict weak ordering
5) 폭죽쇼 BOJ 1773
pigoen hole 방식을 사용한다. 폭죽이 끝나는 시간보다 적으면 배수로 늘린다.
6) 체스판 다시 칠하기 BOJ 1018
#include<iostream>
#define INF 65
using namespace std;
//use '\n'
string WB[8] = {
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW"
};
string BW[8] = {
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB",
"BWBWBWBW",
"WBWBWBWB"
};
int cntWB(int x, int y, char** chess) {
int cnt = 0;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (chess[x + i][y + j] != WB[i][j])
cnt++;
}
}
return cnt;
}
int cntBW(int x, int y, char** chess) {
int cnt = 0;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if (chess[x + i][y + j] != BW[i][j])
cnt++;
}
}
return cnt;
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
char** chess = new char*[n];
for (int i = 0; i < n; i++) {
chess[i] = new char[m];
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> chess[i][j];
}
}
int count = INF;
for (int i = 0; i < n-7 ; i++) {
for (int j = 0; j < m-7; j++) {
int temp = min(cntWB(i, j, chess), cntBW(i, j, chess));
count = min(count, temp);
}
}
cout << count;
return 0;
}너무 간단한 delete를 놓쳤다 동적할당에서 주의할 필요가 있다
처음에 WB,BW string 배열을 만들지 않고 접근해서 꽤나 시간이 걸렸다
만약 WB, BW의 string 배열의 크기가 크다면, 어떻게 풀 수 있을까?
7) 벚꽃이 정보섬에 피어난 이유 BOJ 17127
8) 한수 BOJ 1065
9) 창문 닫기 BOJ 13909
#include<iostream>
using namespace std;
int n;
void cnt(int i, bool* windowCnt) {
int temp, x=1;
temp = x * i;
while (temp <= n) {
if (windowCnt[temp])
windowCnt[temp] = 0;
else
windowCnt[temp] = 1;
x++;
temp = x * i;
}
}
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> n;
bool* windowCnt = new bool[n+1];
for (int i = 1; i <= n; i++) {
windowCnt[i] = 0;
}
for (int i = 1; i <= n; i++) {
cnt(i, windowCnt);
}
int count = 0;
for (int i = 1; i <= n; i++) {
if (windowCnt[i])
count++;
}
cout << count;
delete[] windowCnt;
return 0;
}
[error] 메모리 초과
#include<iostream>
using namespace std;
int main(void) {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, count = 0;
cin >> n;
for (int i = 1; i * i <= n; ++i)
count++;
std::cout << count;
return 0;
}
풀이 : 주어진 범위 내의 제곱수의 개수를 구해 문제를 해결한다
n번째 창문이 열려있으려면 열고 닫은 횟수(=n의 약수의 개수) : 홀수번
약수의 개수가 홀수인 것은 제곱수이다