세종대왕은 현수에게 현수가 다스릴 수 있는 영지를 하사하기로 했다. 전체 땅은 사각형으로 표시된다. 그 사각형의 땅 중에서 세종대왕이 현수가 다스릴 수 있는 땅의 크기(세로의 길이와 가 로의 길이)를 정해주면 전체 땅 중에서 그 크기의 땅의 위치를 현수가 정하면 되는 것이다. 전체 땅은 사각형의 모양의 격자로 되어 있으며, 그 사각형 땅 안에는 많은 오렌지 나무가 심겨져 있다. 현수는 오렌지를 무척 좋아하여 오렌지 나무가 가장 많이 포함되는 지역을 선택하고 싶어 한다. 현수가 얻을 수 있는 영지의 오렌지 나무 최대 개수를 출력하는 프로그램을 작성하세요. 다음과 같은 땅의 정보가 주어지고, 현수가 하사받을 크기가, 가로 2, 세로 3의 크기이면 가장 많은 오렌지 나무가 있는 영지는 총 오렌지 나무의 개수가 16인 3행 4열부터 시작하는 구역이다.
입력설명
첫 줄에 H(세로길이)와 W(가로길이)가 입력된다. (5<=H, W<=50) 그 다음 H줄에 걸쳐 각 사각형 지역에 오렌지의 나무 개수(1~9개) 정보가 주어진다.
그 다음 영지의 크기인 세로길이(1H)와 가로길이(1W)가 차례로 입력된다.
2) 출력 설명
첫 줄에 현수가 얻을 수 있는 오렌지 나무의 최대 개수를 출력한다.
3) 입력 예제1
6 7
3 5 1 3 1 3 2
1 2 1 3 1 1 2
1 3 1 5 1 3 4
5 1 1 3 1 3 2
3 1 1 3 1 1 2
1 3 1 3 1 2 2
2 3
출력 예제1
16
문제 풀이 핵심
DP 테이블을 구한다.
DP 테이블을 이용해 면적을 계산한다.
1. 풀이1 : DP 테이블을 구한다.
DP 테이블을 구함
i,j 번째 DP 테이블은 아래와 같이 구할 수 있다.
DP 테이블을 이용하여 영지크기를 계산한다.
i,j 번째 영지 크기는 아래와 같이 구할 수 있다.
#include<vector>
#include<algorithm>
using namespace std;
int a[701][701], dy[701][701];
int main() {
int h, w, n, m, i, j, tmp, max = -2147000000;
scanf_s("%d %d", &h, &w);
for (i = 1; i <= h; i++) {
for (j = 1; j <= w; j++) {
scanf_s("%d", &a[i][j]);
dy[i][j] = dy[i - 1][j] + dy[i][j - 1] - dy[i - 1][j - 1] + a[i][j];
}
}
scanf_s("%d %d", &n, &m);
for (i = n; i <= h; i++) {
for (j = m; j <= w; j++) {
tmp = dy[i][j] - dy[i - n][j] - dy[i][j - m] + dy[i - n][j - m];
if (tmp > max) max = tmp;
}
}
printf("%d\n", max);
return 0;
}
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다. DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다. 즉, 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다. 고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다. 이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.
입력설명
첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서 부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을 넘지 않는다고 가정하자.
출력 설명
첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.
입력 예제1
9 3
1 2 3 4 5 6 7 8 9
출력 예제1
17
문제 풀이 핵심
입력값을 모두 더한 값을 sum, DVD 개수를 m이라고 했을 때 정답은 sum / m ~ sum 안에 존재한다고 가정한다.
시작값 : sum / m, 끝값 : sum 으로 잡고 이분 검색 방법으로 정답을 찾는다.
1. 풀이1 : 정답의 범위를 정해놓고, 정답을 이분 검색으로 찾아 나가자!
입력
데이터 개수 저장 : n
DVD 개수 저장 : m
데이터 저장 : data
입력 받을 때 합계 sum 저장
정답 가능한 시작값 설정
lt = sum / m;
정답 가능한 끝값 설정
rt = sum;
mid값이 정답 가능한지 확인
mid = (lt + rt) / 2
가능하다면, mid보다 큰값은 무조건 가능하므로, rt = mid -1 하면서 solution 변수에 mid값을 저장
안된다면, mid보다는 커야 하므로, lt = mid + 1
4를 반복하다가 lt와 rt가 엇갈리면 중단하고 solution 을 출력
주의 할점
가능 여부 판단 시에 mid는 반드시 값의 max값 보다 커야함
DVD 용량이 음악 1곡의 크기보다 커야만 저장이 가능하기 때문
#include<iostream>
#include<vector>
int main() {
#include<iostream>
#include<vector>
bool isAvailable(std::vector<int> data, int mid, int num, int max) {
int cnt = 1;
int sum = 0;
for (int i = 0; i < data.size(); i++) {
sum += data[i];
if (mid < sum) {
cnt++;
sum = data[i];
}
}
if (mid >= max && cnt <= num) {
return true;
}
return false;
}
int main() {
int n, m, sum = 0, max = 0;;
scanf_s("%d %d", &n, &m);
std::vector<int> data(n);
for (auto& dd : data) {
scanf_s("%d", &dd);
sum += dd;
if (max < dd) {
max = dd;
}
}
int lt = sum / m, rt = sum, mid, solution = sum;
while (lt <= rt) {
mid = (lt + rt) / 2;
if (isAvailable(data, mid, m, max)) {
solution = mid;
rt = mid - 1;
}
else {
lt = mid + 1;
}
}
std::cout << solution;
return 0;
}
입력으로 양의 정수 N이 입력되면 2개 이상의 연속된 자연수의 합으로 정수 N을 표현하는 방법의 가짓수를 출력하는 프로그램을 작성하세요. 만약 N=15이면 7+8=15 4+5+6=15 1+2+3+4+5=15 와 같이 총 3가지의 경우가 존재한다.
입력설명
첫 번째 줄에 양의 정수 N(7<=N<1000)이 주어진다.
출력 설명
첫줄부터 각각의 경우의 수를 출력한다. 맨 마지막 줄에 총 개수를 출력한다
입력 예제1
15
출력 예제1
7 + 8 = 15
4 + 5 + 6 = 15
1 + 2 + 3 + 4 + 5 = 15
3
문제 풀이 핵심
2개 연속된 수의 경우 숫자에서 1,2를 뺀 값이 2로 나누어지는지 확인한다.
3개 연속된 수의 경우 숫자에서 1,2,3을 뺀 값이 3으로 나누어지는지를 확인한다.
반복한다.
1. 풀이1 : 오른쪽으로 +1 왼쪽으로 -1을 반복하자.
방법 요약
입력 변수(num)를 n(2~num)으로 나누고, 좌/우로 값을 번갈아 하나씩 연결시키며 더한다.(n 개수 만큼 연결)
더한 값이 num과 같으면 기록하고, 커지면 break한다.
반복하다가 왼쪽 값이 1이거나 오른쪽값이 num과 같아지면 그만한다.
#include<iostream>
#include<vector>
int main() {
#include<iostream>
#include<deque>
int main() {
int num;
scanf_s("%d", &num);
int cnt = 0;
int lIdx = 0, rIdx = 0;
int n = 2;
for (n = 2; n < num; n++) {
int sum = 0;
int mok = num / n;
std::deque<int> result;
bool flag = true;
lIdx = mok; rIdx = mok;
int kk = 1;
sum += mok;
result.push_back(mok);
while (kk < n) {
if(flag){
rIdx++;
sum += rIdx;
flag = false;
result.push_back(rIdx);
}
else {
lIdx--;
sum += lIdx;
flag = true;
result.push_front(lIdx);
}
kk++;
if (sum > num) break;
else if (sum == num) {
std::cout << result[0];
for (int ii = 1; ii < result.size(); ii++) {
std::cout << " + " << result[ii];
}
std::cout << " = " << sum << std::endl;
cnt++;
}
if (lIdx == 1 || rIdx == num) break;
}
}
std::cout << cnt;
return 0;
}
예시
입력 : 15
2로 나누어질 경우
15 / 2 = 7 => 오른쪽하나 증가하여 8 , ==> {7,8}
15 / 3 = 5 => 오른쪽하나 증가 6, 왼쪽하나 증가 4, ==> {4,5,6}
15 / 4 = 3 => 오른쪽 하나 증가 4, 왼쪽하나 증가 2, 오른쪽하나 증가 5 ==> 2+3+4+5 != 15 이므로 (x)
15 / 5 = 3 => 오른쪽 하나 증가 4, 왼쪽하나 증가 2, 오른쪽하나 증가 5, 왼쪽 하나 증가 1 ==> {1,2,3,4,5}
lIdx가 1이므로 멈춤
2. 풀이2 : n이 연속된 2개로 분리된다면, n에서 1,2 를 뺀값을 2로 나누어 떨어진다.
방법 요약
n = 2일 경우, 15 에서 1,2를 뺀 12를 2로 나누어 떨어진다.
1,2에 12/2의 몫 6을 각각 더해주면 된다. ( 7,8 )
n = 3일 경우, 15에서 1,2,3을 뺀 9를 3으로 나누어 떨어진다.
1,2,3에 9/3의 몫 3를 각각 더한다. (4,5,6)
반복한다.
int main() {
#include<iostream>
using namespace std;
int main() {
int a, b = 1, cnt = 0, tmp, i;
scanf_s("%d", &a);
tmp = a;
a--;
while (a > 0) {
b++;
a = a - b;
if (a%b == 0) {
for (i = 1; i < b; i++) {
printf("%d + ", (a / b) + i);
}
printf("%d = %d\n", (a / b) + i, tmp);
cnt++;
}
}
printf("%d\n", cnt);
return 0;
}
예시
입력 : 15
n : 2일 경우
15 에서 1,2를 뺀 12 / 2 는 나머지가 0이므로 1,2에 6을 더한 값이 정답 => {7,8}
n : 3일 경우
15 에서 1,2,3를 뺀 9 / 3 은 나머지가 0이므로 1,2,3에 3을 더한 값이 정답 => {4,5,6}
15 에서 1,2,3,4를 뺀 5 / 4 은 나머지가 1이므로 pass
15에서 1,2,3,4,5를 뺀 0 / 5 는 나머지가 0이므로 1,2,3,4,5에 0을 더한 값이 정답 => {1,2,3,4,5}
1부터 n까지의 수를 한 번씩만 사용하여 이루어진 수열이 있을 때, 1부터 n까지 각각의 수 앞에 놓여 있는 자신보다 큰 수들의 개수를 수열로 표현한 것을 Inversion Sequence라 한다. 예를 들어 다음과 같은 수열의 경우 4 8 6 2 5 1 3 7 1앞에 놓인 1보다 큰 수는 4, 8, 6, 2, 5. 이렇게 5개이고, 2앞에 놓인 2보다 큰 수는 4, 8, 6. 이렇게 3개, 3앞에 놓인 3보다 큰 수는 4, 8, 6, 5 이렇게 4개...... 따라서 4 8 6 2 5 1 3 7의 inversion sequence는 5 3 4 0 2 1 1 0 이 된다. n과 1부터 n까지의 수를 사용하여 이루어진 수열의 inversion sequence가 주어졌을 때, 원래 의 수열을 출력하는 프로그램을 작성하세요.
입력설명
첫 번째 줄에 자연수 N(3<=N<100)이 주어지고, 두 번째 줄에는 inversion sequence가 숫자 사이에 한 칸의 공백을 두고 주어진다.
출력 설명
오름차순으로 정렬된 수열을 출력합니다.
입력 예제1
8
5 3 4 0 2 1 1 0
출력 예제1
4 8 6 2 5 1 3 7
문제 풀이 핵심
입력 데이터 끝에서 부터 시작!
입력 데이터의 값 만큼 앞으로 땡기고, 그 자리에 해당 숫자를 입력
삽입 정렬!!
1. 풀이1 : 1부터 자기 위치에 저장하자!
입력
사용자에게 num을 입력 받음
data vector를 num 개수 만큼 초기화
reuslt vector를 num 개수 만큼 101로 초기화(최대값이 100이므로)
i = 0 ~ n-1 까지 반복
숫자는 1부터 시작하므로 idx = i+1로 저장
j = 0 ~ n-1 까지 반복
result[j] 가 idx보다 크면 개수를 +1
개수가 data[i] + 1 과 같으면 break
result[j] 에는 idx를 저장
반복이 끝나면 값 출력
#include<iostream>
#include<vector>
int main() {
// 데이터 입력
int num;
scanf_s("%d", &num);
std::vector<int> data(num);
for (auto & dd : data) {
scanf_s("%d", &dd);
}
std::vector<int> result(num,101);
int j = 0;
for (int i = 0; i < data.size(); i++) {
int idx = i + 1; // 해당 번호 저장(1~n)
int cnt = 0;
for (j = 0; j < result.size(); j++) {
if (result[j] > idx) {
cnt++;
}
if (cnt == data[i]+1) {
break;
}
}
result[j] = idx;
}
for (auto dd : result) {
std::cout << dd << " ";
}
return 0;
}
예시
입력 : 8
data : 5,3,4,0,2,1,1,0
result : 101,101,101,101,101,1,101,101
result : 101,101,101,2,101,1,101,101
result : 101,101,101,2,101,1,3,101
result : 4,101,101,2,101,1,3,101
result : 4,101,101,2,5,1,3,101
result : 4,101,6,2,5,1,3,101
result : 4,101,6,2,5,1,3,7
result : 4,8,6,2,5,1,3,7
2. 풀이2 : 뒤에서 부터 저장하자!
입력
사용자에게 num을 입력 받음
data vector를 num 개수 만큼 초기화
reuslt vector를 num 개수 만큼 101로 초기화(최대값이 100이므로)
i는 끝에서부터 시작까지 반복
j는 i에서 시작하여 data[i]의 개수만큼 데이터를 앞으로 땡김
result[j] 에 idx를 저장
int main() {
int num;
scanf_s("%d", &num);
std::vector<int> data(num);
std::vector<int> result(num);
for (auto & dd : data) {
scanf_s("%d", &dd);
}
int i = 0, j = 0, idx;
for (i = data.size() - 1; i >= 0; i--) {
idx = i + 1;
for (j = i; j < i + data[i]; j++) {
result[j] = result[j + 1];
}
result[j] = idx;
}
for (auto dd : result) {
std::cout << dd << " ";
}
return 0;
}
자연수 N이 입력되면 1부터 N까지의 자연수를 종이에 적을 때 각 숫자 중 3의 개수가 몇 개 있는지 구하려고 합니다. 예를 들어 1부터 15까지는 1, 2, 3, 4, 5, 6, 7, 8, 9, 1, 0, 1, 1, 1, 2, 1, 3, 1, 4, 1, 5으로 3의 개수는 2개입니다. 자연수 N이 입력되면 1부터 N까지 숫자를 적을 때, 3의 개수가 몇 개인지 구하여 출력하는 프로그램을 작성하세요.
입력설명
첫 줄에 자연수의 개수 N(3<=N<=1,000,000,000)이 주어집니다.
출력 설명
3의 개수를 출력하세요.
입력 예제1
15
출력 예제1
2
문제 풀이 핵심
1의 자리~ n의 자리 숫자까지 순회 한며, 각 자리에서 3이 나오는 횟수를 계산한다.
i 번째 자리 수를 기준으로 왼쪽과 오른쪽의 숫자로 분리한다.
i 번째 자리 수가 3일 경우는 왼쪽의 수와 오른쪽 수의 조합으로 계산 가능하다.
1. 풀이1
사용자에게 num을 입력 받음
vector에 각 자리수를 저장
1의 자리 부터 n의 자리까지 순회 아래 반복
i 번째 기준 왼쪽 숫자와 오른쪽 숫자로 분리
i번째 숫자가 3보다 작으면, 왼쪽 숫자 * 10^i 만큼 3이 발생
i번째 숫자가 3이면 왼쪽 숫자*10^i + 오른쪽 숫자 + 1 만큼 발생
i번째 숫자가 3보다 크면, 왼쪽 숫자*10^i + 10^i만큼 발생
모든 자리에서 3이 나오는 횟수를 합함
#include<iostream>
#include<vector>
#include<deque>
int main() {
int num, cnt = 0;;
scanf_s("%d", &num);
std::vector<int> a;
int sum = 0;
int kk = 1;
//벡터에 각 자리수 삽입
while (num > 0) {
a.push_back(num % 10);
num = num / 10;
}
for (int i = 0; i < a.size(); i++) {
// 앞의 숫자
int numFront = 0, n10 = 1;
for (int j = i + 1; j < a.size(); j++) {
numFront += a[j] * n10;
n10 *= 10;
}
// 뒤의 숫자
int numBack = 0;
for (int j = i - 1; j >= 0; j--) {
numBack = numBack * 10;
numBack += a[j];
}
//3의 개수 구하기
sum += numFront * kk;
if (a[i] == 3) {
sum += numBack + 1;
}
else if (a[i] > 3 ){
sum += kk;
}
kk *= 10;
}
std::cout << sum;
return 0;
}
}
자연수 N이 입력되면 1부터 N까지의 각 숫자들의 약수의 개수를 출력하는 프로그램을 작성하세요. 만약 N이 8이 입력된다면 1(1개), 2(2개), 3(2개), 4(3개), 5(2개), 6(4개), 7(2개), 8(4개) 와 같이 각 숫자의 약수의 개수가 구해집니다. 출력은 다음과 같이 1부터 차례대로 약수의 개수만 출력하면 됩니다. 1 2 2 3 2 4 2 4 와 같이 출력한다.
입력설명
첫 번째 줄에 자연수 N(5<=N<=50,000)가 주어진다.
출력 설명
첫 번째 줄에 1부터 N까지 약수의 개수를 순서대로 출력한다.
입력 예제1
8
출력 예제1
1 2 2 3 2 4 2 4
문제 풀이 핵심
순서 대로 약수를 구하면 속도가 너무 느리다.
i는 1~num 을 순회하며, i의 배수의 자리 개수를 더해주자.!
1. 풀이1 : 순서대로 약수 구하는 방법
두 개의 for문을 돌며, 순서대로 약수를 구하는 방법
이해가 쉽고, 동작되나 속도가 매우 느림(O(N제곱))
int getCount(int num){
int cnt = 2;
for ( int i = 2; <= num / 2; i++ ){
if (num % i == 0){
cnt++;
}
}
return cnt;
}
int main(){
int num;
std::cin >> num;
cout << "1 2 2 3"; // 4까지는 그냥 출력
for ( int i = 5 ; i<= num; i++){
cout<< " " << getCount(i);
}
}
2. 풀이2 : 배수를 이용하는 방법
사용자에게 num을 입력 받음
num개의 숫자에 대한 약수 개수를 가지고 있는 공간 할당
num 개수 만큼 공간 확보 및 1로 초기화
i는 2 에서 num 까지 순회
j는 i 에서 num 까지 i의 배수로 순회
j의 위치 공간에 count를 +1함
최종 출력
#include<iostream>
#include<vector>
int main() {
int num;
// 1. 사용자에게 num을 입력 받음
std::cin >> num;
// 2. num 개수 만큼 공간 확보 및 1로 초기화
std::vector<int> cnt(num, 1);
// 3. i 는 2부터 num까지 순회
for (int i = 2; i <= num; i++) {
// 4. j는 i부터 num까지 순회하며, i의 배수 위치 공간에 count + 1
for (int j = i; j <= num; j = j + i) {
cnt[j - 1] = cnt[j - 1]++;
}
}
// 5. 결과를 출력
std::cout << cnt[0];
for (int i = 1; i < num; i++) {
std::cout << " " << cnt[i];
}
return 0;
}
예시(8 입력 시)
{1,1,1,1,1,1,1,1} : 1은 모두의 약수이므로 제외하고, 개수 공간을 1로 초기화
{1,2,1,2,1,2,1,2} : 2의 배수 위치 개수 증가(4번 순회->2,4,6,8)
std::vector<int> data = { 13,5,11,7,23,15 };
for (int i = 0; i < data.size(); i++) {
int minIdx = i;
for (int j = i + 1; j < data.size(); j++) {
if (data[minIdx] > data[j]) {
minIdx = j;
}
}
int temp;
temp = data[i];
data[i] = data[minIdx];
data[minIdx] = temp;
}
사용 예시
N명의 수학 성적 중 3등의 점수를 구하라
입력 : 80 96 75 82 96 92 100
출력 : 92
1등부터 3등까지만 정렬하면 되므로 선택정렬이 효율적임.
2. 버블 정렬
핵심
이웃값과 비교해서 더 큰 값을 뒤로 보내길 반복하자
제일 큰 값이 오른쪽으로 이동하여 오른쪽부터 정렬된다.
예제(파란색 : 정렬 완료, 빨간색 : 교환)
13, 5, 11, 7, 23, 15
5, 13, 11, 7, 23, 15
5, 11, 13, 7, 23, 15
5, 11, 7, 13, 23, 15
5, 11, 7, 13, 15, 23
5, 7, 11, 13, 15, 23
복잡도 : O(N^2)
소스
std::vector<int> data = { 13,5,11,7,23,15 };
for (size_t i = 0; i < data.size(); i++) {
for (size_t j = 0; j < data.size() -1 - i; j++) {
if (data[j] > data[j + 1]) {
int temp;
temp = data[j + 1];
data[j + 1] = data[j];
data[j] = temp;
}
}
}
사용 예시
음의 정수를 양의 정수 앞으로 오도록 하되 음의 정수, 양의 정수 순서에는 변함이 없게 하라
입력 : 1,2,3,-3,-2,5,6,-6
출력 : -3,-2,-6,1,2,3,5,6
3. 삽입 정렬
핵심
두 번째 위치 부터 끝까지 돌면서 나보다 왼쪽의 위치 중 알맞은 위치로 삽입하자.
데이터가 이미 정렬된(또는 거의 정렬된) 상태에서는 굉장히 빠르다.
예제(파란색 : 정렬 완료, 빨간색 : 삽입 원소, □ : 삽입 위치)
□, 13, 5, 11, 7, 23, 15
5, □, 13, 11, 7, 23, 15
5, □, 11, 13, 7, 23, 15
5, 7, 11, 13, 23, 15
5, 7, 11, 13, □, 23, 15
5, 7, 11, 13, 15, 23
복잡도 : O(N^2)
소스
std::vector<int> data = { 13,5,11,7,23,15 };
int j = 0;
for (size_t i = 1; i < data.size(); i++) {
int temp = data[i];
for (j = i - 1; j >= 0; j--) {
if (data[j] > temp) {
data[j + 1] = data[j];
}
else {
break;
}
}
data[j + 1] = temp;
}
4. 병합 정렬
핵심
제일 작은 2개의 단위로 분리하여 정렬하고 합치자
예제(빨간색 : 비교 대상)
13, 5, 11, 7, 23, 15
5, 13, 11, 7 ,23 ,15
5, 11, 13, 7, 23, 15
5, 11, 13, 7, 23, 15
5, 11, 13, 7, 15, 23
5, 7, 11, 13, 15, 23
복잡도 : O(N*logN)
소스
int number = 6;
int size;
int count = 0;
std::vector<int> sorted(number);
void merge(std::vector<int>& a, int startIdx, int middle, int endIdx) {
int i = startIdx;
int j = middle + 1;
int k = startIdx;
// 두개의 영역을 각각 비교하여 작은 수선대로 sorted에 삽입
while (i <= middle && j <= endIdx) {
if (a[i] <= a[j]) {
sorted[k] = a[i];
i++;
}
else {
sorted[k] = a[j];
j++;
}
k++;
}
// 남은 데이터 삽입(i나 j가 먼저 도달했을 경우을 대비)
if (i > middle) {
// i가 먼저 끝났다면 남은 j값을 넣어주자
for (int t = j; t <= endIdx; t++) {
sorted[k] = a[t];
k++;
}
}
else {
// j가 먼저 끝났다면 남은 i값을 넣어주자
for (int t = i; t <= middle; t++) {
sorted[k] = a[t];
k++;
}
}
// 실제 배열에 복사
for (int t = startIdx; t <= endIdx; t++) {
a[t] = sorted[t];
}
}
void mergeSort(std::vector<int>& a, int startIdx, int endIdx) {
if (startIdx < endIdx) {
int middle = (startIdx + endIdx) / 2;
mergeSort(a, startIdx, middle);
mergeSort(a, middle + 1, endIdx);
merge(a, startIdx, middle, endIdx);
}
}
int main() {
std::vector<int> array = { 13, 5, 11, 7, 23, 15 };
mergeSort(array, 0, array.size() - 1);
for (auto dd : array) {
std::cout << dd << " ";
}
return 0;
}
5. 퀵 정렬
핵심
피벗(특정 값)을 기준으로 두고 왼쪽부터 시작해 오른쪽으로 피벗보다 큰 숫자를 찾고, 동시에 오른쪽부터 시작해 왼쪽으로 피벗보다 작은 숫자를 찾아 두 숫자를 교환한다.
위의 과정을 반복하다가 왼쪽과 오른쪽이 엇갈릴 때 작은 원소와 피벗을 교환한다.
피벗을 기준으로 왼쪽 집단과 오른쪽 집단에 대해 위의 과정을 반복 수행한다.
일반적으로 집단의 가장 앞 원소를 초기 피벗값으로 설정한다.
예제(빨간색 : 피벗, 파란색 : 왼쪽부터 가서 큰 원소, 초록색 : 오른쪽부터 가서 작은 원소)
13, 5, 11, 7, 23, 15
엇갈렸으므로 작은 원소(7)과 피벗(13)을 교환
7, 5, 11, 13, 23, 15
7, 5, 11, 13, 23, 15
엇갈렸으므로 작은 원소(5)와 피벗(7)을 교환
5, 7, 11, 13, 23, 15
엇갈렸으므로 작은 원소(15)와 피벗(23)을 교환
5, 7, 11, 13, 15, 23
복잡도 : O(N*logN)
소스
#include<iostream>
#include<vector>
void quick(std::vector<int>& data, int startIdx, int endIdx) {
if (startIdx >= endIdx) return;
int pivot = data[startIdx];
int i = startIdx, j = endIdx;
for (i = startIdx + 1; i <= endIdx; i++) {
if (data[i] > pivot) {
break;
}
}
for (j = endIdx; j >= startIdx + 1; j--) {
if (data[j] < pivot) {
break;
}
}
if (i >= j) {
data[startIdx] = data[j];
data[j] = pivot;
}
else {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
quick(data, startIdx, j - 1);
quick(data, j + 1, endIdx);
}
int main() {
std::vector<int> data = { 13,5,11,7,23,15 };
quick(data, 0, 5);
return 0;
}
import React from "react"
import Loading from "./Loading"
export default function App() {
return <Loading />
}
결과
3.Getting the location
만약 App에 위치 정보를 사용하고 싶을 때 react native와 expo에서 제공하는 API를 사용 할 수 있다. 링크된 페이지를 참고하면 expo의 location이 더 많고 유용한 라이브러리를 제공하는 것을 알 수 있다(ex.Geofencing : 사용자가 특정 지역에 들어올 때 특정 함수를 호출하는 기능). 따라서 본 포스팅에서는 expo의 location을 이용하며, 사용하기 위해서는 라이브러리 설치가 필요하다.
3.1 Expo의 location library 설치
터미널에서 expo install expo-location 입력
expo install expo-location
결과
3.2 location library import
location을 사용할 파일에서 import
App.js에 아래와 같이 입력
import * as Location from "expo-location"
3.3 location library 사용
권한정보가져오기
비동기식(async await) 방법 사용
requestPermissionsAsync() 함수 사용
try ~ catch 구문을 이용해 에러 발생시 alert 발생
위치 정보 가져 오기
비동기식(async await) 방법 사용
componentDidMount()를 이용해 컴포넌트 생성이 완료되었을 때 getLocation을 실행
