GUESTBOOK
방명록을 남겨 보세요!
  • DEVELOPER
    안녕하세요 바킹독님 실전알고리즘을 보면서 공부중인데 연습문제라고 말씀하시는게 종종 있는데 연습문제가 설명해주시면서 푼 문제가 연습문제인가요? 아니면 따로 연습문제를 체크해두신게 있는지 궁금합니다.
  • 멘붕왔다
    안녕하세요 바킹독님 다름이 아니라 코딩테스트를 준비하면서 문제 난이도가 올라갈수록(백준 골드, 프로그래머스 Level3 문제) 혼자 해결하는 문제는 적어지고 계속 풀이를 봐서 해결하게 되더라구요.. 지금은 거의 남이 작성한 풀이를 계속 반복하면서 외우다시피 공부하고 있는데 이게 실력 향상에 도움이 되고 있는게 맞을까요...?
    • 막히면 풀이를 보는게 나쁜건 아니지만 계속 풀이를 참조해야하면 실력에 비해(그 실력이 구현력 문제일수도 있고 배경지식 문제일수도 있고..) 높은 난이도의 문제를 붙잡고있는게 아닌가 싶어요.

      적어도 70~80%의 문제는 내 힘으로 풀이를 떠올리고 코딩을 할 수 있는(물론 다 짜고나서 틀릴 수는 있지만) 수준에서 공부를 하는게 좋아보여요.
  • dp
    바킹독님 안녕하세요.
    혹시 백준 2758번 문제 코드를 봐주실수 있나요..?
    어떻게 해야 시간초과를 줄일 수 있을 지 감이 잘 안 옵니다.

    http://boj.kr/c828aaa3f0924d3d928a1afa82e94962

    어디가 문제일까요? ㅠㅠ
    • 테케를 직접 뜯어보지는 않았는데 T가 굉장히 큰 경우가 있는 것 같아요.

      지금 dp식이 제가 이해한게 맞다면

      d[i][j] = 1 to m의 수 (n+1-i)개를 써서 만든 수열의 개수, 단 마지막 수는 j이다

      인 것 같은데, 어떻게 잘 바꿔서(거의 비슷한 점화식을 얻을 수 있어요.)

      d[i][j] = 1 to j의 수 i개를 써서 만든 수열의 개수로 정의를 하고 O(10 * 2000)에 d를 전처리로 다 채운 후에 각 질문에 대해서는 O(1)에 답하면 통과할 수 있어요.
  • 비밀댓글입니다
  • 안녕하세요 바킹독님. 우선 무료로 좋은 강의 찍어주셔서 감사합니다 :)
    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;
    }
    }
    • 초기화나 선언을 매번 for문 안에서 해도 상관없습니다.

      https://www.acmicpc.net/source/27877106

      문제집으로 제공된 문제들에 대해서 일부 코드는 블로그에 검색해보면 있긴 할텐데 좀 많이 옛날에 푼 문제들이라 코드가 예쁘지 않아요.

      그렇다고 또 다 새로 짜기엔 너무 일이 많아서 보류중입니다ㅠ
    • 아.. 전역이 아니라서 vis[52][52]={} 처럼 해줘야 한다는 것을 깜빡해서 안됐나보네요... ㅜㅜ 감사합니다 ㅎㅎ!
  • 어렵다
    안녕하세요 바킹독님!
    백준 3151번을 풀다가 막히는 부분이 있어서 질문을 올립니다..
    시간을 줄일 수 있는 방법이 생각나지 않습니다. 코드 좀 봐주실수 있나요..? ㅠㅠ
    http://boj.kr/1a7f19e9671745eab5d0caca30f6a955
    • 일단 이 문제는 O(N^2)으로 통과될 것 같고,

      투포인터로 접근을 거의 잘 하셨는데 29 to 32 line의 로직이 이상해요. 저것 때문에 아래와 같은 데이터에서는 이 코드가 O(N^3)에 동작해요.

      -1 -1 -1 -1 -1 -1 ... -1 0 0 0 0 ... 0 1 1 1 ... 1

      제가 풀어본 문제가 아니어서 확신은 못하지만 mx_idx를 O(1)에 찾는 방법이 있으니 그렇게 고치고 나면 아마 맞을 것 같아요.
    • 바킹독님 정말 감사합니다..
      lower_bound 사용해서 AC 받았습니다.
      근데 혹시 바킹독님이 말한 O(1)에 찾는 방법도 lower_bound가 맞나요??
    • 제가 생각한 방법은 일단 정렬한 후에 수의 범위가 -10000 to 10000이니

      "occur[i] : i-10000이 등장한 최초의 위치"라는 배열을 만든 후에 값을 잘 채워서 O(1)에 계산하는거였고 lower_bound면 O(lgN)이긴 한데 아무튼 축하드립니다ㅎㅎ 다른 사람 코드도 보시면 도움 될 것 같아요.
    • 오오..참신하네요!! 나중에 이 방식으로도 구현해보겠습니다.
  • 안녕하세요
    바킹독님 안녕하세요.
    BOJ 2668번을 푸는데 이해가 안 가는 부분이 있어서 질문 올립니다...
    이 코드가 왜 메모리초과가 되는지 잘 모르겠습니다.
    다른 분들의 코드와 다를 게 없어보이는데 이해가 잘 안갑니다. 코드 한 번 봐주시면 감사하겠습니다.
    http://boj.kr/adadd1676c3f44f6a47b9103ad9379c0
  • black skirt
    바킹독님,, 이번에는 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;
    }
    • 로직을 잘 못따라가겠습니다..

      1. 1-indexed를 0-indexed로 바꾸려다가 삐끗한게 있지는 않는지 모르겠네요.

      2. stack idx의 역할이 잘 이해가 안갑니다. 사실 지금 어떤 알고리즘으로 문제를 해결하려고 한 것인지 자체가 감이 잘 안와서 주석이랑 코드의 로직을 상세하게 남겨주시면 다시 확인하도록 하겠습니다.
  • jaeyook98
    바킹독님 안녕하세요! 강의 잘 보고있습니다. 다름 아니라 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++;
    }
    }
  • black skirt
    바킹독님 안녕하세요! 알고리즘 강의 잘 듣고 있습니다.. 다름이 아니라 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;
    }
    • 저도 검정치마 되게 좋아하는데 반갑습니다ㅋㅋ

      1.
      BFS에서 런타임에러/메모리초과가 뜨는건 대부분의 경우 큐에 원소가 계속 들어가서 생기는 문제이고 실제로 코드를 보면

      3 4
      ####
      #J.#
      ####

      이럴 때 프로그램이 종료되지 않고 큐에 (1, 1), (1, 2)가 계속 쌓여요.

      2.
      두 번째 문제는 강의 내에서도 설명했지만 이 문제에서는 불을 먼저 진행시킨 후 지훈이를 움직여야 하는데 맨 처음 큐에 불과 지훈이가 섞여있다보니 불을 먼저 진행시킨 후 지훈이를 움직인다는 보장이 없어요. 이 문제를 나름대로 해결하기 위해서 코드안에서 board[cur.X][cur.Y] == 'F'일 땐 board[nx][ny] == 'J'여도 덮어버리도록 한 것이 아닌가 싶긴한데

      4 4
      ####
      #FJ#
      #..#
      #..#

      이런 케이스를 생각해보면 또 문제가 되기 때문에 굳이 큐를 1개로 하고 싶다면 맨 처음 큐 안에 불이 먼저 다 들어가고 그 다음 지훈이 좌표를 넣게끔 코드가 바뀌어야 해요.

      3.
      dist를 계산하는 방식이 잘못됐어요.
      10 10
      ..........
      ..........
      ..........
      ..........
      ....J.....
      ..........
      ..........
      ..........
      ..........
      ..........

      이거 돌려보세요.
    • 와 검정치마 좋아하신다니 뭔가 강의 듣는데에 더 열정(?)이 생기네요 ㅋㅋㅋㅋ!!
      바킹독님 해설 너무 잘 들었고 이해했습니다 ㅠㅠㅠ
      메모리 초과라는 오류가 처음 나와보기도 했고 구글링 해봐도 제 코드에서 말해주는 사람이 없으니 막막했는데 바킹독님의 친절하고 꼼꼼한 설명덕에 무엇이 문제인지 확실히 알게되었습니다..! 언제나 좋은 강의 너무 감사하고 빡공하도록 하겠습니당 ㅎㅎ
    • 틀렸을 때 뭐가 잘못됐는지 찾기가 힘든게 가장 큰 벽이죠ㅠㅠ 앞으로도 모르는거 있으면 편하게 질문주시고 화이팅하세용