[99클럽 5기] Day21 TIL - String, Sort, Map, Dynamic Programming

99클럽 5기 | Java | Middler

 

🗝️ 오늘의 학습 키워드 : String Sort Map Dynamic Programming

⌛ 회고

미들러 문제를 풀고 잠깐 졸았는데 어느새 온라인 스터디 마치는 시간이 거의 다 되어서
급하게 출석을 하였는데 딱 10시 정각에 맞게 출석을 하였습니다.
덕분에 오늘은 다른 분들 발표하는 것을 보지 못하였습니다.ㅜㅜ
대신 미들러 문제 풀이 작성 후, 비기너 문제라도 하나 더 풀자는 마음으로 파일 정리 문제를 풀었습니다.
그런데 문자열에 split() 메서드를 사용하는 부분에서 에러가 발생하였고
에러의 원인은 마침표(.)를 기준으로 문자열 분리 시, 그냥 마침표만(split(".")) 넣으면 문자열 분리가 되지 않기 때문이었습니다.
덕분에 마침표를 기준으로 문자열 분리하는 방법을 알게 되었습니다.
엊그제 일본 웹 개발 회사에 이력서를 넣었는데 언제쯤 소식이 오려나 하루가 너무 길게 느껴지는 것 같은데
꼭 붙어서 웹 개발자로 일하며 많이 배우고 얼른 Expert Programmer가 되고 싶습니다.

 

❓ 오늘 만난 문제

• 🥉 비기너 : 파일정리
• 🥈 미들러 : 피보나치 함수
• 🥇 챌린저 : 파괴되지 않은 건물

 

💦 나의 시도 & 해결 방법👍

🥉 비기너 : [백준 | Java] 20291번 파일 정리 - String, Sort, Map
🥈 미들러 : [백준 | Java] 1003번 피보나치 함수 - Dynamic Programming
🥇 챌린저 :

 

❗ 무엇을 새롭게 알았는지

동적 계획법(DP; Dynamic Programming)

작은 문제들을 풀면서 그 결과를 저장해 나아가면서 전체 문제를 해결하는 알고리즘

• 중복 계산을 줄여 계산 속도를 높일 수 있음
  • 메모이제이션(Memoization) 기법을 사용
• 경우의 수가 많은 경우에도 효율적으로 계산 가능
• 일반적으로 재귀적으로 구현

동적 계획법 사용 조건

1. 최적 부분 구조(Optimal Substructure)
   • 큰 문제의 최적해가 작은 문제의 최적해를 포함하는 성질
2. 중복 부분 문제(Overlapping Subproblems)
   • 동일한 작은 문제를 반복적으로 해결하는 성질

동적 계획법 종류

1. 탑다운(Top-Down)
   • 재귀적으로 호출하여 문제 해결
   • 큰 문제를 작은 문제로 나누어 푸는 분할 정복(Divide and Conquer) 방식과 비슷
     단, 중복되는 작은 문제들을 한번만 풂
   • 장점 : 작은 문제들의 결과값을 저장함으로써 동일한 계산 반복 X -> 시간 복잡도 감소
   • 단점 : 재귀적 호출로 인하여 스택 오버플로(Stack Overflow) 문제 발생 가능
2. 바텀업(Bottom-Up)
   • 작은 문제부터 해결하여 큰 문제까지 해결하는 알고리즘
   • 이전에 계산한 부분 문제의 결과를 저장해 두고 나중에 같은 부분 문제가 나타날 때 다시 계산하지 않고 저장된 값을 사용하여 시간 절약
   • 재귀적 수행X, '반복문'을 통하여 문제를 해결해 나아가는 방식

적용 가능 문제

1. 피보나치 수열
2. 최장 공통 수열(LCS; Longest Common Sequence)
3. 최장 공통 문자열(LCS: Longest Common Substring)
4. 최장 증가 부분 수열(LIS; Longest Increasing Subsequence)
5. 최장 감소 부분 수열(LDS; Longest Decreasing Subsequence)

 

---

String 마침표 기준 분리

• split("\\.")
• split("[.]")

 

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

⏹️ 코딩테스트 문제 풀이
⏹️ TIL 작성