GUESTBOOK
방명록을 남겨 보세요!
  • http://colorscripter.com/s/IErxAXY
  • 태우
    http://colorscripter.com/s/8YU6Msw
  • 김성수
    안녕하세요 바킹독님! 저 유튜브에 코드 링크를 계속 남겼는데 유튜브에서 삭제되는거같아서 방명록에 남깁니다!!
    항상 좋은 강의 감사합니다~

    http://colorscripter.com/s/AdI07tA
    • 지금 코드에서 nx가 이전에 등장한 적이 있음에도 불구하고 큐에 계속 넣고 있기 때문에 런타임에러가 발생하는거고, 큐에는 반드시 거리 순으로 저장된다는 BFS의 성질을 이용하면 39번째 줄에서 arr[nx] > arr[cur]+1인 상황은 절대 있을 수 없고, 39번째 줄(즉 nx가 이전에 등장한 경우)을 continue로 수정한 후 제출하면 통과됩니다.

      숨바꼭질 문제와 지금 작성하신 코드를 다시 비교해보시면 어떤 점이 잘못됐는지 알 수 있을 것 같습니다.

      (정답코드) http://boj.kr/034ea79d3ee749239bbcc7f5e6c3100d

    • 큐에는 반드시 거리순으로 저장되는 BFS의 성질을 제가 생각 못하고 있었네요 ㅠㅠ 드디어 문제가 해결 됐어요! 정말 감사드립니다!!!
  • 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