tony9402

문제 : 1,2,3 더하기 6유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기 4, 5보단 조금 더 쉽고 재밌었던 문제였다.더하기 식이 대칭이 되도록 만들면 되는 문제이다. 이를 어떻게 풀지 고민하다가 다이나믹 프로그래밍이므로 재귀적으로, 또한 합이 대칭을 만족해야 한다는 요점을 잡고 다시 보니 바로 눈에 보였다. 어떤 수 x가 있는데 이를 어떻게 대칭적이고 재귀적으로 풀 수 있을까?바로 x에서 2, 4, 6을 빼고 반을 나눠 양쪽에 이어서 붙이면 된다.ex) x => 1 + (x-2) + 1, 2 + (x-4) + 2, 3 + (x-6) + 3 이렇게 빼면 된다. 근데 여기서 궁금증을 가지는 사람이 있을 수 있다.ex) 4를 1 + 1 + 1 + 1로 만들 수 있는데 이는 어떻게 만들어지지.....

문제 : 1,2,3 더하기 5문제 유형 : 다이나믹 프로그래밍 일단 정수 4인 경우, 1,2,3의 합으로 나타내는 방법이 왜 3개인지 알아보자. 처음엔 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수를 구해보면 아래와 같다. 3 + 11 + 32 + 22 + 1 + 11 + 2 + 11 + 1 + 21 + 1 + 1 + 1 여기서 문제 조건에 만족하지 않은 것은 2 + 2와 1 + 1 + 1 + 1, 2 + 1 + 1, 1 + 1 + 2이다.이를 어떻게 풀까.......? 정수 n이 있다고 가정해보자. n은 아래와 같이 쓸 수 있을 것이다. 1. 3 + (n - 3)2. 2 + (n - 2)3. 1 + (n - 1) 1번에서 n - 3이 3이 아닌 1과 2로 식을 전개하면 된다.3 + 1 + (n -..

문제 : 1,2,3 더하기 4 문제 유형 : 다이나믹 프로그래밍 이 문제는 1,2,3 더하기로 표현하는 것들 중에서 더하기 순서를 바꿨을때랑 같은 것을 한 종류로 보는 문제이다. 4를 가지로 예를 들어보자. 4를 1,2,3더하기로 표현해보면 3+1 2+2 1+3 2+1+1 1+2+1 1+1+2 1+1+1+1 이렇게 7가지가 있는데 더하기 순서를 바꾸면 같아지는것을 묶어보자. 3+1 (1+3) 2+2 2+1+1 (1+2+1, 1+1+2) 1+1+1+1 이렇게 4가지가 있다. 이것을 어떻게 수식으로 표현할까? 1,2,3 더하기 시리즈 문제는 모두 다이나믹 프로그래밍으로 풀 수 있다. 이를 재귀적으로 생각해보면 점화식이 보인다. 한 종류로 만들 때, 여러가지 순서 중 비오름차순으로 짜면 된다. 4를 가지고 예..

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 3 위 문제는 1, 2, 3 더하기 문제에서 n의 범위가 더 커졌고 모듈러 연산을 하면 되는 문제이다.따라서 이 문제는 여기에서 세운 점화식에다가 모듈러 연산만 추가 하면 된다. 1234567891011121314151617181920212223242526272829#include long long dp[1000001] = {0, 1, 2, 4 }; const long long mod = 1000000009; long long DP(int n){ if (n

알고리즘 분류 : 다이나믹 프로그래밍 문제 : 1,2,3 더하기 2 이 문제는 1,2,3 더하기 문제를 이용해서 풀었다. 먼저 4를 본다고 하면 DP[3] + DP[2] + DP[1]를 더한게 DP[4]의 값이다. 아래 그림을 보며 이해를 하자. 4는 3 + 1, 2 + 2, 1 + 3인 경우의 수를 알 수 있고 이를 사전 순으로 정렬하면 1 + 3, 2 + 2, 3 + 1이렇게 된다. 따라서 4를 간단한 규칙으로 정리하면 1부터 DP[4-1]까지는 1로, DP[4-1] + 1부터 DP[4-1] + DP[4-2] 까지는 2로, DP[4-1] + DP[4-2] + 1부터 DP[4-1] + DP[4-2] + DP[4-3] 까지는 3으로 채워진다. 이런 방식으로 계산을 하면 원하는 구간에서 값을 계속 vect..

알고리즘 분류 : 다이나믹 프로그래밍(DP) 문제 : 1, 2, 3 더하기 이 문제는 계산을 어떻게 할껀지 점화식을 세우면 금방 푸는 문제이다. 난 이 문제를 풀면서 재귀적인 풀이를 생각하며 풀었다. 5라는 숫자가 있을 때, 여기서 1, 2, 3을 뺀 숫자들 4, 3, 2가 1, 2, 3의 합으로 나타내는 경우의 수를 다 더하면 된다는 것을 발견하였다. 이를 수식으로 쓰면 DP[n] = DP[n-1] + DP[n-2] + DP[n-3]이다. 여기서 n을 1, 2, 3을 빼다 보면 DP[0]인 경우가 나온다. 이럴 때, DP[0]의 값을 뭐로 하면 좋을까? 간단한 예를 보자. 2라는 숫자가 있다. 2라는 숫자는 보자마자 1 + 1와 2로 경우의 수가 나온다. 이를 내가 푼 방식으로 한번 보자. 2는 1, ..

시스템 생명 주기(System Life Cycle) 요구사항 - 프로젝트들의 목적을 정의한 명세들의 집합 - 입력과 출력에 관한 정보를 기술 분석 - 문제들을 다룰 수 있는 작은 단위들로 나눔 설계 - 추상 데이터 타입(abstract data type) 생성 - 알고리즘 명세와 설계 기법 고려 정제와 코딩 - 데이터 객체에 대한 표현 선택 - 수행되는 연산에 대한 알고리즘 작성 검증 - 정확성 증명 : 수학적 기법들을 이용해서 증명 - 테스트 : 프로그램의 정확한 수행 검증, 프로그램의 성능 검사 오류 제거 - 독립적 단위로 테스트 후 전체 시스템으로 통합 객체 지향 설계 구조적 프로그래밍 설계와의 비교 - 유사점 : 분할 - 정복 기법 : 복잡한 문제를 여러개의 단순한 부분 작업으로 나누어 각각을 개..

백준 2178 미로탐색 이 문제는 (1,1)부터 시작해 (N,M)로 가는 길 중 가장 짧게 갈 수 있는 경로를 찾는 것이다. 최단 경로를 구하는 문제는 대부분 BFS로 푸는 문제이다. 따라서 이 문제도 BFS로 푸는 문제이다. BFS는 queue를 이용하는데 queue에서 pop할때 도착 지점의 좌표가 나올때까지 하면 된다.문제에 길은 무조건 있다고 하니깐 그냥 없을 경우를 생각하지 않고 계속 push하고 pop을 하면 된다. 1. pair가 있다는 걸 몰랐을 때 짠 소스(queue에 대해서 독학 했을 때...) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585..

오랜만에 에듀코포가 있어 해보게 되었다. 너무 오랜만이라 그런지 문제를 해석해야하는데 해석도 안되고 문제를 읽기도 싫어서 대충 예제를 보고 풀려고 했지만 A번은 1시간 동안 안 풀려서 B -> A -> C로 풀었더니 1시간이 훌쩍 지나가버렸다. A번은 두 문자의 차이가 2 또는 0(같은것)인것을 보면 되는 단순한 문제였는데 문제를 안읽어 제출을 많이 했다. B번은 대충 배열 쓰면 되겠지하고 봤더니 n의 범위가 최대 10^9여서 멍 때리다가 규칙을 찾고 대충 제출 했지만 케이스 n == 2일때만 틀려서 2일땐 그냥 노가다로 if문 떡칠을 하였다. C번은 처음에 O(n^2)로 풀었는데 TLE가 떠서 O(n) 풀이가 있을꺼 같아 살짝 그리디하게 짜봤더니 AC가 떳다. 시간 복잡도 A번 -> O(N)B번 -> ..

백준 2606 바이러스 이 문제는 (매우..?) 쉬운 문제이다. 알고리즘 분류에는 플로이드 와샬로 되어있는데 이건 단순히 DFS로 풀린다.입력 받는 데이터를 이용해 인접리스트를 만들고 컴퓨터 1번에서 DFS를 한 번 돌리면 답이 나온다. 1234567891011121314151617181920212223242526272829303132333435363738#include#include using namespace std; vector map;bool visit[101] = { false };int computer_num, ans = 0; void dfs(int x){ ans++; visit[x] = true; for (int k = 0; k