안녕하세요 바킹독님 실전알고리즘을 보면서 공부중인데 연습문제라고 말씀하시는게 종종 있는데 연습문제가 설명해주시면서 푼 문제가 연습문제인가요? 아니면 따로 연습문제를 체크해두신게 있는지 궁금합니다.

안녕하세요 바킹독님 다름이 아니라 코딩테스트를 준비하면서 문제 난이도가 올라갈수록(백준 골드, 프로그래머스 Level3 문제) 혼자 해결하는 문제는 적어지고 계속 풀이를 봐서 해결하게 되더라구요.. 지금은 거의 남이 작성한 풀이를 계속 반복하면서 외우다시피 공부하고 있는데 이게 실력 향상에 도움이 되고 있는게 맞을까요...?

바킹독님 안녕하세요.
혹시 백준 2758번 문제 코드를 봐주실수 있나요..?
어떻게 해야 시간초과를 줄일 수 있을 지 감이 잘 안 옵니다.

http://boj.kr/c828aaa3f0924d3d928a1afa82e94962

어디가 문제일까요? ㅠㅠ

안녕하세요 바킹독님. 우선 무료로 좋은 강의 찍어주셔서 감사합니다 :)
BFS 문제 중 유기농 배추 https://www.acmicpc.net/problem/1012 에서 궁금한 게 있습니다.

일단 정답은 맞혔습니다.

k번 반복하는 과정에서 board(배추밭), vis(방문)를 초기화 할 때 애를 먹었는데,
왜 board와 vis를 전역으로만 선언해야 하는 건가요?.

초기에 가장 밖의 반복문 for(int w = 0 ; w < t; w++) 안에다가 선언, 초기화를 해줬었는데 이상한 값이 나오더라구요.. 그래서 memset으로 풀었네요 ㅜ


p.s) 혹시 정리해주신 실전 알고리즘 문제집, 바킹독님의 답안도 공개되어 있나요??


#include<iostream>
#include<queue>
#include<string.h> // for memset
#define X first
#define Y second
using namespace std;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
int t, m, n, k, a, b;
int board[52][52];
bool vis[52][52];
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
queue<pair<int, int>> Q;
cin >> t;
for (int w = 0; w < t; w++)
{
memset(board, 0, sizeof(board));
memset(vis, 0, sizeof(vis));
int mx = 0;
cin >> n >> m >> k;
for (int i = 0; i < k; i++)
{
cin >> a >> b;
board[a][b] = 1;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if (board[i][j] == 0 || vis[i][j] == 1) continue;
Q.push({ i, j });
vis[i][j] = 1;
mx++;
while (!Q.empty())
{
pair<int, int> cur = Q.front(); Q.pop();
for (int nr = 0; nr < 4; nr++)
{
int nx = cur.X + dx[nr];
int ny = cur.Y + dy[nr];
if (nx < 0 || ny < 0 || nx >= n || ny >= m || vis[nx][ny] == 1 || board[nx][ny] == 0) continue;
Q.push({ nx,ny });
vis[nx][ny] = 1;
}
}
}
}
cout << mx << endl;
}
}

안녕하세요 바킹독님!
백준 3151번을 풀다가 막히는 부분이 있어서 질문을 올립니다..
시간을 줄일 수 있는 방법이 생각나지 않습니다. 코드 좀 봐주실수 있나요..? ㅠㅠ
http://boj.kr/1a7f19e9671745eab5d0caca30f6a955

바킹독님 안녕하세요.
BOJ 2668번을 푸는데 이해가 안 가는 부분이 있어서 질문 올립니다...
이 코드가 왜 메모리초과가 되는지 잘 모르겠습니다.
다른 분들의 코드와 다를 게 없어보이는데 이해가 잘 안갑니다. 코드 한 번 봐주시면 감사하겠습니다.
http://boj.kr/adadd1676c3f44f6a47b9103ad9379c0

바킹독님,, 이번에는 BOJ 9466번 입니다 .. ㅜㅜ 큐 2개를 사용하였고 전부다 쓸모 없을 때에는 pop도 해준 것 같은데 메모리 초과가 왜 나오는지 모르겠습니당 .. 코드 한번만 봐주시면 너무 감사하겠습니다..!

#include <bits/stdc++.h>
using namespace std;

int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int T;
int n;
int num = 0;

cin >> T;


