노는 게 제일 좋아

이러한 것은 다이나믹 프로그래밍이라는 것과 같이 동적으로 수행하면서 최대부분을 갱신하면서 찾는 것이다. 물론 for문 2번 돌아서 가능하지만.. n^2은 써서는 안되는 최악의 시간 복잡도다. 다른 방법을 찾아보자 우선 정답코드를 보고난 다음 설명을 해보자 int MaxSubArray(int a[], int length) { int maxSoFar = 0, maxEndingHere = 0; // 1 for(int i = 0; i 이것은 부분배열합의 특성때문이다. 우선 문제부터 정의하자 부분배열합이란 무엇인가하니? 배열의 원소 중에서 임의의 원소 k번째부터 k + x까지의 합을 부분 배열이라 하고 해당 원소들의 합을 부분배열 합이라고 한다. 그렇다면 최대한의 합이 나오려면 가장 큰 부분을 고르면 되겠네? 맞..

어렵다기보다.. 수학으로 풀면 규칙 찾아내는 것이지만 다이나믹 프로그래밍 분류에 있어서 뭐 그렇게 풀려고 했으나..내 머리가 모자라서.. https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 우선 다이나믹프로그래밍으로 풀려고하는 방법은 큰 문제를 작은 문제로 쪼개는 것이다. 때문에 x부터 y라면 x 부터 y-1까지 가는 방법에서 y-1에 2로 도착하는 방법과 y-1에 1로 도착하는 방법이 있으니 이것을 잘..

우리가 가장 먼저 정렬을 배울 때 배우는 삽입정렬. 그것에 대해서 알아보자 입력으로는 n 개의 수열이 주어지고 출력은 n개의 수열들이 정렬된 채로 나오기를 원한다. 아래와 같이 하는 것이 삽입 정렬을 적용하는 방법이다. 위와 같은 방식은 어떤 식으로 구현해야 할까?? 우선 pseudo code로 봐보자 조금만 프로그래밍 공부를 했다면 프로그램이 어떻게 작동하는 지는 알 것이다. 하지만 이를 추상화시켜서 설명하는 것은 어려울 수 있다. 다시 말하면 삽입 정렬의 코드를 보여줄 수는 있지만 삽입 정렬이 뭐냐고 물어보면 정확하게 답하기 어려운 이유가 그렇다. 그렇다면 한 줄씩 뜯어서 살펴보자. 첫 번째 2번째 원소부터 n번째 원소까지 끝까지 조사를 한다. 두 번째 조사를 하는 해당 원소는 key가 된다. 세 번..

어렵지 않지만.. 헷갈렸다. 행과 열을 바꿔서 해버렸따.. https://www.acmicpc.net/problem/2225 #나의 풀이 #include #define MAX 1000000000 using namespace std; int N, K; long long dp[201][201]; // N, K int main() { int i, j, k; cin >> N >> K; //하나를 선택할 때는 무조건 하나를 선택함. for (i = 0; i

용량도 작다 https://www.acmicpc.net/problem/2293 심히 기분이 좋지 않다. 재귀로 푸는 방법을 알았지만.. 용량도.. 시간도 초과할 것이 뻔했다. 다른 방법을 찾는데.. 너무 헤맸다. 이러한 방법은 정말 많은데 충분히 익혀놔야할 방법 중 하나같다. 하향식보다 이번엔 상향식으로 하는 것이 맞았다.dp에 저장해가며 푸는 것이 이 문제의 핵심이었을 것이다. #include using namespace std; int n,k; int coin[101]; int dp[100001]; int main(){ cin >> n >> k; for(int i = 1; i> a; coin[i] = a; } //dp[0] = 1 을 추가시켜주어야함 //첫번째 코인으로 만들 수 있는 경우의 수를 추가..

다이나믹 프로그래밍이 재밌어지는 시기 https://www.acmicpc.net/problem/2193 우선 예를 몇개 들고나보면 하위 문제로 쪼개지는 것을 알 수 있고 하위 문제에 대해 답을 구하면 된다. 재귀함수로 구현을 해보고 해당 함수를 Memoization 하게되면 시간 안에 풀어진다. #include using namespace std; int N; long long dp[91][2]; int main(){ cin >> N; dp[1][1] = 1; dp[2][0] = 1; for(int i = 3; i

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/17298 이것은 그냥 뭐 생각대로 하기 쉽지 않다. 해보려 했는데..인덱스가 저장이 안되어서 정말 힘들었다.그래서 pair를 쓸까 하다가.그냥 스택 2개를 썼다. 인덱스를 이용해야 한다라는 생각을 하면 어렵지만 생각할 수 있는 문제라고 한다.한 번에 생각하기는 확실히 힘든 것 같다. 다른 사람과 풀이를 비교하지 않는 이유는원리는 같아서 그렇다. #include #include #include #include using namespace std; stack num; // 숫자를 넣음 stack stk; // 인덱스를 넣음 int N; int arr[1000001]; void init(){ io..

DFS, BFS 알고리즘을 알아야 풀 수 있는 문제다. https://www.acmicpc.net/problem/1260 이것은 그냥 뭐..그냥 구현하면 된다. 다만 여기서 주의할 점은 방문을 언제할 것이냐를 판단하느냐 문제다. 나머진 어렵지 않다. 그냥 머릿속에서 생각하는 그대로 구현한다. #include #include #include using namespace std; int N, M, V; // 정점, 간선, 시작 노드 int map[1001][1001]; int visited[1001]; int backup[1001]; queue Q; stack S; void copy(int origin[1001], int backup[1001]) { for (int i = 1; i > N >> M >> V;..

바로 생각한 대로 실행하면 되는 문제다. https://www.acmicpc.net/problem/2003 우선 N~M번째 까지의 합은 1~M - 1~N-1 인것을 나는 이용했다. 하지만 이제부터는 잘한 사람들에게서도 나와 무엇이 다른지 공부하기로 했다 우선 나의 풀이를 보고 다른 잘한 사람들의 풀이를 비교해보자 #맞은 풀이 #include using namespace std; int N,M; int arr[10001]; int dp[10001]; // dp[i] -> 1~i번째까지의 합 // N~M 까지의 합은 1~M번째 까지의 합 - 1~N-1 번째까지의 합. int main(){ cin >> N >> M; int cnt = 0; for(int i=1; i> arr[i]; dp[i] = dp[i-1]..

https://www.acmicpc.net/problem/1094 처음에 생각했을 때.. 이진법? 생각났다. 문제를 읽고 예를 읽어보니 맞다. 즉, 이진법 수에서 1의 개수를 구하는 문제다. 즉, 우리가 이진법 변환을 어떻게 했는지 생각해봤다. 2로 나누면서 나머지를 세었다. 마지막까지 2로 나누어서 숫자를 판단했다. 코딩도 그렇게 했다. #include using namespace std; int N; int main() { cin >> N; int sum = 0; while (N >= 1) { sum += N % 2; N /= 2; } cout