본문 바로가기

백준28

[DFS] 백준 1182번 부분수열의 합 - Python 파이썬 생각하기 부분 수열을 만들 수 있는 모든 경우를 다 탐색해야 하는 브루트포스 문제이다. 모든 경우를 탐색하면서 S가 될 때를 판단해야 하므로 반복문을 통해 하나씩 하는 건 말이 안된다 DFS를 사용해서 내려가면서 S와 비교를 하면서 개수를 카운트해야겠다고 생각했다 부분수열은 순서는 신경쓰지 않으니 DFS의 전체적인 로직은 시작하는 숫자를 Data의 Idx에따라 계속 바꾸어 나가자는 것! 구현하기 answer 변수를 전역에 선언, 재귀적으로 DFS를 돌면서 answer을 쌓아갈 예정 sum은 매번 DFS를 새로 시작할 때, 시작 포인트에서 첫 숫자로 초기화해준다 각 DFS는 recursive 하게 돌면서 자신이 쌓은 answer을 반환 DFS 메서드 구성 sum이 S와 같은 경우 idx가 마지막 idx인경.. 2021. 10. 19.
[DP] 백준 15988번 - 1, 2, 3 더하기 3 생각하기 20을 나타내는 방법의 수 = 4를 나타내는 방법의 수 x 16을 나타내는 방법의 수 각 숫자 나타내는 방법의 수 구하는 방법 = 백트레킹? 하짐나 DP로 풀어야 하는 문제이기 때문에 DP적으로 생각! dp[num] = dp[num-1] + dp[num-2] + dp[num-3] 마지막에 각 단계에서 부족했던 숫자들만 더해서 값을 뽑을 수 있다 1을 구하는 방법에서 2을 더하는 방법 2를 구하는 방법에서 1을 더하는 방법 이미 구해 놓은 값들을 통해 구해낸다 * 각 숫자 때마다 dp값을 도출하기 #include #include #include #include #include #include #include #include #include using namespace std; #define end.. 2021. 1. 28.
[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.

티스토리툴바