천천히 하자

문제https://www.acmicpc.net/problem/11724풀이과정먼저 문제를 풀기 전에 연결요소에 대한 개념을 찾아봤다. 연결 요소란 1~N까지 정점으로 이루어져있는 그래프가 나누어 존재할 경우 각각의 그래프를 연결 요소라고 한다. 연결 요소에 속한 모든 정점은 연결하는 경로가 있어야 하며, 다른 연결 요소에 속한 정점과 연결하는 경로가 있으면 안된다.아래 그림을 참고하면 쉽게 이해할 수 있다. 이러한 연결 요소의 개수를 세는 방법은 DFS를 이용하여 구현했다. DFS를 이용해 1부터 탐색을 시작하며 DFS(1) 이후에 check[i]가 false로 나오면 연결요소가 하나 더 있다는 뜻으로 해석했다.소스코드#include #include using namespace std; vector a[..

문제https://www.acmicpc.net/problem/2193풀이과정쉬운 계단 수, 오르막 수를 풀어보고 나니 쉽게 풀 수 있었다. 먼저, D[1][0] 은 이친수의 조건 1규칙을 위반하기 때문에 0개였으며 D[1][1] 은 그냥 한개이다. 그 이후로 계속 생각해 본 결과 D[i][0]은 길이가 i-1인 수의 마지막 숫자가 0과 1일 경우의 이친수 개수를 더하면 됐다. 하지만 D[i][1] 의 경우는 이친수의 조건 2번을 적용하면 길이가 i-1이고 마지막 숫자가 0인 경우의 이친수의 개수와 같다는 사실을 알 수 있다. 이러한 결과를 식으로 나타내면 아래와 같다. D[i][0] = D[i-1][0] + D[i-1][1] D[i][1] = D[i-1][0] 소스코드#include using names..

문제https://www.acmicpc.net/problem/11057풀이과정쉬운 계단 수 문제와 비슷한 문제이다. D[i][j] = 숫자의 길이가 i이며 마지막 숫자가 j인 수의 오르막 수의 개수라고 정하고 규칙을 찾아봤다. 그 결과로 길이가 i, 마지막 숫자가 j인 숫자의 오르막 수의 개수는 길이가 i-1이고, 마지막 숫자가 j 이하인 숫자들의 오르막 개수를 모두 더하면 됐다. 식으로 나타내보면 아래와 같다. D[i][j] += D[i-1][k] (0#include using namespace std; #define NUM_MAX 10 // 0~9 까지의 수 (10개) #define mod 10007 int N,ans; long long D[1001][NUM_MAX]; // D[i][j] = 수의 길..

문제 출처 : https://www.acmicpc.net/problem/2309 풀이과정 아홉명의 난쟁이 중에 진짜 난쟁이 일곱명을 추려내는 문제이다. 일곱 난쟁이의 키의 합은 100이라는 사실을 이용해 풀이하면 된다. 9명 중 2명을 선택해 난쟁이가 아니라고 생각하고 나머지 7명의 키 합이 100이면 된다.9명 중 2명을 선택하는 경우의 수가 36가지 이므로 완전 탐색으로 풀었다.코드가 더러운 것 같다. 불필요한 과정을 생각해서 코드를 깔끔하게 바꾸는 연습도 해야겠다. 소스코드 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std..

문제 출처 : https://www.acmicpc.net/problem/11502 풀이과정 D[i] 를 붕어빵 i개를 팔아서 얻을 수 있는 최대 수익이라고 할 때,가능한 경우를 생각해보면 붕어빵 1개를 P[1]에 팔 경우에 남은 붕어빵의 개수는 i-1개가 되는데이 경우에 P[1]+D[i-1] 라는 생각을 할 수 있다. 하지만 D[i]는 얻을 수 있는 '최대' 수익이기 때문에 최대값만 저장해야한다. 그러므로 아래와 같은 식을 생각할 수 있다.D[i] = max(D[i],D[i-j]+P[j])이러한 식을 이용하면 쉽게 해결할 수 있다.DP문제는 많이 풀어보면 감이 온다고 했는데 점점 감이 오는거 같아 기분좋다. 소스코드 1234567891011121314151617181920212223242526272829..

문제 출처 : https://www.acmicpc.net/problem/10844 풀이과정 D[i]를 길이가 i인 수의 계단수의 개수라고 생각해보고 풀려고 하다가 시간을 엄청 날려먹었다.결국 검색을 통해 답을 보고 해결했다. D[i][j]를 길이가 i, 마지막 수가 j인 수의 계단수의 개수라고 생각하고 풀면 된다고 한다.그러면 D[i][j] = D[i-1][j-1] + D[i-1][j+1] 이라는 식이 나온다고 말한다.식만봐서는 이해하기 힘들어서 직접 길이가 3이고 마지막 수가 3인 경우를 생각해봤다.D[3][3]은 직접 경우를 따져보니 123, 323, 343, 543 총 4개였다. 이렇게 직접해보니 위의 식이 이해가 됐다. 소스코드 12345678910111213141516171819202122232..

문제 출처 : https://www.acmicpc.net/problem/1932 풀이과정 DP를 활용하면 간단하게 풀 수 있는 문제이다.맨 왼쪽과 맨 오른쪽을 제외한 곳은 오른쪽, 왼쪽 중 큰 것을 더하여 저장하며, 맨 왼쪽, 오른쪽은 정해진 수를 더해서 저장한다. 소스코드123456789101112131415161718192021222324252627282930#include #include using namespace std; int n,ans;int DP[501][501]; int main(){ cin.sync_with_stdio(false); cin >> n; for (int i = 1; i DP[i][j]; if (j == 1) DP[i][j] = DP[i - 1][j] + DP[i][j]; /..

문제 출처 : https://www.acmicpc.net/problem/2606 풀이과정 처음에 문제를 보고 아 BFS나 DFS를 사용하면 되겠다 라고 생각했는데 밑에 알고리즘 분류에 플로이드-워샬 알고리즘이라고 적힌 것을 보고 플로이드-워샬 알고리즘에 대해 찾아보고 사용해보려고 했는데 너무 어려운 것 같다.그리고 검색해보니 사람들도 주로 BFS, DFS를 이용하여 풀어서 DFS를 이용해서 풀었다.DFS, BFS 에 대한 개념은 머리에 있는데 아직은 구현이 매끄럽게 되지 않는 것 같다. 소스코드 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include using nam..

문제 출처 : https://www.acmicpc.net/problem/11655 풀이과정 알파벳을 13칸씩 밀려서 출력하는 문제이다. 아스키코드를 참고하면 쉽게 풀 수 있다.시험기간이라서 쉬운 문제를 풀었다. getline(cin,s)로 한 줄을 입력받아 문자열 처리를 하면 된다. 소스코드1234567891011121314151617181920212223242526272829#include #include std::string s; int main(){ std::getline(std::cin, s); int len = s.length(); for (int i = 0; i = 'A' && s[i] 90) s[i] -= 13; else s[i] += 13; } else if (s[i] >= 'a' && s..

문제 출처 : https://www.acmicpc.net/problem/1158 풀이과정 1부터 n까지의 정수를 큐를 활용하여 저장한 후에 m번째 사람의 제거를 위해 반복문을 돌린다.m번째가 아닌 사람들은 front에서 나간 후 다시 back으로 넣어준다.큐를 활용하면 쉬운 문제였다. 소스코드 12345678910111213141516171819202122232425262728293031323334#include #include using namespace std; int main() { int n, m; cin.sync_with_stdio(false); cin >> n >> m; queue q; for (int i = 1; i