촌수계산(백준 2644) 질문

AI AI 님 안녕하세요 🙂이 경우에는 가장 작은 노드부터 시작하지 않아도 동일한 답이 나올 수 있을 것 같아요!다만 작은 노드부터 큰 노드까지 방문하는 게 직관적이기도 하고 코드 구현도 단순해서 이렇게 많이 구현하는 것 같습니다 🙂 현재는 두 노드 간의 거리를 계산하는 문제와 같으니 동작에 차이는 없을 것 같습니다!

다른 주제 강의

안녕하세요 AI AI님! 죄송스럽게도 아직 구체적인 일정이 나온게 없습니다 ㅠ 조금씩 추가 준비는 하고 있지만, 계획에 없던 대학원 생활을 하게 되고, 생각보다 널널하지 않다는 걸 와보고서야 알게 되었네요 ㅠ. 그래도 아예 포기한 것은 아니고 최대한 틈 내서 준비하고 있습니다..!! 얼른 더 좋은 강의로 돌아오겠습니다!

최근에 올린 질문, 코드블럭으로 공유드립니다!

예현님 안녕하세요! 제 생각에는 출력해야 되는 내용을 잘못 이해하셔서 문제가 발생하는 것 같은데, 공교롭게도 예시에서는 그 차이가 뚜렷하게 보이지 않아서 헷갈리는 것 같습니다.우선 문제에서 요구하는 건 '각 숫자가 출력된 순서' 이기 때문에, 우리가 배열에 담아야 하는 값은 '순서'이고, 담아야 할 배열의 위치(index)가 숫자가 되는 겁니다. 그래서 결과적으로 answer[2] = 4라고 한다면 2번 노드는 4번째 방문됐다 라는 것이 문제에서 요구한 것이고, 그래서 정답이 위에 말씀해주신 제 코드처럼 나오게 됩니다!예현님께서 작성하신 코드는 반대로 '각 순서에 출력된 숫자'를 구현하셨기 때문에 배열에 담기는 값이 '숫자(idx)'이고, 위치가 순서가 됩니다. 한 가지 예시를 들자면, dfs 동작 상 노드 방문 순서가 다음 같다고 가정할게요: 1 -> 5 -> 2 -> 3 -> 4. 그러면 예현님 답은 이 순서 그대로 출력을 하겠지만, 문제에서 원하는 답은 1 3 4 5 2 가 될겁니다.왜냐하면 1은 첫번째 방문했고, 2는 3번째 방분, 3은 4번째 방문, 이런 식이기 때문입니다! 결론은 코드는 문제가 없어보여서 잘 나오는데, 다만 문제에서 의도한 정답을 잘못 이해하셔서 그런 것 같습니다! 문제 다시 한번 확인해보시고 혹시 추가로 궁금한 점 있으면 말씀해주세요!!

질문이 있습니다. dfs 메서드에 order를 이렇게 구현하면 안되는 이유가 무엇인가요?

안녕하세요 예현님 🙂 코드를 스크린샷 말고 코드 블럭으로 공유 부탁드립니다!공유해주시는 대로 확인해보겠습니다~

Max로 초기화하는 이유

안녕하세요 color.park님 🙂 우선 결론부터 말씀 드리자면 n+1, m+1로 하셔도 됩니다! 이렇게 작성하는 게 더 최적화된 답변일 수 있어서 손에 익으신 다음에는 이렇게 작성하는 것이 더 좋을 것 같습니다.다만 제가 MAX로 초기화 하는 이유는 1) 코드를 단순하게 작성해서 공부하실 때 수월하시기 위해서와 2) 혹시라도 예상하지 못한 불량을 방지하기 위해서입니다! n+1, m+1로 당연히 될 줄 알지만 꼭 하나씩 더 필요하거나, 예상과 달라지는 경우들이 생기고, 시험장에서 이런 경우가 발생하면 멘탈 관리가 어려워서 떨어지시는 분들이 많더라고요. 나중에 알고보니 그냥 max로 초기화했으면 아무런 문제가 되지 없어서 한번 더 멘탈이 나가곤 하셔서, 메모리를 살짝 낭비하는 대신 문제를 안전하고 빠르게 맞추는 것이 나을 것 같아 이렇게 추천드립니다! 그렇지만 굳이 필요없다고 판단되시면 최적화 하셔도 됩니다 :)

백준 24479 문제 제출 결과 "틀렸습니다" 라고만 나와서 어떤 부분이 틀렸는지 잘 모르겠어요 피드백 부탁드립니다

AI 인턴보다 한 발 늦었지만 두 가지 수정하면 될 것 같습니다! 엣지 읽기 루프:엣지를 읽는 루프가 1부터 N + 1까지 반복되는데, M개의 엣지를 읽어야 합니다. 현재 구현은 N이 M보다 크면 필요한 것보다 더 많은 엣지를 읽을 수 있습니다!방문 순서 초기화:방문 순서(visitOrder)가 시작 노드 R로 초기화됩니다. 방문 순서는 1부터 시작하되, 첫 노드 번호를 R로 초기화 하도록 수정하면 정답이 될 것 같습니다 🙂

