비밀일기

흐흑너무 어려웠다경우의 수를 구하는 문제였는데, 뭔가 묘하게 이해가 될까 말까 했다. 현재 금액을 만들 수 있는 가짓 수를 찾는 문제인데 이해하기 쉽게 가정을 해본다.  [동전]번호  1     2      3      4 금액  10   20   30   40  60원을 만들기 위해서는 동전의 개수만큼 루프를 돈다     해당 인덱스의 동전이 만들 수 있는 금액부터 최대액 까지 루프를 돈다.           이 금액을 만들기 위한 가지수는  루프를 돌면서 [금액- 현재 동전의 가치] 만큼씩 더해준다for(동전의 가지수 i)     for(가능한 금액 j)           dp[금액 j] += dp[금약 j - i 번째 동전의 개수] 이런 식의 루프를 형성한다. 제일 중요하다고 생각한 부분은 dp배열..

n개의 물건과 배낭이 있고, 물겅에는 가치와 무게 값이 존재한다. 배낭에는 최대 용량이 존재하고 이 용량 안에서 담을 수 있는 물건의 최대 가치를 찾는다. 다이나믹 프로그래밍 , 즉 큰 문제를 작은 문제로 쪼개 푸는 것으로 해결 가능하다.dp는 이차원 배열로 작성하고 dp [ 현재 탐색하는 물건 ] [ 가방의 남은 공간 ] = 최대 가치 가방 최대 5키로0 번 물건/3kg1번 물건2 번 물건3 번 물건4 번 물건0키로     1키로     3키로     4키로     5키로      이런 형태의 표를 생각 할 수 있다 ..d[1][6] 은 1번 물건을 담으려 하는데 남은 공간이 6키로라는 의미다.1번 물건이 3키로에 3달러라 했을 때, 배낭의 최대 가치는 d[i][3] 중 최대 값 +3 달러 일 것이다...

문제를 있는 그대로 받아들여서 교차점이 제일 많은 전깃줄부터 제거하여 문제를 풀려 했지만 교차점이 같은 전깃줄에서 어느 것을 먼제 제거할지 결정하기가 어려웠다..결국 서치하여 알아낸 것은문제 풀이 방법이 증가하는 가장 긴 부분 수열을 구하는 문제라는 것!  왼쪽 전봇대와 오른쪽 전봇대를 볼 때, 왼쪽에서 출발하는 전깃줄이 도착하는 오른쪽 전봇대의 인덱스를 나열하여, 그중에서 제일 긴 증가하는 부분수열을 구하면 되는 문제였다.. 가장 긴 증가하는 부분 수열을 구하는 방법은?dp 배열을 이용한다.dp[a]=b의 의미는 a번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이는 b이다. 라는 의미임  정렬되지 않은 순서로 입력이 주어질 수 있으므로 저장한 값을 먼저 정렬해주고, dp 배열에 값을 할당한다. #i..

#include#include#includeusing namespace std;vector a;void find(int s, int e, long long i) { int mid = (s + e) / 2; if (e i) { find(s, mid-1, i); } if (a[mid] > n; for (int i=0; i > k; a.push_back(k); } cin >> m; sort(a.begin(), a.end()); for (int j = 0; j > k; find(0, a.size()-1, k); } return 0;}배열에 원소를 삽입하고 find 함수를 작성하여 그 안에서 이분탐색을 진행하였다. end>start인 경우에는 정답을 찾지 못한 것이므로 0을 출력, a[mid]가 찾던 값인..

#include#include#includeusing namespace std;int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vectorarr(n,0); for (int i = 0; i > arr[i]; } sort(arr.begin(), arr.end()); int max; int x, y, z; for (int m = n - 1; m >= 0; m--) { max = arr[m]; for (int j = m; j >= 0; j--) { y = arr[j]; for (int i = j; i >= 0; i--) { x = arr[i]; z = max - x - y; if (z  숫자를 n 개 입력받아 ar..

