TIL_20230414

오늘 할 일

• LeetCode 데일리 문제 풀기
• 네이버 코딩테스트 준비

오늘 배운 것

LeetCode 데일리 문제 풀기

• 오늘의 문제: 516. Longest Palindromic Subsequence(https://leetcode.com/problems/longest-palindromic-subsequence/)
• 문제 조건
  
  • 문자열 s가 주어졌을 때, s 내에서 가장 길게 팰린드롬 서브 시퀀스의 길이를 찾아라.
• 문제 해결 과정
  
  • 투 포인터로 해보려고 했으나 fail -> 중간에 껴있는 애들부터 앞이나 뒤에 연속으로 몰린 경우를 처리하지 못한다.
  • 문자열에서 팰린드롬이 가능한 경우를 찾기 위해 LCS가 적합하다는 이야기를 들었으나 이해가 잘 가지 않아서 HELP...
  • top-down 방식과 bottom-up 방식이 있는데, top-down으로 해보겠다.
  • 재귀적으로 첫 값과 끝 값을 비교하면서 같은 값인 경우와 다른 값인 경우로 나눠서 부분 문자열을 만들 수 있다.
  • 우선 기저를 설정해주어야 한다.
    • l > r이면 0, l == r이면 1, memo[l][r] > 0이면 memo[l][r]을 반환한다. 그 이유는 l이 r보다 커지는 경우는 해당 위치에서 시작하는 팰린드롬을 고려할 필요가 없기 때문이고, l == r인 경우는 문자 하나가 팰린드롬이 될 수 있기 때문에 1이 되는 것이고, memo[l][r]에 이미 값이 있다면 해당 값을 반환해줘야 팰린드롬이 되는 경우를 합산할 수 있기 때문이다.
  • 같은 경우
    • 첫 값 + 1, 끝 값 - 1씩 해줘서 안쪽에 있는 값이 팰린드롬이 될 수 있는지 확인하고 문자의 개수인 2를 더해준다.
  • 다른 경우
    • 현재 가리키고 있는 memo[][]에서 (첫 값 + 1, 끝 값)과 (첫 값, 끝 값 + 1)의 값 중 더 큰 값을 할당한다. 그 이유는 팰린드롬이 되는 경우 더 큰 값이 반환될 것이기 때문이다.

네이버 코딩테스트 준비

• 문제를 풀기에는 시간이 너무 없어서 dfs/bfs, 이진탐색, 슬라이딩 윈도우 등 이전에 나온 네이버 기출 문제들의 유형을 익히는 시간을 가졌습니다.

느낀점

• 리트코드에서 나오는 문제 중 dp는 구현하기가 좀 어렵습니다. 알고리즘 책을 사서 공부해야 하나 고민중입니다...
• 코딩테스트를 내일 봐야 하는데, 시간 조절이 잘 안됐습니다. 새벽 2시에 자게 생겼네요.

내일 할 일

• LeetCode 데일리 문제 풀기
• 네이버 코딩테스트