#230202 목
알고리즘 스터디를 하면서 농장에서 알고리즘을 심는 사람이 있다..? 그게 바로 나야~ 일주일 전의 난 '알고리즘? 알고리즘이 뭐죠? Are go리듬~ 뭐 이런 건가요(ㅈㅅ)' 이러고 있었는데 갑자기 스터디를 하면서 일주일에 알고리즘 세 문제씩 푸는 사람이 되었고 오늘부턴 하루에 세 문제씩 푸는 사람이 된다. 와 일일드라마도 이 전개속도로 쓰면 욕 먹을 듯. 실화냐?
그래도 이왕 일일드라마 쓰는 거 제대로 써서 꼭 해피엔딩으로 끝내도록 해보겠다.. 겨우 나따위 때문에 대한민국 일일드라마 해피엔딩의 대법칙이 파괴되면 안 되는 거잖아요..
1. 백준 7568번 덩치
<문제>
우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩치가 각각 (x, y), (p, q)라고 할 때 x > p 그리고 y > q 이라면 우리는 A의 덩치가 B의 덩치보다 "더 크다"고 말한다. 예를 들어 어떤 A, B 두 사람의 덩치가 각각 (56, 177), (45, 165) 라고 한다면 A의 덩치가 B보다 큰 셈이 된다. 그런데 서로 다른 덩치끼리 크기를 정할 수 없는 경우도 있다. 예를 들어 두 사람 C와 D의 덩치가 각각 (45, 181), (55, 173)이라면 몸무게는 D가 C보다 더 무겁고, 키는 C가 더 크므로, "덩치"로만 볼 때 C와 D는 누구도 상대방보다 더 크다고 말할 수 없다.
N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 "큰 덩치"의 사람의 수로 정해진다. 만일 자신보다 더 큰 덩치의 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다. 이렇게 등수를 결정하면 같은 덩치 등수를 가진 사람은 여러 명도 가능하다. 아래는 5명으로 이루어진 집단에서 각 사람의 덩치와 그 등수가 표시된 표이다.
| 이름 | (몸무게, 키) | 덩치 등수 |
|---|---|---|
| A | (55, 185) | 2 |
| B | (58, 183) | 2 |
| C | (88, 186) | 1 |
| D | (60, 175) | 2 |
| E | (46, 155) | 5 |
위 표에서 C보다 더 큰 덩치의 사람이 없으므로 C는 1등이 된다. 그리고 A, B, D 각각의 덩치보다 큰 사람은 C뿐이므로 이들은 모두 2등이 된다. 그리고 E보다 큰 덩치는 A, B, C, D 이렇게 4명이므로 E의 덩치는 5등이 된다. 위 경우에 3등과 4등은 존재하지 않는다. 여러분은 학생 N명의 몸무게와 키가 담긴 입력을 읽어서 각 사람의 덩치 등수를 계산하여 출력해야 한다.
<입력>
첫 줄에는 전체 사람의 수 N이 주어진다. 그리고 이어지는 N개의 줄에는 각 사람의 몸무게와 키를 나타내는 양의 정수 x와 y가 하나의 공백을 두고 각각 나타난다.
<출력>
여러분은 입력에 나열된 사람의 덩치 등수를 구해서 그 순서대로 첫 줄에 출력해야 한다. 단, 각 덩치 등수는 공백문자로 분리되어야 한다.
<제한>
2 ≤ N ≤ 50
10 ≤ x, y ≤ 200
솔직히 문제 읽을 땐 이정도면 완전 쉽지~ 했는데 생각보다 나는 멍청이였다,, 50분은 걸린 것 같다. 알고리즘 종류 확인하려고 내렸다가 한국정보올림피아드 초등부 2번 문제였다는 것을 확인하고 나선 그냥 물에 젖은 새 됐음 나 지금 온 방이 눈물로 축축해,, 그때 저 문제를 푼 사람들이 지금 대강 나랑 동갑이다
내 코드:
#include <iostream>
using namespace std;
int input_array[50][2];
int main() {
int num;
cin >> num;
for (int i = 0;i < num;i++) {
cin >> input_array[i][0] >> input_array[i][1];
}
int rank[50] = { 0, };
for (int i = 0;i < num;i++) {
for (int j = 0;j < num;j++) {
if (input_array[i][0] < input_array[j][0]
&& input_array[i][1] < input_array[j][1]) {
rank[i]++;
}
}
}
for (int i = 0;i < num;i++) {
cout << rank[i]+1 << ' ';
}
}input_array 2차원 배열로 각 인물의 몸무게와 키를 받는다. 인물별로 덩치 순위를 기록할 rank는 0으로 초기화한다.(처음에 1로 초기화했다가 오류 나서 배열 초기화는 0으로만 할 수 있다는 정보를 습득하게 되었다..) 인물별로 각 input_array 속 다른 사람들에 대하여 자기보다 몸무게와 키가 모두 큰 사람을 만날 때마다 자신의 rank에 1씩 더한다. 몸무게만 높거나 키만 큰 사람은 덩치를 비교하지 않으므로 고려하지 않아도 된다.
마지막으로 출력할 땐 rank에 1을 더한 값을 출력한다(처음에 0으로 초기화해서 그렇다. 1등의 rank는 0이 아닌 1이어야하므로 더해준다)
2. 백준 2309번 일곱 난쟁이 문제
이것도 초등부 정보올림피아드 문제라서 그런가 내용이 좀 귀엽다,,ㅎ
<문제>
왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.
아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.
아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.
<입력>
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
<출력>
일곱 난쟁이의 키를 오름차순으로 출력한다. 일곱 난쟁이를 찾을 수 없는 경우는 없다.
내 코드:
#include <iostream>
using namespace std;
int h[9];
int ex1;
int ex2;
int main() {
int sum = 0;
for (int i = 0;i < 9;i++) {
cin >> h[i];
sum += h[i];
}
for (int i = 0;i < 9;i++) {
for (int j = i + 1;j < 9;j++) {
if (h[i] > h[j]) {
int tmp = h[j];
h[j] = h[i];
h[i] = tmp;
}
}
}
for (int i = 0;i < 9;i++) {
for (int j = i + 1;j < 9;j++) {
sum -= (h[i] + h[j]);
if (sum == 100) {
ex1 = i;
ex2 = j;
break;
}
sum += (h[i] + h[j]);
}
if (sum == 100) break;
}
for (int i = 0;i < 9;i++) {
if (i != ex1 && i != ex2) cout << h[i] << endl;
}
}맞긴 맞았는데 뭐랄까 좀.. 묘하게 구린 느낌은 뭐지
1) 키를 입력 받으면서 더함
2) 오름차순으로 정렬시킴
3) 제외시킬 2명을 고르고 전체 키를 더한 것에서 2명의 키를 뺌
3-1) 만약 100이면 탈출하고 출력
3-2) 만약 100이 아니면 다음 2명을 고름 (brute force)
를 선택했는데 왠지 더 좋은 코드가 있을 것만 같은 기분이 든다. 하여튼 시간 제한이 2초라서 다행인 듯,, for문만 몇 개니
3. 백준 1018번 체스판 칠하기 문제
왔다...ㅋ 알고리즘 스터디 2회차에서도 포기하고 경작 2일차 벨로그에서도 포기한 대망의 체스판 칠하기 문제.. 진짜 기어코 피할 수 없을 때까지 날 따라오는 구나 너.. 나 조와해? 나 조아하냐구. 미안하지만 난 널 받아줄 생각이 없어
그니까 제발 가줘..ㅠㅠ
(체스판 : 싫어)
선배님들께서 스터디에서 해설하실 땐 검정으로 시작하는 체스판과 하양으로 시작하는 체스판을 둘 다 구현한 뒤 비교하는 것도 언급하신 것 같고 뭐 또 있었는데 다 잊어버렸다. 그땐 내가 문제를 못 푼 상태여서 스스로 해결하고픈 욕심에 해설을 일부로 안 들었다..(왜 그랬지) 하여튼 그렇게 풀려고 해도 난 일단 체스판을 구현하는 것도, 비교하는 것도 어떻게 하는 건지 잘 모르겠다. 그래서 1시간 정도 밥 먹고 설거지하면서 내가 구현하는 것을 기준으로 최대한 쉬운 방법을 생각해봤는데 그냥 모든 입력을 글자 하나씩 2차원 배열에 저장하고, 검정색으로 시작하는 체스판으로 만들 때 몇 번 칠해야 하는지, 하얀색으로 시작하는 체스판으로 만들 때 몇 번 칠해야 하는지 일일이 세서 가장 적은 걸 고르면 되지 않을까? 라는 결론을 내렸다. 와 진짜 brute force 그잡채
..대충 1시간/1시간 반 뒤..
으아아아아앙아아악 풀었어어어어어어어어어ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ
내 코드:
#include <iostream>
#include <string>
using namespace std;
char input[51][51];
int function_b(int co, int ro) {
int count=0;
for (int i = 0 ; i < 8 ; i++) {
for (int j = 0; j < 8; j++) {
if ((i + j) % 2 == 0) {
if (input[co + i][ro + j] != 'B') count++;
}
else {
if (input[co + i][ro + j] != 'W') count++;
}
}
}
return count;
}
int function_w(int co, int ro) {
int count = 0;
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 8; j++) {
if ((i + j) % 2 == 0) {
if (input[co + i][ro + j] != 'W') count++;
}
else {
if (input[co + i][ro + j] != 'B') count++;
}
}
}
return count;
}
int main() {
int co, ro;
cin >> co >> ro;
for (int i = 0;i < co;i++) {
for (int j = 0;j < ro;j++) {
cin >> input[i][j];
}
}
int result = 64;
for (int i = 0;i <= co - 8;i++) {
for (int j = 0;j<=ro - 8;j++) {
int bresult = function_b(i, j);
int wresult = function_w(i, j);
if (bresult < wresult) {
result = (bresult < result) ? bresult : result;
}
else {
result = (wresult < result) ? wresult : result;
}
}
}
cout << result;
}입력된 판 글자 하나씩 input[co][ro]에 넣고 나서도 얘네를 검정/흰색으로 시작하는 체스판들이랑 어떻게 비교하지? 하는 의문점 때문에 한참 고민하고, 오류도 내고 해보다가 문득 스터디에서 홀수/짝수라는 단어 들은 게 생각나서 따져보니 아주 유용한 말씀이었다.
(그림판으로 그렸다ㅎ)
검정색으로 시작하는 체스판이라고 가정하면, 행의 인덱스와 열의 인덱스를 더한 것이 짝수인 곳은 모두 검정, 홀수인 곳은 모두 흰색이다. 따라서 비교하기 위해선
if ((i + j) % 2 == 0) {
if (input[co + i][ro + j] != 'B') count++;
}
else {
if (input[co + i][ro + j] != 'W') count++;
}(i+j)%2 == 0 인 칸은 블랙이어야 하므로, 아닌 경우(!='B') 다시 칠해줘야 하는 칸의 개수(count)를 하나 늘린다.
(i+j)%2 == 0이 아닌 경우(홀수)의 칸은 흰색이어야 하므로, 흰색이 아니면(!='W') 다시 칠해줘야 하는 칸의 개수(count)를 하나 늘린다.
..나처럼 이렇게 무식하게 for문을 네 번이나 중첩시켜 푼 사람들이 있을까..? 시간복잡도가 O(n^4)인 brute force로..?
언젠가 미래의 내가 이 코드를 다시 보고
"누가 이따구로 풀어 ㅋㅋ 진짜 brute(무식한 게) force(힘)이다.. "
라고 비웃을 날도 오길 바란다,,
하여튼 오늘 10시에 기상해서 현재 시각 4시 22분까지 아침 먹는 시간, 설거지 하는 시간, 휴식 타임(ㅎ) 빼고 한 게 알고리즘 세 문제를 풀기 뿐이라니 이게 말이 됨? 사실 난 뇌 대신 회로 몇 개 정도 포함된 고철 덩어리를 머릿속에 들고 다니는 거 아닐까? 더 열심히 하도록 하자.
