개인적으로 알고리즘은 즉각적으로 바로 구현할 수 있도록 몸에 베어야 하되 복습하는 데 너무나 많은 시간을 투자해서는 안 되고, 문제를 풀면서 실전으로 익혀야 한다고 생각한다. 학기가 시작되면서 바빠진 만큼 지난 잊힌 알고리즘 개념들을 핵심과 코드만 짧게 정리하여 평소에도 자주 보면서 익숙해지고자 한다. 기본적으로 코드는 특별한 설명이 없으면 C++를 기반으로 한다. 가장 긴 증가하는 부분 수열 Longest Increasing Subsequence(LIS) 정의 주어진 sequence의 모든 부분 수열(subsequence) 중 오름차순으로 정렬된 가장 긴 수열 문제 길이가 $N$인 임의의 수열 A의 Longest Increasing Subsequence(LIS) 길이를 구해보자. 방법 시간복잡도에 따라..

BOJ 백준 22953 도도의 음식 준비 문제: https://www.acmicpc.net/problem/22953 22953번: 도도의 음식 준비 첫째 줄에 요리사의 수 $N$ ($1 \le N \le 10$), 만들어야 할 음식의 개수 $K$ ($1 \le K \le 1\,000\,000$), 격려해줄 수 있는 횟수 $C$ ($0 \le C \le 5$)가 주어진다. 둘째 줄에 길이가 $N$인 정수 수열 $A$가 주어 www.acmicpc.net K개의 요리를 조리하는 N명의 요리사의 조리시간이 주어진다. 한 요리사에게 격려를 여러 번 할 수 있고, 요리사에게 격려를 한 번 할 때마다 격려를 받은 요리사의 조리 시간은 1초 감소한다. 격려할 수 있는 최대 횟수가 C회일 때, K개의 요리를 조리하는 데..

BOJ 백준 22991 수요응답형 버스 문제: https://www.acmicpc.net/problem/22991 22991번: 수요응답형 버스 현대오토에버는 In-Car와 Out-Car 영역 전반의 소프트웨어와 인프라 관련 업무를 수행하는 회사이다. 현재 현대오토에버에서 수요응답형 버스(MOD)를 개발하고 있다. 수요응답형 버스는 승객이 호 www.acmicpc.net 배차 요청이 N개, 버스가 M개 주어졌을 때, 조건을 만족하면서 배차 요청에 버스를 최대 몇 대 배차 가능한지를 구하는 문제이다. 버스를 요청에 배차 가능한 조건은 다음과 같다. 배차의 탑승 인원 ≤ 버스의 정원 배차의 최대 대기 가능 시간 ≥ 버스의 도착 예정 시간 올해 2021년 SUAPC Summer(https://icpc-sinc..

BOJ 백준 16472 고냥이 문제: https://www.acmicpc.net/problem/16472 16472번: 고냥이 고양이는 너무 귀엽다. 사람들은 고양이를 너무 귀여워했고, 결국 고양이와 더욱 가까워지고 싶어 고양이와의 소통을 위한 고양이 말 번역기를 발명하기로 했다. 이 번역기는 사람의 언어를 고 www.acmicpc.net 문제에서 주어지는 문자열을 S라고 하자. 이 문제는 크게 두 가지 풀이가 있다. 하나는 인식할 수 있는 문자열의 길이를 가지고 이분 탐색(Binary Search)하는 것과 다른 하나는 두 포인터(Two Pointer)를 사용해서 푸는 것이다. 1. 이분 탐색으로 풀기 이분 탐색 대상을 인식할 수 있는 문자열의 길이로 설정한다. 즉, 길이 mid만큼 연속되는 문자열을 ..