열심히해보겠씁니다

동전이 최소가 되도록 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번에 넣..

목차 연산자 오버로딩의 이해 이제 C++에 대해서 어느 정도 감이 잡혔다. 이번에는 C++의 핵심적인 기능 중 하나인 연산자 오버로딩을 살펴보자. 지난 글까지 객체 다형성과 함수의 다형성에 대해서 들여다 봤다. 하지만 C++ 다형성의 끝판왕은 개인적으로 연산자 오버로딩이라 생각한다. 기본적인 원리와 방식은 기존과 동일하므로 어렵지 않게 공부할 수 있으니 한 번 들여다 보자. 연산자의 오버로딩은 함수의 오버로딩과 거의 차이가 없다. return 타입을 제외한 키값들, 함수명과 인자의 타입, 개수만이 오버로딩의 조건이 된다. 즉 return 타입은 오버로딩과 관련이 없었다는 것을 기억하고 천천히 접근해보자. 가장 기본적인 이해를 위해 잠깐 생성자의 호출을 다시 돌아보자. 앞서 살펴본 생성자 중 복사 생성자라..

오늘은 맥북 에어를 산 기념으로 맥북에 윈도우 세팅을 하려고 했다. 근데 부트캠프를 깔자니 번거롭게 왔다갔다 하기 귀찮고, 패러럴즈를 깔자니 깡통 맥북이라 ( 8GB 램 + 256GB SSD ) 리소스가 너무 아깝다. 게다가 굳이 맥북에서 윈도우 돌려서 성능에 손해를 보는 것보다는 집에 데스크탑 자원을 그대로 사용하는 것이 이롭지 않을까? 그래도 라이젠 3700x 에 1660 super 니 맥북 에어보다는 잘 돌아가지 않을까해서 그 첫 단계로 집 컴퓨터 외부에서 키기! 를 준비했다. 아주아주 쉬우니 금방 끝낼 수 있다. 준비물은 윈도우 데스크탑과 핸드폰이다. 총 3가지 구성이 있다. 1. 메인보드 설정 2. 이더넷 설정 3. 공유기 설정 1. 메인보드 설정 가장 먼저, 메인보드가 신호를 받았을 때 작동할..

목차 상속 객체지향이 절차지향과 아주아주아주 다른 포인트 중 하나인 상속이다. 상속은 말 그대로 누군가에게 물려받는 것을 의미한다. 상속의 개념은 결국 공통점을 묶어서 한 번에 유지,보수하기 편하게 만들기 위함이기 때문에 경제적인 요인과 편의성을 고려한 개념이라고 생각하면 될 것 같다. 클래스에서의 상속은 자신의 멤버 변수와 멤버 함수를 물려주는 것을 의미한다. 이 때, 상속 해주는 클래스는 상위, 기초(base), 슈퍼(super), 부모(parent) 클래스라고 부르고, 상속 받는 클래스는 하위, 유도(derived), 서브(sub), 자식(child) 클래스라고 부른다. 상속의 특징은, 부모의 모든 멤버들을 자식이 물려받는다는 것이다. 또다른 특징은, 부모의 모든 멤버를 자식이 물려받되 온전히 자식..

오늘은 또 SQL 때문에 헤맸습니다. 제 상황은 이랬습니다. TABLE TEMP_TABLE NUMBER STATCODE NAME DATE USEYN 3002352 10 해운대 20120101 y 3002352 20 해운대 20120101 y 3002352 30 해운대 20120101 y 3003001 10 인천앞바다 20131111 y 3003001 20 인천앞바다 20131111 null 3003010 10 속초해수욕장 20221001 n 3003010 20 속초해수욕장 20221001 y 3003010 40 속초해수욕장 20221001 y 여기서처럼 number statCode 와 useYn 만 다르고 다른 필드들은 동일한 경우가 많았습니다. 위 상황을 number 와 date, name 으로 묶고,..

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