노는 게 제일 좋아

//첫번째 풀이 2021.05.26 //두번째 풀이 2022.02.08 이 문제도 백트래킹이지만 조금 꼬아서 냈다. 출력을 조금 더 어렵게했다. https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 우선 내가 접근했던 틀린 풀이부터 보자 #include #include using namespace std; void init() { ios::sync_with_stdio(0); cin.tie(0); } int a, b..

//첫번째 풀이 2021.06.07 //두번째 풀이 2022.02.08 //세번째 풀이 2022.06.13 얘도 모든 걸 다 뒤져봐야 하는 문제다. 다만 모든 걸 뒤질 때 어떻게 뒤지느냐가 문제다. 백트래킹, DFS를 사용했다고 보면 된다. https://www.acmicpc.net/submit/14888/29858716 #맞는 풀이 #include #include #define MAX 1000000000 using namespace std; int N; int num[12]; int oper[4]; // {add, sub, mul, div 순} //최대 최소 int m = MAX; int M = -MAX; //백트래킹 이용같다. //입력은 현재까지의 연산결과를 받고 사용한 연산자 개수도 입력받는다 vo..

우선 숫자가 큰 문제이다. 뭔가 크다. 어렵진 않았지만.. 그냥 오랜만에 푸니까 감이 안왔다. https://www.acmicpc.net/problem/2805 시간초과 될 것을 알면서도 brute force로 해봤다. #include using namespace std; int N,M; int maxi = 0; int sum; int arr[1000001]; int main(){ cin >> N >> M; for(int i = 1; i> a; arr[i] = a; if(a>=maxi){ maxi = a; } } maxi--; while(1){ sum = 0; for(int j = 1; j0) sum += temp; } if(sum>=M){ break; } maxi--; } cout > N >> M; f..

어려웠다. 부분으로 쪼갤 수 있었지만 생각이 잘 안났다. https://www.acmicpc.net/problem/9251 모든 부분을 부분수열로 쪼개보니.. for문이 3개나 나와서 그냥 떄려쳤다. DP문제라는 것을 한 번에 파악할 수 있었다. 어떻게 전체 문제를 부분으로 쪼갤 수 있을까 고민했다. 처음에는 맨앞에서부터 접근했지만 틀린 접근법이었다. 마지막부터 조사했어야 했다. 길이가 L1, L2의 문자열이 있다. 만약 마지막 부분이 같다면 해당 마지막부분을 제외한 채로 나머지 L1 -1 , L2 - 1의 문자열의 가장 긴부분을 조사하면 될 터였다. 마지막 부분이 다르다면 둘 다 제외하는 것이 아닌 L1 - 1, L2 또는 L1, L2 - 1의 문자열을 조사하면되었다. 그리고 문자열이 비어있는 것과의 ..

용량도 작다 https://www.acmicpc.net/problem/2293 심히 기분이 좋지 않다. 재귀로 푸는 방법을 알았지만.. 용량도.. 시간도 초과할 것이 뻔했다. 다른 방법을 찾는데.. 너무 헤맸다. 이러한 방법은 정말 많은데 충분히 익혀놔야할 방법 중 하나같다. 하향식보다 이번엔 상향식으로 하는 것이 맞았다.dp에 저장해가며 푸는 것이 이 문제의 핵심이었을 것이다. #include using namespace std; int n,k; int coin[101]; int dp[100001]; int main(){ cin >> n >> k; for(int i = 1; i> a; coin[i] = a; } //dp[0] = 1 을 추가시켜주어야함 //첫번째 코인으로 만들 수 있는 경우의 수를 추가..

다이나믹 프로그래밍이 재밌어지는 시기 https://www.acmicpc.net/problem/2193 우선 예를 몇개 들고나보면 하위 문제로 쪼개지는 것을 알 수 있고 하위 문제에 대해 답을 구하면 된다. 재귀함수로 구현을 해보고 해당 함수를 Memoization 하게되면 시간 안에 풀어진다. #include using namespace std; int N; long long dp[91][2]; int main(){ cin >> N; dp[1][1] = 1; dp[2][0] = 1; for(int i = 3; i

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/17298 이것은 그냥 뭐 생각대로 하기 쉽지 않다. 해보려 했는데..인덱스가 저장이 안되어서 정말 힘들었다.그래서 pair를 쓸까 하다가.그냥 스택 2개를 썼다. 인덱스를 이용해야 한다라는 생각을 하면 어렵지만 생각할 수 있는 문제라고 한다.한 번에 생각하기는 확실히 힘든 것 같다. 다른 사람과 풀이를 비교하지 않는 이유는원리는 같아서 그렇다. #include #include #include #include using namespace std; stack num; // 숫자를 넣음 stack stk; // 인덱스를 넣음 int N; int arr[1000001]; void init(){ io..

해시태그라 불리는 # 그렇다면 해시 테이블은 뭔지 알까? 수많은 자료 구조들 중 하나로 속도가 빠른 자료구조로 알려져 있다. 한 번 알아보자 해시 테이블은 기본적으로 Key- Value 시스템을 가지고 있다. key는 value를 찾는 수단이고 우리가 찾는 것은 value이다. 사전을 생각해보면 쉽다. "배추" 의 정의는 배추를 찾아야 그 밑에 설명이 있다. 우리가 필요한 것은 배추라는 단어가 아니라 배추가 뭔지이다. 해시 테이블의 적합하지 않은 데이터들도 있다. 정렬된 데이터가 필요하거나, 멀티 미디어 데이터를 저장할 때 혹은 키의 길이가 길거나 가변적이어서 키에 대한 검색이 필요할 때 데이터의 키가 유일하지 않을 때 등이 있다. 해시 테이블은 O(1)의 시간복잡도를 가진다고 알려져 있다. ?? 딱봐도..

백트래킹의 전형적인 문제 조건을 잘 읽어야 하는 문제 https://www.acmicpc.net/problem/15654 #맞은 풀이 #include #include #include using namespace std; int N, M; vector vec; vector ans; bool check[8]; void func(int cnt) { if (cnt == M) { for (auto v : ans) { cout > M; for (int i = 0; i > a; vec.push_back(a); } sort(vec.begin(), vec.end()); // 오름차순정렬 func(0); } 다 비슷한 문제다. 이러한 N이 다 다른 숫자가 주어져서 그렇지 만약 중..

왜 DP 알고리즘 분류에 들어있는지 모를 문제 https://www.acmicpc.net/problem/4963 테스트 케이스가 많은 문제는 어차피 하나에 대해서 풀 수 있다면 모조리 풀 수 있고 ios::sync_with_stdio(0); cin.tie(0); 을 꼭 써주자. 이건 그냥 따로 공부할 필요도 없다. 그냥 대각선까지 가능한 BFS를 풀면된다. 탐색을 4방향에서 8방향으로 늘리면 되는 문제다. 다를게 하나도 없다. #맞은 풀이 #include #include #include #define X first #define Y second //8방향으로 이동가능 제자리 빼고 int dx[8] = {1,1,1,0,0,-1,-1,-1}; int dy[8] = {-1,0,1,-1,1,-1,0,1}; us..