본문 바로가기
반응형

알고리즘/BAEKJOON87

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.
BOJ 2042 : 구간 합 구하기 with 다이나믹 세그먼트 트리 (Dynamic Segment Tree) 알고리즘 문제 전체 링크 https://www.acmicpc.net/problem/2042 참고 - 구간 합 구하기 with 탑 다운 세그먼트 트리 (Top-Down Segment Tree) - 메모리 풀 Memory Pool - 메모리 풀 vs malloc 속도 비교 - 링크드 리스트 Linked List 이전 글에서는 tree의 크기를 넉넉하게 잡았다. 구간의 길이가 100만이기 때문에 실제로는 2배 정도의 크기만 있으면 된다. 여기서는 필요한 만큼만 적절히 잡아서 다이나믹하게 트리를 만들어보자. 배열의 index를 이용하는 방법 원래 update 코드는 아래와 같다. void update(int left, int right, int node, int index, ll value) { if (inde.. 2023. 2. 8.
반응형

티스토리툴바