반응형 스택12 괄호가 있는 중위 표기식 연산하기 삼성 C형 전체 링크 참고 - 스택 - 괄호 - Brainf**k 인터프리터 - 후위 표기식 - 중위 표기식 연산하기 중위 표기법 연산은 아래와 같다. 1. 숫자를 만나면 현재 숫자(cur)를 저장해둔다. 2. +, - 연산자가 나오면 temp에 현재의 숫자를 곱한다. (temp는 1로 초기화) 3. 그리고 result에 temp를 더한다. 4. *, / 가 나오면 temp에 값을 누적한다. 5. 이후 +, - 연산자가 나오면 2 ~ 3을 실행한다. 6. 모두 종료 후 남은 연산 실행 이때 괄호를 만나면 닫힌 괄호까지를 먼저 계산하고 temp로 변경한다. 그리고 괄호 연산이 끝난 경우는 다음 연산을 위해 cur = 1로 초기화 해야 한다. 괄호 내에서는 다시 중위 표기식이 될 것이기 때문에 위의 방법을 .. 2023. 7. 29. BOJ 5397 : 키로거 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/5397 참고 - BOJ 1406 : 에디터 - BOJ 5397 : 키로거 with 세그먼트 트리, 링크드 리스트 풀이는 BOJ 1406 : 에디터와 동일하므로 참고하자. 입력을 받는 방식과 문자열의 크기만 바꾸면 된다. #include int T; char str[1001000]; char stack1[1001000]; char stack2[1001000]; int sp1, sp2; int main(void) { scanf("%d", &T); for (int tc = 0; tc < T; tc++) { scanf("%s", str); int len; for (len = 0; str[len]; len++); sp1 = sp2.. 2023. 1. 18. 유니티 - 컨벡스 헐로 임의의 점을 모두 포함하는 사각형 구하기 (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. BOJ 3954 : Brainf**k 인터프리터 (A형 상시) 삼성 A형 전체 링크 www.acmicpc.net/workbook/view/2771 (상시 A형 문제집) www.acmicpc.net/problem/3954 명령어를 쉽게 판단하기 위해 아래와 같이 define하자. typedef unsigned char uc; #define MAX (50000000) #define DECREASE ('-') #define INCREASE ('+') #define POINTER_LEFT ('') #define POINTER_RIGHTJUMP ('[') #define POINTER_LEFTJUMP (']') #define OUTPUT ('.') #define READ_AND_SAVE (',') #define MODULO (256) 괄호의 짝을 찾는 방법은 BOJ 9012 .. 2021. 4. 21. BOJ 1406 : 에디터 알고리즘 문제 전체 링크 www.acmicpc.net/problem/1406 참고 - BOJ 5397 : 키로거 stack을 2개 이용하면 에디터의 문자열을 쉽게 관리할 수 있다. 먼저 초반에 abcd가 입력되었다고 하자. 커서는 바로 d의 옆에 존재한다. (sp1 = 4) → abcd| 이제 P e 명령어에 의해 e가 추가되었다고 하자. stack1의 크기를 늘려주면서 e를 넣어주면 된다. (sp1 = 5) stack1[sp1++] = 'e'; → abcde| 이제 L 명령어에 의해 왼쪽으로 옮긴다고 하자. 왼쪽으로 옮기는 것은, 문자열은 여전히 abcde 이지만 커서는 d 뒤에 위치하게 된다. 따라서 커서의 뒷부분을 stack2로 옮겨준다. (sp1 = 4, sp2 = 1) stack에서 가장 나중에.. 2021. 3. 15. 이전 1 2 다음 반응형
