divide2 [백준 16438번] 원숭이 스포츠 난이도: 골드 III 문제 링크: https://www.acmicpc.net/problem/16438 16438번: 원숭이 스포츠 승민이는 동물원의 원숭이들을 관리하는 사육사입니다. 이 동물원에는 N마리의 원숭이들이 있고 원숭이들에게 1번부터 N번까지 번호를 붙였습니다. 7일간 동물원에서 원숭이들끼리 스포츠 경기 www.acmicpc.net 문제의 설명이 조금 어려운데, 요약하면 다음과 같습니다. N개의 원소에 대해, 총 7번의 기회 이내에 배열 내의 원소 i가 원소 j (i != j)와 다른 경우가 적어도 한 번 이상 존재해야 합니다. 문제의 조건을 유심히 살펴보고 분석해 보면 다음과 같은 사실을 알 수 있습니다. N은 최대 99인데, 주어진 주는 7주입니다. 전체 원숭이를 재귀적으로 반씩 나누어 팀을.. 2021. 9. 18. [백준 1517번] 버블 소트 난이도: 플래티넘 V 문제 링크: https://www.acmicpc.net/problem/1517 1517번: 버블 소트 첫째 줄에 N(1 ≤ N ≤ 500,000)이 주어진다. 다음 줄에는 N개의 정수로 A[1], A[2], …, A[N]이 주어진다. 각각의 A[i]는 0 ≤ |A[i]| ≤ 1,000,000,000의 범위에 들어있다. www.acmicpc.net 분할-정복 (divide & conquer) 문제입니다. n은 최대 50만이므로, 모든 원소에 대해 모든 다른 원소와 비교해 보는 식으로 하면 시간 초과가 납니다 (O(N^2)). 재귀 방식으로 배열을 구간별로 나누어 접근하도록 합니다. 나눈 구간에 대해 정렬하기 전 swap 횟수를 세고, 정렬되는 값을 별도의 배열에 기록한 후 (arr2).. 2021. 9. 17. 이전 1 다음
