변경이력

돌아가기
8 18개 문자 추가

2016/11/30 03:42

Han Jooyung

이진트리를 그리기 위해 각 노드의 위치 (x,y)를 계산하는 문제다. 트리의 노드 위치를 결정하기 위한 레이아웃 알고리즘은 아래와 같다. 출처: https://sites.google.com/site/prologsite/prolog-problems/4 ## 레이아웃 알고리즘 ![](https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p66.gif) 모든 노드에서 좌우 간격의 대칭을 유지하면서 최대한 컴팩트하게 만든다. ## 입출력 트리를 생성하기 위한 입력 포맷이나, 레이아웃이 적용된 각 노드의 위치를 출력하는 형식은 자유롭게 결정한다. ### 입력 예 #1 `"n(k(c(a,e(d,g)),m),u(p(,q),))"`와 같이 입력받을 수 있다. `parent(left,right)`의 모양을 재귀적으로 표현한 것이다. (자식이 둘다 없으면 괄호부분이 생략된다.) ### 입력 예 #2 `"nkcmaedgupq"`와 같이 입력 받아 각 글자를 노드의 라벨로 하여 이진탐색트리를 만들 수 있다. ### 입력 예 #3 입력을 따로 신경쓰고 싶지 않다면 코드로 직접 트리를 만들어도 된다. 만약 Java라면 다음과 같을 것이다. ```{.java} class Tree<A> { A value; Tree<A> left; Tree<A> right; ... } Tree<String> t = new Tree("root", new Tree("left", null, null), new Tree("right", null, null)); ``` ### 출력 예 #1 inorder 출력으로 각 노드의 내용과 위치 (x,y)를 출력한다. ``` a 1 4 c 2 3 d 2 5 e 3 4 g 4 5 ... ``` ### 출력 예 #2 HTML/SVG/GraphViz 등으로 직접 그려도 좋을 것이다. ### 출력 예 #3 출력할 필요없이 테스트 코드로 확인해도 좋다. ```{.java} public void test() { Tree<Integer> t = ...; Tree<Point> expected = ...; assertEquals(expected, layout(t)); } ``` ## 확인하기 [여기](https://jsbin.com/popudab)에서 눈으로 결과를 확인할 수 있다. 아래 입력들에 대해서 잘 동작하는지 확인해보자. 1. qawrsxedcfvutgbyhnujmikolp 1. qwertyuiopasdfghjklzxcvbnm 1. afgzxtkjijbed
이진트리를 그리기 위해 각 노드의 위치 (x,y)를 계산하는 문제다. 트리의 노드 위치를 결정하기 위한 레이아웃 알고리즘은 아래와 같다. 출처: https://sites.google.com/site/prologsite/prolog-problems/4 ## 레이아웃 알고리즘 ![](https://prof.ti.bfh.ch/hew1/informatik3/prolog/p-99/p66.gif) 모든 노드에서 좌우 간격의 대칭을 유지하면서 최대한 컴팩트하게 만든다. ## 입출력 트리를 생성하기 위한 입력 포맷이나, 레이아웃이 적용된 각 노드의 위치를 출력하는 형식은 자유롭게 결정한다. ### 입력 예 #1 `"n(k(c(a,e(d,g)),m),u(p(,q),))"`와 같이 입력받을 수 있다. `parent(left,right)`의 모양을 재귀적으로 표현한 것이다. (자식이 둘다 없으면 괄호부분이 생략된다.) ### 입력 예 #2 `"nkcmaedgupq"`와 같이 입력 받아 각 글자를 노드의 라벨로 하여 이진탐색트리를 만들 수 있다. ### 입력 예 #3 입력을 따로 신경쓰고 싶지 않다면 코드로 직접 트리를 만들어도 된다. 만약 Java라면 다음과 같을 것이다. ```{.java} class Tree<A> { A value; Tree<A> left; Tree<A> right; ... } Tree<String> t = new Tree("root", new Tree("left", null, null), new Tree("right", null, null)); ``` ### 출력 예 #1 inorder 출력으로 각 노드의 내용과 위치 (x,y)를 출력한다. ``` a 1 4 c 2 3 d 2 5 e 3 4 g 4 5 ... ``` ### 출력 예 #2 HTML/SVG/GraphViz 등으로 직접 그려도 좋을 것이다. ### 출력 예 #3 출력할 필요없이 테스트 코드로 확인해도 좋다. ```{.java} public void test() { Tree<Integer> t = ...; Tree<Point> expected = ...; assertEquals(expected, layout(t)); } ``` ## 확인하기 [여기](https://jsbin.com/popudab)에서 눈으로 결과를 확인할 수 있다. 아래 입력들에 대해서 잘 동작하는지 확인해보자. 1. qawrsxedcfvutgbyhnujmikolp 1. qwertyuiopasdfghjklzxcvbnm 1. afgzxtkjijbed
7 160개 문자 추가

2016/11/30 03:36

Han Jooyung

6 597개 문자 추가 61개 문자 삭제

2016/11/20 13:19

Han Jooyung

5 3개 문자 추가 4개 문자 삭제

2016/11/15 21:50

Han Jooyung

4 2개 문자 추가

2016/11/15 21:42

Han Jooyung

3 114개 문자 추가 22개 문자 삭제

2016/11/15 21:42

Han Jooyung

2 57개 문자 추가 57개 문자 삭제

2016/11/15 21:32

Han Jooyung

1 Original

2016/11/15 21:26

Han Jooyung

코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.