https://www.acmicpc.net/problem/7497 #문제 간단 정리 N 이 주어지고 N 이하의 숫자들에서 각 자리수를 곱햇을때 가장 커지는 숫자를 찾는 문제 #문제 해결 방법 N 이하의 숫자들의 자리수의 곱의 최대라는 말은4876이면 4 * 8 * 7 * 6 이렇게 곱할 수 있고4876 이하의 숫자인 3999도곱해서 3 * 9 * 9 * 9 를 곱해서 최대값을 찾을 수 있다. 여기서 쉽게 생각 할 수 있는건 9를 최대한 많이 만든다는건데 일단 어떤 자리수를 1내리면 그 뒤에 숫자들은 전부 9로 만들수 있다. 때문에 각 자리수를 한번씩 1 내리고 그 뒤에수를 전부 9로 만들어 주면서 최대값을 찾아주면 된다. #전체 코드#include #include #include using name..
https://www.acmicpc.net/problem/16624 #문제 간단 정리 이 문제는 동시에 빙고가 나오는지 확인을 하면 되는데빙고는 행 빙고만 취급한다. #문제 해결 방법 만약 두 빙고카드에 같은 행에같은 숫자가 존재한다면 비길 수 있는 가능성으로 만드는 가능성이 존재한다. 하지만 만약1 2 3 4 5 1 6 7 8 9 2 3 4 6 7 1 2 3 4 5에서 1을 찾고1 6 7 8 9 에서 1을 찾아서 비긴다고 생각을해도 나머지 2 3 4 5, 6 7 8 9을 빙고하다보면2 3 4 6 7 행이 빙고가 되서 비기지 않는다 즉 다른카드에서 겹치는 쌍을 찾고1 2 3 4 5 에서 1을 골랏다면 2 3 4 5 를 추출1 6 7 8 9 에서 1을 골랏다면 6 7 8 9 를 추출해서2 3 4 5 6..
https://www.acmicpc.net/problem/9764 #문제 간단 정리 #문제 해결 방법 // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수 // 1. j를 포함하지 않고 만드는경우 // dp[i][j-1]; // 2. j를 포함해서 i를 만드는경우 // if(i>=j) D[i][j] = (D[i][j] + D[i-j][j-1]) % mod ; // D[i-j][j-1] = i-j를 1 ~ j-1 사이의 수들로 만드는방법의 수 일단 해결로직은 저렇긴한데dp를 떠올리는 발상을 정리해보자면 일단 특정 숫자를 쓰냐 안쓰냐로 생각 할 수 있고j를 안쓰고 만들면 j-1 개를 가지고 만드는 가지수와 같고j까지의 숫자를 써서 N을 만드는..
#동적 계획법(DP)이란? DP의 두 가지 핵심 특성중복되는 부분 문제(Overlapping Subproblems):동적 계획법은 문제를 풀 때 동일한 부분 문제가 여러 번 반복됩니다. 예를 들어, 피보나치 수열에서 F(n)=F(n−1)+F(n−2)F(n) = F(n-1) + F(n-2)F(n)=F(n−1)+F(n−2)를 구할 때, F(n−1)F(n-1)F(n−1)과 F(n−2)F(n-2)F(n−2)을 재귀적으로 구하게 됩니다. 하지만 F(n−2)F(n-2)F(n−2)는 F(n−1)F(n-1)F(n−1)을 계산할 때도 다시 구하게 됩니다. 이처럼 중복된 계산이 자주 발생하므로, 이를 메모이제이션 또는 테이블 저장을 통해 중복 계산을 방지합니다.최적 부분 구조(Optimal Substructure):최적 ..
https://www.acmicpc.net/problem/9764 #문제 간단 정리 #문제 해결 방법 우선 동적 계획법을 사용해야된다는건 쉽게 알아차릴 수 있다 왜냐면 1. 중복되는 부분 문제(Overlapping Subproblems) 2. 최적 부분 구조(Optimal Substructure) 를 n의 조합을 알기 위해서는 이전의 수가 필요하고 이전의 수 조합으로 구할 수 있다는 것을 쉽게 알 수 있기 때문이다. 그렇다면 선택할수 있는건 그 수의 조합을 만들기 위해 어떤수를 사용하던가 사용하지 않던가 로 나뉜다는 것을 알 수 있다. // dp[i][j] 1~j의 수들의 합으로 i 를 만드는 방법의수 // 1. j를 포함하지 않고 만드는경우 // dp[i][j-1]; //..
A. Sakurako's Exam a b 가 주어지는데 a개수만큼 1이 주어지고 b의 개수만큼 2가 주어지는데각 숫자 사이에 부호를 + , -를 배치해서 0을 만들수 있는지 출력하는문제 a와 b의 개수를 파악해서 각자 짝수냐 홀수냐 그리고 1의개수를 잘 따지면 된다#include #include #include #include using namespace std; int main() { int t; cin >> t; while (t--) { int a, b; cin >> a >> b; int remainB = 0; if (b % 2 != 0) { remainB = b % 2; } ..
https://www.acmicpc.net/problem/2589 #문제 간단 정리bfs를 통한 거리 문제 #문제 해결 방법 이 문제는 bfs를 통해서가장 먼 거리의 위치 를 찾는 문제이다 전형적이 bfs에서 조금 활용이라고 볼 수 있다. 모든 육지 노드에 대해 돌면서 그 육지에서가장 먼 노드를 찾고 가장 먼 거리를 변수에 저장하면 된다. #전체 코드#include #include #include #include using namespace std;int n, m;int dy[4] = { 0,1,0,-1 };int dx[4] = { -1,0,1,0 };vector> tMap;int maxDist;int bfs(int inputY, int inputX) { //좌표,거리 queue> q; ..
https://www.acmicpc.net/problem/25601 #문제 간단 정리그래프 탐색을 하면 된다 #문제 해결 방법 dfs로 풀었는데 트리의 부모만 확인해 주면 되니까 이렇게 복잡하게 풀 필요는 없어보인다..그래서 실버1인듯하다 #전체 코드#include #include #include #include #include #include using namespace std;map> node;map dfsCheck;int result;void dfs(string start, string target) { if (start == target) { result = 1; return; } for (auto a : node[start]) { if (..
