본문 바로가기
반응형

알고리즘/BAEKJOON88

BOJ 12015 : 가장 긴 증가하는 부분 수열 2 알고리즘 문제 전체 링크삼성 B형 전체 링크 https://www.acmicpc.net/problem/12015 참고- BOJ 1655 : 가운데를 말해요 with 세그먼트 트리  수열 A의 크기는 1,000,000이고 들어 있는 값은 1부터 1,000,000이므로 세그먼트 트리를 이용해서 문제를 풀 수 있다. 예제의 {10, 20, 10, 30, 20, 50}에서가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)의 길이 4를 찾아보자. 수열에 값이 하나가 추가될 때마다, LIS의 길이를 세그먼트 트리를 이용해서 갱신하면 문제를 풀 수 있다.값 x가 추가되고, 구간 [1, x - 1]의 LIS의 길이가 y라면 구간 [1, x]의 LIS의 길이는 y + 1이 된다.. 2024. 12. 20.
BOJ 2338 : 긴자리 계산 알고리즘 문제 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/2338 참고 - BOJ 10757 : 큰 수 A+B - BOJ 10757 : 큰 수 A+B with 10^N진법 - BOJ 2338 : 긴자리 계산 - BOJ 2338 : 긴자리 계산 with 10^N진법 - 36진법 긴자리 두 수의 곱셈 - 36진법 긴자리 두 수의 곱셈 with 36^5진법 - 36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input 부호가 포함된 A, B의 덧셈, 뺄셈, 곱셈을 해보자. 10진수로 1,000자리가 주어지며, 곱셈 연산에 의해 최대 자릿수는 2,000이다. 큰 수의 정의 큰 수를 정의하기 위해 char 배열, 문자열의 길이, 그리고 부호를 가지는 .. 2023. 7. 29.
BOJ 10757 : 큰 수 A+B 알고리즘 문제 전체 링크 삼성 C형 전체 링크 https://www.acmicpc.net/problem/10757 참고 - BOJ 10757 : 큰 수 A+B - BOJ 10757 : 큰 수 A+B with 10^N진법 - BOJ 2338 : 긴자리 계산 - BOJ 2338 : 긴자리 계산 with 10^N진법 - 36진법 긴자리 두 수의 곱셈 - 36진법 긴자리 두 수의 곱셈 with 36^5진법 - 36진법 긴자리 두 수의 곱셈 with 36^5진법 + Fast Input 큰 수의 덧셈은 3가지 방법으로 가능하다. 1. 더 짧은 자리 앞에 긴 자리 수 만큼 '0'을 추가하고 더하기 2. 문자열을 뒤집고 계산한 후, 다시 뒤집기 3. int로 변경한 후, 뒤집고, 다시 뒤집은 후, char로 변경하기 .. 2023. 7. 29.
BOJ 7453 : 합이 0인 네 정수 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/7453 참고 - 머지 소트 Merge Sort 합이 0이 되는지 확인하기 위해 4000 x 4000 x 4000 x 4000의 경우의 수를 모두 확인하는 것은 비용이 너무 많이 든다. 따라서 A와 B의 합인 AB 배열 (16,000,000)과 C와 D의 합인 CD 배열(16,000,000)을 만든다. 그리고 AB 배열의 값이 x라면 CD에서 -x가 되는 경우를 찾으면 된다. 이 경우 이분 탐색으로 log(16,000,000) ≒ 24번 만에 답을 찾을 수 있게 된다. 물론 이분 탐색을 위해 배열을 머지 소트로 정렬하였다. 구현 입력을 받은 후, AB, CD 배열을 만든다. idx = 0; for (int i = 0; i .. 2023. 4. 7.
BOJ 1991 : 트리 순회 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1991 참고 - 링크드 리스트 Linked List 링크드 리스트를 이용하여 간단히 트리를 만들 수 있다. 노드에 포인터를 2개 사용하면 트리가 된다. typedef struct st { char value; struct st *left; struct st *right; }NODE; NODE node['Z' + 1]; 각 노드에 value를 해당 알파벳으로 설정한다. for (int i = 'A'; i value); preorder(nd->left); preorder(nd->right); } void inorder(NODE *nd) // 중위 순회 { if (nd == NULL) return; inorder(nd->lef.. 2023. 4. 7.
BOJ 6593 : 상범 빌딩 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/6593 참고 - BOJ 11779 : 최소비용 구하기 2 최단 경로는 BOJ 11779 : 최소비용 구하기 2에서 사용한 다익스트라를 이용해서 구할 수 있다. 상범 빌딩은 다익스트라를 3차원에 적용하면 된다. tc가 여러 개이므로 매 tc마다 dist를 INF로 visit을 0으로 초기화한다. for (i = 1; i 2023. 3. 26.
BOJ 1504 : 특정한 최단 경로 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1504 참고 - BOJ 11779 : 최소비용 구하기 2 최단 경로는 BOJ 11779 : 최소비용 구하기 2에서 사용한 다익스트라를 이용해서 구할 수 있다. 이 문제에서는 임의의 두 정점(n1, n2)을 통과하는 최단 경로를 구하려고 하므로, 다익스트라를 여러 번 사용하면 된다. 즉, 출발점 - n1 - n2 - 도착점에 대해 각각 다익스트라를 이용해 거리를 구한다. 여기서 n1이 반드시 n2 보다 먼저 도착해야할 이유는 없다. n1 - n2와 n2 - n1 경로를 비교해서 더 작은 경우가 정답이 된다. ans1 = getDijkstra(1, n1) + getDijkstra(n1, n2) + getDijkstra(n2,.. 2023. 3. 25.
BOJ 12899 : 데이터 구조 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/12899 참고 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 우선순위 큐 - BOJ 1168 : 요세푸스 문제 2 BOJ 1168 : 요세푸스 문제 2와 마찬가지로 세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다. 찾은 값은 update를 이용해 다시 삭제하면 된다. #include int N; int tree[4194304]; int start, leafSize; void update(int index, int diff) { index += start; while (index > 1) { tree[ind.. 2023. 3. 4.
BOJ 1168 : 요세푸스 문제 2 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/1168 참고 - BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제 - 구간 합 구하기 with 바텀 업 세그먼트 트리 (Bottom-Up Segment Tree) - BOJ 1655 : 가운데를 말해요 with 우선순위 큐 큐(Queue)를 사용하는 BOJ 11866, 1158 : 요세푸스 문제 0, 요세푸스 문제보다 N이 매우 큰 경우다. 세그먼트 트리에서 n번째 값을 찾는 방식으로 문제를 해결할 수 있다. N이 100,000이고, 100,000보다 2배 이상 큰 2의 배수는 262,144이다. 따라서 tree의 사이즈는 다음과 같다. int tree[262144]; 이제 N보다 큰 2의 배수를 구해보자.. 2023. 3. 4.
반응형

티스토리툴바