Algorithm

[백준 3109] 빵집 C++

3109번: 빵집 유명한 제빵사 김원웅은 빵집을 운영하고 있다. 원웅이의 빵집은 글로벌 재정 위기를 피해가지 못했고, 결국 심각한 재정 위기에 빠졌다. 원웅이는 지출을 줄이고자 여기저기 지출을 살펴보던 www.acmicpc.net 이 문제는 그리디 알고리즘을 적용한 DFS문제이다 그리디를 어떻게 적용하는가?? 항상 오른쪽 위 부터 탐색을 해야한다(0번째 Row부터 탐색할 경우만 해당. R-1번째 부터 탐색하면 오른쪽 아래부터 탐색) 탐색을 한 부분은 다시 탐색하지 않는다! (DP개념도 같이 적용) 문제를 이해했다면 항상 오른쪽 위 부터 탐색해 간다는건 쉽게 이해할 수 있다 나도 처음엔 이것만 생각해서 백트래킹 방식을 적용해 37 번 라인에 방문했던 곳을 초기화 해주는 코드(Map[r][c] = 0;)가 ..

[백준 12015] 가장 긴 증가하는 부분 수열2 C++

12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 이전까지 풀어봤던 LIS 문제들과 푸는 방법이 조금 다르다 기존LIS는 for문을 2번 돌려서 O(n^2) 시간안에 풀었다면 이번 문제는 수열의 크기가 N st){ int mid = (st + ed)/2; if(key > arr[mid]){ st = mid+1; } else{ ed = mid; } } return ed; } void solve(){ int cnt = 1; res.push_back(arr[0]); for(int i = 1; i

Stack Permutation C++

순열을 구하기위해 dfs를 사용했는데 visit 배열 대신 stack을 사용해서 구현해보았음 n이 8이 넘어가면 하루종일 걸려요.. 모든 경우의 수를 출력해주기 때문에 어쩔 수 없다 if(node == N) 부분의 for 문을 보면 N이 i에 대한 조건으로 있는데 이 N을 입력받은 N보다 작게 바꿔주면 ex ) N이 6일 때 4로 설정 -> 6까지의 숫자 중 4개를 골라 만들 수 있는 모든 순열이 출력된다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include #include using namespace std; vector _stack; int N, check[10] = {0, }; vo..

Union Find Basic Code C++

Union Find를 이해하기 위한 기본 코드 findTopnode를 통해서 최상단 노드를 알 수 있다 union_node를 통해서 입력된 수의 최상단노드를 찾아 두 수를 연결해주는 작업을 한다 check_node를 통해서 두 수가 서로 연결 되었는지 알 수 있다 www.cs.usfca.edu/~galles/visualization/DisjointSets.html Disjoint Sets Visualization www.cs.usfca.edu 위 사이트에서 눈으로 직접 보면서 이해할 수 있다!! 좋음 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 4..

[백준 10090] Counting Inversion C++

10090번: Counting Inversions A permutation of integers from 1 to n is a sequence a1, a2, ..., an, such that each integer from 1 to n is appeared in the sequence exactly once. Two integers in а permutation form an inversion, when the bigger one is before the smaller one. As an example www.acmicpc.net 분할 정복 1. 문제해결 아이디어 임의의 수열에서 자신보다 뒤에 있는데 자신보다 작은 수의 개수의 총 합을 구하는 문제이다 N^2로 풀면 너무 쉽겠지만 N

[백준 1111] IQ Test C++

www.acmicpc.net/problem/1111 1111번: IQ Test 다음 수를 출력한다. 만약 다음 수가 여러 개일 경우에는 A를 출력하고, 다음 수를 구할 수 없는 경우에는 B를 출력한다. www.acmicpc.net 처음에 x가 0이 되는 경우를 깜박해서 ZeroDivisionError 가 발생했었다 같은 수가 연속으로 나올경우 x값이 0이 된다! 모든 점이 한 직선위에 있음을 알아차리고, 직선의 기울기와 y절편을 구한다 구한 기울기와 y절편이 모든 좌표 쌍에 적용된다면 a, b는 구해진 것임 그리고 N==1, N==2일때의 기저조건 예외처리를 해주고 마무리를 했다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2..

[백준 14501] 퇴사 C++

14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net dp와 브루트포스 방식을 모두 적용할 수 있는 좋은 문제이다! solve1은 브루트 포스와 dp를 적용해서 O(n^2)에 풀 수 있는 방법이다 solve2는 solve1과 논리는 같지만 top-down방식으로 재귀함수를 이용한 방법이다 solve3는 동적계획법을 최대한 활용해서 Pi, Ti를 뒤에서부터 탐색하는 방법을 사용해 O(N)만에 해결하는 방법이다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 5..

[백준 2798] 블랙잭 C++

N이 최대 100 이므로 3장을 뽑는 모든 경우의 수를 탐색하는 O(N^3) 알고리즘을 수행할 수 있다 for 문을 돌면서 sum에 현재 선택한 카드 3장의 합을 저장하고, sum이 M을 넘지않지만 현재 결과보다 크다면 현재 결과를 갱신한다 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 #include using namespace std; int main(){ int N, M, num[101], sum = 0, result = 0; cin >> N >> M; for(int i = 0; i > num[i]; } for(int i = 0; i

[백준 1074] Z C++

분할정복은 어려워! 코드만 보면 되게 간단해 보이는데 간단하게 만들기 위해 머리를 짜내는게 힘들다.. 내 머리는 재귀적인 생각을 잘 못하는듯 하다 처음에 입력받은 N값을 2로 나눈 값을 solve()로 넘겨준다 -> 이 때 n == 2라고 가정하자(N == 3인 경우) (r, c)가 몇 사분면에 있는지 4개의 if문을 통해서 판별한다 판별기준 : row + n 과 col + n row+n을 기준으로 r이 이 값보다 작으면 1, 2 사분면 중 하나, 같거나 크면 3, 4 사분면 중 하나이다. col+n을 기준으로는 c가 이 값보다 작으면 1, 3 사분면 중 하나, 같거나 크면 2, 4 사분면 중 하나이다. 총 4가지 기준으로 분할 정복을 실행하고 r, c의 위치를 찾으면 (n == 0) 리턴하여 지금까지 ..

[백준 10830] 행렬 제곱 C++

분할 정복은 어렵다! 거듭제곱에 대해서는 위와 같이 분할이 일어난다. -> m이 짝수일 때, 홀수일 때 분할이 달라지는건 코드에 표현되어있다. 개인적으로 class를 만들어서 객체간의 연산을 해주는 방식으로 만들어서 마음에 든다! #include #include using namespace std; int N; long long B; // 정방 행렬을 저장하는 class class Matrix{ public: int Map[6][6]; Matrix(){} Matrix(int n){ int in; for(int i = 0; i > in; Map[i][j] = in % 1000; } } } // 연산자 오버로딩을 통해서 행렬의 곱..