지민 개발 블로그

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] 였던 것임! ②아이디어 열기신나는 마음으로 코드를 짰는데.. 나름 짧아서 예뻤다. 근데 메모리초과가 떴다!! 오마이갓..사실 저 식이 피보나치잖..

https://www.acmicpc.net/problem/9184 9184번: 신나는 함수 실행입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.www.acmicpc.net풀이과정①문제 바라보기굉장히 와닿지 않았다. 굉장히 굉장히.. 그래서 recursive로 먼저 코드를 작성해보았다.그런데 문제의 설명대로 역시 15  15 15를 넣을 경우 굉장히 연산 속도가 느렸다.조금 생각을 해보니 위의 코드는 탑다운 방식처럼 재귀를 사용해서 느린 것 같다. 그래서 반복문을 활용하는 보텀업 방식을 사용하면 해결 될 수 있을거라는 생각을 하게 되었다. 그런데 문제는, 값이 abc로 세 ..