간단한 블로그

P92 (***) Von Koch's conjecture.Several years ago I met a mathematician who was intrigued by a problem for which he didn't know a solution. His name was Von Koch, and I don't know whether the problem has been solved since. [The "I" here refers to the author of the Prolog problems. ] Anyway the puzzle goes like this: Given a tree with N nodes (and hence N-1 edges), find a way to enumerate the nod..

P91 (**) Knight's tour.Another famous problem is this one: How can a knight jump on an N×N chessboard in such a way that it visits every square exactly once?Hints: Represent the squares by pairs of their coordinates of the form (X, Y), where both X and Y are integers between 1 and N. (Alternately, define a Point class for the same purpose.) Write a function jumps(N, (X, Y)) to list the squares t..

머지 소트(병합 정렬) 역시 강력하고 쉬운 알고리즘이다.절반으로 계속 나누어 나가다가 더 이상 나눌 수 없어지면 다시 합치는 알고리즘이다. 단지 합칠 때 작은 값과 큰 값의 순서를 확인하면서 합쳐나가는 것이 포인트다. 퀵 소트와 마찬가지로 절반으로 나누어 재귀호출하기 때문에 로그단위의 복잡도를 가진다.하지만 퀵 소트와는 다르게 이미 정렬된 값은 순서 그대로 합쳐져 stable한 결과를 가진다. 위키백과의 그림을 참고해 설명하자면 이렇게 두 단계로 나눌 수 있다. 노란 색으로 표시한 두 배열을 합치는 방법을 좀 더 자세히 보면 이런 순서가 된다.합칠 값 두개를 비교한 후 더 작은 값을 새로 만들 배열에 넣고, 나머지 값을 재귀호출 하는 것이다. 스칼라 코드로 구현하면 아래처럼 될 것이다.def mergeS..

퀵소트는 아주 강력하고 쉬운 정렬 알고리즘이다.배열의 값 하나를 선택해서(pivot), pivot보다 작은 것을 왼쪽, pivot보다 큰 것을 오른쪽으로 모은 후 왼쪽에 대한 재귀호출, pivot, 오른쪽에 대한 재귀호출 셋을 순서대로 이어붙이면 된다.함수가 호출될 때마다 피벗의 위치가 확정되고 재귀호출되어 재실행되는 리스트는 이전 배열의 절반 수준이기 때문에 복잡도를 로그단위로 끌어내릴 수 있다. 함수형 프로그래밍 언어들에서는 그 특유의 콤비네이터들이 있어 구현을 굉장히 쉽게 만든다.구글링으로 가장 먼저 볼 수 있는 스칼라 퀵 소트의 알고리즘은def quickSortHead[A](lst: List[A])(implicit ord: A => Ordered[A]): List[A] = lst match{ ca..

P90 (**) Eight queens problemThis is a classical problem in computer science. The objective is to place eight queens on a chessboard so that no two queens are attacking each other; i.e., no two queens are in the same row, the same column, or on the same diagonal.Hint: Represent the positions of the queens as a list of numbers 1..N. Example: List(4, 2, 7, 3, 6, 8, 5, 1) means that the queen in th..

자바는 자바8이 되며 default 키워드가 생겼고, 덕분에 인터페이스에도 메소드 바디 구현이 가능해졌다.스칼라의 trait과 거의 같다고 볼 수 있게 된 것이다. 하지만 trait과 interface에는 아직 차이가 많다. 그 중 하나는 자바 인터페이스에서의 변수는 static final이라는 것이다.interface DogImpl { String color = "Black"; String bark(); } class Dog implements DogImpl{ public String setColor(String newColor) { color = newColor; // 에러 return color; } public String getColor() { return color; } @Override pu..

스칼라는 자바와 다르게 static 키워드가 없다. 대신 비슷한 역할을 할 수 있게 클래스와 같은 이름을 가지는 object를 만들 수 있다.이렇게 만들어진 object를 companion object(동반 객체)라고 하고 같은 이름을 가진 클래스를 companion class(동반 클래스) 라고 한다. class Dog(name: String) { def bark = println("bark! bark!") def getName = name } object Dog { def apply(name: String) = new Dog(name) }object안에 필드나 메소드를 구현해 자바에서 static 키워드를 사용한 것과 같이 사용할 수 있다.또, 위와 같이 apply 메소드를 구현해 new 키워드 없이..

P50 (***) Huffman code.First of all, consult a good book on discrete mathematics or algorithms for a detailed description of Huffman codes!We suppose a set of symbols with their frequencies, given as a list of (S, F) Tuples. E.g. (("a", 45), ("b", 13), ("c", 12), ("d", 16), ("e", 9), ("f", 5)). Our objective is to construct a list of (S, C) Tuples, where C is the Huffman code word for the symbol..

P27 (**) Group the elements of a set into disjoint subsets.a) In how many ways can a group of 9 people work in 3 disjoint subgroups of 2, 3 and 4 persons? Write a function that generates all the possibilities.Example:scala> group3(List("Aldo", "Beat", "Carla", "David", "Evi", "Flip", "Gary", "Hugo", "Ida")) res0: List[List[List[String]]] = List(List(List(Aldo, Beat), List(Carla, David, Evi), Lis..

개미수열은 꽤 유명하다. 111 (1이 1개)12 (1이 2개)1121 (1이 1개, 2가 1개)...이런 식으로 무한히 이어져 가는 수열인데 몇가지 방면에서 만들어볼만한 수열이라고 생각한다.Run-length encoding이라는 것과도 비슷하다. 1. 간단한 방법우리가 푸는 방법 그대로를 구현한다면 어떨까? 이전 단계의 수열을 입력받아 각 수를 세게 하는 방법이다. 수열을 리스트로 입력받는다고 했을 때, 리스트의 앞부분부터 숫자가 같으면 count를 증가시키고 다르면 숫자와 개수를 정답으로 붙이면 된다. /** * @param lst 현재 단계의 수열 * @param numb 현재 세고 있는 수 * @param count numb의 개수 * @return 다음 단계의 수열 */ def antLst1(..