graph 만들때 boolean[][] 으로 만드는 경우랑 int[][] 나 ArrayList<Integer>[] 로 만드는 기준이 어떻게 되나요?

안녕하세요 🙂 답변을 드렸다고 깜빡하고 늦게 댓글 남깁니다 죄송합니다 ㅠ 질문 주신 내용을 두 가지로 나눠보면 자료형을 boolean으로 할지, int로 할지 구분할 기준이 필요하고,둘째는 이중 배열로 할지, ArrayList를 사용할지 결정할 기준이 필요합니다! boolean vs int: boolean을 사용하는 것이 일반적입니다. 왜냐하면 우리에게 필요한 정보는 두 node 간 연결이 되어있는지 아닌지 알고 싶은 것이라 True/False로 구분만 하면 충분히 정보를 담을 수 있기 때문에 boolean이면 됩니다. 그런데 특정 문제에서는 이를 조금 더 복잡하게 출제해서 '연결되어 있냐/없냐'가 아니라 특정 숫자 값을 넣어서 '해당 칸에서 이동할 때 몇칸씩 이동할지' 등 일반 정보보다 추가되는 정보가 있습니다. 이런 경우는 단순 True/False로 표현할 수 없기 때문에 int로 구분을 해줄 필요가 있습니다. 정리하자면 True/False로만 표현이 가능하면 boolean을 쓰고, 그 외에 추가 정보가 필요하다면 int로 담아줍니다. 그리고 헷갈리신다면 매번 int를 쓰시고, boolean이 필요한 경우에는 0/1로 사용하셔도 됩니다![][] vs ArrayList: 이 경우는 정말 선택인데, [][]는 메모리 낭비가 심한 대신 성능이 빠르고, ArrayList는 성능은 상대적으로 느리지만 메모리가 훨씬 효율적인 장점이 있습니다. 그래서 Node 개수가 1000개 이하일 때는 [][]를 사용해도 메모리가 넉넉하기 때문에 [][]를 써서 빠른 성능을 낼 수 있고, 1000개를 넘어가면 애초에 [][]를 만들기 어렵기 때문에 ArrayList를 사용해야만 합니다. 이 경우에도 굳이 선택하거나 고민하기 싫으시다면 ArrayList를 매번 쓰셔도 동작에 문제가 없을 거에요!

graph

네 맞습니다! 방문한 곳을 재방문하지 않도록 방지하는 visited와, 연결 정보를 가진 graph는 거의 매번 필요하다고 생각하시면 됩니다 🙂 MAX를 두는 건 문제의 최대 개수를 관리하기 위해서 정의합니다. 코드를 최대한 공식처럼 사용하실 수 있도록 MAX라는 변수를 두고, MAX 변수를 문제에서 제공하는 N + 10 으로 설정하시면 되도록 정의했습니다! 그래서 원하시다면 이 값은 필수가 아니라 원하는 값으로 바꾸셔도 됩니다.

재귀 함수 Depth

SJ님 안녕하세요! 🙂 표에서 오른쪽으로 간다는 것은 재귀함수가 새로 호출 됐다는 의미로, 한 단계 더 깊이 들어간 것을 의미하고,해당 칼럼에서 숫자가 순차적으로 나오는 건, 그 단계(그 함수 호출, 그 재귀 함수) 내에서 여러 숫자들을 방문하는 것을 의미합니다!그래서 칼럼 2 마지막에 5(무시)를 적은 건, 1번에서 다음 재귀함수를 호출할 때 2번을 호출하고 나서 한바탕 다 검사하고 돌아오면, 아직 N번까지 확인하지 않았기 때문에 나머지를 확인해줘야 하고, 그 중 5번이 있어서 5번을 확인해보지만, 이미 방문했기 때문에 무시하고 넘어간다는 것을 이렇게 표기해봤습니다.정리하자면, 꼭 제가 제안 드린 방식대로 정리를 할 필요는 없지만, 재귀함수가 다음 재귀함수를 또 호출할 때 어떤 숫자들을 순차적으로 확인하는지, 그리고 그때마다 다시 재귀함수가 호출되는지 아니면 무시되고 다음 숫자를 확인하는지를 완벽하게 이해할 수 있어야 합니다. 그래서 그림이나 표로 정리해보는 걸 추천드립니다!

백준 DFS

SJ님 안녕하세요!저는 프로그래머스, 백준, 엘리스 다 많이 사용하고 있고 다 좋은데, 백준이 알고리즘 분류별로 문제를 집중적으로 풀 수 있어서 알고리즘을 하나씩 도장깨기(?) 할 수 있어서 좋고요, 많은 분들이 백준을 사용하신다고 생각해서 백준으로 진행하고 있습니다!SJ님은 주로 다른 플랫폼을 활용하시나요? 자주 사용하시는 플랫폼이나 원하시는 플랫폼이 있다면 말씀해주세요!! 참고해서 다음 강의 제작 때 제작이 가능할지 검토해보겠습니다~