Deff_Dev

문제https://www.acmicpc.net/problem/2579풀이다이나믹 프로그래밍 문제이다. dp[1] = stair[1];dp[2] = stair[1] + stair[2];dp[3] = max( stair[1] + stair[3], stair[2] + stair[3])dp[n] = stair[n] + max (dp[n - 2], dp[n - 3] + stair[n -1])#include #include using namespace std;int dp[301] = { 0, };int main() { int n; cin >> n; vector vec(n + 1); for (int i = 1; i > vec[i]; } dp[1] = vec[1]; dp[2] = dp[1] + vec[2]; dp[3..

문제https://www.acmicpc.net/problem/2839 풀이이 문제는 상근이가 3kg와 5kg 봉지를 사용하여 정확히 N kg의 설탕을 배달할 때, 최소한의 봉지 개수를 구하는 프로그램을 작성하는 문제다. 다이나믹 프로그래밍을 이용하여 풀이하였다. dp[3] = dp[5] = 1dp[n] = min (dp[i], dp[n - 5] + 1 )#include #include #include using namespace std;int dp[5001] = { 0, };int main() { int n; cin >> n; dp[3] = dp[5] = 1; for (int i = 6; i

문제 https://www.acmicpc.net/problem/2252풀이이 문제는 위상 정렬을 사용하여 풀이했다. 위상 정렬이란 ?비순환 방향 그래프(DAG)에서 정점을 선형으로 정렬하는 것이다.위상 정렬을 사용하기 위해서는 조건이 필요하다.방향 그래프(Directed Graph)여야 한다.비순환 그래프(Acyclic Graph)여야 한다. 즉, 사이클이 없어야 한다.최소한 하나의 위상 정렬 결과가 존재해야 한다.이 문제는 위 조건에 만족하기 때문에 위상 정렬을 사용하여 풀이했다.#include #include #include using namespace std;int n, m;int degree[32001];vector vec[32001];void Topological_Sort() { queue q..

문제 https://www.acmicpc.net/problem/2161풀이이 문제는 1 ~ N 까지 이루어진 숫자들에서 특별한 규칙을 부여하여 첫 번째 숫자들을 출력 후 삭제하는 문제이다. 여기서 주어진 규칙은 다음과 같다.첫 번째 요소를 출력 후 삭제한다.이후 첫 번째 요소가 된 숫자를 맨 뒤로 옮긴다.숫자들이 남지 않을 때까지 반복한다.난 Queue를 이용하여 해당 문제를 풀이했다.#include #include using namespace std;int main() { int n; cin >> n; queue q; for (int i = 1; i

문제https://www.acmicpc.net/problem/2607 풀이 문자열 입력비슷한 문자 찾기0 번째 단어 탐색 ▶ 각 알파벳 갯수 count - 1n 번째 단어 탐색 ▶ 각 알파벳 갯수 count + 1차이점 계산같은 문자일 경우 ▶ 0문자 하나 추가 or 삭제 ▶ 1문자 하나 변경 (문자 제거 + 추가) ▶ 2 비슷한 단어라면 결과 값 + 1출력#include #include #include #include using namespace std;bool isSimilar(string target, string word) { if (abs((int)target.length() - (int)word.length()) > 1) return false; vector count(26, 0);..