Sort Function을 커스텀해서 정렬 조건을 설정하는 문제이다. 문제에서 제시한 3가지 조건을 comp 비교 함수 내부에 잘 정의하면 쉽게 풀 수 있다. condtion1 : 길이가 더 작은 문자열이 앞으로 온다. condition2 : 모든 수의 합을 비교해 작은 합이 먼저 온다. condition3 : 사전순으로 정렬한다. // a의 합이 b보다 작다 if (a_digit_sum != b_digit_sum) return a_digit_sum tip : 정렬되어야 하는 순서를 비교 연산식으로 리턴하는 것이 실수를 줄일 수 있다. PS2026/12월/1431.cpp at main · novvvv/PS202626년 알고리즘 문제 풀이 레포지토리 . Co..
문제에서 제시하는대로 단순히 배열에 담고 원소를 Reverse 하는 방식은 시간 복잡도가 O(N)만큼 소요된다. 따라서 최악의 경우 100,000(p) * 100,000(n) * 100(t)를 하면 시간초과가 발생하기에 단순 Reverse로는 문제를 풀이할 수 없다. 그렇기에 처음에는 current_deque와 reverse_deque 2개를 두어 R연산이 발생할때마다 swap하는 방식을 채택하였으나 마찬가지로 시간초과가 발생하여 코드를 분석해 보았더니 Java나 Python같은 언어와는 달리 Cpp에서는 아래 코드처럼 덱에 다른 덱을 대입하면 참조에 의한 복사가 아닌 값에 의한 복사가 발생해 단순 주소값을 변경하는것이 아니라 모든 원소를 복사하여 O(N)만큼의 시간 복잡도가 소요된다는 정보를 얻게되었다..
* Cpp STL max_element, min_element의 사용법과distance method를 사용해 벡터 내부의 최대/최소 원소의 인덱스를 구하는 방법에 대해 소개합니다.#max_element / min element usage max_element(vector_name.begin(), vector_name.end())min_element(vector_name.begin(), vector_name.end()) Header에 선언되어 있다. 벡터 내부의 최대/최소 원소의 첫 번째 위치를 "이터레이터" 형태로 반환한다. 반환타입이 "값"이 아닌 "이터레이터" 이기에 * 연산자를 사용해 값에 접근해야 한다. #include #include #include using namespace std;int ..
#1 About Union-Find유니온 파인드는 여러 개의 노드가 주어졌을 때 특정한 노드들이 같은 그룹에 속해있는지 판별하고 여러 개의 그룹 노드를 하나로 합치는 작업을 수행할 때 사용되는 알고리즘이다.이름에서 유추 가능하듯 노드를 한 그룹으로 합치는 "유니온(Union)"연산과 노드가 특정 그룹 내에 존재하는지 판별하는 "파인드(Find)"연산으로 이루어진다. Union-Find 알고리즘을 직접 구현해 보자.우선 크기가 5인 배열을 모두 -1로 초기화해준다. 각 배열의 원소값은 해당 인덱스의 부모 노드를 가리킨다. 배열의 원소가 -1이라면 부모 노드가 자기 자신 즉, 루트노드라는 의미이다. union(1, 5)노드1과 노드5를 유니온 연산을 진행한다. 노드5는 노드1의 자식노드가 되며 배열의 5번째..
본 문서는 이차원 배열에서 누적합 알고리즘을 적용하는 방법에 대해 다루고 있습니다. BOJ 23247 Ten 문항을 기반으로 설명합니다. https://www.acmicpc.net/problem/23247 이차원 배열에서 누적합을 구하는 방법1. 행 방향으로 원소들의 누적합을 계산한다. // 2차원 누적합 계산 로직 // [Logic1] row(행) 방향으로 모든 원소의 합을 구한다. for (int y = 1; y 2. 행 방향으로 누적된 누적합 배열을 기반으로열 방향으로 누적합을 계산한다. 그러면 최종적으로 2차원 배열 누적합이 완성된다.apple_sum 누적합의 1행2열(17)에는기존 apple 배열의 0행0열부터 1행2열까지의 합이 담기게 된다. // [Logic2] C..
