분류 전체보기
백준 2579: 계단오르기 해설- python
✏️ 문제 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net ✏️ 풀이 케이스는 두가지로 분리된다. 이전에 두 계단을 연속으로 오른 경우. 그리고 3계단 이전에는 두계단을 오르고 바로 이전에서 현지점까지 연속으로 올라오는 경우. 본 문제에서는 리스트를 두개 만들었다. i번째 계단까지 최대값을 저장하는 dp[] & 문제에서 준 계단점수를 저장하는 arr[] 이를 점화식으로 나타내보면 아래와 같을 것이다. 1. dp[i-2] + arr[i] 2. dp[i-3] + arr[i-1] + arr[i] n=int(input()) ar..
백준 2748번 런타임에러(IndexError)
2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 이건 글 쓸 생각 없었는데 현타가 와서 글을 남긴다. 나같은 사람이 어딘가에 또 있을거라 생각하고 도움이 되고자한다. DP로 간단하게 코드를 적고 제출버튼을 딱 눌렀더니 런타임에러가 떴다. n=int(input()) dp=[0]*(n+1) dp[1]=1 dp[2]=1 dp[3]=2 for i in range(4,n+1): dp[i]=dp[i-1]+dp[i-2] print(dp[n]) 왜 일까 한참을 고민하고보니 3이하의 수를 ..
밤이 얼마나 지났는가. 아직 절반도 못 되었네
夜如何其夜未央 밤이 얼마나 지났는가. 아직 절반도 못 되었네 繁星粲爛生光芒 뭇별들이 눈부시게 빛을 내누나. 深山幽邃杳冥冥 깊은 산 그윽한 골짜기 어둡기만 한데 嗟君何以留此鄕 그대는 어이해 이 고장에 머무는가. 훈련소 동기가 몰래 가져온 책을 통해 접한 김시습의 夜如何라는 시의 일부였다. 인상이 강렬해 노트에 옮겨적었던 몇가지 글 중 일부였다. 저자 김연수의 설명은 김시습이 마주한 상황의 암담함을 더욱 선명하게 전달해주었다. 김시습은 이 시에서 '杳冥冥'이라고 그러니까 어둡고 어두울 정도로 어둡다며 세번이나 어둡다는 말을 썼다. 김시습이 마주한 어둠은 과연 어떤 것이었을까? 당시는 선조가 의주파천을 하던 때였다. 그때의 어둠에 비할 수는 없겠으나 군입대를 위해 포기해야만 했던 소중한 것들에 대한 억울함과 ..
백준 9095: 1, 2, 3 더하기 해설- python
✏️ 문제 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net ✏️ 풀이 늘 그렇듯 규칙을 찾아보자. n=1 일 때, 1n=2 일 때, 1+1, 2n=3 일 때, 1+1+1, 1+2, 2+1, 3n=4 일 때, 1+1+1+1, 1+3, 3+1, 4....어? 이거다. 1+3은 1+(1+1+1), 1+(1+2), 1+(2+1), 1+(3). 아까 n=3일 때 해결한 문제를 내포하고 있다.즉 n이 3보다 커지면 그 문제들은 n=1,2,3일 때의 문제를 포함하고 있다.즉 작은 문제(n=1,2,3)를 이용해 큰 문제를 해결하는 동적계획법(Dynamic Programming)을 이용하면 적합하겠다. [Python & A..
[俳句] 이 숯도 한때는
白炭ややかぬむかしの雪の枝 -神野忠知 이 하이쿠의 季語는 雪, 흰눈이다. 俳句는 저마다 각자의 계절을 가진다. 계절은 시간이고 시간은 무언가의, 또는 누군가의 이야기다. "이 숯도 한때는 흰 눈이 얹힌 나뭇가지였겠지" 까맣게 타버린 사물에서 神野忠知(타다토모)는 이야기를 발견했다. 숯의 이야기는 그저 사물이었던 숯에 가치를 부여하지만 역설적으로 그 이야기는 존재의 덧없음과 유한성에 대해 말한다. 한국의 선시(禪詩)에서 느껴지지 않는 무언가를 내가 俳句에서 느끼는건 季語를 가지기 때문일 것이다. 俳句의 季語 덕분에 하이쿠는 시간을 사진을 찍듯 간직하고 그걸 접하는 이들의 생각 속에 하이쿠가 담은 시간을 그려낸다. 하이쿠가 그려내는 그림들이 마음에 든다.
백준 11727: 2xn 타일링(2) 해설- python
✏️ 문제 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net ✏️ 풀이 2xn 타일링 문제에서 2x2타일이 추가된 형태의 문제로 점화식만 살짝 수정해주면 된다. 2xn 타일링 문제는 아래에서 다시 풀어보자 백준 11726: 2xn 타일링 해설- python ✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acm duckracoon.tistory.com 이전의 문제에서는 점화식이 c..
백준 11726: 2xn 타일링 해설- python
✏️ 문제 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net ✏️ 풀이 뭘 어쩔지 모를땐 늘 그렇듯 규칙을 찾아보자. 모든 경우의 수를 한번 생각해보았다. n=1 > size 1 : 1개 n=2 > size 1: 2개 || size 2: 1개 n=3 > size 1: 3개 || size 1: 1개 + size 2: 2개 || size 1: 2개 + size 2: 1개 n=4 > size 1: 4개 || size 1: 2개 + size 2: 2개(L) || size 1: 2개 + size 2: 2개(R) || size 1: 1개 + s..
백준 1463: 1로 만들기 해설- python
✏️ 문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net ✏️ 풀이 해당 풀이는 주로 동적계획법 (Dynamic Programming) 을 이용하는 것 같다. 동적계획법에 대한 설명은 아래글을 참고하자. [Python & Algorithm] Dynamic Programming(동적프로그래밍) ✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나 duckracoon.tistory.com 어떻게 시작해야할지 잘 모르겠으니 나는 임의의 X를 가지고 수가 어떻게 변하는지를..
[俳句] 하이쿠
蝉時雨子は担送車に追ひつけず -石橋秀野 매미소리 쏴- 아이는 구급차를 못 쫓아왔네. 해군 훈련소 6주를 버티다 우연히 접한 하이쿠다. 하이쿠는 5.7.5의 음수율을 가진 일본의 정형시인데, 처음 봤을땐 시로 느껴지지도 않았고, 어떤 감상도 없었다. 하지만 이 시의 배경을 알게되면서 하이쿠에 빠지게 되었다. 이시바시 히데노가 이 俳句를 지을 당시인 1947년엔 쿄토에 결핵이 유행했었다한다. 그리고 이시바시 또한 결핵환자였다. 병이 심해져서 곧 죽음을 앞두게 된 이시바시는 구급차에 실려가게 된다. 이를 보는 그녀의 딸이 구급차를 쫓아간다. 하지만 아이의 짧은 다리로써는 구급차를 따라갈 수 없었다. 매미들이 시끄럽게 우는 가운데 아이도 함께 울고, 병실에서 이시바시는 눈물을 흘리며 매미소리를 듣는 수 밖에 없었..
[Python & Algorithm] Dynamic Programming(동적프로그래밍)
✏️ Dynamic Programming 큰 문제를 작은 문제로 나누어 푸는 문제를 이야기한다. 이름에 의미는 없다. 그냥 말이 멋있어서 이렇게 지었다고 한다. 1) 분할정복과의 차이 '작은 문제가 중복이 일어나는지 아닌지' 에 차이가 있다. 분할정복은 큰 문제를 해결하기 어려워서 단지 작은 문제로 나누어서 푸는 방법이다. 특징은 작은 문제에서 반복이 일어나는 부분이 없다는 점이다. 하지만 동적프로그래밍은 작은 부분문제들이 반복되는 것을 이용해 문제를 풀어낸다. 2) 다이나믹 프로그래밍의 방법 모든 작은 문제들은 한번만 풀어낸다. 따라서 정답을 구한 작은 문제를 어딘가에 메모해둔다. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 작은 문제가 나타나면 앞서 메모한 작은 문제의 결과값을 이용한다. 3) 다이나믹..