간단한 블로그

퀵소트는 아주 강력하고 쉬운 정렬 알고리즘이다.배열의 값 하나를 선택해서(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(..

함수형 프로그래밍의 주요 함수 중 하나인 map은 n개의 요소 각각에 함수를 적용한 결과를 만들어내는 함수이다. 많은 문제를 접하다 보면 자연스레 for보다 map을 선호하게 되는데 문제에 따라 for문을 사용하는 것이 더 간결한 코드를 만들어 낼 수 있었다. 구구단의 예를 들어 보자. 원하는 결과가 1단부터 9단까지 결과의 리스트라고 하자. 이 때 flatMap함수를 사용한다면 이렇게 쓸 수 있다.val range = 1 to 9 val result = range.flatMap{i => range.flatMap{j => List(i * j) } } 1) 2의 배수 단의 결과만을 얻고 싶다고 해 보자.val result = range.filter(_ % 2 == 0).flatMap{i => range.f..

1. 스트림끼리 연결Stream(1, 2) #::: Stream(3, 4) // Stream(1, 2, 3, 4) 2. 우측 스트림의 요소로 삽입100 #:: Stream(3, 4) // Stream(100, 3, 4) 3. 우측 스트림의 요소로 삽입 2 Stream.cons(Stream(1, 2), Stream(3, 4)) // Stream(Stream(1, 2), 3, 4) 4. 빈 스트림Stream.empty // 새로운 빈 스트림 Stream.Empty // 패턴 매칭 case문에서 사용 5. 시드값으로부터 일정 수만큼 더해져 나가는 스트림Stream.from(1, 2) // Stream(1, 3, 5, 7 ...) 6. 시드값으로부터 계산되어가는 스트림Stream.iterate(2)(s => s..

함수형 = 재귀함수는 아니지만 재귀함수를 많이 사용한다는 것은 틀림없을 것이다.하지만 컴퓨터 프로그램의 구조상 함수를 호출할 때마다 스택에 값들이 쌓여 StackOverFlow를 피할 수 없다. 이 친숙한 스택오버플로를 피하기 위한 방법들이 있다.꼬리재귀와 트램폴린, 지연 콜렉션 Stream이다. 사실 스트림은 스택오버플로를 피하기 위한 방법은 아니다.하지만 스택오버플로가 발생할 수 있는 문제에서 스트림을 사용, 더 이른 스택 복귀를 통해(혹은 다른 방법으로의 접근) 문제를 해결한 경험이 있어 함께 적어둔다. 1. 꼬리재귀(Tail Recursive)꼬리재귀는 어떤 함수가 자기 자신을 호출하되 그 호출이 함수의 마지막 연산인 경우를 말한다.꼬리재귀는 아주 쉽게 반복문으로 변경할 수 있다. 많은 함수형 프..