문제 제한 사항을 보고 target의 범위와 개수가 많다는 것을 보고 완전 탐색은 불가능하다고 생각했다. 모든 target을 처리해야 하기 때문에 정렬한 후 그리디로 처리해도 될 것이라 판단했다. 문제 설명 A 나라가 B 나라를 침공하였습니다. B 나라의 대부분의 전략 자원은 아이기스 군사 기지에 집중되어 있기 때문에 A 나라는 B 나라의 아이기스 군사 기지에 융단폭격을 가했습니다. A 나라의 공격에 대항하여 아이기스 군사 기지에서는 무수히 쏟아지는 폭격 미사일들을 요격하려고 합니다. 이곳에는 백발백중을 자랑하는 요격 시스템이 있지만 운용 비용이 상당하기 때문에 미사일을 최소로 사용해서 모든 폭격 미사일을 요격하려 합니다. A 나라와 B 나라가 싸우고 있는 이 세계는 2차원 공간으로 이루어져 있습니다. ..
알고리즘/기타
연속된 부분 수열의 합 오름 차순으로 정렬된 수열에서 부분 수열의 합이 k인 가장 짧고 왼쪽에 있는 부분 수열을 찾는 문제이다. 이미 정렬되어 있기 때문에 투 푸인터를 이용하면 쉽게 풀 수 있다. 문제 설명 비내림차순으로 정렬된 수열이 주어질 때, 다음 조건을 만족하는 부분 수열을 찾으려고 합니다. 기존 수열에서 임의의 두 인덱스의 원소와 그 사이의 원소를 모두 포함하는 부분 수열이어야 합니다. 부분 수열의 합은 k입니다. 합이 k인 부분 수열이 여러 개인 경우 길이가 짧은 수열을 찾습니다. 길이가 짧은 수열이 여러 개인 경우 앞쪽(시작 인덱스가 작은)에 나오는 수열을 찾습니다. 수열을 나타내는 정수 배열 sequence와 부분 수열의 합을 나타내는 정수 k가 매개변수로 주어질 때, 위 조건을 만족하는 ..
과제 진행하기 시간을 시간, 분으로 관리하면 헷갈릴 것 같아 분으로 환산한 뒤 계산했다. 그리고 모든 데이터가 string으로 들어온다. 이를 원하는 타입으로 변환하여 계산하는 부분이 번거로웠는데 여러 문제에서 이런 부분이 있다. 항상 생각했지만 regex를 공부해서 쉽게 처리하면 좋을 것 같다. (성능 문제) 현재 문제에서는 char의 ASCII값을 기준값('0'의 ASCII)을 빼는 식으로 계산했고 소요 시간의 자릿수가 고정된 것이 아니라 stoi를 사용하여 변환했다. find, substr을 사용하는 것을 추천 int det = 문자열.find('찾을 문자'); string pre = 문자열.substr(0, det); string suf = 문자열.substr(det + 1); 성능은 ASCII를..
