Algorithm

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 풀이과정 ①문제 들여다보기 dp 문제임은 자명하고, dp테이블을 만들어서 for문을 통해서 답을 도출하는 것임에 분명하다. 계단을 타는 조건은 세 가지인데 한 번에 한 계단 또는 두 계단씩 오를 수 있음 연속된 세 계단은 오를 수 없음 마지막 도착 계단은 무조건 밟아야함 ②아이디어 펼치기 1번 조건은 for문으로 해결할 수 있다. 3번 조건은 계단순서를 reverse해서 미리 한 칸을 밟아놓은 상태로 시작하면..

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(d..

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

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를 넣을 경우 굉장히 연산 속도가 느렸다. 조금 생각을 해보니 위의 코드는 탑다운 방식처럼 재귀를 사용해서 느린 것 같다. 그래서 반복문을 활용하는 보텀업 방식을 사용하면 해결 될 수 있을거라는 생각을 하게 되었다. 그런데 문제는, 값이 a..