지민 개발 블로그

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)www.acmicpc.net풀이과정①문제 들여다보기이 문항은 앞전에 푼 11053문제에서 아주 살짝 업그레이드 된 버전의 문제이다.https://stopmin.tistory.com/46 [백준] 11053번 가장 긴 증가하는 부분수열 (Python)https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이www.acmicpc.net풀이과정①문제 바라보기N으로 전체 수열의 길이를 받고, 다음줄에 array가 입력된다.array에서 몇 개의 수를 지움으로써 만들 수 있는 가장 긴 증가하는 수열의 길이를 인쇄하는 문제다. ②아이디어 열기이 문제는 동적계획법으로 해결이 된다.이중 for문을 활용하여서 해결되는 문제였다.현재 해당하는 위치의 숫자보다 앞에 있는..

https://www.acmicpc.net/problem/2156 2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net풀이과정①문제 바라보기DP문제임은 자명하다. 계단 오르기 문제랑 굉장히 유사하게 느껴졌다.더보기이것이 계단오르기다.https://stopmin.tistory.com/42 [백준] 2579번 계단오르기 (Python)https://www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www...

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.www.acmicpc.net풀이과정①문제 바라보기DP문제인데 규칙을 발견해야한다고 생각했다. 0과 9의 경우 특별한 Case이기에 따로 분류해서 처리해야 한다. ②아이디어 펼치기아래는 수형도이다.N == 1일 경우, 0은 불가능하고 나머지 1~9는 모두 가짓수가 1개가 된다.N == 2일 때 부터 규칙이 발견이 되는데 편의상 N이 3~4일 때로 예시를 들었다. dp[4][0]으로 가기 위한 방법의 개수는 dp[3][1] 온전히 갖게 된다.dp[4][9]으로 가기 위한 방법의 개수는 dp[3][8] 온전히 갖게 된다.나머지 경우에서는 모두 양쪽..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.www.acmicpc.net풀이 과정①문제 바라보기처음에 이 문제가 Greedy 문제인 줄 알았다. 그러나 알고보니 DP문제! 뭔가 greedy로 풀릴 것 같기도하다.이 문제도 메모이제이션 기법으로 풀릴 것이다. 문제에서 내가 할 수 있는 조치는 다음과 같다.X가 3으로 나누어  떨어지면 3으로 나눈다.X가 2로 나누어 떨어지면 2로 나눈다.1을 뺀다. ②아이디어 펼치기자명한 사실이 있다. N을 만드는 데 x번의 단계가 필요하다면 그냥 -1만 가능하다고 할 때, N+1은 x+1단계가 필요하다. 이 문제를 풀기 위해서는 dp 테이블이 필요하고 ..

https://www.acmicpc.net/problem/2579과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/problem/2579" data-og-url="https://www.acmicpc.net/problem/2579" data-og-image="https://scrap.kakaocdn.net/dn/cbS18u/hyPBHwY36Z/t4fQQICEuyrkeFlre3K2dk/img.png?width=2834&height=1480&face=0_0_2834_1480,https://scrap.kakaocdn.net/dn/znlJ..

https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.www.acmicpc.net풀이과정①문제 들여다보기이건 RGB 문제랑 유사한 것 같음. 다만, list의 len이 매번 달라져서 이 부분을 좀 신경써줘야 한다고 생각함. ②아이디어 열기일단 range를 거의 쌩까고 코드를 짜봄역시 IndexError가 떴다. 심지어 print(max(dp[N-1])) 로 해줘야함! 굉장히 멍청한 실수였다. list의 첫 번째와 마지막 부분일 때 예외적으로 dp[i-1][j-1]과 dp[i-1][j]를 비교할 수 없기에 따로 처리를 해주었다.근데 이 코드가 과연? 시간..

https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net풀이과정①문제 들여다보기누가봐도 dp문제다. 보텀업 방식으로 이 문제는 해결될 것이다. ②아이디어 열기이 문제를 풀기 위해서는 max함수를 활용하고 역시 하던대로 반복문을 활용해야한다.dp[i] = max(dp[i],dp[i-1]+dp[i])가 필요함을 느꼈다.그래서 일단 코드를 짜봤는디생각보다 짧게 나왔다.2주전에 한 코드보다 더 좋았다. 그런데 한번 실수를 했었는데,dp[i] = max(dp[i],dp[i-1..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의www.acmicpc.net풀이 과정① 문제 바라보기 관찰을 해보니 점화식 작성이 간단하게 됩니다. 알고보니 피보나치였음! ② 아이디어 열기그럼 보톰업방식으로 해결이 아래와 같이 됩니다.**보톰업방식: 단순히 반복문을 이용하여 소스코드를 작성하는 경우 작은 문제부터 차근차근 답이 도출되는 것dp = [0 for _ in range(101)]dp[1] = 1dp[2] = 1dp[3] = 1for i in range(4,101):    ..

https://www.acmicpc.net/problem/1904 1904번: 01타일지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이www.acmicpc.net풀이과정①문제 바라보기 이 문제는 타일링문제로 dp문제 중 하나이다. 저번에 타일링 문제를 풀었었는데 그때 점화식으로 푼 기억이 난다. 사실 dp문제가 점화식으로 많이 풀리긴 하더라..고통을 받으며 점화식을 찾게 되었다.dp[i] = dp[i-1] + dp[i-2] 였던 것임! ②아이디어 열기신나는 마음으로 코드를 짰는데.. 나름 짧아서 예뻤다. 근데 메모리초과가 떴다!! 오마이갓..사실 저 식이 피보나치잖..