Algorithm (23) 썸네일형 리스트형 [C++] 백준 2042 구간 합 구하기 [!NOTE]세그먼트 트리 자료 구조에 대한 설명을 보려면 다음 포스트 참조: 세그먼트 트리 (Segment Tree) - C/C++로 설명세그먼트 트리는 구간 합이나 최소값, 최대값을 구하는 데 유용한 자료구조이다. 특히 데이터가 자주 업데이트되면서도 특정 구간의 값을 빠르게 조회해야 하는 문제에서 큰 효율성을 제공한다. 이번 글에서는 백준 온라인 저지의 2042번 문제, 구간 합 구하기를 통해 세그먼트 트리를 구현하고 문제를 해결하는 과정을 설명한다.문제 설명N개의 수가 주어질 때, 중간에 특정 수를 변경하면서 주어진 구간의 합을 빠르게 구하는 문제이다.예제 입력 설명1부터 5까지의 수가 주어지고, 3번째 수를 6으로 바꾸고 2번째부터 5번째까지의 합을 구하라고 한다면 결과는 17이 된다. 그 상태에.. Solved.ac: 알고리즘 문제 풀이를 위한 필수 사이트 Solved.ac는 백준 온라인 저지(BOJ)를 기반으로 알고리즘 문제 풀이를 보다 효율적으로 할 수 있도록 도와주는 서비스이다. 백준은 국내에서 가장 많은 알고리즘 문제를 제공하는 사이트로 유명한데, Solved.ac는 이러한 문제들을 효율적으로 정리하고 난이도, 추천 문제 등을 제공해 사용자가 학습 목표를 체계적으로 세울 수 있도록 도와준다.그리고 재미있는 사실 하나! 이 훌륭한 서비스를 만든 사람이 바로 내 직속 선배이신 서강대 컴퓨터공학과 박수현님 이라는 점이다.처음에 베타 버전으로 시작했을 때만 해도 이렇게 커질 줄은 몰랐는데, 이제는 아예 회사를 차리고 대표님이 되셨다.Solved.ac의 주요 기능Solved.ac는 문제 풀이를 시작하는 초보자부터 고급 알고리즘 문제를 도전하는 상급자까지 모두.. 알고리즘 시간 복잡도 계산하기: 효율성을 높이자! 시간 복잡도(Time Complexity)는 알고리즘이 문제를 해결하는 데 걸리는 시간을 수학적으로 표현한 것으로, 입력의 크기에 따라 실행 시간이 어떻게 증가하는지 나타낸다. 이 시간 복잡도 계산은 효율적인 알고리즘을 설계하고, 문제의 제약 조건에 맞게 최적의 접근을 찾기 위한 핵심적인 과정이다.이번 글에서는 시간 복잡도를 계산하는 기본 개념과 방법을 설명하고자 한다.시간 복잡도를 왜 계산해야 할까?시간 복잡도를 계산하는 것은 알고리즘의 효율성을 예측하기 위해 중요하다. 시간 제한이 있는 프로그래밍 문제에서, 알고리즘이 제한 시간 내에 문제를 해결할 수 있을지 판단하려면 시간 복잡도를 알고 있어야 한다.시간 복잡도를 표현하기 위해 O 표기법(Big-O Notation), Θ 표기법(Theta Notat.. 프로그래밍 문제 해결을 위한 가이드: 접근법, 자료 구조, 시간 복잡도 분석까지 프로그래밍 문제 해결을 위한 접근법프로그래밍 문제 해결 능력(PS, Problem Solving)은 여러 분야에서 유용하며, 특히 컴퓨터 과학과 관련된 학문이나 직무에서 필수적이다. 문제를 푸는 데 필요한 자료 구조와 알고리즘, 그리고 제한 조건을 이해하고 이를 코드로 구현하는 것이 중요한데, 여기에는 몇 가지 핵심 과정이 있다. 이번 글에서는 문제 해결에 필요한 다양한 접근 방식과 대회 및 학습 자료들을 소개한다.문제 해결 실력을 쌓아가는 5단계 비법프로그래밍 문제를 푸는 과정은 마치 보물찾기 같다. 처음에는 막막할 수 있지만 단계를 따라가다 보면 어느새 보물에 가까워진다. 하나하나 단계를 살펴보자.1. 문제를 정확히 이해하기문제를 마주하면 일단 목표부터 확실히 잡아야 한다. 입력과 출력 형식부터 제한.. [C] 백준 2268 수들의 합 7 https://www.acmicpc.net/problem/2268문제 분석 및 접근 방식문제에서 요구하는 것은 배열 A에 대해 두 가지 연산을 효율적으로 처리하는 것이다:Sum(i, j): 배열의 A[i]부터 A[j]까지의 합을 구하는 연산.Modify(i, k): 배열의 A[i]를 k로 업데이트하는 연산.제약 조건에 따르면 배열의 크기(N)와 연산 횟수(M) 모두 최대 1,000,000으로, 최악의 경우 Sum과 Modify 연산을 모두 포함하여 최대 백만 번의 연산을 수행해야 한다. 단순히 모든 구간을 반복하며 합을 구하거나, 각 Modify 연산에 대해 배열을 새로 갱신하면 시간 초과가 발생할 가능성이 높다.따라서 구간 합과 부분 배열 업데이트를 모두 빠르게 수행할 수 있는 자료 구조가 필요하다. .. [C++] 백준 6603 로또 6603 로또 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net (1) 일반적 풀이 C++ // // Created by SangWon Kang on 2020/09/04. // Copyright © 2020 SangWon Kang. All rights reserved. // #include using namespace std; typedef long long ll; typedef vector vi; typedef pair pii; typedef vector vpii; #define INF 987654.. [C++] 백준 15650 N과 M (2) 15650 N과 M (2) 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net C++ // // Created by SangWon Kang on 2020/09/04. // Copyright © 2020 SangWon Kang. All rights reserved. // #include using namespace std; typedef long long ll; typedef vector vi; typedef pair pii; typedef vector vpii; #define INF 987654321 #defin.. 세그먼트 트리 (Segment Tree) - C/C++로 설명 세그먼트 트리(Segment Tree)는 효율적으로 구간합이나 최소값, 최대값을 구하는 데 매우 유용한 자료구조이다. 특히, 데이터가 자주 업데이트되면서도 특정 구간의 값을 빠르게 조회해야 하는 상황에서 효과적이다. 다음은 세그먼트 트리의 기본 개념과 사용법을 예제를 통해 정리한 내용이다.세그먼트 트리 - 쓰임새세그먼트 트리는 연속적인 데이터가 있을 때, 특정 범위의 합/ 최소, 최대값 등을 구할 때 유용하게 활용될 수 있다.특정 구간의 합을 구하는 방법에 대해 살펴보자면, 일반적으로 다음과 같은 방법이 떠오른다.. 1. $arr[l] + arr[l+1] + ... + arr[r-1] + arr[r]$을 일일히 더해 구하는 방법 2. $i$번째까지의 합을 저장하는 배열을 하나 더 만들어서, 조금 더.. [C/C++] 백준 11092 Safe Passage 11092 Safe Passage 11092번: Safe Passage A group of friends snuck away from their school campus, but now they must return from the main campus gate to their dorm while remaining undetected by the many teachers who patrol the campus. Fortunately, they have an invisibility cloak, but it is only lar www.acmicpc.net C++ #include #include #include using namespace std; vector list; int DP (int e) { if(.. [C/C++] 백준 14501 퇴사 14501 퇴사 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 마지막 날부터 거꾸로 생각하면 풀기 쉬워진다. DP[i]: n 번째 날부터 i 번째 날까지 일했을 때 얻는 최대 이익. DP[i]는 두 가지 경우로 나눌 수 있는데, i 번째 날에 잡힌 상담을 하는 경우와 그렇지 않은 경우이다. i 번째 날에 잡힌 상담을 하지 않는 경우: DP[i] = DP[i + 1]과 같다 할 수 있다. i 번째 날에 잡힌 상담을 하는 경우: DP[i] = DP[ i + (i 번째 날에 잡힌 상담 일수)] + (i 번째 날에 잡힌 상담의 금액) 이때 i + (i 번째 잡힌 상담 일수)가 n+1을 넘으면 일을 할 수 없으므로 예외 처리를 해준다. C #include.. [C/C++] 백준 12865 평범한 배낭 12865 평범한 배낭 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net C #include #define MAX(a, b) (((a) > (b)) ? (a) : (b)) int DP[103][100003]; int w[103]; int v[103]; int main() { int n, k; scanf("%d %d", &n, &k); for (int i = 1; i n >> k; for (int i = 1; i > w[i] >> v[i]; for .. [C++] 백준 2482 색상환 2482 색상환 2482번: 색상환 첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다. www.acmicpc.net C++ #include #include #include using namespace std; #define MOD 1000000003 int DP[1003][1003]; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, k; cin >> n >> k; for (int i = 0; i 이전 1 2 다음
