본문 바로가기

전체 글107

[DP] 백준 2748번 - 피보나치 수 2 case1) n이 0 혹은 1일 때, 0 / 1을 출력 case2) n이 2이상 일 때, memoizate해 놓은 이전 두개의 수를 더한 수를 출력 하지만 이런식으로 진행한다면 시간초과가 발생한다 memoization을 사용하여 연산을 최대한 줄여야 한다 #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' int N; long long fib[100]; long long pibo(int n) { if(n==0){ return 0; } if(n==1){ return 1; } if(fib[n]!=-1) return fib[n]; else{ fib[.. 2021. 1. 25.
[Back Tracking] 백준 9663번 - N Queen 완전탐색을 한다면? N = 14일때, 14x14의 요소중에서 14개를 뽑는 것이기 때문에 256^14가 된다 제한 시간은 10초(10^9)이기 때문에 초과한다 -> Back Tracking 으로 풀어야 한다 2차원 배열에서 알아두면 좋은 점 col이 i, row가 j라고 할 때 생각 처음에는 15*15 배열을 만들어 놓고 아래의 규칙에 따라 퀸이 배치된 칸 퀸이 배치된 칸의 모든 아래 칸들 퀸이 배치된 칸의 왼쪽 대각선 아래 칸들 퀸이 배치된 칸의 오른쪽 대각선 아래 칸들을 모두 false 처리 했다 하지만 이렇게 하는 경우 문제가 있다 빨간색이 파란선과 겹치면서 파란색을 원상복귀 시켜놓는다. 이러한 경우를 방지하기 위해서는 각 케이스를 독립적이게 분리할 필요가 있다. 2차원 배열에서의 인덱스들의 특징을.. 2021. 1. 25.
[Back Tracking] 백준 15650번 - N과 M (2) 재귀함수를 통해 경우의 수를 찾아가는 방법은 N과 M(1) 블로그 포스팅을 참고! #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' int M, N, min_num, cnt1, cnt2; char input; bool choosed[10]; int answer[10]; void loop(int stage) { if (stage == M + 1) { for (int i = 1; i M; for (int i = 0; i < 8; i++) { choosed[i] = false; } loop(1); } 2021. 1. 23.
[Back Tracking] 백준 15649번 - N과 M(1) N과 M모두 8이하의 수이기 때문에 최대 8중 for문으로 돌아간다. 8^8 Brute Force로 풀 수 있는 문제이다 가변하는 여러 겹의 for를 어떻게 만들것인가? -> 재귀함수 사용한다 choose[] = 이미 선택된 것을 나타내는 배열 answer[] = 답을 순서대로 출력하기 위해서 저장해 놓는 배열 만약 세개를 다 선택했다면 loop를 나간다 나갈때, 답을 출력한다. loop를 나가고 나서 다시 2단계로 돌아올 때 끝난 과정의 3단계에서 choose된 것을 false로 바꾸어 준다 추후 다른 2단계에서 선택된 경우에서 써야 한다 (같은 단계에서는 어차피 for문이 다음으로 넘어가기 때문에 상관 없다) #include #include #inclu.. 2021. 1. 22.

티스토리툴바