본문 바로가기
반응형

알고리즘/BAEKJOON87

BOJ 14427 : 수열과 쿼리 15 with 세그먼트 트리 삼성 B형 전체 링크 https://www.acmicpc.net/problem/14427 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 10868 : 최솟값 - BOJ 14427 : 수열과 쿼리 15 with 우선순위 큐 BOJ 10868 : 최솟값을 관리할 때, 세그먼트 트리를 이용하였는데, 이 문제에서는 값이 변경되고, index도 같이 관리하면 된다. 따라서 tree는 아래의 구조체로 만들어진다. typedef struct st { int index; int value; }NODE; 같은 값인 경우는 index가 더 작은 값을 출력하기 위해.. 2023. 1. 19.
BOJ 1572, 9426 : 중앙값 측정 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1572 https://www.acmicpc.net/problem/9426 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 BOJ 1655 : 가운데를 말해요 with 세그먼트 트리에서 세그먼트 트리를 이용해 가운데 값을 찾았으므로, 이 방법을 이용해 중앙값을 측정해보자. 주어지는 숫자가 0 ~ 65535이기 때문에 65536 * 2개의 tree가 필요하다. 또한 세그먼트 트리는 index가 1로 시작하도록 구현을 .. 2023. 1. 19.
BOJ 1655 : 가운데를 말해요 with 세그먼트 트리 알고리즘 문제 전체 링크 삼성 B형 전체 링크 삼성 C형 전체 링크 www.acmicpc.net/problem/1655 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 우선순위 큐 - 세그먼트 트리를 이용한 링크드 리스트의 삽입과 삭제 세그먼트 트리를 이용해 가운데 값을 찾아보자. 세그먼트 트리를 이용하면 index를 잘 관리해서 중앙값을 구할 수 있다. 설명을 위해 입력되는 숫자의 범위가 1 ~ 16이라고 가정하자. 그러면 아래와 같은 트리를 만들어야 한다. (파란색 숫자는 tree의 index) 아래의 배열.. 2023. 1. 19.
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.
BOJ 2357 : 최솟값과 최댓값 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2357 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 10868 : 최솟값 BOJ 10868에서 답을 구한 방법으로 최솟값을 구할 수 있고, 응용하면 최댓값도 구할 수 있다. 따라서 세그먼트 트리를 2개 이용하면 된다. 하지만 구조체로 묶으면 조금 더 간편하다. TREE 라는 구조체를 선언해서 min과 max를 동시에 관리한다. typedef struct st { int min; int max; }TREE; init에는 leftTree와 rightTree에서 각각.. 2023. 1. 16.
BOJ 10868 : 최솟값 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/10868 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 2357: 최솟값과 최댓값 세그먼트 트리의 노드에 저장된 값은 아래 두 노드 중 작은 값이어야 한다. isMin 함수를 이용하여 더 작은 값을 판단하여 init을 하면서 tree에 저장한다. int isMin(int a, int b) { return (a < b) ? a : b; } int init(int left, int right, int node) { if (left == right) return tre.. 2023. 1. 16.
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.
반응형

티스토리툴바