알고리즘 102

[C++] 중복 처리 (1)

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

Language/C++ 2023.09.07

[프로그래머스] 신규 아이디 with C++

문제 설명 제한 사항 및 입출력 예제 개념 주어진 문자열에 대해서, 문제에서 제시한 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..

[C++] sort vs stable_sort with C++

sort vs stable_sort 개요 데이터를 정렬할 때 동일한 값들이 존재하는 경우가 발생할 수 있다. 이때, 우리가 사용하는 일반적인 정렬 알고리즘은 동일한 값들의 순서를 보장하지 않아서, 정렬 후의 순서가 원래의 순서와 다를 수 있다. 예를 들어, 이름으로 사람들을 정렬한 후, 나이로 다시 정렬하면 나이가 같은 사람들의 상대적인 순서가 정렬된 후에 변경될 수 있다. 본문 C++ 표준 라이브러리에는 정렬 함수로서 std::sort()와 std::stable_sort()가 존재한다. 이 두 함수는 기본적으로 배열 또는 벡터의 시작과 끝 위치를 인자로 받으며, 선택적으로 비교 함수를 추가하여 사용할 수 있다. 둘 모두 시간 복잡도는 평균적으로 O(n log n)으로, 대략적으로 n log n 번의 비..

Language/C++ 2023.08.05

[백준] 1015 수열 정렬 with C++

문제설명 입출력 예제 개념 원본 수열에서 정렬을 적용한 후, 각 원소가 원래 있던 위치에서 어떤 위치로 이동하였는지 확인하는 문제다. 즉, 원본 수열의 원소들이 정렬된 후의 위치 값을 찾는 문제다. 유의해야 할 점은, 중복된 원소의 값을 처리하는 것이다. 이는 동일한 원소의 경우 원본 수열에서 사전순으로 앞서는 것을 출력해야 한다는 것을 의미한다. 따라서 각 원소의 값을 그 원소의 원래 위치와 함께 저장하는 pair 자료형을 사용하여 해결할 수 있다. 또한, 오름차순을 정렬할 때 정렬 후에 동일한 값의 원소들 사이의 상대적인 순서를 유지하기 위해 stable_sort를 사용해야 한다. 풀이 #include #include #include using namespace std; bool custom(pair..

Algorithm/백준 2023.08.02

[백준] 1013 Contact With C++

문제설명 입출력 예제 개념 주어진 문자열에서 특정 패턴을 찾는 문제다. C++에서 문자열에서 특정 패턴을 찾는 데 사용할 수 있는 주요 라이브러리로는 정규 표현식(Regex) 라이브러리 regex가 있다. 이는 문자열 검색 알고리즘이 사용할 수 있는 템플릿으로 작동한다. 이를 이용하여 문자열에서 특정 내용을 찾거나 대체하거나, 입력된 문자열이 특정 패턴과 일치하는지 확인하는 등의 작업을 수행할 수 있다. 정규 표현식의 구문 중 문제에서 제시하는 표현들은 다음과 같다. abc: 정확히 abc와 일치하는 문자열을 찾는다 a+: a가 1번 이상 반복되는 문자열을 찾는다 (ab)+: ab가 1번 이상 반복되는 문자열을 찾는다 a|b: a또는 b를 찾는다 이를 이용하여 정규 표현식 패턴을 나타내는 클래스인 reg..

Algorithm/백준 2023.08.01

[백준] 1004 어린 왕자 with C++

문제설명 입출력 예제 개념 이 문제는 어린 왕자가 출발점에서 목표점까지 지나가야 하는 최소 행성계의 수를 찾는 문제다. 각 행성계는 2차원 평면에서 원으로 표현된다. 이 문제를 풀기 위한 핵심 개념은 다음과 같다. 1. 원의 내부에 점이 위치하는지 확인: 이 문제를 해결하기 위해서는 주어진 점이 원 안에 있는지를 확인해야 한다. 이를 위해 거리 계산 공식을 사용하면 된다. 주어진 점 (x, y)와 원의 중심 (x1, x2) 사이의 거리는 sqrt((x-x1)^2 + (y-x2)^2)로 계산하고, 이 값이 원의 반지름 r보다 작거나 같으면 점은 원 내부에 있다. 2. 출발점과 도착점이 동일한 원에 있는 경우: 문제에서는 출발점과 도착점이 동일한 원 안에 있을 경우, 어린 왕자가 그 원을 지나가지 않고 무시..

Algorithm/백준 2023.07.28

[프로그래머스] 개인정보 수집 유효기간 with C++

문제 설명 제한 사항 및 입출력 예제 개념 개인정보의 수집 유효기간을 확인하는 문제다. 이 문제에서는 오늘 날짜와 각 개인정보의 수집일을 바탕으로 개인정보의 수집이 유효한지, 아니면 파기해야 하는지를 판단하게 된다. 이때, 날짜는 YYYY.MM.DD 형태로, 개인정보는 YYYY.MM.DD A 형태로 주어집니다. 각 개인정보에는 수집일과 개인정보 유형(A)이 포함되어 있다. 이 유형은 유효 기간을 결정한다. 예를 들어, A 유형의 개인정보는 수집일로부터 특정 기간 동안만 유효한다. 유효 기간은 'terms'라는 문자열 벡터에 정의되어 있으며, 각 문자열은 유형과 그 유형의 유효 기간을 나타내는 월 단위의 숫자로 구성되어 있다. 따라서 이 문제의 목표는 오늘 날짜를 기준으로 개인정보의 유효 기간이 지났는지를..

[백준] 1002 터렛 with C++

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

Algorithm/백준 2023.07.20

[백준] 1094 막대기 with C++

문제설명 입출력 예제 개념 이 문제는 64cm 막대기를 이용하여 길이가 Xcm인 막대기를 만드는 문제다. 이때, 우리가 사용할 수 있는 도구는 막대기를 정확히 절반으로 자르는 것뿐이다. 따라서, 가능한 막대기의 길이는 64, 32, 16, 8, 4, 2, 1cm 등 2의 거듭제곱 형태다. 이는 우리가 풀려고 하는 문제를 이진수 표현으로 해석하는 키가 된다. 각 이진수의 자리는 2의 거듭제곱을 나타내며, 우리가 필요한 막대의 개수는 이진수 표현에서 1의 개수와 같다. 이는 막대기를 사용하느냐, 사용하지 않느냐를 이진수의 1과 0으로 표현한 것과 같다. 이런 점에서 볼 때, 이 문제는 그리디 알고리즘을 사용하여도 풀 수 있다. 그리디 알고리즘을 사용하는 경우, 가장 큰 막대부터 시작하여 목표 길이를 초과하지..

Algorithm/백준 2023.07.04

[백준] 14725 개미굴 with C++

문제설명 입출력 예제 개념 부모 노드를 기준으로 트리가 어떻게 구성되어 있는지 파악하는 문제다. 문자열을 효율적으로 관리하는 트라이(trie) 자료 구조를 활용하거나, 트리를 구성해 DFS 탐색을 이용해 문제를 풀어도 되지만, 필자는 set의 자동 정렬 특성을 이용해 모든 문자열 경로를 알파벳 순서로 정렬하고, 이에 해당하는 구조를 출력하는 방식으로 문제를 해결하였다. 풀이(1) #include #include #include using namespace std; int main() { int N, n; cin >> N; set s; while (N--) { string tmp, str; cin >> n; while (n--) { cin >> tmp; str += ' ' + tmp; s.insert(st..

Algorithm/백준 2023.06.29