다이제 공부방

어떻게 생각하면 지난 N-Queens 알고리즘이 좀 더 어렵다고 생각할 수도 있겠지만, 이번 멱집합도 만만치는 않은 것 같다. 일단 수학 공부를 손에서 뗀 지 꽤 지난 시점이다 보니 수학적인 이해를 동반해야 하고, 거기에 가장 난감한 재귀함수적인 사고로 재귀함수적인 알고리즘을 짜내야 하기 때문에 복합적으로 작용이 되어 난도가 많이 올라간 것 같다는 느낌이 든다. 그렇지만 최대한 정리해보고자 한다. 멱집합? Powerset 집합 A={a, b, c, d}가 있다. 집합 A가 구성할 수 있는 부분집합의 수는 2^4=16개이다. {Ø} => 1개 {a}, {b}, {c}, {d} => 4개 {a, b}, {a, c}, {a, d}, {b, c}, {b, d}, {c, d} => 6개 {a, b, c}, {a,..

점점 공부하면서 어려워지는 알고리즘을 배우고 있는 것 같다는 생각이 든다. 재귀적인 함수 사고를 가져가고 있다고 생각했는데, 이번에는 게임(?)에 실제로 사용될 법한 알고리즘을 공부해 보았다. 여왕 알고리즘은 사이즈가 N인 정사각형 2차원 배열에 N만큼의 여왕이 있어야 하는데, 서로의 영향권에 들지 않는 곳에만 있어야 한다. 이게 무슨 말이냐면, 다음과 같이 여왕들이 서로의 간섭을 피하기 위해서는 나름의 규칙이 존재한다는 것이다. 여왕이 놓인 위치를 기준으로 가로, 세로, 좌우의 대각선으로는 다른 여왕이 놓일 수 없다. 아래의 사진을 참고하자면, 점선이 지나는 곳이 놓인 여왕의 영향권에 드는 구역이다. 따라서 여왕의 영향권에 들지 않는 구역에만 또 다른 여왕을 배치할 수 있다. 여기서 잠깐! 프로그래밍을..

개인적으로 미로 알고리즘 다음으로 재귀적인 사고방식을 갖게 해 준 알고리즘인 것 같다. 재귀적인 함수 사고를 갖기란 정말 쉽지가 않은 것 같다. 훈련을 여러 번 거듭하면서 비로소 재귀적인 사고가 가능해질 것 같다는 생각이 든다. 이번에는 좀 생소한 Blob이라는 개념을 가지고 알고리즘을 코딩해보도록 하겠다. 미로찾기 알고리즘 (재귀함수 응용문제) JAVA 개인적으로 재귀함수적인 사고를 할 수 있도록 도와 준 정말 고마운 알고리즘이라고 생각한다. 아무래도 재귀함수적인 사고에 익숙하지 않기 때문에 이런 훈련이 필요하다고 생각은 했다. 재귀함수는 팩토리얼과.. digest1.tistory.com Rules of Counting cells in a Blob 잠깐!! 여기서 Blob이란? Binary large ..

개인적으로 재귀함수적인 사고를 할 수 있도록 도와 준 정말 고마운 알고리즘이라고 생각한다. 아무래도 재귀함수적인 사고에 익숙하지 않기 때문에 이런 훈련이 필요하다고 생각은 했다. 재귀함수는 팩토리얼과 같은 간단한 수식 정도만 계산하는 장난감스러운 아이디어라고 생각했는데, 이러한 선입견을 완벽하게 깨부쉈다. 재귀함수 하나만으로도 이렇게 문제를 해결할 수 있다는 데에 감탄사가 절로 나온다. 문제 확인 public class Maze{ private static int N = 8; private static int[][] maze= { {0,0,0,0,0,0,0,1}, {0,1,1,1,0,1,0,1}, {0,1,0,1,0,0,0,1}, {0,0,0,1,1,1,0,0}, {1,0,1,1,0,0,1,1}, {0,..

재귀 함수란? 특정 문제를 해결할 때 자신의 메서드를 계속 호출(참조)해 가면서 문제를 해결해 나가는 것! 그런데, 자기 자신을 끝없이 호출하게만 한다면 다음과 같은 현상이 일어난다. 이것은 마치.. 무한루프??? 맞다. 반복문과 마찬가지로 끝 점이 없다면 무한루프에 빠지게 된다. 반복문에서의 무한루프는 반복문을 헤어 나올 수 없다는 것이라면, 재귀 함수에서의 무한루프는 나 자신을 끝도 없이 호출하게 된다. 그래서 Stack Overflow라는 그 유명한 오류가 발생하게 된다. 그렇다면 어떻게 해야 할까? 끝 지점이 있어야 한다. 다음의 C 코드를 살펴볼까? 2014년도 계리직 문제 응용 #include int sub(int n){ if(n==0) return 1; //base code if(n==1) ..