[99클럽 5기] Day13 TIL - Deque, Brute Force, Greedy

99클럽 5기 | Java | Middler

 

🗝️ 오늘의 학습 키워드 : Queue Deque LinkedList Brute Force Greedy Back-Tracking

⌛ 회고

오늘은 생각보다 문제가 빨리 풀려서 자료구조 공부를 하였습니다.
Java Collection Frame Work에 대한 블로그 글을 읽어보고
다시 한번 정리해 볼 수 있어서 좋았습니다.
비기너 문제를 2가지 방법으로 풀어보았는데 완전 탐색과 그리디로 해결해 보고
그리디에 대해 조금 더 찾아보았습니다.
Solved.ac 마라톤을 달리려고 했는데 팩토리얼3문제에서 시간초과 및 메모리 초과가 나서 결국 해결하지 못하였습니다.
n!을 계산해야하는데 n의 범위가 0 ~ 100,000이라서 
long 범위도 초과하는 경우가 발생하기 때문에 BigInteger를 사용해 보기도 하였지만
시간 초과가 발생하였습니다.
그래서 long 범위 안에서 계산할 수 있는 만큼 반복문으로 곱하여 계산하고 해당 값을 초과하는 경우,
BigInteger에 값을 곱해주는 식으로도 문제를 해결해 보려 하였지만 시간 초과!
그래서 반복문으로 곱할 때, long을 초과하는 값의 경계를 미리 구해놓고 
Map에 값을 저장한 상태에서 문제를 해결하려고 하였는데 첫번째 시도는 실패...
두번째 방법은 숫자를 몇개 곱하면 long을 초과하는 지 개수를 비교해 보니 일정 범위마다 개수가 비슷한 구간이 많아서
해당 구간과 개수를 Map에 저장해 놓고 풀려고 했는데 어제 저녁 시간이 늦어 결국 해결하지 못하였습니다.
내일은 그 문제를 해결할 수 있었으면 좋겠습니다.

❓ 오늘 만난 문제

• 🥉 비기너 : 큐
• 🥈 미들러 : 부등호
• 🥇 챌린저 : 스타 수열

💦 나의 시도 & 해결 방법👍

• 🥉 비기너 : [백준 | Java] 10845번 큐
• 🥈 미들러 : [백준 | Java] 2529번 부등호
• 🥇 챌린저 :

❗ 무엇을 새롭게 알았는지

Java Collection Framework

- Linear Data Structure
    - List
    - Queue
    - Deque

- Nonlinear Data Structure
    - Graph
    - Tree
- Set Data Structure
    - Set

Greedy Algorithm

부분 최적해를 통해 전체 최적값을 도출하는 알고리즘

적용 조건

• 탐욕 선택 속성 : 이전 선택이 이후에 영향을 주지 않음.
• 최적 부분 구조 : 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야 함.

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

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