수학과의 개발자 도전기

-문제: https://www.acmicpc.net/problem/1965

가장 긴 증가하는 부분수열 문제

-정답풀이:

n=int(input())
data=list(map(int,input().split()))
dp=[0]*n

for i in range(n):
    for j in range(i+1):
        if data[i]>data[j] and dp[i]<dp[j]:
            dp[i]=dp[j]
    dp[i]+=1
print(max(dp))

-문제: https://www.acmicpc.net/problem/17070

깊이우선 탐색인 것 같은데 이전에 풀었던 문제는 동,서,남,북 네 방향이었는데 이거는 대각선 포함 방향 3개라서 또 새로운 문제였다 

-정답풀이1: 

• pypy3으로 돌려야지 시간초과가 안 뜬다 
• 방향이 세개인 걸 shape으로 나누어서 진행하면 된다 
• 파이프를 옮기다 보면 n-1 컬럼에 있을 때 예외상황을 어떻게 처리해야하는지 잘 몰랐는데 10,14,18번 줄처럼 if문 처리하면 된다 
• 진행할 때 주변에 벽(숫자 1)이 있는지 없는지 확인할 방법은 11,15,19번 줄을 참고하면된다 

-정답풀이2:

• 따로 0행렬을 만들어서 거기에 경우의수 누적하려고 했는데 방향이 3개라서 경우의 수를 나누는게 어려웠다.
• 그런데 이제 같은 크기의 행렬을 3개 만들어서 각각 움직이는 경우의 수 대입한 후에 행렬 오른쪽 끝 값을 모두 더해서 출력하면 답이다. 

-문제: https://www.acmicpc.net/problem/1915

-정답풀이: 

• DP 문제풀면서 접했던 유형 -> 풀이방법 계속 익혀야함 

-문제: https://www.acmicpc.net/problem/10942

문자열 뒤집어서 생각하면 되겠지라고 단순하게 여겼는데, 생각보다 어려웠던 문제. dp문제이니 dp원리로 푸는 연습 꾸준히 해야할 것 같다 

-참고한 블로그

이해한 원리로는

• start부터 end까지 팰린드롬인지 확인하려고 할 때, 문자열 start+1 부터 end-1까지 팰린드롬이라면 start와 end만 비교하면 팰린드롬인지 알 수 있다. 
• 즉, 어떤 문자열이 팰린드롬인지 확인하려면 양 끝의 문자가 같은지를 확인하고 양 끝단을 제외한 문자열이 팰린드롬인지 확인하면 된다

따라서, 어떤 문자열이 팰린드롬인지를 판단하는 과정은 다음과 같다.

• 양 끝의 문자가 다르면 -> 팰린드론 아님 
• 양끝의 문자가 같을 때, 가운데 문자열이

         -팰린드롬이라면 팰린드롬

         -팰린드롬이 아니라면 팰린드론 아님 

• 가운데 문자열이 팰린드롬인지 아닌지 모른다면 알 때까지 문자열의 길이를 앞뒤로 하나씩 줄이면서 위의 과정을 반복한다

-> 문자열의 범위를 줄여가면서 같은 과정을 계속 반복한다는 점에서 DP 문제라고 할 수 있다

-정답풀이: