분류 전체보기103 [백준 C++] 2042번: 구간 합 구하기 1. 문제https://www.acmicpc.net/problem/2042 2. 알고리즘 분류자료 구조세그먼트 트리 3. 소스 코드#include #define MAX_N 1000006using namespace std;typedef long long ll;int N, M, K;ll arr[MAX_N];ll tree[4 * MAX_N];// Segment Tree 생성 함수ll init(int node, int start, int end) { // leaf node인 경우, if (start == end) return tree[node] = arr[start]; int mid = (start + end) / 2; int child_node1 = 2 * node; int child_node2 = 2 * n.. 2024. 9. 13. [자료구조] Segment Tree(세그먼트 트리) 1. Segment Tree(세그먼트 트리) Segment Tree(세그먼트 트리)는 배열 간격에 대한 정보를 이진 트리에 저장하는 자료구조입니다. Segment Tree를 도식화하면, 아래와 같습니다. Segment Tree는 다양한 활용법이 있겠지만, 특히 특정 데이터 배열의 구간 합을 계산할 때 유용합니다. 아래 예시를 통해, 단순 배열 방법과 Segment Tree 활용법을 비교해보겠습니다. 예시 1) 단순 배열 방법 array = {1, 2, 3, ..., N} 배열에서 특정 범위의 구간 합과 특정 인덱스의 값 변경을 M번 수행 (1) array 배열에서 1번째 ~ N번째까지 구간 합 연산S = array[0] + array[1] + array[2] + ... + array[N - 1]시간 복.. 2024. 9. 12. [알고리즘] 파스칼 삼각형을 활용한 조합 계산 1. 파스칼 삼각형 2. 소스 코드(C++)int Combination[53][53];// 조합 계산 함수int cal_combination(int n, int r) { if (Combination[n][r]) return Combination[n][r]; // 이전에 계산해놓은 값이 있으면, 바로 반환 else if (n == r || r == 0) Combination[n][r] = 1; // n=r 이거나, r = 0일 때, 1 반환 else { Combination[n][r] = cal_combination(n - 1, r) + cal_combination(n - 1, r - 1) % MOD; // nCr = n-1Cr + n-1Cr -1 } return Combination[n][r];} 2024. 9. 5. [백준 C++] 16565번: N포커 1. 문제https://www.acmicpc.net/problem/16565 2. 알고리즘 분류수학다이나믹 프로그래밍조합론포함 배제의 원리 3. 소스 코드#include #define MOD 10007using namespace std;int N;int Combination[53][53];// 조합 계산 함수int cal_combination(int n, int r) { if (Combination[n][r]) return Combination[n][r]; // 이전에 계산해놓은 값이 있으면, 바로 반환 else if (n == r || r == 0) Combination[n][r] = 1; // n=r 이거나, r = 0일 때, 1 반환 else { Combination[n][r] = cal_com.. 2024. 9. 5. [React GitHub 배포] React 웹 사이트 GitHub Pages에 배포하기 1. GitHub Pages 생성 1) Git Repository에서 [Settings] - [Pages]로 이동 2) Branch에서 [None] 클릭한 후, "main" 선택 3) [Save] 클릭 4) 몇 분 후, [GitHub Pages]에서 생성된 사이트 주소 확인 2. gh-pages 패키지 설치 및 세팅 1) gh-pages 패키지를 설치npm install gh-pages 2) package 설치한 후, package.json 파일의 script 부분 내용 추가 "scripts": { ..., "predeploy": "npm run build", "deploy": "gh-pages -d build" }, 3) package.json 파일 상단에 "homepage" 추가{.. 2024. 8. 4. [Day 001] 알파벳 현대의 거의 모든 알파벳은 4000년 전 고대 이집트인이 노예와 의사소통을 하기 위해 상형문자를 간단하게 변형해서 만든 기호 체계에서 파생했다고 언어학자들은 추정한다. 기원전 2000년경 고대 이집트 왕들은 한 가지 고민을 가지고 있었다. 수많은 노예들은 이집트인이 사용하는 상형문자를 읽지 못했기 때문에 그들에게 서면으로 명령을 내릴 수 없었던 것 이다. 이를 해결하기 위해 기존의 상형문자를 간단하게 변형하여 독특한 기호 체계를 만들었고, 이것이 점점 발전하여 알파벳 체계가 만들어졌다. 간소화된 새로운 표기 체계는 하나의 문자가 하나의 소릿값을 나타냈다. 이것이 알파벳 체계이다. 표기 방식의 획기적 변화로 문자의 수는 수천에서 수십으로 줄었고, 이로 인해 문자를 배우고 사용하는 일이 훨씬 쉬워졌다. .. 2024. 8. 4. [백준 C++] 15824번: 너 봄에는 캡사이신이 맛있단다 1. 문제https://www.acmicpc.net/problem/15824 2. 알고리즘 분류수학정렬조합론분할 정복을 이용한 거듭제곱 3. 소스 코드#include #include #define MAX_N 300000using namespace std;typedef long long ll;ll scovile[MAX_N];ll MOD = 1000000007;// binary exponentiation 알고리즘ll binpow(ll a, ll b) { ll res = 1; while (b) { if (b & 1) res = (res * a) % MOD; a = (a * a) % MOD; b >>= 1; } return res;}int main() { ios_base::sync_with_stdio(fa.. 2024. 6. 15. [백준 C++] 13334번: 철로 1. 문제https://www.acmicpc.net/problem/13334 2. 알고리즘 분류자료 구조정렬스위핑우선순위 큐 3. 소스 코드#include #include #include #include using namespace std;int N, d, ret;vector> pos;priority_queue, greater> pq;bool cmp(pair a, pair b) { if (a.second == b.second) { return a.first > N; // 집과 사무실 거리 입력 for (int i = 0; i > h >> o; if (h > o) swap(h, o); pos.push_back({ h, o }); } // d : 철로의 길이 cin >> d; // end 거리 기준으로.. 2024. 6. 9. [백준 C++] 14725번: 개미굴 1. 문제https://www.acmicpc.net/problem/14725 2. 알고리즘 분류자료 구조문자열트리트라이 3. 소스 코드#include #include #include #include #include using namespace std;int N, K;struct Trie { map m; // 트라이 삽입 함수 void insert(vector& v, int idx) { // 삽입할 vector 인덱스 넘었을 경우, Return if (idx == v.size()) return; // 새 트라이 할당 및 추가 if (m.find(v[idx]) == m.end()) { Trie* trie = new Trie.. 2024. 6. 9. [백준 C++] 2533번: 사회망 서비스(SNS) 1. 문제https://www.acmicpc.net/problem/2533 2. 알고리즘 분류다이나믹 프로그래밍트리트리에서의 다이나믹 프로그래밍 3. 소스 코드#include #include #include #define MAX_N 1000006using namespace std;int N;vector graph[MAX_N];int dp[MAX_N][2]; // dp[x][y] = x번 노드가 0(얼리 아답터) 또는 1(일반인) 경우,bool visited[MAX_N];void dfs(int cur){ visited[cur] = true; dp[cur][0] = 1; // 얼리 아답터인 경우 1 // 1. 현재 노드가 0(얼리 아답터)인 경우, dp[현재 노드][얼리 아답터] += min(dp[다.. 2024. 6. 6. 이전 1 2 3 4 ··· 11 다음
