코딩 테스트 준비를 하고 있는데 재귀가 어렵더라고
주로 dfs같은 게 많이 나오니까 이 부분 관련해서 연습 좀 하려고 하는데
dfs가 그래프나 트리 탐색 유형 중 하나잖아.
근데 또 그래프 문제는 출제가 잘 안된다는데
그래프 유형은 아닌데 dfs로 푸는 문제는 무슨 유형이라 부름? 그냥 탐색 문제인건가?
알지는 모르겠는데 프로그래머스의 타겟 넘버같은 문제. 코드는 짧고 막상 보면 이해가는데 생각해내는 게 개어렵더라 (dfs/bfs 쪽에 분류되어있음)
문제 내용은 음이 아닌 정수가 담긴 배열을 받아서 각 숫자에 +/-를 마음대로 적용해서 주어진 수를 만들 수 있는 방법이 몇 가지인지 알아내는 문제
무슨 유형을 풀어보는 게 도움이 될까? 해커랭크나 리트코드에서.
백준을 풀어
그냥 리트코드나 해커랭크가 더 깔끔한 것 같고 어차피 영어에도 계속 익숙해지려고 일부로 저기서 풀음. 그리고 백준은 골라서 풀기가 어려운 것 같아서.
대부분 그런게 dfs나 bfs로 분류되는 이유는 그래프로 모델링이 가능하기 때문임
그럼 그냥 그래프 문제라는건 애초에 그냥 문제에 그래프가 주어지는 걸 말하는건가? 음 그런듯 하군
음이 아닌 정수가 담긴 배열을 받아서 각 숫자에 +/-를 마음대로 적용해서 주어진 수를 만들 수 있는 방법이 몇 가지인지 알아내는 문제 -> +/-를 나눌 때마다 분지해서 새 노드가 만들어진다고 생각하면 트리로 모델링되는 거임. 다른 예로는 턴을 번갈아 하는 2인용 perfect information 게임에서 minimax search를 적용할 때 게임 트리라는 말을 쓰는데 그 게임 트리라는 게 결국 그래프의 일종이고 minimax는 일종의 최적화된 DFS라고 할 수 있음