시간 다이나믹 프로그래밍 기본 문제 틀리기 쉬운 점 복기하면서 재활

1. 문제 19947번: 투자의 귀재 배주형 (acmicpc.net) 19947번: 투자의 귀재 배주형 2020년에 학교로 복학한 주형이는 월세를 마련하기 위해서 군 적금을 깨고 복리 투자를 하려고 한다. 주형이가 하려는 투자에는 3가지 방법의 투자 방식이 있다. 1년마다 5%의 이율을 얻는 투자 ( www.acmicpc.net 2. 풀이 아주 기본적인? 다이나믹 프로그래밍.. 근데 어떻게 하는건지 잠깐 기억이 안났었다는게 함정 dp를 길이가 y+1인 배열 [0]*(y+1) 초기화할테고 dp[0] = h여서.. y년 후의 금액이 dp[y]라고 해서.. 1년,3년,5년 투자 방식중 최댓값을 골라 dp에 저장할텐데 이거 어떻게 하더라... 잠깐 정적.. ------------------------------..

  • format_list_bulleted 다이나믹 프로그래밍
  • · 2023. 5. 10.
  • textsms

라그랑주의 네 제곱수 정리를 이용한 알고리즘(다이나믹 프로그래밍, 브루트포스 연습)

1. 라그랑주의 네 제곱수 정리 모든 자연수 n은 많아야 음이 아닌 4개의 정수의 제곱수 합으로 표현할 수 있다. n=a2+b2+c2+d2을 만족하는 0 이상의 정수 a,b,c,d가 존재한다. 증명은 매우 까다롭다.. 너무 길어서 따라하기도 힘들다.. https://jjycjnmath.tistory.com/295 [퍼온글] 라그랑주의 네제곱수 정리(Four Square Theorem)와 그 증명 ※ 출처 - http://kevin0960.tistory.com/ 디오판토스의 저서 '산학'에는 '모든 양의 정수는 네 제곱수의 합으로 표현될 수 있다.' 라는 내용이 담겨 있다. 예를 들어, \[ \begin{aligned} 3 &= 1^2 + 1^2 + 1^2 + 0..

  • format_list_bulleted 정수론
  • · 2023. 4. 23.
  • textsms

문자열 비교 응용 - 다시 처음부터 되돌아가면서 비교해야할때

1. 문제 5555번: 반지 (acmicpc.net) 5555번: 반지 당신은 N개의 반지를 가지고 있다. 각각의 반지는 대문자 10 문자로 이루어진 문자열이 새겨져 있다. 반지는 문자열의 시작과 끝이 연결된 형태로 문자가 새겨져 있다. 반지에 각인된 문자열을 www.acmicpc.net 2. 풀이 보통 target 문자열 찾을때는 한줄 안에서 똑같이 있는지 찾았지만 이 문제는 target 문자열이 뒤로 넘어가면 다시 처음부터 되돌아가야한다 ZAAAAAAAXY에서 XYZ를 찾고자 할때, Z XY 하면 하나를 찾을 수 있다는 뜻 어떻게 할 수 있을까 찾고자 하는 문자열 XYZ의 길이가 3이고 처음부터 끝까지 순회하는데... ZAAAAAAAXY XYZ에 도달하면 끝인데.. 여기서 YZ는 다시 처음 2글자 Z..

  • format_list_bulleted 문자열 알고리즘
  • · 2023. 3. 14.
  • textsms

정수론 - 방정식을 만족하는 순서쌍의 수 세기 - 브루트포스 탐색 범위 줄이는 테크닉 익히기

1. 문제 C - Four Variables (atcoder.jp) C - Four Variables AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이1 당연히 안될 것 같지만 방법을 모르겠다면 브루트포스로 접근하는게 기본이다 AB+CD = N을 만족하는 양의 정수쌍 A,B,C,D를 찾기 위해 1부터 N까지 순회해본다 이 값을 AB = x라 하고, 그렇다면 CD는 자동으로 N-x로 결정된다 그리고 AB = x에서 1부터 x까지 순회해서 그 수를 A라 하고, 만약 x가 A로 나누어 떨어진다면 B를 찾은 것이다. 마..

  • format_list_bulleted Atcoder
  • · 2023. 3. 11.
  • textsms