바위타는 두루미

문제 이미지 편집 프로그램에서 흔히 쓰이는 '영역 칠하기'함수를 구현하여라 영역 칠하기 함수는 화면(색이 칠해진 이차원 배열)과 그 화면상의 한 지점, 그리고 새로운 색상이 주어졌을때, 그 주어진 지점과 색이 같은 인접한 주변 영역을 새로운 색상으로 색칠하여라 해결법 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로 움직인다고 가정해보자. 이 때 배열..

문제 어던 아이가 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):..

퍼즐 혹은 수수께끼라고 불리는 문제들은 정책적으로 이런 종류의 문제를 면접에 출제하는 것을 금지하고 있지만, 이런 문제를 받게 될 가능성이 있다. 왜냐하면 수수께끼라는 것의 정의 자체가 모호하기 때문이다. 퍼즐 혹은 수수께기 문제의 좋은 점 중 하나는 꽤나 그럴싸하게 공정하다는 것이다. 대체로 문제로 말장난을 하지 않고 거의 대부분 논리적으로 추론이 가능하기 때문이다. 여기서는 이러한 문제들을 푸는데 기본적인 방법들과 반드시 알아야 하는 지식에 대해서 알아볼 것이다. -소수 소수판별 가장 단순한 방법 : 1 부터 n-1까지 돌면서 나누어지는 경우가 있는지 확인한다. 개선된 방법 : 1부터 n의 제곱근까지만 돌면서 나누어 지는 경우가 있는지 확인한다. import math def getPrime(n): i..