본문 바로가기

재귀

8. DFS로 푼 그래프 문제 (백준 4963 파이썬) 정말 그래프 문제는 아마도 푸는 방법이 다양한 것 같은데 일단 DFS로 풀었다. 반복되는 걸 느끼는 순간 재귀 못놓아.. 그래서 이번에도 필연적으로 또 Recursion Error만났죠.. 하지만 생각해보니 BFS도 재귀하면 되는걸.. 다음에는 시도해보는걸로.. https://www.acmicpc.net/problem/4963 4963번: 섬의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 지도의 너비 w와 높이 h가 주어진다. w와 h는 50보다 작거나 같은 양의 정수이다. 둘째 줄부터 h개 줄에는 지도 www.acmicpc.net 문제 정사각형으로 이루어져 있는 섬과 바다 지도가 주어진다. 섬의 개수를 세는 프로그램을 작성하시오. 한 정사각형과 가로, 세로 또.. 더보기
3. 이제는 친숙해진 DFS, BFS (백준 1260 파이썬) 처음 배웠을 때는 충격과 공포였는데, 이제는 오히려 안심이 되는(?) 친근해진 DFS, BFS다. 생각보다 개념은 단순하게, 트리모양을 보면 이해가 빨리 되고, 실제 문제를 풀 때 내가 가장 쉽게 이해한 방법은: DFS는 stack, 그리고 재귀는 결국 stack이므로 재귀로 풀 수 있음 BFS는 queue, 그래서 더 쉽긴한데 pop(0)이 좀 효율성이 안좋다 이외에 좀 주의해야 하는 부분은 입력 값을 어떻게 저장하는가 부분이다. 사실 그래프 유형과 DFS BFS 유형도 비슷한 것 같고,, 재귀로 푸는 문제들도 서로서로 비슷한 것 같고.. 약간 딱 나눠서 할 수 있나 싶은데 (백준에서도 브루트포스 재귀로 분리되어 있는 문제가 DP로 풀기도 하고..) 여튼 그래프 형식은 노드, 간선, 시작점 입력에 익숙.. 더보기
1. DP 이것은 무엇인가 (백준 1463 파이썬) DP : Dynamic Programming 내 머릿속에 일단 DP는 피보나치이다. 한 번 나왔던 값은 저장을 해서 다시 구하는 시간을 절약할 수 있다는 것이 핵심이다. Top-down(하향식) 방식 : 내려가며 재귀 Bottom-up(상향식) 방식 : 올라가며 반복문 나는 재귀를 처음 이해한 후에 재귀에 빠져서 하향식을 더 선호했는데, 사실 이제 다 잊어버리기도 했고(...) 문제마다 어떤 방식이 더 좋은지가 애초에 달라질 수 있는 것 같다. 백준 1463번 풀이를 하며 이해해보도록 노력하겠다. https://www.acmicpc.net/problem/1463 문제 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, .. 더보기

티스토리툴바