printf("hellow coding");

https://www.acmicpc.net/problem/11726

이 문제는 앞에서 포스트 했던 '이친수' 문제와 상당히 유사합니다. 

경우의 수를 나열해 보아도 쉽게 규칙이 보이지만, 이론적으로 생각해 보아도 쉽게 규칙을 발견할 수 있습니다. 

위 그림은 i = 5 일 때의 예시입니다. 

따라서 이와 같은 알고리즘을 코드로 구현하면 쉽게 풀이가 가능합니다. 

#타일 2xn n = int(input()) dp = [0 for _ in range(n+1)] for i in range(n+1): if i == 0: dp[i] = 0 continue elif i==1 or i==2: dp[i] = i else: dp[i] = dp[i-2]+ dp[i-1] print(dp[n]%10007)

https://www.acmicpc.net/problem/15664

유명한 N과 M 시리즈이다. 

이 문제는 앞에서 포스트한 N과 M(8)번 문제의 연장선이다.

이 문제에서 중요한건 dfs를 이용하여 필요한 경우의 수를 탐색한 후 결과값으로 출력하는 것이다 

즉, 핵심 알고리즘 부분은 for문에서 index 범위를 지정하여 탐색하는 부분이라 할 수 있다. 

우선 코드는 다음과 같다. 

# 엔과 엠 (10) n,m = map(int,input().split(' ')) number = list(map(int,input().split(' '))) number.sort() array = [] result = [] def solve(level, index): if level == m: a= ' '.join(map(str,array)) if a not in result: result.append(a) print(a) return for i in range(index, n): #핵심 부분 array.append(number[i]) solve(level+1, i+1) array.pop() solve(0,0)

앞서 포스트한 N & M(8)서는

solve(level+1, idx) -> 탐색을 하고 해당 idx를 넘어가지 않고 그대로 input으로 두어 탐색할 수 있게 하였다면 

이번 포스트에서는 solve(level+1,idx+1) 로 지정하여 한번 탐색한 경우는 다시 고려하지 않고 넘어가는 식으로 구현하는것이 차이라고 볼 수 있다. 처음에 풀때 input 문자열을 굳이 int형으로 지정하여 문제를 풀었었는데 그럴필요없이 str 자료형으로 문제를 해결하면 될듯하다. 

https://www.acmicpc.net/problem/2193

이 문제는 '타일' 문제와 비슷하다 

시작은 무조건 1로 시작해야하며, 11이 두 번 연속으로 나타나지 않는 이진수를 찾는 문제이다.

그냥 경우의 수를 나열해 봐도 쉽게 규칙을 찾을 수 있지만 

조금만 생각해보면 알고리즘을 금방 생각할 수 있다. 

만약 4자리 이친수의 갯수를 찾는다하면 (dp[4]라고 하자) 

dp[3](3자리 이친수) 에다 마지막에 '0'을 하나 붙여도 이친수를 만족하며

dp[2](2자리 이친수) 에다 앞에 '10'을 붙여도 위 두 조건을 만족한다 

따라서 규칙은 dp[i] = dp[i-1]+dp[i-2]임을 알 수 있다. 

코드는 아래와 같다.

n = int(input()) dp = [0, 1, 1] for i in range(3, n+1): dp.append(dp[i-1]+dp[i-2]) print(dp[-1])

https://www.acmicpc.net/problem/8595

이 문제는 사실 알고리즘이 특별하다기보다 구현하는데 있어서 조금 생각이 필요했던 문제였습니다. 

어설프게 for문을 여러번 돌릴경우에 시간초과가 나기 때문에, 주어진 문자열을 for문 한번에 돌려 

해답을 찾아내는 구현을 하는것이 관건입니다.

이를 위해서 앞에서 부터 문자열을 탐색하는 것이 아닌 뒤에서 부터 문자열을 탐색하여

숫자가 하나씩 나올 때마다 (자리수) * 해당숫자, 즉 처음 나온 숫자라면 1*(해당 숫자) 

두번째 연속으로 나온 숫자라면 10*(해당숫자), 이런 식으로 탐색하여 더해주는것이 해답입니다. 

코드는 아래와 같습니다.

import sys n = int(input()) word = input() number = [str(i) for i in range(10)] def solve(): jump = 1 result = 0 temp = 0 for i in range(n): i = -i -1 if word[i] in number: temp += int(word[i])*jump jump = 10*jump if i ==-n or word[i] not in number: if jump >= 10000000: #숫자가 6자리 이상이라면 종료, jump = 1 temp = 0 continue result += temp jump = 1 temp = 0 print(result) solve()

https://www.acmicpc.net/problem/15657

이번 문제는 장장 1시간 가까이 삽질을 한 문제입니다.. 

알고리즘 자체는 dfs를 잘 알고 있다면 무난하게 풀 수 있는 문제입니다. 

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다

이 3가지 조건중에서 3번째 조건은 맨처음 받은 입력을 정렬만 해주면 해결되는 문제이고,

첫번째 M개를 고른다는 조건은 dfs에서 level M 까지 탐색하고 종료한다는 뜻 

두번 째 같은 수를 여러 번 골라도 된다 라는 조건은 알고리즘 적인 코딩을 통해 해결할 수 있습니다. 

그에 따라 작성한  코드는 다음과 같습니다. (주의!  틀린부분이 있습니다.)  

n,m = map(int, input().split(' ')) number = input().split(' ') number.sort() array = [] def dfs(level, index): if level == m: print(' '.join(result)) return for i in range(index,n): array.append(number[i]) dfs(leve+1, i) # 같은수를 여러번 뽑을 수 있으니까 i번을 넣음, # 여러번 뽑을 수 없다면 i+1을 넣음 array.pop(-1) #또다른 경우를 넣어주기위해 기존의 경우를 pop

