본문 바로가기
반응형

수학42

괄호가 있는 중위 표기식 연산하기 삼성 C형 전체 링크 참고 - 스택 - 괄호 - Brainf**k 인터프리터 - 후위 표기식 - 중위 표기식 연산하기 중위 표기법 연산은 아래와 같다. 1. 숫자를 만나면 현재 숫자(cur)를 저장해둔다. 2. +, - 연산자가 나오면 temp에 현재의 숫자를 곱한다. (temp는 1로 초기화) 3. 그리고 result에 temp를 더한다. 4. *, / 가 나오면 temp에 값을 누적한다. 5. 이후 +, - 연산자가 나오면 2 ~ 3을 실행한다. 6. 모두 종료 후 남은 연산 실행 이때 괄호를 만나면 닫힌 괄호까지를 먼저 계산하고 temp로 변경한다. 그리고 괄호 연산이 끝난 경우는 다음 연산을 위해 cur = 1로 초기화 해야 한다. 괄호 내에서는 다시 중위 표기식이 될 것이기 때문에 위의 방법을 .. 2023. 7. 29.
유니티 - 세 점을 지나는 평면 구하기 (Creating a Plane from 3 Dots) Unity 전체 링크 참고 - 평면과 직선의 접점 좌표 구하기 - 3차원 세 점의 좌표로 삼각형의 넓이 구하기 - Vector3.Cross로 평면 위에서 시계 방향 판단하기 세 점의 좌표를 지나는 평면을 만들어보자. 먼저 투명한 평면과 임의의 세 점(Sphere)를 만든다. 유니티 오브젝트 Plane의 노멀 벡터는 transform.up이다. 그리고 유니티에서 제공하는 Plane으로 매우 쉽게 임의로 평면을 만들 수 있다. 여기서 normal 벡터를 유니티 오브젝트 평면의 transform.up으로 설정하면 된다. 이 평면은 세 점 중 하나를 지나기만 하면 되므로 position은 적절히 설정하면 된다. void setPlane(Vector3 a, Vector3 b, Vector3 c) { Plane p.. 2023. 3. 27.
유니티 - 컨벡스 헐로 임의의 점을 모두 포함하는 사각형 구하기 (Points in a Rectangle with Convex Hull) Unity 전체 링크 참고 - 스택 - 임의의 다각형을 포함하는 사각형 구하기 - 볼록 껍질 (Convex Hull, Graham Scan) - 컨벡스 헐로 볼록 다각형을 만드는 점의 좌표 구하기 임의의 다각형을 포함하는 사각형을 구할 때, 다각형의 좌표가 시계 방향이 아닌 경우, 아래와 같이 사각형을 제대로 만들지 못하는 경우가 발생한다. 따라서 컨벡스 헐로 볼록 다각형을 만들고, 다시 볼록 다각형을 포함하는 사각형을 만들자. 구현 PolygonInSquare.cs에서 아래의 내용을 추가한다. 기존의 함수랑 이름이 겹치기 때문에 함수 이름(ccwBy2D → ccw, compare → compare2)을 변경하였다. Vector3 findMinXZ(List position) { Vector3 min = .. 2022. 12. 28.
유니티 - 컨벡스 헐로 볼록 다각형을 만드는 점의 좌표 구하기 (Find Points that Make the Polygon with Convex Hull) Unity 전체 링크 참고 - 스택 - 비교 함수를 이용하여 리스트 정렬하기 - 임의의 다각형을 포함하는 사각형 구하기 - 볼록 껍질 (Convex Hull, Graham Scan) - 컨벡스 헐로 임의의 점을 모두 포함하는 사각형 구하기 아래와 같이 임의의 점이 불규칙하게 있다고 가정하자. 컨벡스 헐(그레이엄 스캔)을 이용하면 아래와 같이 모든 점을 포함하는 볼록 다각형을 만들 수 있다. 구현 구현은 BOJ 1708 - 볼록 껍질을 참고해서 C# 버전으로 만든다. 유니티에서는 (x, y)가 아니라 (x, z)에서 가장 작은 좌표를 먼저 찾는다. Vector3 findMinXZ(List position) { Vector3 min = new Vector3(100000, 0, 100000); foreach .. 2022. 12. 28.
BOJ 1708 : 볼록 껍질 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1708 참고 - 스택 - 머지 소트 - 컨벡스 헐로 볼록 다각형을 만드는 점의 좌표 구하기 - 컨벡스 헐로 임의의 점을 모두 포함하는 사각형 구하기 점의 좌표가 주어졌을 때, 볼록 다각형을 만드는 점의 개수를 구해보자. 볼록 다각형을 찾는 컨벡스 헐 알고리즘(Convex Hull Algorithm)은 스택을 이용한다. 먼저 주어진 점에서 가장 작은 (x, y) 좌표를 찾는다. for (int i = 0; i = a[i].y) // 가장 작은 y, x 좌표를 찾는다. { if (minXY.y == a[i].y) .. 2022. 12. 28.
BOJ 1935 : 후위 표기식2 알고리즘 문제 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/1935 참고 - 스택 - 괄호 - 후위 표기식 (중위 표기식을 후위 표기식으로 변경하기) - 중위 표기식 후위 표기식의 연산은 매우 간단하다. 다음의 규칙대로 구현하면 된다. 1. 숫자는 stack에 넣는다. 2. 연산자가 나오면 stack에서 숫자 두 개를 빼고 연산한 후, 결과를 다시 스택에 집어 넣는다. 이때, 처음 나온 숫자가 뒤에 있는 연산이 된다. ( - 연산자를 만나고 a가 먼저 나온 후 b가 나온다면 b - a가 된다.) 3. 위 과정을 모두 반복하고 스택에 남아 있는 숫자가 최종 연산 결과가 된다. 숫자(알파벳)와 연산자를 구분하기 위해 table 배열을 사용하여서 위의 내용을 구현한.. 2022. 12. 26.
BOJ 1918 : 후위 표기식 알고리즘 문제 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/1918 참고 - 스택 - 괄호 - 후위 표기식2 (후위 표기식 연산하기) - 중위 표기식 중위 표기법(infix)으로 주어진 식을 후위 표기법(postfix)으로 바꿔보자. 아래의 규칙대로 구현하면 중위 표기식을 후위 표기식으로 바꿀 수 있다. 1. stack이 비어있거나 열린 괄호 "(" 는 stack에 넣는다. 2. 열린 괄호 "(" 다음의 연산자는 stack에 넣는다. 3. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 큰 연산자는 넣는다. ( * = / > + = - ) 4. 현재 stack의 가장 위에 있는 연산자보다 우선순위가 낮은 연산자가 들어오려고 한다면, 스택이 비거나, 열린.. 2022. 12. 26.
유니티 - 3차원에서 두 직선 사이의 최단 거리를 만드는 직선 (How to Find the Points of Intersection Two Lines in 3D) Unity 전체 링크 참고 - 평면과 직선의 접점 좌표 구하기 - 튜플로 여러 값 반환하기 아래와 같이 빨간 직선과 파란 직선이 3차원 공간에 있을 때, 두 직선의 최단거리와 최단거리를 만드는 초록색 직선을 구해보자. 3차원에 있는 두 직선의 최단거리 두 직선의 최단거리 공식은 다음과 같다. 점 A, B가 만드는 직선과 점 C, D가 만드는 직선이 있을 때, 직선 AB의 점 하나(=A)와 직선 CD의 점 하나(=C)로 직선을 만들고 아래의 공식을 대입하면 거리를 구할 수 있다. 위의 공식 AC에서 A나 C가 아니더라도 각각 직선 AB와 직선 CD에 포함된 모든 점이 가능하다. 유니티에서는 아래와 같이 구현하면 된다. float getDistanceTwoLine(Vector3 A, Vector3 B, Ve.. 2022. 11. 26.
유니티 - 다각형 좌표의 시계 방향 판단하기 (How to Determine If a Polygon is Clocwise) Unity 전체 링크 참고 - 세 점을 지나는 평면 구하기 - 3차원 세 점의 좌표로 삼각형의 넓이 구하기 - Vector3.Cross로 평면 위에서 시계 방향 판단하기 다각형 좌표의 시계 방향 판단하기 = 다각형의 넓이 구하기 아래와 같이 별 모양의 다각형이 주어졌다고 가정하자. 점의 배치를 보면 시계방향으로 좌표가 정렬되어 있다. 처음 3개의 점은 시계 방향이다. 하지만 다음 3개의 점은 반시계 방향이다. 좌표를 볼 때, 시계 방향으로 배치하였지만, 점 3개씩 방향을 체크하면 시계 방향과 반시계 방향이 같이 존재한다. 즉, 점 3개씩 비교하는 것으로 좌표가 시계 방향인지 반시계 방향인지 판단할 수 없다. 좌표가 주어졌을 때 시계 방향인지, 반시계 방향인지 판단하는 함수를 만들어보자. Settings .. 2022. 11. 25.
반응형

티스토리툴바