개발일지

맵리듀스개요　지금까지 우리가 다룬 분할 정복은 주로 알고리즘 설계 패러다임으로 간주했다. 이번엔 이 방식을 일반 컴퓨팅 환경을 초월한 고성능 컴퓨터에 적용하는 방법에 대해 논의하려고 한다. 이러한 확장의 핵심에는 컴퓨터 클러스터(Cluster)라는 개념이 있다. 컴퓨팅 클러스터, 즉 복수의 컴퓨터를 네트워크로 연결하여 단일 시스템처럼 작동하게 하는 방식으로, 이를 통해 더 복잡하고 규모가 큰 문제를 효과적으로 해결할 수 있다. 　하지만, 단순히 컴퓨팅 리소스를 확장하는 것만으로 대규모 데이터 처리에 필요한 세밀함과 효율성을 보장하긴 어렵다. 이러한 관점에서 맵리듀스(MapReduce)는 대용량 데이터를 효과적으로 처리할 수 있는 프로그래밍 모델이다. 맵리듀스는 컴퓨팅 클러스터를 활용해 거대한 양의 데이터..

문제설명 입출력 예제 개념 이 문제는 주어진 문자열 내에서 특정 문자가 등장하는 빈도를 특정 구간에서 확인하는 것을 요구한다. 일반적으로, 구간 l에서 r까지 특정 문자 비교를 직접 수행하는 경우, 문자열의 길이가 매우 긴 경우엔 계산 시간이 지나치게 오래 걸릴 수 있으므로 시간 초과 문제에 직면하게 된다. 이러한 문제를 극복하기 위해 '특정 구간'이라는 핵심 키워드에 주목하고, 누적합의 개념을 적용하면 이 문제를 보다 효율적으로 해결할 수 있다. 또한 문자의 등장 횟수를 벡터에 초기화하여 이진 탐색을 통해 구현할 수도 있다. 풀이 (1) 이진 탐색 #include #include #include using namespace std; vector v[26]; string str; int T, l, r; ..

선형 시간 선택개요　선형 시간 선택(Linear time selection)은 데이터 관리의 효율성을 극대화하기 위해 컴퓨터 과학에서 도입된 알고리즘이다. 이 알고리즘은 평균적으로 선형 시간 복잡도 O(n)을 통해, 정렬되지 않은 데이터 집합에서 k번 째로 작거나 큰 요소를 신속하게 식별할 수 있다.대규모 데이터 셋에서 중요한 순위를 차지하는 값을 파악해야 하는 경우, 예를 들어 데이터의 중앙값을 추출하는 등의 상황에서, 선형 시간 선택 알고리즘이 매우 효율적이라 할 수 있다.특징　선형 시간 선택의 두드러진 특징 중 하나는 그 성능이다. 평균적인 시간 복잡도가 O(n)인 선형 시간 선택은 대량의 데이터를 처리하는 데 있어 매우 효율적이다. 또한, 이 알고리즘은 전체 데이터 집합을 미리 정렬할 필요가 없이..

문제설명 입출력 예제 개념 정수 배열을 AC 언어를 이용해 연산하는 문제다. 이때 입력이 대괄호와 쉼표가 포함되는 것에 유의해야 한다. 그 후 정수들을 뒤집거나 지우는 과정이 필요한데, 전체 배열을 뒤집는 연산을 효율적으로 처리하기 위해 deque 자료구조를 이용하면 된다. 풀이 #include #include #include #include #include using namespace std; int main() { int T, n; string p, str; cin >> T; 테스트 케이스의 개수 T, 배열에 들어있는 수의 개수 n, 명령을 수행할 함수 문자열 p, 배열을 저장할 문자열 str를 초기화한다. while (T--) { cin >> p >> n >> str; deque dq; string..

문제설명 입출력 예제 개념 1부터 N까지의 수열 중에서 특정 위치의 수를 최소한으로 회전하며 뽑아내는 문제다. 따라서 왼쪽으로 갈지 오른쪽으로 갈지 판단한 후, 값을 뽑아내면 된다. 이때 양방향으로 선입선출하는 구조이므로 dequeue를 사용하면 편하다. 풀이 #include #include #include using namespace std; int main() { int N, M, n, cnt = 0; cin >> N >> M; deque dq; for (int i = 1; i > n; auto it = find(dq.begin(), dq.end(), n); int distance = it - dq.begin(); bool isLeft = distance N >> M; deque dq; for (in..

문제설명 입출력 예제 개념 문자열을 입력받아 덱의 기본 동작을 확인하는 간단한 문제다. dequeue의 기본적인 원리를 이해하고 있다면 쉽게 해결할 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; cin >> N; deque dq; string str; while (N--) { cin >> str; if (str == "push_back") { cin >> n; dq.push_back(n); } if (str == "push_front") { cin >> n; dq.push_front(n); } if (str == "front") { if (d..

퀵 정렬개요　퀵(quick) 정렬은 주요한 연산의 평균 실행 시간을 최적화하는 것을 목표로 삼는 정렬 방법이다. 병렬 정합이 큰 규모의 데이터 세트에 대한 정렬에 초점을 맞춘 것과는 대조적으로, 퀵 정렬은 분할 정복 전략을 통해 입력 배열을 작은 서브 배열로 분해하고, 각각의 서브 배열을 독립적으로 정렬한 다음, 이들을 다시 결합하여 전체적으로 정렬된 배열을 생성하는 방식을 사용한다. 이러한 접근법에서 퀵 정렬의 핵심 연산은 바로 분할이다.본문　퀵 정렬은 다음과 같은 단계로 수행된다.분할(Divide): 배열에서 특정 원소를 피벗으로 선택하고, 이를 기준으로 입력 배열을 두 개의 부분 배열로 나눈다.정복(Conquer): 피벗을 제외한 두 부분을 재귀적으로 퀵 정렬한다.결합(Combine): 재귀적으로 ..

문제설명 입출력 예제 개념 문서의 개수와 중요도가 주어졌을 때, 큐에서 M번째에 해당하는 문서가 몇 번째로 출력되는지 묻는 문제다. 프린터 대기열은 큐 자료 구조를 사용한다는 점과, 문서의 중요도가 필요하다는 점에서 문서의 이름과 중요도를 자료형 pair로 받아 처리해야 한다는 점을 유의하자. 풀이 #include #include #include using namespace std; int main() { int T, N, M, n; cin >> T; 테스트 케이스의 수 T, 문서의 개수 N, 출력 순서가 궁금한 정수 M, 중요도 n을 초기화한다. while (T--) { int index = 0; cin >> N >> M; queue q; pair ans; for (int i = 0; i < N; ++..

문제설명 입출력 예제 개념 예제 (7,3) 요세푸스 순열이 생성되는 과정은 다음과 같다. 따라서 K번 만큼 수를 뒤로 보낸 후 수를 뽑으면 요세푸스 순열이 생성된다. 즉, 선입선출의 구조를 갖고 있으므로 큐 자료구조를 활용하면 쉽게 풀 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, K; cin >> N >> K; queue q; for (int i = 1; i

문제설명 입출력 예제 개념 큐의 기본적인 구조를 잘 이해하고 있는지 묻는 문제다. 기존의 스택(10828) 문제처럼 입력받은 문자열에 맞게 큐의 동작을 수행하게끔 작성하면 해결할 수 있다. 풀이 #include #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N, n; cin >> N; queue q; while (N--) { string str; cin >> str; if (str == "push") { cin >> n; q.push(n); } else if (str == "front") { if (q.empty()) cout