코딩테스트 문제 추천! (2023년 1월 3주차)

코딩테스트 문제를 추천해 드립니다! 이번 주는 구독자 분들이 질문 주신 문제들로 준비했습니다. 난이도나 유형의 차이는 있지만 둘 다 좋은 문제로 한번 풀어보시면 도움이 될겁니다. 이번 주 목요일과 토요일에 풀이가 올라갈 예정이니 그 전에 꼭 풀어보시면 좋겠습니다 :)
다트 게임 문제 : school.programmers.co.kr/lear...
냅색문제 : www.acmicpc.net/problem/1450
#백준 #다트게임 #냅색문제

[@gaebal]

다트 게임 문제 : school.programmers.co.kr/learn/courses/30/lessons/17682
냅색문제 : www.acmicpc.net/problem/1450

[@user-gt2it3ef2x]

우와 감사합니다 ㅠ-ㅠ
항상 열심히 올려주시고 풀어주시고 추천해주셔서 감사해요!!

[@gaebal]

감사합니다! 좋은 문제 추천해주셔서 이번 주도 잘 풀었습니다 :)

[@Re_Go]

드디어 프로그래머스! 감사합니다 ㅜㅜ 사실 이제 그레이드 0을 푸는 제입장에서는 따라가기 힘들겠지만 그래도 여지껏 설명해주신 것이 있으시니 기대가 커지는 것 같네요.
개발 본업도 힘드실텐데 문제 업로드 해주셔서 감사드립니다 :)

[@gaebal]

안녕하세요 re_go님, 항상 배려 깊은 댓글 감사합니다 ㅎㅎ 저도 최근에 생긴 Lv 0 문제들도 많이 풀어봤는데 좋은 문제들이 많이 있더라고요. 그것만 순서대로 풀어보셔도 초반에 잡기에는 아주 큰 도움이 될 것 같아요. 다만 프로그래머스는 알고리즘 분류별로 문제 보기가 어렵게 되어 있어서 풀이를 제작하는 입장에서는 백준을 더 선호하게 되더라고요. 그래도 중간 중간 프로그래머스 문제도 많이 풀어보도록 할게요!! 감사합니다 :)

[@_1_423]

선생님 덕분에 요즘 알고리즘 푸는게 재밌습니다

[@gaebal]

알고리즘 푸는 게 재밌으시다니, 제가 할 일을 다 한 것 같네요 ㅎㅎ 문제 풀이도 한번 재미 들리면 생각보다 시간도 잘 가고 흥미로워요. 남들이 잘 푸는 것 보면서 배우는 것도 재밌고, 말도 안되게 짧게 짠 분들을 보면 감탄이 나기도 하고 ㅋㅋ 재미 붙이셨다니 이제 앞으로 쭉 잘 공부하실 수 있겠네요!! 저도 지금 편집 중인데 더 힘내서 편집해야겠네요.

[@_1_423]

@@gaebal 매번 감사합니다. DFS와 BFS 공부하다 궁금한 점이 생겼습니다. 그래프 탐색에서 어떤 문제는 BFS, DFS 둘 다 풀리는 문제가 있는 반면 어떤 문제는 BFS로만 풀어야하고 DFS로 풀면 스택오버플로우가 발생하던데, 이 기준이 잡힐랑말랑 한데 혹시 정리 가능하실까요? (1. BFS, DFS 둘다 사용가능한 경우 2. BFS로만 풀어야 하는 경우 3. DFS로만 풀어야 하는 경우) 숨바꼭질 같은 경우 BFS로만 풀어야하고 DFS로 풀경우 메모리초과가 떠서요. 이런 기준을 명쾌하게 알고 싶습니다.

[@_1_423]

숨바꼭질은 백준 1697문제입니다. 이 기준을 몰라 처음에 DFS 풀었는데 시간 초과가 떠서 BFS로 풀었습니다. BFS, DFS 원리는 알겠는데 요즘은 메모리나 시간도 중요해서 사용 기준이 궁금합니다. 어떤 문제 유형에 BFS/ DFS를 각각 적용해야하는지 궁금합니다.

[@gaebal]

@@_1_423 우선 코딩테스트 관점에서 둘의 가장 큰 차이점은 DFS는 "모든 경우의 수를 만들어서 비교해야 되는 경우에 적합하고, 한번에 하나의 경우의 수만 만들기 때문에 메모리 효율이 좋다"는 장점이 있습니다. 그래서 특정 문제에서 모든 경우의 수를 따져야 한다면 DFS로 짜는 것이 코드가 간결하기도 하고 메모리 사용량도 줄일 수 있습니다. (예를 들어 visited 배열을 한 개만 써도 되는거죠).
그에 비해 BFS는 여러 경우의 수를 한 단계씩 전진하며 확인하는 방식이다 보니, visited 배열이 각 경우의 수 마다 관리되어야 하고 메모리 사용량이 늘어납니다. 그렇지만 여러 경우의 수를 동시에 비교하기 때문에 가장 큰 장점은 "최단 거리 구하기"에 적합합니다. 왜냐하면 이때는 모든 경우의 수를 끝까지 다 비교할 필요가 없고, 이 중 하나라도 도착지에 도착했다면 이것이 정답이고, 나머지는 최단 거리가 아닐 것이기 때문입니다.
그래서 제 경험상 DFS/BFS 문제는 1) DFS/BFS 둘다 풀 수 있는 문제 혹은 2) BFS로만 풀 수 있는 문제로 많이 나뉘는 것 같아요. 왜냐하면 DFS로 모든 경우의 수를 따지나, BFS로 모든 경우의 수를 따지나 결국 다 따져봐야 하기 때문에, DFS로 풀 수 있다는 것은 BFS로도 웬만하면 풀 수 있습니다. 그렇지만 최단 거리를 찾는 유형과 같이 '가지 치기'를 잘 해야 되는 문제들은 BFS를 쓰지 않으면 시간 초과가 발생하거나 스택 오버플로우가 발생합니다.
그러므로 가장 쉬운 방법은 모두 BFS로 푸는 거예요. 그런데 저는 개인적으로 DFS를 더 선호하는 게 메모리도 아끼고, 재귀 함수로 작성하면 코드가 훨씬 짧아집니다. 재귀 함수가 한번 이해하기가 어렵지, 이해하고 나면 코드를 몇 줄 작성하지 않아서 불량이 발생할 확률이 매우 적어집니다.
그래서 DFS와 BFS를 구분하고 싶으시다면 기준은 "결국 모든 경우의 수를 다 따져야 하는가?"라는 겁니다. 결국 다 따져야 한다면, 메모리를 아끼고 코드도 간결한 DFS로 풀어보시고, 최단 거리 유형과 같이 모든 경우의 수를 따져보지 않아도, 최적의 해를 찾는 순간 정답이라는 걸 알 수 있다면 BFS를 사용하셔야 문제를 풀 수 있을 것입니다.

[@_1_423]

@@gaebal 안녕하세요 선생님. 먼저 장문의 답변 남겨주셔서 감사합니다. 덕분에 BFS, DFS 그 차이를 이해할 수 있었습니다. 어제 새벽에 해당 문제를 다시 풀고 잤습니다. 맞았을 때 짜릿함과 드디어 문제를 제대로 이해하고 풀었다는 뿌듯함이 맴돌았습니다. 항상 바쁘신데 꾸준히 영상 업로드 해주셔서 감사합니다! 오늘도 좋은 하루 보내세요