공부 기록용 블로그

아직 백트래킹에 익숙하지 않아서인지, 생각보다 잘 풀리지 않아 아래 강의의 도움을 받았다. 강의 듣고 문제를 다시 푸니까 백트래킹 개념이 잡히는 것 같다. youtu.be/Enz2csssTCs 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 #include using namespace std; #define MAX 40 bool isused1[MAX]; //열 y bool isused2[MAX]; //좌측하단 우측상단 연결 대각선. x+y bool isused3[MAX]; //좌측상단 우측하단 연결 대각선. x-y+n-1(n-1은 인덱스를 음수로 보내지 않..

방문 여부를 체크해주지 않으면 간단히 풀리는 문제! visit 배열을 사용하지 않으면 된다. 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 #include using namespace std; int arr[9]; int N, M; int cnt, num; void dfs(int cnt) { if (cnt == M) { for (int i = 0; i

중복 조합 모두 출력하기. 예제에서 힌트를 얻어서 풀 수 있었다. dfs를 호출하면서 i를 넘겨주면 풀림! 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 #include using namespace std; int arr[9]; bool visit[9]; int N, M; int cnt, num; void dfs(int num, int cnt) { if (cnt == M) { for (int i = 0; i

15649번은 순열, 15650번은 조합. 순열은 이전에 봤었던 것까지 고려하는 것이지만, 조합은 현재 뽑은 원소의 이전 값들은 고려하지 않게끔 for문의 i값을 넘겨준다. 조합은 순열과 달리 중복되면 안되므로 시작점이 필요하며 이전에 건든 작은 숫자를 건들지 않기 위해 구현한다. 인덱스를 추가하여 넘겨주면 끝! 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 #include #define MAX 10 using namespace std; int arr[MAX]; bool visit[MAX]; int N, M; void dfs(int cnt..

백트래킹 문제이다. 복습할겸 다시 풀어본 문제. 정답 비율이 60%라 풀어봤는데,, 처음 풀었을 때는 어려웠었던 기억이 있다. 다시 풀어보니까 확실히 뭔지 알 것 같았던 문제. 길이 M까지 cnt가 올라가면 arr에 있는 수 출력, 그게 아니라면 N까지 증가시켜주면서 dfs를 호출한다. 중복되는 수열을 여러번 출력하면 안된다고 했으니까 visit배열에 방문 여부를 표시해준다. 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 #include #define MAX 9 using namespace std; int arr[MAX]; bool visit[MAX]; int N,..

문제를 딱 보자마자 점화식이 떠올라야한다! P(3)부터 P(10)까지 대놓고 나 규칙 있어요~~ 하는 문제. 마찬가지로 미리 다 구해놓고, 입력받는 식으로 문제를 풀면 된다. 100까지 입력받으니까 자료형을 잘 선언해 주는 것 주의. 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; long long dp[101] = { 1,2,2 }; int main(void) { cin.tie(NULL); ios_base::sync_with_stdio(false); int T,N; cin >> T; for (int i = 3; i > N; if (N

재귀호출만 생각하면 신이 난다!(...) DP 메모이제이션 익히기 좋은 문제라고 한다...네.. 문제에서 기저 사례(base case : 문제를 더 이상 쪼갤 수 없는 조건. 기저사례에 도달하면 return.)와 점화식까지 모두 주었다! 그래서 그대로 구현만 하면 되는 문제이다. 윗쪽 if문을 보면 0 b >> c; if (a == -1 && b == -1 && c == -1) break; cin >> a >> b >> c; cout

DP문제들을 다시 풀어보려고 한다. 피보나치 함수에서 0과 1의 출력을 각각 구하는 문제. 처음에 문제를 접근할 때 피보나치 함수 그 자체에만 집중을 해서 꽤나 어려웠었던 것으로 기억하는데, 예제를 보면 더 쉽게 풀 수 있다. 각각 1,0의 출력은 0일 때 : 1 0 1일 때 : 0 1 2일 때 : 1 1 3일 때 : 1 2 이렇게 보면 규칙성이 보인다. 나는 1을 기준으로 문제를 풀었다. 1을 기준으로 보면, 1 0 1 1 2 3 5... 이렇게 늘어나는데 결국 피보나치와 같은 방식으로 풀면 된다. i번째의 1의 출력 횟수는 i-1+i-2를 하여 구해주면 된다. 0의 출력 횟수는 1의 출력 횟수를 저장해놓은 배열에서 배열에서 i+1의 횟수와 동일하다. 이걸 그대로 코드로 풀면 문제 해결 1 2 3 4 ..

처음 코드에서 시간초과가 나면서 문제 접근에서 좀 생각했던 문제다. 예제를 보면, 각각 10, 15의 중량을 견딜 수 있는 2개의 로프로 들어올릴 수 있는 최대 무게는 20이다. 각 로프에는 고르게 w/k만큼의 중량이 걸리게 된다는 조건에서 힌트를 얻어서 오름차순으로 정렬하여 로프가 견딜 수 있는 중량 * (N-1)를 해주면서 문제를 해결하였다. 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 #include #include #include using namespace std; vector v; int main() { //시간 줄이기 cin.tie(NULL); ios_ba..

연속하는 P일 중, L일 동안만 사용할 수 있으면 우선 V를 P로 나눠주고, 나머지도 변수로 따로 저장해준다. L이 나머지보다 작으면 저장해놓은 나머지를, 나머지가 L보다 크다면 L을 더하여 출력해준다. 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 #include #include #include using namespace std; vector v; int main() { //시간 줄이기 cin.tie(NULL); ios_base::sync_with_stdio(false); int L, P, V; int cnt = 0; while (1) { cin >> L >> P >..