열심히해보겠씁니다

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

목차 21.11 ~ 22.09 내 소중한 토요일을 모두 바쳐가며 공부했던 Expert 가 마무리 되었다. 감상과 회고 SCSA16기로 합격하여 공채 SW검정 수준인 Advanced를 준비하면서 친구들과 스트레스 오지게 받던게 엊그제 같은데 뿌듯하다. SCSA 6개월 과정 중, 고향집 침대에 누워서도 끊임없이 문제만 생각하고 고민했던 시간들이 새록새록 떠올랐다. 아침 8시부터 머리를 돌리면서 점심/저녁 시간에 잠시 숨을 돌리고, 다시 야간 자율학습을 시작하여 12시, 1시까지 알고리즘을 풀었었다. 거의 고3임 그게 한 3주 정도 됐었나? 다른 교과과정이 있어서 C, JAVA, NETWORK 등등 배우면서 알고리즘을 계속 풀었던 것이라서 더더욱 쉽지 않았다. 대학교 4년에 해당하는 내용을 (실제로 4년어치는..

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

오늘은 짜-증나는 exception을 겪었다. 프론트에서 연도와 월을 픽한 후 백으로 날리는 과정인데, 'yyyyMM'의 String으로 날려주고 있었다. 나는 당연히 LocalDateTime과 DateTimeFormatter를 사용하여 String을 DateTime 형식으로 바꿔주려고 했으나 index0 오류 때문에 도저히 진행할 수가 없었다. 기존 실행했던 함수는 다음과 같다. String frontDate="201212"; LocalDateTime localDateTime; localDateTime = LocalDateTime.parse(frontDate, DateTimeFormatter.ofPattern("yyyyMM")); 당연히 에러가 났다. Unable to obtain LocalDateTi..

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

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