개발일지

이진 탐색 개요 예전 이진 탐색에 대한 개념적인 부분을 해당 글에서 다룬 적이 있었다. 다시 상기하자면, 정렬된 배열을 반으로 나눠가며 원하는 값을 찾는 알고리즘이 이진 탐색이다. 이번 시간에는 해당 알고리즘을 구현한 std::binary_search 함수에 대한 사용법을 알아보도록 하자. 본문 사용법 이진 탐색 또한 탐색의 일종이므로, 배열 내에서 특정 요소가 존재하는지 확인할 때 사용된다. 이때 대상 범위가 이미 정렬되어 있어야 하며, 중복 요소가 있는 경우 어느 요소인지 알 수 없다. 이는 함수가 단순히 주어진 값이 배열 내에 존재하는지 여부만을 체크하기 때문이다. #include #include #include int main() { std::vector v = { 1, 2, 4, 5, 9, 10..

본문 중복 인덱스 처리 #include #include #include #include int main() { unsigned seed = std::chrono::system_clock::now().time_since_epoch().count(); std::mt19937 generator(seed); std::vector word_pairs = { {"game", "게임"}, {"start", "시작하다"}, {"smart", "똑똑한"}, {"string", "문자열"}, {"combination", "조합"}, {"pair", "쌍"} }; 다음과 같이 벡터에 단어와 그 정의가 저장되어 있고, 여기서 무작위로 5개의 문제를 낸다고 해보자. 이때 중복된 문제가 없으려면 어떻게 해야 할까? std::sh..

중복 처리 개요 지난번에 업로드된 게시글에서는 다양한 난수 생성 방법들을 알아보았다. 이러한 난수를 활용하여 시스템을 설계하게 되면, 중복 문제가 불가피하게 발생할 수 있다. 특히 무작위로 고유한 값을 생성하거나 선택하는 과정에서 중복은 예기치 않은 오류를 발생시킬 수 있다. 따라서 중복 처리는 이러한 시스템에서 필수적인 단계가 되어야 한다. 이번에는 난수 생성 시 발생하는 중복 문제와 그를 효과적으로 해결하는 방안들에 대해 살펴볼 예정이다. 특히, 중복된 값 자체의 처리와 중복 인덱스 처리, 이 두 가지 주제에 초점을 맞추어 알아보도록 하겠다. 본문 중복 제거 std::vector v = { 7, 7, 1, 2, 3, 5, 5, 2, 8 }; 다음과 같이 vector 배열에 중복된 값이 있다고 가정해 ..

문제 설명 제한 사항 및 입출력 예제 개념 주어진 문자열에 대해서, 문제에서 제시한 7단계의 규칙을 순차적으로 적용하여 새로운 문자열을 생성하는 문제다. 각 단게는 특정 문자열 패턴의 변환 및 제거를 포함하며, 모든 단계를 차례대로 완료하면 최종적으로 원하는 문자열 형태를 얻을 수 있다. 풀이 #include #include #include using namespace std; string solution(string new_id) { string answer = ""; // 1단계 transform(new_id.begin(), new_id.end(), new_id.begin(), static_cast(std::tolower)); // 2단계 new_id.erase(remove_if(new_id.begi..

문제설명 입출력 예제 개념 이 문제는 원의 방정식을 이용하여 해결할 수 있다 된다. 즉, 조규현의 좌표에서 목표인 류재명까지의 거리를 반지름으로 하는 원과, 백승환의 좌표에서 목표까지의 거리를 반지름으로 하는 원을 그린 후, 두 원의 교점의 개수를 구하면 문제를 해결할 수 있다. 따라서 두 원의 교점의 개수를 구하는 관계를 파악하기 위해, 두 원 사이의 거리를 이용할 수 있다. 이는 교점이 2개, 1개, 0개, 무한개일 때로 나눌 수 있다. 이때 두 원의 반지름을 각각 r1, r2라고 하고, 두 원의 중점 사이의 거리를 d라고 할 때 다음이 성립한다. 교점이 무한 개: d = 0 교점이 0개: r1- r2 < d < r1 + r2 교점이 1개: d = r1 ± r2 교점이 2개: d < r1 + r2 이..

문제설명 입출력 예제 개념 올림픽에서 메달 획득 별 등수를 출력하는 문제다. 올림픽 메달 순위에서는 동점의 경우 같은 등수를 가지며, 그다음 등수는 동점인 나라의 수를 고려하여 건너뛰게 된다. 예를 들어, 금메달 수가 1개인 나라가 1등에 2개가 있다면, 그다음 나라는 3등이 된다. 이러한 동점 상황을 고려하여 문제를 풀면 해결할 수 있다. 풀이 #include #include #include using namespace std; struct medal { int _id, _gold, _silver, _bronze; bool operator > (const medal& m) const { if (_gold != m._gold) return _gold > m._gold; else if (_silver !=..

벨만-포드 알고리즘개요　이전 게시물들에서는 그래프 내의 두 정점 사이의 최단 경로를 찾는 방법들에 대해 다루었다. 특히 가중치가 부여된 그래프에서 최단 경로를 찾는 대표적인 방법인 다익스트라 알고리즘은 그리디 알고리즘의 원리를 활용해 각 단계에서 최단 경로를 계산한다. 이 방법은 효율성 면에서 뛰어나지만, 한 가지 큰 제약 사항이 존재하는데, 바로 음의 가중치를 가진 에지를 처리할 수 없다는 점이다. 다익스트라 알고리즘이 음의 가중치를 처리하지 못하는 이유는 그 알고리즘의 핵심 원리에 있다. 이 알고리즘은 '현재까지 발견된 최단 경로'를 기반으로 작동한다. 그리고 이 경로는 더 이상 개선될 수 없다고 가정한다. 즉, 한 번 '최단'으로 판단된 경로는 그 이후에 변경되지 않는다. 　하지만 음의 가중치가 그..

문제 설명 제한 사항 및 입출력 예제 개념 연속된 문자를 제거한다는 측면에서 스택을 활용하면 쉽게 해결할 수 있다. 풀이 #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