본문 바로가기

728x90
SMALL

분류 전체보기

(443)
백준 15624번 [피보나치 수 7](C++)-yes6686- 티스토리 백준 문제 풀이: 15624 [피보나치 수 7]문제 링크: https://www.acmicpc.net/problem/15624문제 설명:n번째 피보나치 수를 구하는 문제로, 결과를 1,000,000,007로 나눈 나머지를 출력합니다. 피보나치 수의 정의는 다음과 같습니다:F(0) = 0F(1) = 1F(n) = F(n-1) + F(n-2) (n ≥ 2)문제 해결 코드#include #define MOD 1000000007using namespace std;long long int dp[1000001];int main() { int n; cin >> n; dp[0] = 0; dp[1] = 1; for (int i = 2; i 코드 설명핵심 알고리즘: 동적 프로그래밍을 활용하여 피..
백준 9019번 [DSLR](C++)-yes6686- 티스토리 백준 문제 풀이: 9019 [DSLR]문제 링크: https://www.acmicpc.net/problem/9019문제 설명:주어진 정수 A를 B로 변환하기 위해 네 가지 연산(D, S, L, R)을 사용합니다. 각 연산은 다음과 같습니다:D: 2를 곱한 결과를 10000으로 나눈 나머지S: A에서 1을 뺀 결과 (A가 0이면 9999)L: A의 각 자릿수를 왼쪽으로 회전R: A의 각 자릿수를 오른쪽으로 회전A를 B로 변환하는 가장 짧은 명령어를 출력하는 문제입니다. 여러 가지 방법이 있을 경우 사전 순으로 가장 앞서는 결과를 출력합니다.문제 해결 코드#include #include #include #include using namespace std;queue> q;int visited[10001];in..
백준 9095번 [1, 2, 3 더하기](C++)-yes6686- 티스토리 백준 문제 풀이: 9095 [1, 2, 3 더하기]문제 링크: https://www.acmicpc.net/problem/9095문제 설명:정수 n(1 ≤ n ≤ 10)이 주어졌을 때, 1, 2, 3의 합으로 n을 만들 수 있는 모든 방법의 수를 구하는 문제입니다. 각 숫자는 여러 번 사용될 수 있습니다.문제 해결 코드#include using namespace std;int dp[10];int main() { int T; cin >> T; int n; // 초기값 설정 dp[1] = 1; dp[2] = 2; dp[3] = 4; // 동적 프로그래밍으로 dp 배열 계산 for (int i = 4; i > n; cout 코드 설명핵심 알고리즘: 동..
백준 1463번 [1로 만들기](C++)-yes6686- 티스토리 백준 문제 풀이: 1463 [1로 만들기]문제 링크: https://www.acmicpc.net/problem/1463문제 설명:정수 n이 주어졌을 때, n을 1로 만들기 위해 사용하는 연산의 최소 횟수를 구하는 문제입니다. 사용할 수 있는 연산은 다음과 같습니다:n이 3으로 나누어떨어지면, n을 3으로 나눕니다.n이 2로 나누어떨어지면, n을 2로 나눕니다.1을 뺍니다.문제 해결 코드#include using namespace std;int dp[1000001];int main() { int n; cin >> n; dp[1] = 0; for (int i = 2; i 코드 설명핵심 알고리즘: 동적 프로그래밍을 이용하여 최소 연산 횟수를 계산합니다.구현 세부사항:dp[i]는 i를 1로..
백준 1849번 [순열](C++)-yes6686- 티스토리 백준 문제 풀이: 1849 [순열]문제 링크: https://www.acmicpc.net/problem/1849문제 설명:길이가 n인 배열의 각 요소는 그 배열의 인덱스 값보다 크거나 같은 위치로 이동해야 합니다. 주어진 배열을 기반으로 순열을 만들어야 하며, 이 과정에서 세그먼트 트리를 활용해 효율적으로 해결합니다.문제 해결 코드#include using namespace std;int arr[100001];int ans[100001];int tree[400001];int init(int n, int s, int e) { if (s == e) { return tree[n] = 1; } return tree[n] = init(2 * n, s, (s + e) / 2) + ini..
백준 1777번 [순열복원](C++)-yes6686- 티스토리 백준 문제 풀이: 1777 [순열복원]문제 링크: https://www.acmicpc.net/problem/1777문제 설명:길이가 n인 순열이 주어질 때, 순열을 복원하는 문제입니다. 주어진 입력은 각 순열의 원소가 올바른 위치에 들어가기 위해 필요한 남은 빈자리의 개수를 의미합니다. 세그먼트 트리를 사용하여 효율적으로 순열을 복원합니다.문제 해결 코드#include using namespace std;int arr[100001];int ans[100001];int tree[400001];int init(int n, int s, int e) { if (s == e) { return tree[n] = 1; } return tree[n] = init(2 * n, s, (s + ..
백준 1517번 [버블 소트](C++)-yes6686- 티스토리 백준 문제 풀이: 1517 [버블 소트]문제 링크: https://www.acmicpc.net/problem/1517문제 설명:버블 소트 알고리즘으로 주어진 배열을 정렬할 때, 몇 번의 swap이 발생하는지 계산하는 문제입니다. 단순히 O(n²)의 버블 소트를 구현하는 대신, 세그먼트 트리를 사용해 효율적으로 해결합니다.문제 해결 코드#include #include #include using namespace std;vector> arr;int tree[2000001];int init(int n, int s, int e) { if (s == e) { return tree[n] = 1; } return tree[n] = init(2 * n, s, (s + e) / 2) + in..
백준 2243번 [사탕상자](C++)-yes6686- 티스토리 백준 문제 풀이: 2243 [사탕상자]문제 링크: https://www.acmicpc.net/problem/2243문제 설명:사탕 상자에 여러 가지 맛의 사탕이 있으며, 이 사탕들을 꺼내거나 추가할 수 있는 기능을 제공합니다. 사탕 상자는 총 1,000,000개의 칸으로 이루어져 있으며, 각 칸에 사탕이 들어 있습니다. 두 가지 작업을 수행합니다:맛의 순서에 따라 사탕을 꺼내는 작업특정 맛의 사탕을 추가하는 작업문제 해결 코드#include using namespace std;int arr[1000001];int tree[4000001];int query(int n, int s, int e, int d) { if (s == e) return e; if (tree[2 * n] >= d) { ..

728x90
LIST