Algorithm Study/Java
-
[알고리즘] 파스칼의 삼각형 만들기Algorithm Study/Java 2020. 5. 29. 18:43
오늘은 파스칼의 삼각형을 구현하는 방법을 알아볼 것이다. 파스칼의 삼각형은 위 그림처럼 생긴 삼각형으로 각 층의 양 끝은 1이고 나머지 값은 위층에 있는 값의 합으로 구성되어 있다. 이 삼각형이 가지고 있는 의미는 여러가지가 있겠지만 대표적으로 삼각형의 각 항목이 조합으로 표현되는 Combination의 각 항목을 나타내고 있다는 점이다. 예를 들어 1C0 부터 6C6까지의 조합을 나타낸 것과 파스칼의 삼각형의 위에서 2번 ~ 7번 층의 항목이 동일하다는 것을 알 수 있다. 그럼 이 파스칼의 삼각형을 어떻게 활용할 수 있을까? 조합의 경우 n!의 연산을 수행해야하기 때문에 n의 크기가 커지면 int형으로 나타낼 수 있는 범위를 초과하는 문제가 발생한다. 이 때, 파스칼의 삼각형을 이용하면 각 항목 nCk..
-
[알고리즘] 단순 다각형 그리기Algorithm Study/Java 2020. 4. 16. 20:56
단순 다각형은 연속한 두 변 이외에는 어느 두 변도 교차하지 않는 다각형이다. 여러 개의 점을 입력받은 다음 단순 다각형을 만들어서 출력하는 프로그램을 구현해보자. 단순 다각형을 그리는 방법은 여러가지가 있겠지만 여기서는 다음 방법을 이용하여 다각형을 구성하려고 한다. 1. 가장 낮은 Y좌표를 가지는 기준점을 잡는다 (C) Y 좌표가 동일한 경우 X좌표까지 계산한다. 2. 기준점에서 출발하는 X축 반 직선을 그린다. 3. 기준선과 각 점들의 각도 θ를 계산한다. 4. 낮은 각도부터 순서대로 연결한다. 위 이미지를 기준으로 C -> G -> H -> E -> D -> B -> A -> F -> C 가 된다. 입력은 점의 총 갯수 N과 각 점의 좌표 X, Y를 파일로 받아온다. 출력은 화면에 직접 하는 것으..