코드플러스 그래프와 BFS 파트에 들어왔다. DFS 를 활용하는 문제라고 생각은 했는데, 너무 오랜만이라 감이 잘 안와서 계속 틀렸다. DFS 문제 핵심 1. 재귀를 돌 때, 종료조건을 확실하게 설정한다. 2. 방문 체크를 확실히 해주고, 재귀 코드 뒤쪽에 꼭 방문 해제를 해주는 게 필요하더라. 이거만 유의해서 풀어보았다. #include #include #include #include using namespace std; int isvisited[2002]; vector table[2002]; bool possible = false; void check_relation(int start, int depth) { if(depth > 4) { possible = true; return; } isvisite..

#include #include #include using namespace std; long long dp[10002]; int main() { int n; int podo[10002]; cin>>n; for (int i = 1; i >podo[i]; } dp[0] = 0; dp[1] = podo[1]; dp[2] = podo[2] + podo[1]; for (int i = 3; i

가장 긴 증가하는 부분 수열 문제를 그대로 적용한 후, 더 증가하는 인덱스를 참조할 때마다 해당하는 인덱스에 이전의 수열 저장값을 저장하고 뒤에 새로 추가될 값을 추가해 주었다. (뭔 소리지?) #include #include #include #include using namespace std; vector lst[1002]; int main() { int n; int arr[1002]; int dp[1002]; int max_val = -1; int max_idx= -1; cin>>n; for (int i = 0; i >arr[i]; for (int i = 0; i < n; i++) { dp[i] = 1; lst[i].push_back(arr[i]); for (int j = 0..

요즘 백트래킹, 브루트포스 부분을 공부하고 있는 상황에서 순열 3총사를 만났다. "다음 순열"의 경우 백트래킹을 활용해 모든 조합을 만들어 가다, 입력으로 준 숫자를 찾으면 그 다음번에 오는 조합을 답으로 출력하는 방식을 사용하였는데, 시간 초과가 났다. 알고보니 이렇게 하는게 아니더라. 다른 방법이 있는데, 백트래킹 같은 개념을 사용하지 않는 단순 수학문제 였다. "모든 순열" (10974) 문제가 내가 "다음 순열" 문제를 풀 때 만든 백트래킹 코드를 그대로 사용하면 답으로 나왔다. #include #include #include #include using namespace std; int n; int flag = 0; vector givens; int isused[10002]; int pack[10..

진짜 오래 걸린 문제였다. 단순 백트래킹으로 구현하여 답도 제대로 나오는데, 95프로에서 계속 틀렸다고 나와서 정신이 나가는 줄 알았다. #include using namespace std; int n,m,k; int isused[12][12]; int arr[12][12]; int lst[12]; int ans = -2147483648; void func(int row, int col, int lim) { if (lim == k) { int sum = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (isused[i][j] == 1) sum += arr[i][j]; } } ans = max(ans, sum); return ; } fo..

쉬운 문제부터 백준 codeplus 문제집을 차례로 풀어보려고 한다. #include #include #include using namespace std; int main() { vector arr; for (int i = 0; i >tmp; arr.push_back(tmp); } sort(arr.begin(), arr.end()); for (int i = 0; i