Algorithm with C
-
조약돌 놓기 문제Algorithm with C/DFS 2020. 9. 16. 19:22
문제 출처 문제 i열에 돌을 둘 수 있는 가지수를 살펴보자. 위의 임시 테이블에 i열을 다음과 같이 설정하자. i열에 돌을 둘수 있는 경우의 수를 파악하자. 아래와 같이 4가지 경우가 있음을 알 수 있다. i열에 돌을 둘 수 있는 가지수는 4가지임을 알 수 있다. 우선 최적 부분구조의 존재를 확인해보자. n열 중 1열부터 i열까지 돌을 놓는 경우에 1열부터 i열까지의 합의 최고치를 생각해보자. 위에서처럼 i열에는 4가지 패턴 중 하나의 경우로 돌이 놓여질 것이다. (1). i열이 패턴1로 놓여 있을 경우의 최고점 (2). i열이 패턴2로 놓여 있을 경우의 최고점 (3). i열이 패턴3으로 놓여 있을 경우의 최고점 (4). i열이 패턴4로 놓여 있을 경우의 최고점 그리고, 다음과 같은 경우에 대해서도 생각..
-
N 개의 계단Algorithm with C/DFS 2020. 9. 16. 18:58
문제 N 개의 계단을 사람이 오른다고 하자. 한 번에 1계단 오르기도 하고, 2계단이나 3계단씩 오르기도 한다. 계단을 오르는데 몇 가지 방법이 있는가? 문제 분석 N 번째 계단에 도달하는 방법을 생각해보자. N - 1 번째 계단에서 한 계단 더 올라 N 번째 계단에 도달했을 수도 있고, N - 2 번째 계단에서 두 계단을 뛰어 N 번째 계단에 도달했을 수도 있고, N - 3 번째 계단에서 세 계단을 한 번에 뛰어 N 번째 계단에 도달했을 수도 있다. 그러므로, 마지막 계단에 오르는 방법의 가짓수는 그 전 세 계단에 도착하는 경우의 수를 전부 더한 것이다. 구현 프로그램 실행결과 소스 파일
-
이동 경로의 가지수를 구하라.Algorithm with C/DFS 2020. 9. 16. 18:47
문제 본인이 프로그래밍을 한 이후에 올바르게 값이 출력이 되는지 궁금할 것이다. 이 문제에서 구하는 경로의 개수는 아래와 같이 표현된다. 위와 같이 식이 세워지는 이유를 찾아보자. X번 오른쪽으로, 그리고 Y번 아래쪽으로 진행하여 만들 수 있는 모든 경로의 수를 세야 한다. 이 경로는 ( X + Y ) 개의 이동 단계로 구성된다. 경로 하나를 만들려면, X + Y 번 이동하는 가운데 X번은 오른쪽으로 움직이도록 해야 한다. 그러므로, 전체 경로의 수는 ( X + Y ) 가운데 X의 항목을 뽑는 경우의 수와 같다. 그래서, 위와 같은 이항식이 나온다. 문제 분석 위의 문제의 초점은 로봇이 움직이는 방향이다. 로봇은 두 방향으로만 움직이는 것이 가능하다. 그리고, 시작위치와 끝 위치가 주어져 있다. 여기서 ..
-
Matching System - 파티원 조직Algorithm with C/ETC 2020. 9. 12. 23:21
1. 문제 2. 문제 해결 전에 해야할 것 의 문제를 해결 하기 전에 다음과 같은 문제에 대한 답을 해보자. 아래와 같이 숫자들이 정의되어있다고 하자. 1, 4, 7, 2, 5, 8, 3, 6, 9, 10, 11 첫 번째 그룹 11 10 1 두 번째 그룹 9 8 5 세 번째 그룹 7 6 4 3 2 위와 같이 3개의 그룹이 있으며, 각 그룹에 위와 같이 값들이 저장되어있다고 하자. 그러면, 위의 그룹의 특징이 눈에 보이는가? 1그룹의 숫자 합 = 2그룹 숫자 합 = 3그룹 숫자 합 임을 알 수 있다. 각 그룹의 각 각의 합은 22이다. 그리고, 위의 숫자의 총합은 66이다. (1부터 11까지의 합이므로.) 숫자 총합 / 3 = 22 위와 같은 프로그램을 작성해보자. 힌트는 아래와 같다. ..
-
Graham ScanAlgorithm with C/Math 2020. 9. 11. 20:22
1. 정의 Graham Scan은 평면 상에서 유한한 점들의 볼록 껍질(Convex hull)을 찾는 방법이다. 자세한 사항은 아래를 참고 하자. ko.wikipedia.org/wiki/%EA%B7%B8%EB%A0%88%EC%9D%B4%EC%97%84_%EC%8A%A4%EC%BA%94 그레이엄 스캔 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 2차원 볼록 껍질을 찾는 그레이엄 스캔의 예시 그레이엄의 스캔(Graham Scan)은 평면상에서 유한한 점들의 볼록 껍질을 찾는 방법으로, 시간 복잡도는 O(n log n)이�� ko.wikipedia.org 2. 문제 8개의 좌표를 순서대로 입력받는다. (3,1) (1 3) (2 2) (3 2) (1 2) (2 3) (1 1) (2 1)..
-
세 점의 방향 판단Algorithm with C/Math 2020. 9. 11. 10:35
벡터의 외적을 먼저 보고 오자. designatedroom87.tistory.com/103 벡터의 외적(Cross product) 1. 외적의 기하학적 정의 벡터의 외적을 한 결과값은 벡터이다. 벡터는 크기와 방향을 갖는다고 하였으므로 벡터의 외적을 한 결과 또한 크기와 방향을 갖는다. 이 방향은 벡터v1과 v2에 동시에 �� designatedroom87.tistory.com 벡터의 외적을 이용해서 세 점의 방향을 판단할 것이다. 위 그림에서 나타난 바와 같이 세 점의 방향 판단은 외적을 통해 이루어진다. 세 점의 방향을 판단하는 함수 메인 함수 및 프로그램 실행결과 프로그램 실행결과 소스 파일
-
벡터의 외적(Cross product)Algorithm with C/Math 2020. 9. 11. 00:48
1. 외적의 기하학적 정의 벡터의 외적을 한 결과값은 벡터이다. 벡터는 크기와 방향을 갖는다고 하였으므로 벡터의 외적을 한 결과 또한 크기와 방향을 갖는다. 이 방향은 벡터v1과 v2에 동시에 수직인 방향인데 오른손 법칙에 의해서 엄지손가락이 가리키는 방향이 선택된다. [그림 1] [그림 2] 2. 벡터의 성분에 대하여 외적을 정의 벡터의 외적은 결과값이 벡터이므로 성분에 대해서 나타낼 수 있다. 아래는 벡터의 성분에 대해서 외적을 정의한 것이다. [그림 3] 아래의 두 그림에 대해서는 약간의 설명이 필요한데, 점 A,B,C가 xy평면에 대해서 정의되어 있다고 가정하자. (점A,B,C의 좌표에서 z성분은 0이라고 생각하자.) 왼쪽 그림과 같이 우리 눈 쪽으로 오는 수직축을 z축의 음의 방향, 오른쪽 그림..
-
점과 점의 각도(삼각함수의 역함수를 이용)Algorithm with C/Math 2020. 9. 10. 08:32
1. 설명 위의 정보를 가지고 우리는 각도 theta를 구할 수 있다. dx와 dy를 알고 있으므로 이는 tangent함수를 이용해서 구할 수 있다. 각도는 반시계 방향을 기준으로 한다. 위의 내용으로부터 알 수 있는 사실은 dx와 dy만 구하면, 두 점에서의 각을 구할 수 있다. case1. originPos와 destPos의 x좌표와 y좌표가 모두 일치하는 경우 dx = 0, dy = 0 case2. originPos의 y좌표와 destPos의 y좌표가 일치하는 경우 (1). dy = 0, dx > 0 (2). dy = 0, dx 0 (2). dx = 0, dy < 0 case4. ..