Kata의 IOS

안녕하세요. KataRN입니다. 오늘은 DP에 대해 알아보겠습니다. DP란 탈영병들을 잡는 병사들을 일컫는... 죄송합니다. DP(Dynamic Programming)란 ? 일반적으로 주어진 문제를 풀기 위해서, 문제를 여러 개의 하위 문제(subproblem)로 나누어 푼 다음, 그것을 결합하여 최종적인 목적에 도달하는 것이다. 각 하위 문제의 해결을 계산한 뒤, 그 해결책을 저장하여 후에 같은 하위 문제가 나왔을 경우 그것을 간단하게 해결할 수 있다. 이러한 방법으로 동적 계획법은 계산 횟수를 줄일 수 있다. 특히 이 방법은 하위 문제의 수가 기하급수적으로 증가할 때 유용하다. 출처 : 나무위키 핵심은 저장입니다. Memoization(메모이제이션)이라고 불리기도합니다. 동일한 계산을 반복해야할 때,..

안녕하세요. KataRN입니다. 오늘은 DFS, BFS에 대해 알아보겠습니다. DFS : Depth First Search(깊이 우선 탐색) weigh을 가지지 않는 방향 그래프에서 모든 경우를 구해볼 때 이 DFS를 사용됩니다. 예를 들면 1부터 N까지의 자연수 중 n개의 집합을 만들 수 있을 때, 가능한 모든 순열을 구해야 할 때 사용할 수 있습니다. 스택을 통해 구현하며, 재귀함수를 통해 구현합니다.(함수가 호출되면 스택 영역에 쌓이게 된다. 효율성이 떨어지는 이유) 코드로 확인해 볼게요. func practiceDFS(numbers: [Int], m: Int) { // 1. 궁극적으로 구하고자 하는 값. 재귀 함수의 외부에 선언되었다. 재귀 함수를 돌며 특정 기준에 만족할 경우 이 값을 변경할 것..