열심히해보겠씁니다

동전이 최소가 되도록 n 가지 동전을 이용해 k 원을 만든다. n이 100가지이고 10만 보다 작거나 같은 가치이며, k는 1만 원 이하이다. 사용한 동전의 구성이 같은데 순서가 다르면 같은 경우이다. -> 순열이 아닌 조합으로 풀 수 있다. 가치가 같은 동전이 여러 개 있을 수 있으므로 중복된 검색은 피할 수 있다. k원을 만들었을 때 동전의 최소 개수만 알면 되므로 Dynamic Programming 을 이용한다. 1. dp 배열 정의) dp[k] = k 원 일때 사용한 최소 동전의 개수로 정의한다. 2. 기저사례) dp[0] = 0, dp[동전 1개 가치] = 1 이 기저 사례이다. 3. 점화식) dp[i] = max(dp[i], dp[i - 동전 1개 가치] + 1) 개이다. #include #i..

Codeforces Codeforces codeforces.com 구글 코드잼이 2023년을 마지막으로 사라집니다... 더 이상 훌륭한 사람들을 뽑으러 큰 대회를 진행할 필요가 없을 정도로 구글의 위상이 높아지기도 했고, 코드잼 자체를 비용으로 생각하게 되었기 때문에 힘들어지는 지금 시기에 대규모 lay off와 더불어 사라진 것 같네요. 그래서 상시 대회가 열리는 codeforces 로 가보도록 합시다. 이미 꽤나 역사가 되었기 때문에 꽤나 공신력이 있습니다. 백준처럼 남의 코드를 제출해도 랭크가 오르는 것과는 다르게 특정 요일 특정 시간에만 풀 수 있는 대회가 열리고, 빠르고 정확하게 풀수록 랭크가 많이 오릅니다. 회원가입/로그인을 하고 메인에 들어가봅시다. 무슨 페이지인지도 모르겠네요 ㅋㅋ 자세히 ..

