바위타는 두루미

문제 어떤 집합의 부분집합을 전부 반환하는 메서드를 작성하라 해결법 우선 시간복잡도와 공간복잡도를 한번 알아보자 한 집합의 부분집합은 얼마나 될까? n개의 원소가 있다고 할때 그 부분집합에 있거나, 없거나 2가지 경우에 대한 경우의 수이기 때문에 2^n개이다. 그렇다면 모든 부분집합의 리스트를 반환하는 경우에는 공간이 얼마나 차지할까? 각 원소는 전체 부분집합에 1/2에 속하게 된다. 그러면 각 원소들은 2^(n-1)개씩 존재할 것이고 원소의 갯수를 n이라고 하면 n * 2^(n-1)의 공간복잡도를 차지하게 될 것이다. 1. 재귀적으로 해결하기 이 문제는 초기사례로부터의 확장을 적용하기 좋은 문제이다. S = { a1, a2, a3 ...} 라고 했을때 a1을 가지고 만들 수 있는 부분집합 : {} ,{..

문제 배열 A[0 ... n-1]에서 A[i] = i 인 인덱스를 마술 인덱스(magic index)라고 한다. 정렬된 상태의 배열이 주어졌을때 마술 인덱스가 존재한다면 그 값을 찾는 메서드를 만들어라. 해결법 가장 무식하고 간단하게 푸는 방법은 0부터 순환하면서 해당하는 index가 있는지 확인하는 것이다. 하지만 정렬된 데이터라는 점에서 이진 탐색 으로 문제를 해결 할 수 있을 것 같다. 중복된 데이터가 없다는 가정하에는 -40 -20 -1 1 2 3 5 7 9 12 0 1 2 3 4 5 6 7 8 9 이러한 데이터가 있다고 보자 A[5] = 3 A[mid] < mid 이므로 마술인덱스는 오른쪽에 있음을 알 수 있다. 정말 왼쪽에 있을 수는 없을까? i에서 i-1로 움직인다고 가정해보자. 이 때 배열..

문제 어던 아이가 n개의 계단을 오른다. 한 번에 1계단 오르기도 하고 2계단이나 3계단을 오르기도 한다. 계단을 오르는 방법이 몇가지가 있는지 계산하는 프로그램을 구현하라. 접근법 n번째 계단을 딛기 바로 직전에 마지막에 딛는 계단은 3계단전, 2계단전, 1계단전에 있었을 것이다. 따라서, n개의 계단을 오르는 모든 경로를 생각해 본다면 1계단, 2계단 3계단 전까지의 경로를 단순히 더해주면 될 것이다. 무식하게 재귀로 구현할 수 있겠지만 반복적으로 호출되는 함수가 많아서 비효율적일 것이다. 따라서 메모이제이션을 통해 좀 더 효율적으로 해결 할 수 있다. def Solution(n): memo = [-1]* (n+1) return countWay(n, memo) def countWay(n, memo):..