그리디
그리디 개념
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 단순히 탐욕적으로 문제를 해결하기 때문에 탐욕법이라고도 함
- 그리디로 문제를 해결할 때 이것이 정당한지 검토할 수 있어야 답을 도출할수 있음
문제풀이
거스름돈
입력받은 값을 값이 큰 동전부터 500, 100, 50, 10으로 나눔
#include <iostream>
using namespace std;
int main()
{
int n, ans;
cin >> n;
ans = 0;
ans += n / 500;
n %= 500;
ans += n / 100;
n %= 100;
ans += n / 50;
n %= 50;
ans += n / 10;
cout << ans << endl;
return 0;
}큰 수의 법칙
배열을 조건에 맞게 입력받은 뒤 오름차순으로 정렬함. 그 다음 m번동안 가장 마지막에 있는 원소를 k번 더하고 마지막 앞의 원소를 한번 더함.
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, m, k, cnt, ans;
int arr[1001];
cin >> n>>m>>k;
for (int i = 0; i < n; i++)
cin >> arr[i];
sort(arr, arr + n);
ans = cnt = 0;
while (1)
{
for (int j = 0; j < k; j++)
{
ans += arr[n - 1];
cnt++;
if (cnt == m)
{
cout << ans << endl;
return 0;
}
}
ans += arr[n - 2];
cnt++;
if (cnt == m)
{
cout << ans << endl;
return 0;
}
}
}숫자 카드 게임
행을 그룹으로 생각하고 각 행에서 가장 작은 수를 배열에 집어넣음. 그 배열에서 가장 큰 수를 골라서 출력함.
#include <iostream>
using namespace std;
int main()
{
int n, m, ans;
int arr[10001];
int min[101];
cin >> n >> m;
for (int i = 1; i <= n * m; i++)
cin >> arr[i];
for (int i = 0; i < n; i++)
{
for (int j = 1; j < m; j++)
{
if (arr[(i * n) + j] < arr[(i * n) + j + 1])
min[i + 1] = arr[(i * n) + j];
else
min[i + 1] = arr[(i * n) + j + 1];
}
}
for (int i = 1; i < n; i++)
{
if (min[i] > min[i + 1])
ans = min[i];
else
ans = min[i + 1];
}
cout << ans << endl;
return 0;
}1이 될 때까지
n을 k로 나눈 나머지가 0이라면 나누기, 아니라면 빼기
#include <iostream>
using namespace std;
int main()
{
int n, k, cnt;
cin >> n >> k;
cnt = 0;
while (n != 1)
{
if (n % k == 0)
{
cnt++;
n /= k;
}
else
{
cnt++;
n--;
}
}
cout << cnt << endl;
return 0;
}11501 주식
그리디로 풀었다. 현재 남은 날짜 중 가장 주가가 높은 날 주식을 팔고 나머지 경우에는 주식을 한주씩 산다. 주가가 가장 높은 날 보유한 주식이 0이라면 아무것도 하지 않는다.
주가가 내림차순인 날에 정답이 음수로 뜨는 오류가 있었다. max_element를 처음 사용해보는데 v.begin()+i 로 식을 써서 생긴 문제...였다. max인 날에 도착하면 다음 max를 찾아야 하는데 v.begint()+i+1이 바른 식이었다.
첫 제출 때 틀렸습니다가 떴다. 최대 1000000*10000이면 당연히 21억 넘어가는데 int로 출력해서 생긴 오류였다. long long으로 바꾸는 것으로 해결했다.
반례 처리하니까 잘 돌아가는데 시간복잡도 이슈가 있었다.
<추가>
알고리즘 헤더에 있는 max_element함수 복잡도가 o(n)이라고 한다. 안그래도 이중반복문인데 이런 함수를 써서 시간초과가 나왔다고 판단하고 알고리즘을 전면 수정했다. 마지막 날의 주가를 최고 주가로 설정해놓고 뒤에서 앞으로 돌면서 그것보다 주가가 큰 날을 만났을 때 최대 주가를 수정하고 최대주가 - 현재 주가를 더해준다.
[수정 전 코드]
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int main()
{
long long n, l, max, cnt, current;
vector<int>v;
cin >> n;
for (int j = 0; j < n; j++)
{
v.clear();
int m;
cnt = current = 0;
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> l;
v.push_back(l);
}
max = *max_element(v.begin(), v.end());
for (int i = 0; i < m; i++)
{
if (v[i] == max)
{
if (cnt != 0)
{
current = (cnt * v[i]) + current;
cnt = 0;
if (i != m - 1)
max = *max_element(v.begin() + i + 1, v.end());
}
else
{
if (i != m - 1)
max = *max_element(v.begin() + i + 1, v.end());
continue;
}
}
else
{
current = current - v[i];
cnt++;
}
}
cout << current << '\n';
}
return 0;
}[수정후]
#include <iostream>
#include <vector>
using namespace std;
int main()
{
long long int T, N, current, max;
vector<int>v;
cin >> T;
while (T--)
{
cin >> N;
current = 0;
for (int i = 0; i < N; i++)
{
int n;
cin >> n;
v.push_back(n);
}
max = -1;
for (int i = N - 1; i >= 0; i--)
{
if (max < v[i])
max = v[i];
current += max - v[i];
}
v.clear();
cout << current << '\n';
}
return 0;
}구현
구현개념
- 구현은 코딩테스트에서의 피지컬적인 부분임. 라이브러리 활용 능력이나 타자 등 개발자의 피지컬을 파악하기 위해 출제됨
- 이 파트는 완전탐색/시뮬레이션을 포함함
문제풀이
상하좌우
x, y, n 변수를 만들어서 x와 y의 값을 각각 설정해주면 됨. n은 사용자에게 받아옴. 여행가가 몇 번 동작을 수행할지 알 수 없기 때문에 getline함수를 사용해서 입력 기준을 엔터로 받게 함. 나는 x, y 순서로 출력했는데 책에서는 y, x 순서로 출력됨. 내가 문제를 잘못 이해한건지 확인
#include <iostream>
#include <string>
using namespace std;
int main()
{
int n, x, y, cnt;
string s;
char arr[101];
cin >> n;
cin.ignore();
getline(cin, s);
cnt = 0;
x = y = 1;
for (int i = 0; i < s.size(); i++)
{
if (s[i] == 'L')
{
if (x - 1 >= 1)
x -= 1;
}
else if (s[i] == 'R')
{
if (x + 1 <= n)
x += 1;
}
else if (s[i] == 'U')
{
if (y - 1 >= 1)
y -= 1;
}
else if (s[i] == 'D')
{
if (y + 1 <= n)
y += 1;
}
}
cout << x << " " << y << '\n';
return 0;
}시각
시간/분/초 단위로 삼중반복문 만들어서 0시0분0초-n시59분59초까지 모든 경우의 수를 세어 줌. 10으로 나눴을 때 몫/나머지가 3인 경우만 카운트함.
시간복잡도 안 걸리나? -> 최대 23*60*60이라 복잡도 신경쓰지 않아도 됨.
#include <iostream>
using namespace std;
int main()
{
int n, cnt;
cin >> n;
cnt = 0;
for (int i = 0; i <= n; i++)
{
for (int j = 1; j <= 60; j++)
{
for (int k = 1; k <= 60; k++)
{
if (i / 10 == 3 || i % 10 == 3)
cnt++;
else if (j / 10 == 3 || j % 10 == 3)
cnt++;
else if (k / 10 == 3 || k % 10 == 3)
cnt++;
}
}
}
cout << cnt << '\n';
return 0;
}왕실의 나이트
상하좌우 문제와 비슷하게 x, y값을 받아서 조건 판단함. 어차피 8*8 보드라 입력받는 문자열이 2글자를 넘어가지 않기 때문에 s[0], s[1]의 문자를 숫자로 변경시켜서 그걸로 연산함.
#include <iostream>
using namespace std;
int main()
{
string s;
int x, y, cnt;
cin >> s;
x = s[0] - 'a' + 1;
y = s[1] - '1' + 1;
cnt = 0;
if (x + 2 <= 8)
{
if (y - 1 >= 1 && y + 1 <= 8)
cnt += 2;
else if (y - 1 >= 1 || y + 1 <= 8)
cnt++;
}
if (x - 2 >= 1)
{
if (y - 1 >= 1 && y + 1 <= 8)
cnt += 2;
else if (y - 1 >= 1 || y + 1 <= 8)
cnt++;
}
if (y + 2 <= 8)
{
if (x - 1 >= 1 && x + 1 <= 8)
cnt += 2;
else if (x - 1 >= 1 || x + 1 <= 8)
cnt++;
}
if (y - 2 >= 1)
{
if (x - 1 >= 1 && x + 1 <= 8)
cnt += 2;
else if (x - 1 >= 1 || x + 1 <= 8)
cnt++;
}
cout << cnt << '\n';
return 0;
}게임 개발
2503 야구 게임
완전탐색을 돌렸다. 알고리즘을 직접 짜고 싶었으나 처음 접근해보는 관계로 블로그 참고해서 풀었다. 하나의 입력에 대해 123~987까지 스트라이크와 볼의 갯수를 만족하는 수만 false로 남겨뒀다. 입력에 세개의 수에 '중복되는 수'와 '0'은 포함되지 않는다고 해서 마지막에 답을 카운트 할 때 삼중반복문 초기값을 모두 1로 설정했다. 그리고 삼중반복문의 변수가 같을 때 카운트하지 않고 다음 반복으로 넘겨버렸다.
오타 이슈로 몇분 잡아먹었는데 코드 작성할 때 꼼꼼하게 확인해야 이런 자잘한 실수 줄일 것 같다. 전역변수 안쓰고 static 쓸까 하다가 찾아보기 귀찮아서 전역변수로 작성했다. ㅎ
#include <iostream>
#include <string>
using namespace std;
bool arr[1000];
void check(string base, int s, int b)
{
int st, ba;
for (int i = 123; i <= 987; i++)
{
st = ba = 0;
string now = to_string(i);
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{
if (now[j] == base[k])
{
if (j == k)
st++;
else
ba++;
}
}
}
if (s != st || b != ba)
arr[i] = true;
}
}
int main()
{
int n, s, b, ans;
cin >> n;
for (int i = 0; i < 1000; i++)
arr[i] = false;
string base;
for (int i = 0; i < n; i++)
{
cin >> base >> s >> b;
check(base, s, b);
}
ans = 0;
for (int i = 1; i <= 9; i++)
{
for (int j = 1; j <= 9; j++)
{
if (i == j)
continue;
for (int k = 1; k <= 9; k++)
{
if (k == j || k == i)
continue;
if (arr[i * 100 + j * 10 + k] == false)
ans++;
}
}
}
cout << ans << '\n';
return 0;
}