구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. 도입 2. 배열 3. 연결 리스트 4. 예제: 조세푸스 문제 (문제 ID: JOSEPHUS, 난이도: 하) 5. 큐와 스택, 데크 6. 예제: 짝이 맞지 않는 괄호 (문제 ID: BRACKETS2, 난이도: 하) 1. 도입 def. 요소가 일렬로 나열되어 있는 자료 구조 ex. 정적 배열, 동적 배열, 연결 리스트, 스택, 큐, 데크 ✒️ Tip. 자료 구조에서의 시간 복잡도 자료 구조 접근 탐색 삽입 삭제 배열(array) O(1) O(N) O(N) O(N) 스택(stack) O(N) O(N) O(1) O(1) 큐(queue) O(N) O(N) O(1) O(1) 이중 연결 리스트(doubly ..

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. 도입 2. 도시락 데우기 (문제 ID: LUNCHBOX, 난이도: 하) 3. 문자열 합치기 (문제 ID: STRJOIN, 난이도: 중) 4. 미나스 아노르 (문제 ID: MINASTIRITH, 난이도: 상) 1. 도입 • 탐욕적 알고리즘 • 예제: 회의실 예약 • 예제: 출전 순서 정하기 (문제 ID: MATCHORDER, 난이도: 하) • 탐욕적 알고리즘 레시피 📌 탐욕법(Greedy Method) 완전 탐색과 동적 계획법 알고리즘과 동일하게 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어간다. 하지만 결정적 차이는 모든 선택지를 고려하고 가장 좋은 답을 찾는 것이 아니라, 각..

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. 도입 2. 와일드카드 (문제 ID: WILDCARD, 난이도: 중) 3. 전통적인 최적화 문제들 4. 합친 LIS (문제 ID: JLIS, 난이도: 하) 5. 원주율 외우기 (문제 ID: PI, 난이도: 하) 6. Quantization (문제 ID: QUANTIZE, 난이도: 중) 7. 경우의 수와 확률 8. 비대칭 타일링 (문제 ID: ASYMTILING, 난이도: 하) 9. 폴리오미노 (문제 ID: POLY, 난이도: 중) 10. 두니발 박사의 탈옥 (문제 ID: NUMB3RS, 난이도: 중) 1. 도입 • 중복되는 부분 문제 • 메모이제이션을 적용할 수 있는 경우 • 메모이제이션 구현 패..

구종만님의 "프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략"을 기반으로 공부한 내용입니다. 📕 목차 1. 도입 2. 쿼드 트리 뒤집기 (문제 ID: QUADTREE, 난이도: 하) 3. 울타리 잘라내기 (문제 ID: FENCE, 난이도: 중) 4. 팬미팅 (문제 ID: FANMEETING, 난이도: 상) 1. 도입 📌 분할 정복(Devide & Conquer) 쉽게 말해, 각개 격파 전략이다. 주어진 문제를 둘 이상의 부분 문제로 나누고, 각 부분 문제의 답으로 전체 문제의 답을 계산해낸다. 부분 문제를 나눌 때는 거의 같은 크기로 나눈다. 일반적으로 3가지 과정으로 구성된다. 문제를 더 작은 문제로 분할하는 과정(devide) 각 문제에 대해 구한 답을 원래 문제의 답으로 병합하는 과정(merge..