바위타는 두루미

문제 8*8 체스판 위에 여덟 개의 퀸(queen)이 서로 잡아 먹히지 않도록 놓을 수 있는 모든 가능한 방법을 출력하는 알고리즘을 작성하라. 즉, 퀸은 서로 같은 행, 열, 대각선 상에 놓이면 안된다. 여기서 '대각선'은 모든 대각선을 의미하는 것으로 체스판을 양분하는 대각선 두개로 한정하지 않는다. 해결법 한 열에 하나씩 놓고 다음 놓는 말은 이전 열들과 규칙을 지키면서 놓을 수 있는 모든 경우의 수를 놓아가면서 가장 끝가지 경우를 만들어 가고 , 갈 곳이 없다면 다시 돌아와서 다른 경우의 길로 선택해 가는 것을 반복하는 backtracking 기법을 이용하면 해결 할 수 있다. def Solution(): result = [] queens = [-1]*8 def isVaild(queens, inde..

문제 쿼터(25센트 ) , 다임(10센트) , 니켈 (5센트 ) , 페니(1센트)의 4가지 동전이 무한히 주어졌을때 n센트를 표현하는 모든 방법의 수를 계산하는 코드를 작성하라. 해결법 이 문제도 재귀로 풀 수 있으므로 부분 문제를 만드어보자 n = 100일때 쿼터가 0개 1개 2개 3개 4개 있을 수 있다. (4개면 100을 만들 수 있을니까!) 그런데 1개의 쿼터로 100을 만드는 것은 0개의 쿼터로 75를 만드는 것과 같음을 알 수 있다. 이 논리를 2개의 쿼터, 3개의 쿼터에도 적용한다면 다음의 결과를 얻을 수 있다. makeChange(100) = makeChange(0개의 쿼터로 100만들기 + makeChange(0개의 쿼터로 75만들기) + makeChange(0개의 쿼터로 50만들기 + ..

문제 이미지 편집 프로그램에서 흔히 쓰이는 '영역 칠하기'함수를 구현하여라 영역 칠하기 함수는 화면(색이 칠해진 이차원 배열)과 그 화면상의 한 지점, 그리고 새로운 색상이 주어졌을때, 그 주어진 지점과 색이 같은 인접한 주변 영역을 새로운 색상으로 색칠하여라 해결법 DFS나 BFS같은 탐색법으로 해결할 수 있다. 재귀를 사용하는 단원이니 재귀를 사용해서 풀기 위해 DFS로 해결해 보겟다. import enum class Color(enum.Enum) : Black = 0 White = 1 Red = 2 Yellow= 3 Green = 4 def ChangeColor(map, point, oldColor, newColor): if point[0]=len(map) or point[1]= len(map[0]..

문제 n-쌍의 괄호로 만들 수 있는 모든 합당한(괄호가 열리고 닫힌) 조합을 출력하는 알고리즘을 구현하여라 입력 :3 출력 : ((())), (()()), (())(),()(()),()()() 접근법 첫번째는 f(n-1)의 결과로 f(n)을 만드는 재귀적인 방법을 통해 결과쌍을 찾을 수 있을 것이다. n = 2인경우 (()), ()() 두가지가 있다. n = 3인경우 (()()) ((())) (()(()) (())() ()()() 5가지가 있다. 그러면 (())=> (()()) - 첫번째 괄호 다음에 새로운 괄호 넣기 ((())) - 두번째 괄호 다음에 새로운 괄호 넣기 ()(()) - 가장 시작점에 넣는다. ()() => (())() - 첫번째 괄호 다음에 새로운 괄호 넣기 ()(()) - 두번째 괄호..

문제 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 문자는 중복되어 나타날 수 있지만, 나열된 순열은 서로 중복 되면 안된다. 접근법 가장 간단한 방법은 현재 순열이 이미 만들어 졌는지를 확인하고 만들어진 적이 없다면 리스트에 더해주는 것이다. 해시테이블을 사용하면 되지만, 최악의 경우에 n!의 시간이 걸린다. 따라서 모든 순열을 만들어서 중복된 경우를 제거하는 것 보다는 중복되지 않은 순열만을 나열하는 것이 더 효율적일 것이다. 문자열 aabbcccc가 있다고 할때 a->2 b->2 c->4 개가 존재한다. 그럴때 해시테이블을 이용하여 문자열 순열을 나열하는 방법을 생각해보자. P (a ->2, b->2, c->4) ={a + P (a ->2, b->2, c->4) } + {b ..

문제 문자열이 주어졌을 때 모든 경우의 순열을 계산하는 메서드를 작성하라. 단, 문자는 중복되어 나타날 수 없다. 해결법 1. 첫 n-1개 문자의 순열을 이용해서 만들기 P(a1) = a1 P(a1a2) = a1a2, a2a1 P(a1a2a3) = a1a2a3, a1a3a2, a2a1a3, a2a3a1, a3a1a2, a3a2a1 다음 원소를 이전에 만든 순열들에 각 위치에 추가해주면 된다. def getPerms(str): if len(str) == 0 : return [""] permutations = [] first = str[0] words = getPerms(str[1:]) for word in words : for i in range(len(word)): permutations.append(w..

문제 전형적인 하노이타워에서는 크기가 서로 다른 N개의 원반을 세개의 기둥 중 아무 곳이나 옮길 수 있다. 초기에 원반의 크기가 맨 위에서부터 아래로 커지는 순서대로 쌓여있다. 그리고 문제에는 다음과 같은 제약 조건이 있다. 1. 원반을 한번에 하나만 옮길 수있다. 2. 맨 위에 있는 원반 하나를 다른 기둥으로 옮길 수 있다. 3. 원반은 자신보다 크기가 작은 디스크 위에 놓을 수 없다 . 스택을 사용하여 모든 원반을 첫번째 기둥에서 마지막 기둥으로 옮기는 프로그램을 작성하라 . 해결법 n=1 1. 원판1을 기둥1에서 기둥3으로 옮긴다 n=2 1. 원판1을 기둥 1에서 기둥 2로 옮긴다. 2. 원판2을 기둥 1에서 기둥 3로 옮긴다. 3. 원판 1을 기둥 2에서 기둥 3로 옮긴다. n=3 1. 원판1을 ..

문제 * 연산자를 사용하지 않고 양의 정수 두 개를 곱하는 재귀함수를 작성하라. 덧셈, 뺄셈, 비트 쉬프팅 연산을 사용할 수 있지만 사용횟수를 최소화해야한다. 접근법 곱셈은 격자판 안의 셀의 갯수와 같다고 볼 수 있다. 7*8은 7*8 격자판의 셀의 갯수를 세는 것과 같을 테니까 말이다. 그렇다면 셀의 갯수는 어떻게 샐 수 있을 까? 절반을 세고 이것을 곱절로 만들어 가는 과정을 재귀적으로 처리할 수 있을 것이다. def Solution(a, b): small = a if a1 side1 = minProduct(s, b) side2 = side1 if small%2==0 else minProduct(small-s, b) return side1 +side2 이 코드에도 minProduct가 반복적으로 호출..

문제 어떤 집합의 부분집합을 전부 반환하는 메서드를 작성하라 해결법 우선 시간복잡도와 공간복잡도를 한번 알아보자 한 집합의 부분집합은 얼마나 될까? 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로 움직인다고 가정해보자. 이 때 배열..