간단한 블로그

P98 (***) Nonograms.Around 1994, a certain kind of puzzles was very popular in England. The "Sunday Telegraph" newspaper wrote: "Nonograms are puzzles from Japan and are currently published each week only in The Sunday Telegraph. Simply use your logic and skill to complete the grid and reveal a picture or diagram." As a programmer, you are in a better situation: you can have your computer do the..

P97 (**) Sudoku. (alternate solution)Sudoku puzzles go like this: 주어진 스도쿠 퍼즐을 푸는 알고리즘을 작성하는 문제다.스도쿠의 룰은 모두가 아는 것처럼 간단하다. 9 x 9의 스도쿠 퍼즐 판이 있을 때 가로 방향으로 1에서 9까지의 숫자, 세로 방향으로도 1에서 9까지의 숫자만을 포함하고 작은 섹션에서도 1에서 9까지의 숫자만을 가지면 된다. N-Queens 알고리즘과 마찬가지로 스도쿠를 풀기 위한 알고리즘도 여러가지가 있다. 가장 유명하고 단순한 방법인 백트래킹부터 제시된 풀이인 Dancing Links(알고리즘 X)와 같은 방법까지 있다. 나는 N-Queens와 마찬가지로 재귀를 이용한 백트래킹으로 문제를 풀어 보려 한다. 이전 문제들과 마찬가지의..

P94 (***) Generate K-regular simple graphs with N nodes. In a K-regular graph all nodes have a degree of K; i.e. the number of edges incident in each node is K. How many (non-isomorphic!) 3-regular graphs with 6 nodes are there? 노드의 갯수 N, 각 노드의 엣지 갯수 K를 입력받아 정규 그래프를 만드는 문제다. 정규 그래프(Regular graph)란 각 노드가 동일한 갯수의 엣지를 가지는 그래프로 각 엣지는 다른 노드와 연결된다. 노드와 엣지 갯수에 따른 정규 그래프들 정규 그래프를 그려보면 몇 가지 간단한 규칙을 찾을 수 ..

스칼라의 암시는 크게 두 가지의 방법으로 쓰인다. 1. 암시적 파라미터(암시적 인자)메소드의 파라미터에 implicit 키워드를 사용하는 방법이다.이미 implicit 키워드를 이용해 선언한 값이 존재할 때 그 값을 쓰게 된다. implicit val x: Int = 500 def plusValue(paramX: Int)(implicit paramY: Int) = paramX + paramY println( plusValue(100)(200) ) // 300 println( plusValue(200) ) // 700 이런 사용은 Future를 사용할 때를 생각하면 편하다.ExecutionContext가 필요한 Future 함수는 두번째 인자로 ExecutionContext를 입력받는다.* @param e..

자바에서는 비교 가능한 클래스의 구현을 위해 두 가지 인터페이스를 사용한다. 첫 번째로 자바빈 클래스에 구현해 '다른 객체와 비교' 하는데 사용하는 Comparable다.public class Fruit implements Comparable { public String name; public int price; public Fruit(String name, int price) { this.name = name; this.price = price; } @Override public String toString() { return this.name + " " + this.price; } @Override public int compareTo(Fruit that) { return this.price - th..

P93 (***) An arithmetic puzzle.Given a list of integer numbers, find a correct way of inserting arithmetic signs (operators) such that the result is a correct equation. Example: With the list of numbers List(2,3,5,7,11) we can form the equations 2-3+5+7 = 11 or 2 = (3*5+7)/11 (and ten others!). 리스트로 주어진 수의 사이에 '=' 를 넣어 양 쪽 식의 값이 같게 되는 경우를 찾는 문제다.List(2, 3, 5, 7, 11)을 입력했을 때 답의 일부는 아래와 같다.2 = (3 ..

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..