수학과의 개발자 도전기

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

-정답풀이: 

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

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

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

-참고한 블로그

이해한 원리로는

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

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

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

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

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

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

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

-정답풀이:

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

-정답 풀이1:

• 1~2번 라인 입력 해줘야 시간초과 발생하지 않는다 
• dp인덱스는 i,j 모두 +1씩 해줘야 계산하기 편함

-정답 풀이2:

-틀린풀이:

• 간단하게 for문 두개로 풀려고 했는데 이게 O(n^2)라서 시간초과가 발생한다 

-문제풀이 원리는 https://claude-u.tistory.com/427 여기를 참고했다. 

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

점화식이 문제에 주어져있었던 문제라 메모이제이션을 하면 되는 걸 알았지만 어떻게 메모이제이션을 할지 몰랐다

a,b,c 인자가 세개 이므로 1x3행렬을 만들어서 메모이제이션하고 그 값을 리턴해주면 된다

-정답풀이:

• 여기서 23번째 줄에 '=' 앞 뒤에 띄어쓰기를 안 줘서 엄청 틀렸다; 30분 동안 헤맸음 
• 답 출력할 때는 문제에서 주어진 답 형태로 출력해야함
• 1) 메모이제이션 하는 법 익히고 2) 답 정확히 출력하는 것 익히자