[99클럽 코테 스터디] 📝 Day30. 문자열 2

99클럽 코테 스터디 30일차 TIL + 문자열

📍 오늘의 학습 키워드

• 팰린드롬
• 중심 확장 알고리즘
• 동적 계획법(Dynamic Programming)
• 시간 복잡도와 공간 복잡도

📝 공부한 내용 본인의 언어로 정리하기

오늘은 문자열 알고리즘 중에서 팰린드롬 관련 내용을 공부했습니다. 팰린드롬은 앞에서부터 읽으나 뒤에서부터 읽으나 동일한 문자열을 의미합니다. 이를 찾기 위해 중심 확장 알고리즘과 동적 계획법을 배웠습니다.

중심 확장 알고리즘은 문자열의 각 위치를 중심으로 팰린드롬을 확장해나가는 방식으로, 홀수 길이와 짝수 길이의 팰린드롬을 모두 처리할 수 있습니다. 이 알고리즘을 이용하면 O(n^2)의 시간 복잡도로 가장 긴 팰린드롬 부분 문자열을 찾을 수 있습니다.

동적 계획법은 중복 계산을 최소화하면서 문제를 해결하기 위한 방법으로, 이를 활용하여 효율적인 팰린드롬 탐색 알고리즘을 설계하는 방법도 배웠습니다.

📖 오늘의 회고

📚 어떤 문제가 있었고, 나는 어떤 시도를 했는지

오늘은 팰린드롬을 찾는 다양한 알고리즘에 대해 학습하였습니다. 초기에는 브루트 포스 방식과 재귀적 접근을 통해 팰린드롬을 찾는 방법을 구현하고자 했으나, 이 방법들은 효율성이 낮고 중복 계산이 많아 성능이 좋지 않음을 배웠습니다.

이후 중심 확장 알고리즘과 동적 계획법을 배우고, 이를 활용하여 효율적인 팰린드롬 탐색 알고리즘을 구현하였습니다. 각 알고리즘의 시간 복잡도와 공간 복잡도를 비교하고, 각각의 장단점을 이해하며 문제 해결에 대한 접근 방법을 조정했습니다.

🤔 어떻게 해결했는지

🔖 참고링크 (https://develop-tracking.tistory.com/112)

🤓 무엇을 새롭게 알았는지

팰린드롬을 찾는 다양한 방법과 각 방법의 성능 차이를 배웠습니다. 특히 중심 확장 알고리즘과 동적 계획법의 활용법을 심도 있게 이해할 수 있었습니다.

⏳ 내일 학습할 것은 무엇인지

내일은 문자열 알고리즘의 또 다른 주제인 KMP(Knuth-Morris-Pratt) 알고리즘에 대해 학습할 예정입니다. 문자열 검색을 효율적으로 수행할 수 있는 이 알고리즘에 대해 깊이 있게 이해하고 구현하는 것이 목표입니다.