알고리즘
[BOJ] 1519 부분 문자열 뽑기 게임
문제 링크 www.acmicpc.net/problem/1519 모든 알고리즘 문제는 C++로 구현되어 있습니다. 다이나믹 프로그래밍 사용해 풀 수 있는 문제이다. 이 문제의 핵심은 크게 두 가지로, 첫 번째는 어떤 수의 진 부분 문자열을 구하는 것이고, 두 번째는 승패를 판정하는 것이다. 부분 문자열을 뽑아내기 위해 나는 입력값을 string으로 받아 substr() 함수로 부분 문자열을 뽑아내고, stoi() 함수를 이용해 int형으로 바꿔서 뺄셈했다. for (i = 1; i < len; i++) { // i : 부분 문자열의 길이 for (j = 0; j + i
2021 KAKAO BLIND RECRUITMENT - 광고 삽입
이 문제는 주어진 시간 단위를 초 단위로 바꿔서 푸는 것이 핵심이다. 시간이 최대 99:59:59까지 주어지는데, 이를 초단위로 바꾸면 359,999초이다. 이는 배열로 충분히 표현할 수 있는 크기이므로, 배열 logs에 주어진 각 구간들의 시작 시간과 끝 시간을 이용해 배열을 채워준 뒤, adv_time 크기의 구간합 중 최대값을 구해주면 된다. 문제를 풀기 위해 먼저 string 형으로 주어진 시간을 int 형 초로 바꾸는 함수와, 반대로 다시 문제에 주어진 포맷으로 바꾸는 함수를 만들었다. int toInt(string time) { // string형 시간 -> int형 초 int hour = stoi(time.substr(0, 2)) * 3600; int minute = stoi(time.sub..
2021 KAKAO BLIND RECRUITMENT - 합승 택시 요금
이 문제는 택시비를 간선 간의 거리로 보면 그래프 상에서 최단거리를 구하는 문제로 생각해 볼 수 있다. 주요 포인트는 두 사람 A와 B가 합승을 통해 전체 비용을 단축시킬 수 있다는 것이다. 최소비용으로 A와 B 각자의 목적지에 갈 수 있는 경우는 두 가지 경우로 나눠볼 수 있다. 합승해서 같이 임의 지점까지 최단 비용으로 이동한 후, 여기서 각자의 목적지를 향해 최단 비용으로 가기 합승을 하지 않고 시작점 s에서 각자의 목적지를 향해 최단 비용으로 가기 두 가지 경우의 비용을 비교해서 더 작은 비용이 답이 될 것이다. 1번 방법의 최소 비용을 구하기 위해서는 시작점 s에서 임의의 지점까지 가는 최소 비용과 함께, 이 지점에서 각자의 목적지까지 가는 최소비용이 필요하다. 마침 지점의 갯수 n의 최대값도 ..