for (int i = 0; i < T; i++) {
int board[100002];
queue<int> Q;
stack<int> idx;
int *visited;

cin >> n;

fill(board, board + 100002, 0);
visited = new int[n];

for (int j = 0; j < n; j++) {
cin >> board[j];
}
for (int j = 0; j < n; j++) {
visited[j] = -1;
if (board[j] <= 0) continue;
Q.push(board[j]-1);
int cur = Q.front(); Q.pop(); // 현재 애가 가르키는 것
//if (board[cur] <= 0) board[]
int nxt = board[cur] - 1; // 다음 애가 가르키는 것
if (nxt == cur) {
board[j] = -1;
board[nxt] = -2;
continue;
}
if (nxt <= 0) {
board[j] = -1;
continue;
}
Q.push(board[nxt]-1);
idx.push(j);
idx.push(cur);
idx.push(nxt);
visited[cur] = -1;
visited[nxt] = -1;
while (!Q.empty()) {
int tmp = Q.front(); Q.pop();

if (tmp == idx.top()) {
while (!idx.empty()) {
board[idx.top()] = -2;
idx.pop();
}
break;
}
if (tmp == j) {
while (!idx.empty()) {
board[idx.top()] = -2;
idx.pop();
}
break;
}
if (board[tmp] <= 0) {
while (!idx.empty()) {
board[idx.top()] = -1;
idx.pop();
}
break;
}
if (visited[tmp] == -1) {
while (idx.top() != tmp) {
board[idx.top()] = -2;
idx.pop();
}
board[idx.top()] = -2;
idx.pop();
while (!idx.empty()) {
board[idx.top()] = -1;
idx.pop();
}
break;
}
visited[tmp] = -1;
idx.push(tmp);
Q.push(board[tmp]-1);
}
}
for (int i = 0; i < n; i++) if (board[i] == -1) num++;
cout << num << "\n";
num = 0;
delete[] visited;
}

return 0;
}

바킹독님 안녕하세요! 강의 잘 보고있습니다. 다름 아니라 BOJ4889 문제를 제출하니깐 자꾸 틀렸습니다가 나오는데 어디가 잘못됐는지 모르겠어서 고민끝에 질문드립니다.
-----------------------------------------------------------
#include <bits/stdc++.h>
using namespace std;

int main(){
int number = 1;
while(1){
string sent;
cin >> sent;
int cnt=0;
stack<char> s;

if(sent[0]=='-'){
break;
}

for(int i=0; i<sent.length(); i++){
if(s.empty() && sent[i] == '}'){
cnt++;
sent[i]='{';
s.push(sent[i]);
}
else if(!s.empty() && sent[i] == '}'){
s.pop();
}
else{
s.push(sent[i]);
}
}
cnt = cnt + s.size()/2;
cout << number<<". " << cnt;
number++;
}
}

바킹독님 안녕하세요! 알고리즘 강의 잘 듣고 있습니다.. 다름이 아니라 BFS 강의를 들으며 연습문제 BOJ 4179 불! 문제를 푸는 중이었는데요, 자꾸 메모리초과가 나와서 이유를 당최 모르겠어서 질문 드립니다.. 2차원 배열 1개만 사용하였는데 무엇이 문제일까요..? ㅜㅜ

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second // pair에서 first, second를 줄여서 쓰기 위해서 사용
char board[1000][1000];// 1이 파란 칸, 0이 빨간 칸에 대응
//bool vis[502][502]; // 해당 칸을 방문했는지 여부를 저장
int n, m;
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 }; // 상하좌우 네 방향을 의미

int dist = 0;
int cnt = -1;
int choice = 0; // 1 = 'J', 2 = 'F'
void BFS(queue<pair<int, int>>& Q) {
for (int i = 0; i < n; i++) {
for(int j = 0; j < m; j++){
if(board[i][j] == 'J' || board[i][j] == 'F') Q.push({ i, j });
}
}
while (!Q.empty()) {
pair<int, int> cur = Q.front(); Q.pop();
//cout << '(' << cur.X << ", " << cur.Y << ") -> ";
for (int dir = 0; dir < 4; dir++) {
choice = 0;
int nx = cur.X + dx[dir];
int ny = cur.Y + dy[dir];
if (board[cur.X][cur.Y] == 'J') { // J가 가장자리에 도착하면 성공
choice = 1;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
cnt = 1;
break;
}
if (board[nx][ny] == '#' || board[nx][ny] == 'F') continue;
}
else if (board[cur.X][cur.Y] == 'F') {
choice = 2;
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (board[nx][ny] == '#' || board[nx][ny] == 'F') continue;
}
if (choice == 1) {
board[nx][ny] = 'J';
}
else if (choice == 2) {
board[nx][ny] = 'F';
}
Q.push({ nx,ny });
}
if (board[cur.X][cur.Y] == 'J') {
dist++;
board[cur.X][cur.Y] == '.';
}
if (cnt == 1) break;
}
if (cnt == 1) {
cout << dist;
}
else cout << "IMPOSSIBLE";
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
queue<pair<int, int>> Q;

cin >> n >> m;

for (int i = 0; i < n; i++) fill(board[i], board[i] + m, '#');
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> board[i][j];
}
}

BFS(Q);

return 0;
}