개인적으로 알고리즘은 즉각적으로 바로 구현할 수 있도록 몸에 베어야 하되 복습하는 데 너무나 많은 시간을 투자해서는 안 되고, 문제를 풀면서 실전으로 익혀야 한다고 생각한다. 학기가 시작되면서 바빠진 만큼 지난 잊힌 알고리즘 개념들을 핵심과 코드만 짧게 정리하여 평소에도 자주 보면서 익숙해지고자 한다. 기본적으로 코드는 특별한 설명이 없으면 C++를 기반으로 한다. 접미사 배열(Suffix) 정의 문자열 $S$의 모든 접미사들을 사전 순으로 정렬한 배열. 여기서 접미사들은 문자열 $S$에서 시작 위치 번호로 관리한다. 문제 문자열 $S$="abcbca"의 접미사 배열을 구해보자. 접미사: "abcbca", "bcbca", "cbca", "bca", "ca", "a" 사전 순으로 정렬 시 "a", "abc..

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

BOJ 백준 13257 생태학 문제: https://www.acmicpc.net/problem/13257 13257번: 생태학 첫째 줄에 N, C, D, M이 주어진다. (1 ≤ N ≤ 20, 1 ≤ C ≤ 20, 1 ≤ D ≤ 5, 0 ≤ M ≤ N) www.acmicpc.net $D$일 동안 매일마다 $C$ 마리를 포획하여 측정기가 부착이 안 된 새에 모두 측정기를 부착한다고 한다. 새가 총 $N$ 마리일 때, $D$일 후 $M$ 마리가 될 확률을 구하는 것이 문제이다. 처음에 문제를 봤을 때는 $N$, $C$, $D$, $M$의 크기가 작은 편이어서 브루스포스로 구하는 단순 확률 문제인 줄 알았으나, 날마다 C마리의 새를 포획했을 때 몇 마리가 이미 측정기가 부착되었는지를 고려해야 하므로 생각보다 ..

BOJ 백준 23242 Histogram 문제: https://www.acmicpc.net/problem/23242 23242번: Histogram For a range of $[1, n]$, the natural numbers in the interval are called the data values and let $f_i$ be the frequency count of the data value $i$ in the range. The frequency of a data value $i$ is the number of occurrences of the data value $i$ in the lis www.acmicpc.net 길이가 n인 수열을 B개의 bucket으로 나누었을 때, 각 bucket의 ..

BOJ 백준 20047 동전 옮기기 문제: https://www.acmicpc.net/problem/20047 20047번: 동전 옮기기 입력은 표준입력을 사용한다. 첫 번째 줄에 나열된 동전 개수를 나타낸 양의 정수 n (3 ≤ n ≤ 10,000)이 주어진다. 다음 두 줄에 n 개의 동전이 나열된 상태인 S 와 T 가 각각 주어지며, 이 때 S와 T www.acmicpc.net 두 개의 동전을 서로 순서를 바꾸지 않고 자리를 이동하여 문제에서 주어지는 동전 배치를 만들 수 있는지 묻는 문제이다. 학회에서 ACM ICPC 예선을 준비하면서 팀원과 같이 풀었던 문제이다. 처음에는 Queue를 이용하여 푸는 구현 문제인 줄 알고 시도했는데, 계속 채점을 돌려봐도 86퍼센트에서 틀렸다고 떠서 접근 자체가 틀..

BOJ 백준 16467 병아리의 변신은 무죄 문제: https://www.acmicpc.net/problem/16467 16467번: 병아리의 변신은 무죄 학교공부를 끝내고 집을 가던 다진이는 길가에서 병아리를 팔고 있는 아저씨를 발견했다. 병아리를 무척 사고 싶었던 다진이는 병아리의 상태를 확인하지도 않고 한 마리를 사서 집으로 향했다 www.acmicpc.net 병아리가 매일마다 혼자서 알을 한 개씩 낳고 이 알은 K일 후에 부화할 때, N일이 지난 후의 병아리 수를 구하는 것이 문제이다. 개인적으로 이런 유형의 문제는 우선 관찰을 자세히 하는 것이 중요하다고 생각한다. K = 0일 때와 K = 1일 때를 한 번 살펴봤다. K = 0일 때는 i일 후의 병아리의 수를 2의 거듭제곱 꼴로 나타낼 수 있고..

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..