개발일지

문제설명 입출력 예제 개념 각 사람이 돈을 인출하는 데 필요한 시간 합의 최솟값을 출력하는 문제다. 대표적인 그리디 알고리즘으로 효율적으로 해결할 수 있는 문제로서, 실행 시간이 가장 짧은 프로세스부터 우선적으로 처리하는 최단 작업 우선 스케줄링 방식을 이용하면 된다. 여기서 돈을 인출하는데 걸리는 시간을 작업으로 보고, 이 작업들을 가장 짧은 것부터 처리하면 모든 사람이 돈을 인출하는데 필요한 최소 시간을 구할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N; cin >> N; vector v(N); int* sum = new int[N]; for (int i = 0; i > v[i]; s..

문제설명 입출력 예제 개념 이 문제는 회의 시간이 겹치지 않도록 하면서 동시에 가능한 한 많은 수의 회의를 배정하는 문제다. 이를 해결하는 방법 중 하나는 먼저 회의들을 종료 시간 기준으로 오름차순 정렬하는 것이다. 그리고, 가장 먼저 끝나는 회의를 선택한 후, 이전에 선택한 회의와 시간이 겹치지 않는 회의 중 가장 빨리 끝나는 회의를 다음으로 선택하는 것이다. 이러한 방식을 반복함으로써 가능한 많은 수의 회의를 배정할 수 있다. 풀이 #include #include #include using namespace std; int main() { int N, n, k, count = 1; cin >> N; vector v(N); 회의의 수 N, 그리고 회의의 시작과 끝에 대한 입력을 초기화할 변수 n, k,..

문제설명 입출력 예제 개념 K원을 만드는데 필요한 최소한의 동전 개수를 구하는 문제다. 가장 가치가 큰 동전부터 사용하는 것이 최선의 서택이므로, 이러한 선택을 통해 가장 적은 동전을 사용하여 주어진 금액을 만들 수 있는 최적의 해답을 찾을 수 있다. 즉, 그리디 알고리즘을 사용하여 문제를 효율적으로 풀 수 있다. 풀이 #include #include using namespace std; int main() { int N, K, n, answer = 0; cin >> N >> K; vector v(N); for (int i = 0; i > v[i]; for (auto it = v.rbegin(); it != v.rend(); ++it) { if (*it < K) { answer..

문제 설명 제한 사항 및 입출력 예제 개념 이 문제는 최대 2명만 탑승 가능한 구명보트를 최소한으로 사용해 모든 사람을 구조하는 문제다. 이러한 상황에서 구명보트의 수를 최소화하려면, 남은 사람들 중 가장 가벼운 사람과 가장 무거운 사람을 동시에 태울 수 있는지 확인하면 된다. 따라서 투 포인터 알고리즘을 이용하여, 매 순간 보트에 최대한 많은 사람을 태우는 그리디 알고리즘을 구현하면 문제를 해결할 수 있다. 가장 가벼운 사람과 가장 무거운 사람이 보트의 무게 제한 내에 함께 탈 수 있다면, 두 사람을 동시에 태우는 것이 최선의 선택 그렇지 않다면, 가장 무거운 사람만 보트에 태우는 것이 최선의 선택 풀이 #include #include using namespace std; int solution(vec..

문제 설명 제한 사항 및 입출력 예제 개념 이 문제는 끝말잇기 게임의 참가자들 중에서 규칙을 어긴 첫 번째 참가자와 그 참가자의 턴을 식별하고 출력하는 것을 목표로 한다. 여기서 주요 과제는 두 가지다. 각 턴에서 주어진 단어가 이전 단어의 마지막 글자로 시작하는지 판별 각 턴에서 주어진 단어가 이전에 사용된 적 있는 단어인지 확인 첫 번째 규칙은 문자열의 마지막 문자와 첫 문자를 비교하는 방식으로 해결할 수 있고, 두 번째 규칙은 find() 함수를 이용하여 단어의 이력을 관리하는 데이터 구조를 검색함으로써 해결할 수 있다. 이 두 가지 체크를 통과하지 못하는 첫 번째 단어를 발견하면, 해당 단어를 말한 참가자의 번호와 차례를 리턴하게 하면 된다. 풀이 #include #include #include ..

문제 설명 제한 사항 및 입출력 예제 개념 연속된 문자를 제거한다는 측면에서 스택을 활용하면 쉽게 해결할 수 있다. 풀이 #include #include using namespace std; int solution(string s) { stack st; for (int i = 0; i < s.size(); ++i) { if (st.empty()) st.push(s[i]); else if (st.top() == s[i]) st.pop(); else st.push(s[i]); } return st.empty(); }

문제 설명 제한 사항 및 입출력 예제 개념 주어진 정수 벡터에서 모든 숫자의 조합 중 가장 큰 수를 찾는 문제다. 다음과 같은 조건을 고려해 보자. 숫자의 순서: 수를 이루는 각 숫자들의 배치 순서를 문자열로 바꾸어 정렬 숫자의 자릿수: 두 숫자가 주어졌을 때, 자릿수가 다르다면 두 숫자의 문자열로 바꾼 후 이어 붙였을 때 큰 방향을 확인 따라서 정렬 기준을 두 문자열을 더했을 때 큰 쪽을 리턴하게 새롭게 정의하면 된다. 풀이 #include #include using namespace std; string solution(vector numbers) { string answer = ""; vector v; 정답을 저장할 문자열 answer와 벡터 v를 초기화한다. for (const auto& val ..

문제 설명 제한 사항 및 입출력 예제 개념 피보나치 수를 나눈 나머지를 구하는 문제다. 일반적인 재귀 함수 방식으로 피보나치 수열을 구해서 계산하면 같은 값을 여러 번 계산하게 되기 때문에 높은 확률로 시간 초과가 걸린다. 따라서 소수를 구할 때 에라토스테네스의 체 방식으로 미리 값들을 구해놓은 것처럼, 피보나치 수도 미리 구해놓고 계산하는 다이나믹 프로그래밍 방식을 채용하면 문제를 효율적으로 해결할 수 있다. 풀이 #include using namespace std; int solution(int n) { vector dp(n + 1, 0); dp[0] = 0; dp[1] = 1; for (int i = 2; i

문제 설명 제한 사항 및 입출력 예제 개념 주어진 정수 n의 이진 표현에서 1의 개수가 같은 n보다 큰 정수 중 가장 작은 정수를 찾는 문제다. 이진 표현을 하기 위해 bitset 라이브러리를 이용하면 효율적으로 문제를 해결할 수 있다. 풀이 #include #include #include using namespace std; int CountOnesInBinary(int number) { bitset binaryRepresentation(number); string binaryString = binaryRepresentation.to_string(); return count(binaryString.begin(), binaryString.end(), '1'); } int solution(int n) { ..

문제 설명 제한 사항 및 입출력 예제 개념 이 문제는 자연수 n을 연속한 자연수들의 합으로 표현하는 방법의 수를 찾는 문제다. n이 주어지면, 한 개 이상의 연속된 자연수의 합으로 n을 표현하는 방법의 수를 찾아야 한다. 풀이는 다음 두 가지 방법으로 접근하여 보았다. 투 포인터 알고리즘: 두 개의 포인터를 이용하여 연속된 수들의 합을 관리. start와 end 두 포인터를 동시에 이동시키면서 그 사이의 합과 n이 어떻게 비교되는지를 확인. 합이 n보다 작다면 end를 증가시키고, n과 같다면 카운트를 증가시킨 후 start를 증가시키고, n보다 크다면 start를 증가. 브루트 포스 알고리즘: 가능한 모든 연속된 수열을 검사하며 그 합이 n인 경우를 찾음. 두 방법 모두 적절히 활용한다면 문제를 해결할..