-
안녕하세요. 알고리즘 풀이 찾다가 방문하게 되었는데
블로그 설명도 잘 하시지만 코드를 너무 깔끔하게 짜셔서 깊이 감명받고 갑니다..
존경합니다.. 갓갓 .. 갓 블로거..
-
ㅋㅋㅋ 감사합니다
-
-
안녕하세요! 요즘 알고리즘 공부를 하면서 바킹독님 영상을 보고있는데 혹시 제 블로그에 알고리즘 강의 내용을 정리하려고 하는데 작성해도 될까요 ?? ㅠㅠ
-
넵 괜찮아요
-
-
boj 14897번에서 Mo's+압축으로 시간초과가 나길래 O3 Ofast 등등 추하게 비벼서 턱걸이로 4908ms 성공했는데 원래 어떻게 푸는 문제인지 알려주실 수 있으신가요?
http://boj.kr/d20748c8acb54b5bb12465f489dfd954-
저도 되게 옛날에 푼거긴한데 코드 보니까 Mo's 썼네요
-
아 구글에 검색해보니 PST나 Merge Sort Tree로 푸는 방법이 있다고 하네요. 감사합니다!
-
-
바킹독님 안녕하세요! 제가 2021 하반기 삼성공채 코딩테스트 문제를 풀다가 궁금한 점이 생겨서 여쭈어보려고 댓글 남깁니다 ㅜㅜ
BOJ 23288번 문제 주사위 굴리기 2 인데요, 여기서 다른건 바로바로 잘 해결을 했는데 주사위를 굴리는 방향마다 바뀌는 주사위 전개도를 구하는데에 있어서 조금 어려움이 있었어요. 다행히 잘 해결을 했는데 제 코드보다 더 좋은 방법이 있을까 궁금해서요. 사실 저는 주사위를 굴리는 방향마다 바뀌는 전개도를 하드코딩(?)해서 구했는데 (밑에 코드의 주석 //1. 주사위 굴리기 부분을 참고해주세요!) 혹시 주사위를 굴릴 때마다 바뀌는 주사위의 전개도의 기본틀(?) 약간 BFS의 기본 틀같은 느낌으로 그러한 코드가 있을까 궁금합니다! 맨 밑부분에 전체 코드도 남겨놓도록 하겠습니다!
// 1. 주사위 굴리기
void rollDice() {
int nx = m.X + dx[dir];
int ny = m.Y + dy[dir];
if (nx < 0) dir = 0;
if (nx >= N) dir = 2;
if (ny < 0) dir = 1;
if (ny >= M) dir = 3;
int tmp[4];
m.X += dx[dir];
m.Y += dy[dir];
switch (dir) {
case 0:
tmp[0] = dice[0];
tmp[1] = dice[4];
tmp[2] = dice[5];
tmp[3] = dice[2];
dice[4] = tmp[0];
dice[5] = tmp[1];
dice[2] = tmp[2];
dice[0] = tmp[3];
break;
case 1:
tmp[0] = dice[0];
tmp[1] = dice[1];
tmp[2] = dice[5];
tmp[3] = dice[3];
dice[1] = tmp[0];
dice[5] = tmp[1];
dice[3] = tmp[2];
dice[0] = tmp[3];
break;
case 2:
tmp[0] = dice[0];
tmp[1] = dice[2];
tmp[2] = dice[5];
tmp[3] = dice[4];
dice[2] = tmp[0];
dice[5] = tmp[1];
dice[4] = tmp[2];
dice[0] = tmp[3];
break;
case 3 :
tmp[0] = dice[0];
tmp[1] = dice[3];
tmp[2] = dice[5];
tmp[3] = dice[1];
dice[3] = tmp[0];
dice[5] = tmp[1];
dice[1] = tmp[2];
dice[0] = tmp[3];
break;
default :
break;
}
sum += BFS({ m.X, m.Y });
if (dice[5] > board[m.X][m.Y]) {
dir -= 1;
if (dir < 0) dir = 3;
}
else if (dice[5] < board[m.X][m.Y]) {
dir = (dir + 1) % 4;
}
}
------- 전체 코드 -------
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define X first
#define Y second
using namespace std;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int N, M, K;
int board[22][22];
bool tmp[22][22];
int dice[6] = { 1, 3, 2, 4, 5, 6 };
// dir = 0 (남쪽), dir = 1 (동쪽), dir = 2 (북쪽), dir = 3 (서쪽)
int dir = 1;
// 현재 위치
pair<int, int> m = { 0, 0 };
// 총점
int sum = 0;
// 2. 닿은 면과 같은 점수 부분의 면적 구하기(BFS)
int BFS(pair<int, int> c) {
int cnt = 0;
int pre = board[c.X][c.Y];
queue<pair<int, int>> Q;
Q.push({ c.X, c.Y });
tmp[c.X][c.Y] = true;
while (!Q.empty()) {
auto cur = Q.front(); Q.pop();
cnt++;
for (int dir = 0; dir < 4; dir++) {
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
// 범위 밖일 때
if (nx < 0 || nx >= N || ny < 0 || ny >= M) continue;
// 이미 방문했으면 패스
if (tmp[nx][ny] == true) continue;
// 현재 수와 다음 수가 같지 않을 때
if (board[nx][ny] != board[cur.X][cur.Y]) continue;
tmp[nx][ny] = true;
Q.push({ nx, ny });
}
}
return pre * cnt;
}
// 1. 주사위 굴리기
void rollDice() {
int nx = m.X + dx[dir];
int ny = m.Y + dy[dir];
if (nx < 0) dir = 0;
if (nx >= N) dir = 2;
if (ny < 0) dir = 1;
if (ny >= M) dir = 3;
int tmp[4];
m.X += dx[dir];
m.Y += dy[dir];
switch (dir) {
case 0:
tmp[0] = dice[0];
tmp[1] = dice[4];
tmp[2] = dice[5];
tmp[3] = dice[2];
dice[4] = tmp[0];
dice[5] = tmp[1];
dice[2] = tmp[2];
dice[0] = tmp[3];
break;
case 1:
tmp[0] = dice[0];
tmp[1] = dice[1];
tmp[2] = dice[5];
tmp[3] = dice[3];
dice[1] = tmp[0];
dice[5] = tmp[1];
dice[3] = tmp[2];
dice[0] = tmp[3];
break;
case 2:
tmp[0] = dice[0];
tmp[1] = dice[2];
tmp[2] = dice[5];
tmp[3] = dice[4];
dice[2] = tmp[0];
dice[5] = tmp[1];
dice[4] = tmp[2];
dice[0] = tmp[3];
break;
case 3 :
tmp[0] = dice[0];
tmp[1] = dice[3];
tmp[2] = dice[5];
tmp[3] = dice[1];
dice[3] = tmp[0];
dice[5] = tmp[1];
dice[1] = tmp[2];
dice[0] = tmp[3];
break;
default :
break;
}
sum += BFS({ m.X, m.Y });
if (dice[5] > board[m.X][m.Y]) {
dir -= 1;
if (dir < 0) dir = 3;
}
else if (dice[5] < board[m.X][m.Y]) {
dir = (dir + 1) % 4;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M >> K;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) cin >> board[i][j];
while (K--) {
for (int i = 0; i < N; i++) fill(tmp[i], tmp[i] + M, false);
rollDice();
}
cout << sum;
return 0;
}-
저도 마땅히 좋은 방법을 알고 있지는 않고, 다만 돌리는걸 인덱스 가지고 넣을 때 조금 예쁘게 넣으려고 하긴 해요
http://boj.kr/f4d1f744e8284036b39106a41f13ffe2 -
아 그리고 질문 답변 내용을 다른 분들도 참고할 수 있게 방명록보다는 해당 단원 게시글에 댓글로 남겨주시면 감사하겠습니다
-
-
바킹독 님, 혹시 바킹독 님을 직접 만나 뵐 수 있을까요?
-
오호,,, 대전 오실 일 있으면 ㄱㅊ습니다
-
-
바킹독님 덕분에 네이버 AI 부스트캠프 붙었습니다 :) 좋은 강의 항상 감사하며 취업까지 열심히 달리겠습니다! 감사합니다 !
-
적어도 코테는 줘팹시다^^77
-
-
코테의 ㅋ자도 몰랐는데 킹킹독님 덕분에 대기업 IT 계열사에 합격하게 됐습니다 ㅎㅎ 너무 감사드립니당 (주위에 많이 홍보중이에요 ㅎㅎ) 회사 다니면서도 꾸준히 킹킹독님 강의 들으면서 이직 준비하려고 합니다. 앞으로도 좋은 강의 잘 부탁드립니당 ㅎ.ㅎ
-
ㅋㅋㅋ 축하드립니다!! 연말 잘 보내세용
-
-
http://boj.kr/b35ccb6c8a8d46d0beabb579f4479b6a
-
안녕하세요 바킹독님
비트 연산을 이용한 알고리즘 풀이에 대해서도 익숙해지면 좋을까요?
같은 코드라도 비트 연산으로 푸는 풀이는 확연히 짧은것을 보고 이 부분에서도 공부를 해야하나 싶어서요
바킹독님 실전 알고리즘 강의를 보면 2의 제곱수를 표현하실 때 2<<size 이렇게 사용하시던데 그 외에도 공부를 해볼 필요가 있을까요?-
익숙해지면 좋긴한데 진짜 별거 없어서 따로 거창하게 공부를 한다기보다는 코드 찾아보다가 비트연산자가 나오면 무슨 의미인가 살펴보는 식으로 배우시면 될 것 같아요. 별개로 비트마스킹은 익혀두면 좋구요.
-
-
http://colorscripter.com/s/IErxAXY