위에서 틀린 부분 눈치채셨나요?

이 코드를 작성할 때 입력을 한자리수 숫자로 가정하고 작성하였습니다.. 

한자리 수일 때는 문제가 없지만 만약 숫자가 한자리수 이상일 경우에는 

문자열로 받을경우 1234 -> '1','2','3','4' 로 받게 되기 때문에 기존의 생각한 것과 다른결과를 얻게됩니다..

저는 이 부분을 생각을 못해 1시간 동안 오류를 찾는데 시간을 보냈습니다..

수정한 코드는 아래와 같습니다. 

n, m = map(int, input().split(' ')) number = list(map(int, input().split(' '))) number.sort() array = [] def dfs(level, index): if level == m: print(' '.join(map(str, array))) return for i in range(index, n): array.append(number[i]) dfs(level+1,i) array.pop() dfs(0,0)

https://www.acmicpc.net/problem/1937

이번 문제는 구현을 생각하는데 있어서 까다로웠던 문제였습니다. 

일단 그래프를 탐색하는데 있어서 dfs를 재귀적으로 구현, 또 탐색에 조건문을 달고, dp의 메모이제이션을 이용하여 연산 케이스 감소 등 3개의 콤비네이션을 이용한 구현이 필요했는데요.. 처음 구상한 주도 코드는 다음과 같습니다

어차피 조건에 항상 더 큰 숫자가 있는곳으로만 이동한다 하였으니, 다시 같은곳으로 되돌아오게될 경우를 

체크할 필요는 없습니다. 다만 문제에 주어진 조건을 잘 정의하고, 해당하지 않는경우는 pass, 

그리고 dfs로 탐색하게 될경우 재귀적으로 반환값을 받아 차례대로 각 이동경로마다의 best값을 설정하게 해주는 부분이 생각하기 까다로웠던것 같습니다.  

위 주도코드를 기반으로 작성한 코드는 다음과 같습니다. 

import sys n = int(input()) forest = [list(map(int, input().split(' '))) for _ in range(n)] dp = [[-1 for _ in range(n)] for _ in range(n)] direct = [(0,1),(0,-1), (1,0), (-1,0)] sys.setrecursionlimit(1000000) #중요, 선언하지 않으면 런타임 에러.. def dfs(i,j): if dp[i][j] != -1: return dp[i][j] else: dp[i][j] = 1 for k in direct: mv = tuple(sum(elem) for elem in zip((i,j), k)) if mv[0] <0 or mv[0]>=n or mv[1] <0 or mv[1]>=n or forest[i][j] >= forest[mv[0]][mv[1]]: continue else: dp[i][j] = max(dp[i][j], dfs(mv[0],mv[1])+1 ) return dp[i][j] def solve(): best = 0 for i in range(n): for j in range(n): best = max(best, dfs(i,j)) print(best) solve()

여기에서 중요한 부분은 sys.setrecursionlimit(1000000) 를 선언해주는 것이었는데요..

파이썬에서는 재귀적 탐색할 경우 탐색할 수 있는 깊이가 제한되어있어서 이렇게 리미트를 해제해야 합니다 

또한 dp[i][j]가 기본적으로 어떠한 값이 설정되어있다면, 그 값을 return하게 하여 불필요한 탐색경우를 줄였습니다. 

이상으로 욕심쟁이 판다 포스트를 마치겠습니다. 

https://www.acmicpc.net/problem/1912

dp문제는 일단 배열에 적어가다보면 해결방법이 보이는것 같습니다. 

우선 위 검은색 글자가 주어진 수열이며, 빨간색이 갱신되는 dp 배열에 들어갈 요소입니다. 

최고값만 찾으면 되므로 일단은 다 더해본 후 그중 최고의 값을 찾으면 됩니다. 

다만 한가지 규칙이 있는데요 바로 dp[i]와 그 다음 i+1번째의 숫자요소를 더해 본 후 

그값이 i+1번째 숫자요소보다 작을경우는 dp[i+1]번째 값을 i+1번째 숫자요소로 갱신합니다. 

왜냐하면 dp[i]와 num[i+1]이 그냥 기존의 num[i+1]값보다 작게된다면, 

num[i+1]부터 숫자를 더해가는것이 기존의 값을 이어가는 것 보다 더 크기 떄문입니다. 

따라서 이와같은 규칙을 염두하여 코드를 작성하면 다음과 같이 간단히 짤 수 있습니다. 

n = int(input()) num_list = list(map(int,input().split(' '))) dp = [num_list[0]] for i in range(n-1): best.append(max(dp[i]+num_list[i+1], num_list[i+1])) print(max(dp))

https://www.acmicpc.net/problem/2163

이 문제는 dp 문제로 굉장히 쉬운 문제입니다. 

복잡하게 생각할 필요없이 배열에 수를 채워나가다 보면 규칙이 보이는 문제인데요

먼저 임의의 NxM의 배열에 대해서 쪼개는 갯수를 다음과 같이 채워넣어봅시다.

규칙은 한눈에 봐도 알수 있을만큼 단순합니다.

즉 첫번째 열의 N번째 요소에 대해서  x m +(m-1)을 수행한다면

(i,m) 번째 요소를 구할 수 있습니다. 즉 우리가 필요한 것은 (5,4), 즉 (m,n)의 요소이므로 

(1,m)*m+m-1을 계산하면 답을 구할 수 있겠네요, 따라서 코드를 작성하면 다음과 같습니다. 

m, n = map(int, input().split(' ')) dp = [] def init(dp): for j in range(n): dp.append(j) def solve(dp,m,n): init(dp) print(dp[n-1]*(m)+(m-1)) solve(dp,m,n)