아랫글 전달이 잘못된 거 같은데
PS 갓 시작한 사람들 보면 백트래킹 짜서 배열만 추가함.
메모이제이션이 결국 같은 함수 인자에서 리턴값이 다르면 안되는데
전역변수 건드리면서 백트래킹으로 짠 코드를 메모이제이션으로 바꾼단 말이야..
메모이제이션을 초보자가 하면 단순 1~2차원 dp도 채우는 순서를 모르는 경우가 생김.
저게 dp 원리 몇개를 모르거나 씹어도 풀리는 경우가 매우 많아서, dp 기초를 못 쌓고 넘어가는 경우가 매우 많음.
그래서 나는 쉬운 dp는 반복문으로 무조건 짜보라고 하는 편인데
옛날에 boj 질문게시판에서, LCS같은 2차원 dp를 메모이제이션으로 이상하게 비비다가 못푼다고 질문 올리는 경우도 있더라.
당연히 코포 블루 넘어가면 뭘 쓰든 상관없는데, 저게 하필 종만북에 있어서 저런일이 많더라고.
그리고 내가 아만보 소리를 듣는다니.. 흑흑
아 취소선 찐따냄시
PS갤에 뉴비가 있다고요?
근데 사실 반복문으로 짜는게 실력늘리는데는 훨 도움이 됨. 그건 ㅇㅈ하는부분
백트래킹으로 짠 코드를 배열추가해서 메모이제이션 구현한게 뭐 어떻다는건지?;; 완전탐색, 메모이제이션을 이용한 동적프로그래밍도 단순하지만 강력한 방법입니다. 그리고 자꾸 반복이 더 낫니 이런류의 말이 나오는데, 확실히 말씀드릴게요. 문제가 복잡해질수록 재귀가 무조건 더 낫습니다. 5중 6중 for문 남발하실건가요? 알고리즘 디버깅은 어떻게 하시나요? 복잡도에 비례해 for문은 재귀보다 훨~~씬 더 난잡해질 수 밖에 없으며, 위에서 말씀하신 배열만 간단하게 추가해서 메모이제이션을 구현하는 것도 힘들죠. 코드가 워낙 장황해지고 변수들이 많이 추가되면서 서로 기능이 얽혀있을 확률이 높기 때문입니다. PS공부하신다는 분들이 for문보다 재귀가 더 안좋다니 이런식의 글들을 저는 이해할 수가 없네요 ㅋㅋ
코드의 간결성을 떠나 재귀를 이용하는 이유는 문제를 파편화해 작은 부분문제들로 문제는 단순화하기 쉬운 이유도 있습니다. 분할정복방법 역시도 재귀 아니던가요? 반복문으로 짜는게 실력늘리는데 훨 도움된다는 말은... 아래글 말을 인용하자면 아만보 입니다. 제가 생각하기엔 정말 실력있는 프로그래머들도 복잡한 알고리즘을 단순하게 반복문으로 짜면서 보람을 느끼진 않을 것 같네요.
그리고 단순 선형 문제에서는 꾸역꾸역 풀 수 있을지도 모르겠으나 비선형적인 트리, 그래프 문제로 들어가면 바로 한계가 드러날 겁니다. 노드나 정점들의 관계를 구현하고 순회하려면 코드는 엄청나게 길어질 것이며 장황해짐에 따라서 버그도 많이 발생하겠죠. 하지만 테스트하기는 더 힘들겁니다. 테스트 방식은 단순히 콘솔에 값을 일일이 뿌리고 추론해야겠죠. 재귀는 문제를 간결하고 서술적으로 만듭니다. 그리고 기능을 적절히 분리한다면 for문보단 훨씬 테스트하기 좋은 코드를 만들 수 있습니다.
나는 NQueen 같은 백트래킹 문제도 배열 추가해서 최적화해보려는 사람들 말한거였는데.. 머 그래도 하나씩 보면, 1. 문제가 어떻게 복잡하냐에 따라 다른데, 어려운 문제일수록 반복문 dp를 자료구조같은 것들로 최적화하는 경우가 많음. 2. 반복문이 디버깅 훨씬 편함. 3. 서로 변수가 얽히는건 코더 문제고, 재귀가 그럴 가능성이 더 쉬움 4. dp 반복문도 결국 점화식을 세워서 푸는건데, 점화식 자체가 문제 파편화 5. 복잡한 알고리즘을 단순하게 짜면 보람을 느끼겠지 6. 그래프는 재귀가 편한 경우가 압도적으로 많지만, dp랑 그래프는 다르자나.
7. 그리고 그래프에 dp가 섞이려면 필수적으로 순서가 있어야되는데, 위상정렬이나 dfs 방문순서 같은거로 순서만 미리 구해놓고 반복문으로 dp값 채우는 경우도 많음. 코딩도 간단하고.
1. 당연히 그러겠죠. 문제에 따라 각각에 적합한 자료구조를 쓰겠죠. 근데 문제는 님이 뜬금없이 메모이제이션은 사탄이다 식의 발언이 너무 기가차서 한말입니다. 제 말의 요지를 잘못 파악하신듯 하구요 2. 그냥 기가차서 웃음만 나네요 ㅋㅋㅋ 유명한 알고리즘 책 사서 좀 보세요. 님들보다 훨씬 능력있는 개발자들은 어떤 코드를 썼는지 공부좀 하시구요. 3. ㅋㅋㅋㅋㅋㅋ 2번과 동일입니다. 4. 아예 재귀 써보신 적 없으신 분 같은데 패스합니다. 5... 더이상 답변할 가치를 못느끼겠네요. 진짜 어디서 겉핥기식으로 배워서 허세부리시는 거 같은데 안타깝네요. 7. 재귀없이 단순 for문 만으로 어떻게 DFS를 한다는건지 ㅋㅋㅋㅋ 재귀 속에 for문 하나만 넣으면 DFS 순회 진짜 20줄도 안되서 할 수 있습니다.
for문만으로 어떻게 DFS 순회를 한다는건지 저로서는 감이 안오긴 하는데 ㅋㅋㅋㅋ 대단하신분이네요. 우물 안 개구리로 사세요~
7번은 후하게 20줄 줬는데 10줄이면 되겠네요 ㅋ