230129 일
블로그 쓰는 건 생각보다 재밌는 일 같다. 왜 내 친구들이 꾸준히 썼는지 알 것 같기도.. 물론 주변에 벨로그 쓰는 친구가 없어서 그런가 외롭기도 하다. 난 관심이 필요한 타입이다.
외딴 섬 한 송이 꽃 같은 나... 후우..
^아직 마크다운 인용문 놀이에서 벗어나지 못한 뉴비의 모습입니다.
하여튼 매일 벨로그 쓰기라는 게 은근 기대되고 코딩도 더 재밌어지는 게, 꼭 농장에서 먹는 새참 같다. ..11am 대신 11pm에 먹는 새참
?? : 야야 저 놈 proprocrastinator라 새참도 밀려서 먹는댄다
오늘은 알고리즘 스터디 2일차를 진행했다.
주제는 brute force을 이용해 백준 알고리즘 문제 풀기! brute force는 말 그래도 '난폭한, 짐승같은' '힘이라는 건데, 어원을 읽어보자니 내가 광야클럽 멤버라도 된 기분이다.
야수같은 나를 느껴! next level! 제껴라제껴라제껴라~
brute force 알고리즘은 완전 탐색 알고리즘으로, 가능한 모든 경우의 수를 탐색하여 결과를 도출하는 문제해결 방식이다. 하지만 백준에서 주어진 시간 제한을 충족하는 알고리즘 코드를 짜려면 말그대로 짐승마냥 달려들어 마구잡이로 따져보는 건 불가능하고, 어떻게 탐색할지 잘 생각해내야 하는 거였다. 효율적인 방식을 찾다보니 백트래킹으로 가지치기도 하게 되고 하는 것이다.
1. 백준 9663번 N-Queen 문제
<문제> N-Queen 문제는 크기가 N x N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.
<입력>
첫째 줄에 N이 주어진다.(1<=N<=15)
<출력>
첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.
퀸은 모든 직선으로 제한 없이 이동할 수 있다. 따라서 가로, 세로, 대각선 모두 겹치지 않게 퀸을 놓아야한다. 사실 bruteforce 풀이는 간단하다. 퀸 N개를 순서대로 아무곳에나 놓아보며 답의 조건에 해당할 때에만 카운트를 하면 된다. 문제는 그걸 어떻게 구현할 것인가이다. 내가 선택한 방법은 다음과 같다.
0) 체스판의 세로줄을 m, 가로줄을 n이라 하고 각 칸을 좌표로 잡는다. (m, n)
1) 첫 번째 줄 퀸을 왼쪽부터 순서대로 놓아본다.
1-1) 두 번째 줄 퀸을 왼쪽부터 순서대로 놓아본다.
1-1-1) 만약 첫 번째 줄의 퀸과 m좌표가 같거나(세로줄로 만남), n좌표가 같거나(가로줄로 만남), m좌표끼리의 차와 n좌표끼리의 차가 같다면(대각선으로 만남) 성립하지 않으므로 1-1)로 돌아가 그 다음 칸으로 이동한다.
1-1-2) 만약 가능한 모든 칸을 검토했으나 성립하지 않으면 바로 이전의 말(두 번째 말인 경우 첫 번째 말)이 잘못 놓인 것이므로 1)로 돌아가 다음 칸에 놓는다.
1-1-3) 둘 다 아니라면 성립하므로 넘어가 세 번째 줄 퀸을 왼쪽부터 순서대로 놓아본다.
.
.
.
그리고 1-1), 1-1-1), 1-1-2)를 하나의 재귀함수로 호출하는 것이다. 문제는 이걸 1시간이나 풀었는데도 brute force 코드를 못 짠 내 자신.. 스터디에 있는 멋진 선배님들도 다행히 나와 비슷한 상황이셨지만 생각해보면 난 선배님들이 잘 푸시는 문제도 못 푸니까 딱히 다행도 아닌 것 같다. 난 못하는 게 맞으니까아앙으아앙ㄱ엉엉
하여튼 지금 블로그를 작성하는 시간은 21시 24분. 목표는 30분 이내로 다시 정리해서 코드를 완성하는 것이다. 파이팅!
과연 정화는 오늘 안에 코드를 짜서 블로그에 올릴 수 있을지..?
..다 풀었다! 근데 지금 10시 50분이다.미친 거 아냐?
내 코드 :
#include <iostream>
#include <vector>
using namespace std;
int coinclude[15];
int Result=0;
bool check(int r, int coarray[]) {
for (int i = 0;i < r;i++) {
if (coarray[i] == coarray[r]
|| (coarray[i] - coarray[r]) == (i - r)
|| (coarray[r] - coarray[i]) == (i - r)) {
return false;
}
}
return true;
}
void function(int r, int coarray[], int N) {
if (r == N) Result += 1;
else {
for (int i = 0;i < N;i++) {
coarray[r] = i;
if (check(r, coarray)) function(r + 1, coarray, N);
}
}
}
int main() {
int num;
cin >> num;
function(0, coinclude, num);
cout << Result;
}스터디에서 짜던 코드는 복잡했는데(위에서 말로 설명한 걸 그대로 다 코드에 구현해놨다.. 전형적인 뉴비 style~) 집에서 다시 침착하게 줄이고 줄여서 드디어 간단하게 써냈다. 아직 c++이 익숙하지 않아서 중간중간 인터넷에 있는 코드 슬쩍 쳐다봤는데 하여튼 맞긴 맞았음~ 암튼 맞음~
모든 경우의 수를 검토하되,
for (int i = 0;i < N;i++) {
coarray[r] = i;
if (check(r, coarray)) function(r + 1, coarray, N);
}만약 조건을 만족하지 않으면(대각선, 가로, 세로에서 만남)
bool check(int r, int coarray[]) {
for (int i = 0;i < r;i++) {
if (coarray[i] == coarray[r]
|| (coarray[i] - coarray[r]) == (i - r)
|| (coarray[r] - coarray[i]) == (i - r)) {
return false;
}
}
return true;
}false를 리턴하도록 하여 너무 오랜 시간이 걸리지 않는 brute force를 만들었다!! 오예!! 재귀함수 없으면 대체 어떻게 알고리즘 풀어? 모든 알고리즘의 구원.. 재귀함수.. 알러뷰
cf) 이건 사실 c++에서 절댓값 쓸 줄 몰라서 일일이 쓴 거다..ㅎ
|| (coarray[i] - coarray[r]) == (i - r)
|| (coarray[r] - coarray[i]) == (i - r)) 2. 백준 1018번 체스판 칠하기 문제
<문제>
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.
체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.
보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 8×8 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.
<입력>
첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. B는 검은색이며, W는 흰색이다.
<출력>
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.
문제가 길어서 처음 읽을 땐 애먹었는데, 결국 다음 그림들과 같이 주어지는 체스판 입력에서
어느 8x8을 잘라내야
"BWBWBWBW
BWBWBWBW
BWBWBWBW
BWBWBWBW
BWBWBWBW
BWBWBWBW
BWBWBWBW
BWBWBWBW"
혹은
"WBWBWBWB
WBWBWBWB
WBWBWBWB
WBWBWBWB
WBWBWBWB
WBWBWBWB
WBWBWBWB
WBWBWBWB"
로 바꾸기 위해 칠하는 횟수가 가장 적을 거냐는 것이다. 따라서 우리는
1) 입력에서 체스판과 가장 차이가 적을 8x8만큼의 영역을 찾아내고
2) 체스판과 똑같이 만들기 위해 칠해야하는 횟수를 구하면
되는 것이다.
나는 이걸 어떻게 풀어야 하는 것인지 감조차 오지 않는다.. 왜 나는 이 스터디에 들어와서.. c++로 고작 스택 하나 만드는 데에도 한두 시간씩 걸리는 멍청이가 대체 왜!!!! 하지만 일단 풀어낸다. 내가 아무리 스터디 깍두기라지만 무 형태는 갖춰야 쫓겨나지 않을 것 아닌가.. 생각해보세요 여러분 상에 양념이 맛 없어 보이는 깍두기를 차렸는데 알고보니 무조차 없었던 겁니다. 그럼 그건 더 이상 깍두기가 아니잖아요? 그럼 상에서 치우겠죠? 저도 최소한의 생존을 위해 노력 정도는 해야 한다는 것입니다. 비록 양념이.. 맛없어도.. 내 코드가 구려도..
내가 처음 생각해낸 방법은 체스판 입력을 한 줄씩 string으로 저장하고 각 string별로 검토하며 b와 w가 교차할 때마다 1, b와 b 혹은 w와 w가 붙어있을 때마다 0을 더해 점수가 가장 높은 string 8개 조합을 선택하는 것이다. 근데 그러면 가로줄 기준으로만 검토하게 되고 세로 줄을 판단할 길이 없어 실패한 아이디어나 다름이 없었다.
그래서 비슷한 방식으로 가되, 스트링 말고 2차원 배열로 만들어보기로 한다. 지금 시각은 11시 15분이므로 11시 50분까지 만드는 것을 목표로 한다. 왜냐하면 11시 50분까지는 와야 12시 전까지 오늘의 블로그를 올릴 수 있기 때문에...... 코딩농장 수금을 채우기 위해서,,
..솔직히 모르겠다. 오늘은 여기까지 하는 걸로 하자ㅎ
대신 스터디 1일차에 했었던 brute force도 올려본다
3. 백준 9095번 1, 2, 3 더하기
<문제>
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
<입력>
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
<출력>
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
내 코드:
#include <iostream>
using namespace std;
int function(int k) {
if (k == 1) { return 1; }
else if (k == 2) { return 2; }
else if (k == 3) { return 4; }
return function(k - 1) + function(k - 2) + function(k - 3);
}
int main() {
int num;
cin >> num;
for (int i = 0;i < num;i++) {
int input_num;
cin >> input_num;
cout << function(input_num) << "\n";
}
}4. 백준 2751번 수 정렬하기 2
그리고 이건 brute force는 아니지만 합병 정렬을 구현한 내 스스로가 그냥 자랑스러워서 올려봄
<문제>
N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.
<입력>
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.
<출력>
첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.
시간복잡도 O(nlogn)의 알고리즘으로 풀라고 내주셔서 합병 정렬로 풀었다. 나는 합병 정렬이 어떻게 이루어지는지 알고 있었어서 잘 안다고 생각했는데 막상 코드로 구현하려고 하니 어렵기도 하고, 오류도 나고, 백준 시간 제한 내로 안 풀리고.. 해서 너무 힘들었다 흑흑
내 코드 :
#include <iostream>
#include <string>
using namespace std;
void merge(int s[], int r[], int low, int mid, int high);
void merge_sort(int s[], int r[], int low, int high) {
if (low >= high) return;
else{
int mid = low + (high - low) / 2;
merge_sort(s, r, low, mid);
merge_sort(s, r, mid+1, high);
merge(s, r, low, mid, high);
}
}
void merge(int s[], int r[], int low, int mid, int high) {
int idx = low;
int j = mid + 1;
int l = low;
for (idx = low;idx <= high;) {
if (low > mid) { r[idx++] = s[j++]; }
else if (j > high) { r[idx++] = s[low++]; }
else if (s[low] <= s[j]) r[idx++] = s[low++];
else r[idx++] = s[j++];
}
for (int i = l;i <= high;i++) {
s[i] = r[i];
}
}
int input_array[1000001];
int emp_array[1000001];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int max_size;
cin >> max_size;
for (int i = 0;i < max_size;i++) {
cin >> input_array[i];
}
merge_sort(input_array, emp_array, 0, max_size-1);
for (int i = 0;i < max_size;i++) {
cout << input_array[i] << "\n";
}
}오늘 벨로그 끝!
