본문 바로가기

전체 글186

[C/C++] 백준 2775, Dynamic Programming 2775번: 부녀회장이 될테야 (acmicpc.net) 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net #include #include #include using namespace std; int compute(int k, int n) { int B[2][15]; int tod = 0; //현재층 (i-1층) int tom = 1; //다음 층 (i층) for (int i = 0; i 2022. 12. 10.
[C/C++] 백준 1463, Dynamic programming 1463번: 1로 만들기 (acmicpc.net) 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net * memoization이 아닌 recursive call을 사용하면 시간초과입니다. #include #include #include using namespace std; int min3(int a, int b, int c) { if (a < b && a < c) return a; else if (b < c) return b; else return c; } int make_one(int n) { vector arr(n + 1); int a = n; int b = n; int c = n; arr[1] = 0; for (int i.. 2022. 12. 10.
[C/C++] 백준 11047, Greedy 문제 11047번: 동전 0 (acmicpc.net) 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 코드1 #include #include #include #include using namespace std; int main() { int n, k; int t; int m = 0; vector arr, cnt; //arr:동전의 액면가, cnt: 동전의 개수 scanf("%d %d", &n, &k); for (int i = 0; i < n; i+.. 2022. 12. 10.
[C/C++] 백준 2839, Greedy 2839번: 설탕 배달 (acmicpc.net) 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net #include #include using namespace std; int main() { int n; int a, b; scanf("%d", &n); //2. a는 쓸 수 있는 최대 갯수의 5kg짜리 봉지의 수/ b=0 a = n / 5; b = 0; while (a >= 0) { //남은 무게: 전체 무게 - 5kg으로 만들 수 있는 무게 //n-5*a if ((n - 5 * a) % 3 == 0) { b = (n - .. 2022. 12. 10.
[C/C++] 백준 1012, DFS 1012번: 유기농 배추 (acmicpc.net) 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net strategy 1. connected component를 찾는 문제입니다 (1) cc_cnt라는 변수를 생성하여 connecte component를 탐색합니다 2. map[1000][1000]배열에 배추의 위치를 표시합니다 (1) 배추가 있는 곳=1 (2) 배추가 없는 곳=0 3. 배추A와 인접한 배추는 해당 배추A의 상, 하, 좌, 우에 위치한 것입니다 (1) 상, 하, 좌, 우는 x좌표 또는 y좌표에 1을 더하거나 뺀 .. 2022. 12. 9.
[C/C++] 백준 1260, DFS BFS 1260번: DFS와 BFS (acmicpc.net) 1260번: DFS와 BFS 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사 www.acmicpc.net #include #include #include #include #include using namespace std; vector edge[10001];//DFS와 BFS에서 같이 사용할 자료구조 int visit[10001];//DFS와 BFS에서 같이 사용할 자료구조 void initVisit(){//방문 기록을 0으로 초기화하는 함수 for(int i=0;i 2022. 12. 9.
[알고리즘] Greedy algorithm (1) - Optimal solution, Kruskal, Prim [1. Greedy algorithm] 1. greedy algorithm → 단계마다 한 번에 하나의 입력을 고려하되, 그 단계별로 최적의 선택을 하는 것 → 항상 최적의 결과를 도출하는 것은 아님, 다만 최적의 근사치를 도출할 수 있음 2. Minimum cost of spanning tree → 가중치그래프의 spanning tree에서 가중치의 합이 가장 적은 탐색방법 모색 → cycle 비허용 → Solution : 모든 개체들을 연결하기 → constraint : 개체가 n개 존재한다면, 최대 n-1개의 간선을 사용하기 → Feasible solution : 최대 n-1개의 간선을 사용해서 모든 개체들을 연결하기 → objective function : 사용하는 간선의 가중치 합을 최소화하기 .. 2022. 12. 9.
[알고리즘] Graph (5) - Breadth first search(BFS) [5. BFS, 너비우선탐색] 1. BFS (1) BFS 기본 전략 → vertex v를 방문할 시 → 인접한 모든 vertex를 방문한 것으로 표시 → queue에 vertex를 추가 → BFS 구현 #include #include #include #include using namespace std; vector edge[10001]; bool visit[10001]; void initVisit() { for (int i = 0; i < 10001; i++) visit[i] = 0; } void BFS(int s) { queue q; int u; q.push(s); visit[s] = 1; while (!q.empty()) { u = q.front(); q.pop(); printf("%d ", u); .. 2022. 12. 8.
[알고리즘] Graph (4) - Biconnected Components(BCC) [4. Biconnected components, 이중연결 구성요소] 1. Articulation point, 분절점 → 어느 무방향그래프의 한 vertex를 제거했을 때, 그 vertex를 제거함으로써 적어도 두 개의 connected components가 생긴다면, 그 제거된 vertex는 분절점이다. Ex) (1) vertex C 제거 => 두 개의 connected components => 따라서 C는 분절점 (2) vertex G 제거 => 두 개의 connected components => 따라서 G는 분절점 2. Biconnected graph → 분절점이 없는 무방향그래프 3. Biconnected component → Biconnected graph의 최대 서브 그래프 (각각의 서브그래프.. 2022. 12. 6.
[알고리즘] Graph (3) - Strongly connected components(SCC) [3. Strongly connected conponents] 1. 방향그래프의 연결관계 connected → 방향 그래프에서 노드 v와 노드 u가 서로에게 도달할 수 있는 경로가 존재할 때, 두 노드는 연결되어 있는 상태 2. SCC 집합 → 개체들을 상호 연결 관계에 따라 개체끼리 집합으로 분류 → SCC내의 모든 노드들은 서로 도달할 수 있음 → 위 그래프의 SCC : {A}, {B, E}, {C, F}, {D}, {G, H, I, J, K, L} 3. SCC의 성질 (1) SCC로 만든 방향그래프는 dag이다. (2) 깊이우선탐색에서 가장 높은 post number를 갖는 노드는 SCC로 만든 그래프의 source에 위치해야 한다. (3) SCC인 C와 C'가 있을 때 C에서 C'로 향하는 간선이.. 2022. 11. 29.
[알고리즘] Graph (2) - Depth-first search(DFS) [2. Depth-first search 깊이우선탐색] 1. 깊이우선탐색 - 무방향그래프 → 그래프의 탐색을 위해 Recursive call을 활용한다. → 가능한 연결되어 있는 노드들을 방문하며 → 방문 순서는 특별한 지시가 없을 경우 오름차순을 따른다. → 각 vertex v에서 탐색을 시작할 경우 → v는 이미 방문한 것으로 표시(visit[v]=1) → v에 연결된 vertex w중에서 아직 방문하지 않은(visit[w]=0인) vertex 방문 → 더이상 방문할 vertex가 없으면 직전 노드로 return Ex) 2. Spanning Tree (DFS Tree) → 주어진 그래프에서 방문되는 n-1개의 간선들로 모든 개체를 연결한 서브그래프 → DFS tree에서 root node에 다른 노드.. 2022. 11. 15.
[알고리즘] Graph (1) - Prologue [1. Prologue 개요] 1. 그래프란? → Graph : 개체와 개체들 사이의 링크로 연결된 1:1 관계를 시각적으로 나타내는 수학적 표시, 개체와 그 개체를 연결하는 링크의 집합 → vertex : 개체 → edge : 개체를 연결하는 링크, 개체간 관계를 나타냄 → G = (V, E), 그래프는 두 개의 요소(개체, 관계)를 가짐 2. 그래프의 종류 → 방항성 : 링크의 방향이 정해진 그래프 / 방향이 정해지지 않은 그래프 → 가중치 : 링크의 가중치가 정해진 그래프 / 가중치가 정해지지 않은 그래프 → 방향x, 가중치x : 무방향 그래프 → 방향x, 가중치o : 가중치 그래프 → 방향o, 가중치x : 방향그래프 → 방향o, 가중치o : 방향가중치 그래프 3. 그래프의 표현 (1) Edge l.. 2022. 11. 8.
[알고리즘] Divide & Conquer (3) - Quick sort [3. Quick sort, 쾌속 정렬] ● 방식 → 집합 A의 원소들을 오름차순으로 정렬하고자 할 때(또는 내림차순) → 집합 내의 원소 중 하나를 무작위로 골라 (주로 A[0]=pivot) → pivot을 기준으로 pivot보다 작은 원소는 pivot의 앞에 → pivot보다 큰 원소는 pivot의 뒤에 배치한다. → 이 때, pivot을 제외한 맨 앞과 맨 뒤의 값들을 서로 비교하여 → 앞의 값이 뒤의 값보다 클 경우, 자리를 서로 바꾼다. → 배열을 두 개로 분할한다는 점에서 합병정렬과 비슷하지만, 결합하지 않으므로 합병정렬의 발전형이라 할 수 있다. ● 알고리즘 → Divide : m=Partition() → Conquer : Quick_sort(s, m-1, A), Quick_sort(m+1,.. 2022. 11. 8.
[알고리즘] Divide & Conquer (2) - Merge sort [2. Merge sort, 합병정렬] ※ 배열의 요소들을 정렬할 때 인접한 각 요소들을 비교하는 방식(bubble sort 등)의 성능 : O(n²) 따라서, 더 효율적일 수 있는 방법은 "분할정복" ● 방식 → 정렬되지 않은 상태로 나열된 요소들의 집합을 절반으로 나누고 → 각각의 분할된 집합을 정렬한 다음 → 다시 결합한다 ● 알고리즘 → Divide : m = (s+e)/2 를 기준으로 더이상 분할할 수 없을때까지 절반으로 분할 O(n) → Conquer : 더 이상 분할할 수 없을 때 원소가 하나인 집합이므로, 정렬된 것으로 간주 → Combine : 분할 후 각 집합들을 결합 O(logn) → Degenerate case : 원소가 하나인 경우 (s==e) (* 배열A내에 원소가 n개인 경우 .. 2022. 11. 8.
[알고리즘] Divide & Conquer (1) - Binary search [1. Binary search, 이진탐색] ● 방식 → A를 오름차순으로 정렬된 n개 요소들의 리스트라고 할 때, → 찾으려는 값 x가 A내에 몇 번째에 존재하는지 확인하는 알고리즘이다. → x를 A내의 요소들의 중앙값(A[m])과 비교하여 → x = A[m]이면 m을 반환, → x A[m]이면 다시 x를 A[m+1 ~ e]에서 탐색하는 방식이다. (* A내에 n개의 원소가 있다면 s=0, e=n-1) ● 알고리즘 → Divide : m = (s+e)/2를 기준으로 배열을 분할 → Conquer : A[s, m-1] 또는 A[m+1, e] → Degenerate case : A 또는 분할된 A 내에 원소가 하나인 경우 (s==e) ● .. 2022. 11. 5.
[알고리즘] Prologue - Recurrence relation, master theorm 1. 점화식 표현 → 수열의 어떠한 항을 표현할 때, 그 이전의 항들을 활용하는 것 Ex) 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, ... → f(n) = f(n-1) + f(n-2) → 위와 같은 표현을 '점화식 표현'이라 한다. 2. Master theorm 3. Fibonacci sequence → 피보나치 수열 : 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... ● 구현 (1) recursive call 방식 #include int Fibonacci(int n) { if (n == 0 || n == 1)//degenerate_case return n; else return Fibonacci(n - 1) + Fibonacci(n - 2); } (2) 배열+반복.. 2022. 11. 5.
[알고리즘] Prologue - Performance & Big-O 1. 성능 • 성능=효율(efficiency), 어떤 성과를 얻기 위해 얼마나 많은 자원을 투입하였는지 측정하여 도출, 효율적≠효과적 • Efficiency = Solution ÷ Resource • 자원 중요도 : 시간(cpu) >>> 공간(memory) • 성능의 세 가지 경우 1) 최선의 경우 (Best case) 2) 평균의 경우 (Average case) 3) 최악의 경우 (Worst case) ★ • 입력의 크기에 따라 성능 결정 - n = 입력의 크기 - f(n) = 시간복잡도의 그래프 표현 - 성능 그래프 = (n, f(n)) → (3)은 존재하지 않으며 (1)은 일반적인 경우, (2)는 최고의 성능 2. 점근적 분석법 • 시간 복잡도는 매우 큰 입력에 대해서 측정함 - n이 매우 큰 경우.. 2022. 11. 5.
[자료구조] 리스트&배열 1. 리스트 • 리스트의 개념 - 유한한 원소들을 한 줄로 나열한 구조 - 각 원소들은 인덱스에 대응됨 • 리스트의 구분 - 정렬되지 않은 리스트 : 위치 예측 불가능, 추가연산에 유리 - 정렬된 리스트 : 위치 예측 가능, 검색 연산에 유리 ⇒ 더 효율적 • 리스트의 종류 - 원소를 저장 : 배열, 연결 리스트 - 원소와 순서를 저장 : 스택, 큐 2. 배열 • 배열의 개념 - 인덱스를 활용하여 리스트를 구현한 구조 (배열의 모든 요소들은 인덱스에 대응됨) - 연속적으로 할당된 공간 (최소한 배열의 크기만큼 연속된 공간이 있을 때 사용 가능) - 하나의 주소로 n개의 자료에 접근 가능함 (첫 번째 원소인 A의 위치 0014를 알면, 연속된 공간을 사용하는 배열의 특성에 의해 그 다음 원소들의 위치 00.. 2022. 10. 9.

티스토리툴바