두 배열을 주고, 두 배열의 연속된 부분집합의 합이 특정 숫자 T를 만족하는 개수를 찾으란다.. T 는 -10억 ~ 10억이고 A, B 배열은 1000개 까지 있다. 각 배열의 값은 -1백만 ~ 1백만이다. 일단 배열의 부분집합수만 해도 Sigma(1000) 이니 각 50만개가 넘는다. 두 개 결합하는 경우의 수는 50만 x 50만이므로 2초 안에 불가능하므로 필요한 경우만 빠르게 찾는 것이 목표다. 나는 두 가지를 이용해서 간편하게 풀길 원했다. 1. presum 2. lower bound, upper bound 문제에서 연속된 부분집합만을 요구하므로 미리 구간합을 계산하여 가지고 있을 수 있다. 예를 들어, A 가 [1,2,3,4,5] 라면 presum = [1, 2, 3, 4, 5, 1+2, 2+3..

최소값/최대값을 구하는 dp 문제이다. 다만 이 경우에 메모리가 4MB 가 한정되어 있으므로 최소한의 메모리를 사용하면 된다. N 이 10만이고 3칸이므로 30만 x int = 1.2MB 정도를 차지하므로 dp 10만 짜리 배열을 하나 추가로 쓰거나 할 수 있지만 ladder 1 x 3 하나와 dp 2 x 3 2개로도 풀 수 있다. 귀찮아서 ladder 는 그냥 다 받기로 했다. 사다리는 다음과 같이 작동한다. 1 2 3 4 5 6 이 있을 때, 1번은 4, 5 번, 2번은 4,5,6번 3번은 5,6 번으로만 내려갈 수 있으므로 4번의 최댓값은 max(1번 + 4번, 2번 + 4번) 이고, 최소값은 min(1번 + 4번, 2번 + 4번) 이다. 5번의 최댓값은 max(1번 + 5번, 2번 + 5번, 3번..

소가 들어가고 싶은 축사가 정해져있고, 한 축사에 한 마리씩 넣으면 된다. 최대유량이나 이분매칭으로 구하면 된다. 훨씬 간단한 이분매칭으로 풀었다. 소 그룹을 A, 축사 그룹을 B 라고 뒀을 때, 소 3마리, 축사 4개가 있고 S1 = [ 1, 2, 3 ] S2 = [ 1, 2, 3, 4 ] S3 = [ 2, 3, 4 ] 일 때를 생각해보자. 그럼 그래프를 다음과 같이 그릴 수 있다.소 1번부터 차례대로 원하는 축사를 고른다고 생각해보자. 1번 소가 1번 축사를 고른다. 그 후 2번 소가 고를 차롄데 2번 소도 1번을 가고 싶다. 그럼 2번 소를 1번 축사에 넣고 1번 소를 1번이 아닌 다른 가고 싶은 축사 2번에 넣는다. 그 후 3번 소가 고를 차롄데 3번 소는 2번이 가고 싶다. 3번 소를 2번에 넣..

보기에는 간단한데 생각보다 난이도가 높은 문제이다. 가장 작은 수는 dp로, max는 그리디로 접근한다. #include #include int t, n; char max[102]; long long dp[101]; //성냥 개수 있을때 만들 수 있는 최대 수 char GreedyMax[8] = { 0x0,0x0,'1', '7', '4', '5','9','8' }; long long min[9] = { 0,0,1,7,4,2,0,8,10 }; void makeMax(int n,int idx) { if (n == 0) { return; } if (n % 2) { max[idx] = GreedyMax[3]; makeMax(n - 3, idx + 1); } else{ max[idx] = GreedyMax[2];..

네트워크를 직접 연결(!!)하는 아주아주 어려운 문제이다... 모든 컴퓨터가 직간접적으로 연결되어 있어야 하고 심지어 그 비용이 가장 적어야 한다.(속도는 상관 없나보다) 비용이 가장 적게 모든 노드를 연결하기만 하면 되므로 최소 신장 트리(MST: Minimum Spanning Tree)를 이용하여 트리 모양으로 고리가 생기지 않도록 연결해준다. (고리가 생기는 경우는 고리가 생기지 않는 경우보다 항상 비싸다) 우리는 MST 알고리즘 중 크루스칼 알고리즘(Kruskal's algorithm - Wikipedia)을 이용한다. 1. 가장 비용이 작은 간선부터 연결한다.(UNION FIND) 2. 같은 그룹에 속할 경우 연결하지 않는다. 간단한 그리디 알고리즘이다. 이 때 MST 가 항상 최소비용인 것은 ..

A -> B 로 가는 최소비용을 구하면 된다. A -> B 로 갈 수 있는 경우만 입력으로 주어진다는 조건이 있으므로 최소 비용 구하는 것만 신경쓰면 된다. 여기서 버스 비용은 0 이상이므로 버스를 이용할수록 손해이므로 버스는 최대 N-1 번 이용할 것이고, 한 번 타는데 최대 비용은 10^5 이고 N 은 10^3 이므로 최대 나올 수 있는 비용은 10^8 이므로 int 로 처리한다. #include #include #include #include using namespace std; int N, M, s, e, c; int start_city, end_city; vector edge[1001];//[도시번호] pair(비용,다음도시) int dijkstra(int start_city, int end_c..

KIS Developers (koreainvestment.com) KIS Developers 제휴사는 별도 제휴계약 후 사용 가능합니다. 요금안내: 기본적으로 제공하는 API 유량에 대해서는 0원이며 추가 유량을 원하시는 고객을 위하여 향후 별도 과금정책을 정하여 포털을 통해 공지 apiportal.koreainvestment.com 1. 한국투자증권에 로그인하고 KIS Developers 서비스 신청하기. 2. Python 설치하기 나는 법인 고객이 아니고 개인 고객이기 때문에 제휴를 하지 않고 일반 사용자로 활동하려고 한다. API 문서를 읽고 원하는 request 를 만든 뒤 테스트베드에서 테스트 한 후 이용하면 될 것 같다. 그 후 엑셀 혹은 스프레드시트에 연동하여 데이터를 자동으로 업로드하고자 ..

1 end 라면 길이가 1인 수열이 제일 짧은 것이므로 종료해도 이상이 없다. len 은 N이 최대 10만이 나올 수 있으므로 초기값을 10만 + 1으로 잡고, 만약 더 짧은 것이 발견되지 않았다면 만들기 불가능한 경우이므로 0을 출력한다. 위의 풀이 방법으로 반드시 해를 찾을 수 있을까? s,e 를 index로 보고 start, end 를 가장 짧은 수열의 인덱스로 보자. 슬라이딩 윈도우의 상황을 여섯 가지로 볼 수 있을 것 같다. 1. s, e 가 모두 start 보다 작을 경우 2. s 가 start 보다 작고 e가 start 보다 같거나 크고 end 보다 작은 경우 3. s 가 start 보다 작고 e가 end 보다 같거나 큰 경우 4. s 가 start 보다 같거나 크고 e 가 end 보다 작은..