공유기 설치  이분 탐색을 이용하여야 한다는 생각을 가지고도 어떻게 문제에 접근해야할지 감이 오지 않아서 블로그 글들을 조금 참고하여 코드를 짰다!... 1. 맨 처음 집에는 무조건 공유기가 설치된다.2. 왼쪽에서 오른쪽 방향으로 공유기가 설치된다. 3. 공유기의 설치 가능한 최소 거리는 1이다. 이 세가지를 중심으로 코드를 짰다.int wifi(int start, int end) { int result = 0;//가장 긴 거리 중 최솟값 while (start = mid) { cnt++; prev_house = house[i]; } } if (cnt >= w) { result = mid; start= mid+1; } //거리를 크게해서 조금 설치 가능; if (cnt re..

c++으로 깊이 우선 탐색을 구현하는 방법과 너비 우선 탐색을 구현하는 방법이 어려워서 정리를 해본다.. DFS는 깊이 우선 탐색으로 재귀함수나 스택으로 구현한다. 1. 탐색 노드를 스택에 삽입하고 방문 리스트에 표시.2. 스택 최상단 노드에 인접한 노드중 방문하지 않은 노드가 존재한다면 그 노드를 스택에 넣고 방문한다.   인접노드를 모두 방문했다면 최상단 노드를 꺼낸다.3. 2번 과정을 계속 반복한다. ** 방문 리스트로 검사를 꼭 해줘야 무한 반복에 빠지지 않는다!!** 스택은 후입선출의 구조이므로 늦게 들어간 노드가 최상단 노드가 됨을 기억하자!===============================================================================Bfs는 너비..

c언어 문풀랜선 자르기 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다!이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.  랜선의 개수가 10000 까지고 길이는 1000000이므로 반복문으로 풀면 시간초과에 걸려 이진 탐색을 해주어야 한다.이진 탐색 함수를 따로 만들어 주었다. 입력을 받으면서 제일 긴 전선의 길이를 따로 저장해주었다.이진 탐색 함수에서 파라미터를 (1,최대 전선길이)로 주어 zero division 에러가 나지 않도록 해주었다.mid값..

#c 언어 #이항계수 #모듈러 역원 # 페르마의 소정리 #이진 곱셈 먼저 이항계수 구하는 방법.. 볼 때마다 기억이 나지 않아서 찾아보는 내가 싫다.. 당연히 모듈러 연산이니까 덧셈, 곱셈처럼 계신해주면 된다고 생각했는데 나눗셈 연산은 그렇게 계산하는게 아니란다.. 나누기 연산은 나누는 숫자의 역원을 구하여 곱해주는 것이 맞음  이때 [페르마의 소정리]와 [확장 유클리드 호제법]이 있음. 페르마의 소정리는 나누는 숫자가 소수여야 한다는 제한이 있고확장 유클리드 호제법은 연산에 사용되는 두 숫자가 서로소여야 한다는 조건이 있음 여기서는 m 이 1000000007로 소수이기 때문에 페르마의 소정리를 이용한다.  (n * n-1 * ...* k+1) / (n-k * n-k-1 * ...* 2) 의 연산을 해주..

가운데 숫자 찾기 c++ 처음에는 이진 탐색을 이용하여 재귀 호출로 문제를 풀어보려 했자.. 그치만 자꾸 메모리 초과가 나와서 다른 방법을 찾아보니 우선순위 큐를 이용하여 중간 값을 찾을 수 있었다! 오름차순으로 정렬한 max heap 과 내림차순으로 정렬한 min heap 을 이용하였다.priority_queue, greater> minheap;priority_queue> maxheap; //비교 함수를 주지 않으면 자동으로 오름차순으로 설정 두 힙에 번갈아가며 수를 넣어주는데, min의 top이 max 의 top 보다 더 작은 경우 top을 swap 해준다.결과적으로 max의 top에는 중간값이 오게 된다!처음에 숫자를 할당해줄 heap 을 min heap 으로 정해 heap 의 size 가 같다면 ..