-
Notifications
You must be signed in to change notification settings - Fork 0
SW Academy
jjin-choi edited this page Jun 30, 2020
·
9 revisions
- main.cpp 와 user.cpp 로 구성
- 강의 코딩 스타일 : IDE : VS2019 (보조 codeblocks(
- #define LM 1000 보다는 const int LM = 1000
- 식별자 : ClassName 은 대문자로 시작
-
O(N * log(N)) : 각 level 마다 N 번씩 연산이 이루어 지며 총 log(N) 만큼의 층으로 구성
-
크기가 N인 배열을 절반씩 쪼개어 크기가 1이 되면 바로 전 배열의 원소간 비교를 수행하며 merge
-
merge 과정
- 앞쪽 절반과 뒤쪽 절반이 각각 정렬된 상태이다.
- 앞쪽 배열의 index i 와 뒤쪽 배열 index j 를 비교하여 작은 값을 새로운 배열에 대입한다.
- 한쪽 배열의 index가 범위를 초과하면, 새로운 배열의 나머지 부분은 다른 한쪽의 배열로 채운다.
- 이 때, 이 배열은 이미 정렬된 상태이므로 그대로 채워주면 된다.
/*
:: Merge Sort ::
divide → conquer → merge
*/
#include <stdio.h>
const int SIZE = (1000 + 5);
int N, in[SIZE], trr[SIZE];
void inputData()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", in + i); // &in[i]
}
void printData(int *arr)
{
for (int i = 0; i < N; i++)
printf("%d ", arr[i]);
puts(""); // printf("\n");
}
void mergeSort(int *arr, int s, int e)
{
if (s >= e) return; // 0. base condition
int m = (s + e) / 2; // 1. divide
mergeSort(arr, s, m); // 2. conquer
mergeSort(arr, m + 1, e);
int i = s, j = m + 1, k = s; // 3. merge
for (k = s; k <= e; k++)
{
if (j > e) trr[k] = arr[i++];
else if (i > m) trr[k] = arr[j++];
else if (arr[i] <= arr[j]) trr[k] = arr[i++];
else trr[k] = arr[j++];
}
for (i = s; i <= e; i++) // 4. copy
arr[i] = trr[i];
printData(arr);
}
int main()
{
// freopen("input.txt", "r", stdin);
inputData();
mergeSort(in, 0, N - 1);
return 0;
}-
문제 개요 필수 문제
- N 명의 학생들이 일렬로 늘어서 있으며 각 학생들은 1 ~ N 까지의 번호가 적인 카드를 한 장씩 들고 있다.
- 같은 번호가 적힌 카드는 없다.
- orderCheck(int left, int right) 함수는 left 번째 학생이 right 번째 학생보다 작다면 1, 아니면 0 을 반환한다.
- 최소의 질의 (함수 호출)로 학생들이 서 있는 순서대로 카드 번호를 알아내는 프로그램을 작성하시오.
-
해결 방안 1
- 학생 번호를 배열의 인덱스로, 수를 배열의 값으로 생각할 수 있다.
- 배열에 담긴 수들은 1 ~ N 까지의 수로 이루어진 순열 중 하나.
- orderCheck(int left, int right) 함수 호출은 비교 횟수와 정비례
-
비교 횟수에 제한이 없다면 ?
- 모든 원소를 1이라고 가정하고 다른 모든 수와 비교하여 자신보다 작은 수가 나올 때마다 1씩 증가한다.
- O(N^2)
-
해결 방안 2
- 학생이 갖고 있는 수에 따라 index가 정렬되어 있다면 ?
- 학생 번호는 모르지만 첫 번째 학생은 1 을 N 번째 학생은 N 을 가지고 있을 것이다.
- 학생이 가지고 있는 수에 따라서 오름 차순 정렬할 수 있을까? → **학생 번호는 배열의 index 다 ! **
- 학생 번호를 차례로 담은 배열을 만들고, 학생 번호를 합병 정렬한다.
- N 번 순회하며 학생이 가진 번호를 기록한다.
- 예시 - 학생(카드) : 1(5) 2(3) 3(4) 4(2) 5(1)
- 학생의 index를 갖는 index[] 를 만든다. index(context) : 1(1) 2(2) 3(3) 4(4) 5(5)
-
정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘
-
리스트 중간 값을 선택하여 찾고자 하는 값과 비교하는 방식
-
찾는 값이 아니면 탐색 범위를 절반으로 줄일 수 있음
-
문제 유형
- 최적화 문제 (최소값, 최대값) 를 결정 문제로 바꿔서 생각하는 경우
- 이분 검색으로 가장 최적의 해를 탐색하는 방법으로 해를 구한다.
- 답의 후보들이 정렬되어 있는 경우 유용하게 사용 가능
-
이진 검색 과정
- 현재 탐색 구간의 가운데 배열 번호 mid를 구한다.
- 만약 A[mid] == target 이면 이 값/ 값의 위치를 return
- A[mid] < target 이라면 low = mid + 1 로 (그 아래로는 볼 필요가 없음) 검색 범위 조정한다.
- low > high 가 되는 경우는 목표 값이 배열이 없는 경우
/*
:: Binary Search ::
*/
#include <stdio.h>
const int SIZE = (int) 5e5 + 5; // (e : exponent) 5 * 10 ^ 5
int N, Q, in[SIZE], trr[SIZE];
void inputData()
{
scanf ("%d", &N);
for (int i = 0; i < N; i++)
scanf ("%d", in + i);
}
void mergeSort(int *arr, int s, int e)
{
// 0. Base condition
if (s > e) return;
// 1. divide
int mid = (s + e) / 2;
// 2. conqure
mergeSort(arr, s, mid);
mergeSort(arr, mid + 1, e);
// 3. merge
int i = s, j = mid + 1, k = s;
for (k = s; k < e; k++)
{
if (e < j) trr[k] = arr[i++];
else if (mid < i) trr[k] = arr[j++];
else if (arr[i] <= arr[j]) trr[k] = arr[i++];
else if (arr[j] < arr[i]) trr[k] = arr[j++];
}
// 4. copy
for (int i = s; i < e; i++)
arr[i] = trr[i];
}
int bsearch_DFS(int *arr, int s, int e, int target)
{
// 1. not found
if (s > e) return -1;
// 2. mid
int mid = (s+ e) / 2;
// 3. find target
if (arr[mid] == target) return mid;
// 4. arr[mid] < target
else if (arr[mid] < target)
return bsearch_DFS(arr, mid + 1, e, target);
// 5. arr[mid] > target
else
return bsearch_DFS(arr, s, mid, target);
}
int bsearch_loop(int *arr, int s, int e, int target)
{
while (s <= e)
{
int mid = (s + e) / 2;
if (arr[mid] == target) return mid;
else if (arr[mid] < target) s = mid + 1;
else e = mid - 1;
}
return -1;
}
void process()
{
scanf ("%d", &Q);
int i, tg;
for (i = 0; i < Q; i++)
{
scanf ("%d", &tg);
printf("%d\n", bsearch_loop(in, 0, N - 1, tg));
}
}
int main()
{
freopen("input.txt", "r", stdin);
inputData();
process();
return 0;
}-
문제 개요
- 임의의 정수 N 이 주어졌을 때 양의 제곱근의 정수 부분 출력하기
- 단 sqrt 함수 사용 하지 말아야 함
- 2^63 - 1 : long long
-
2^63 -1 범위가 너무 크기 때문에 기존 bsearch 를 하게 되면 오버플로우 발생
- 미리 범위를 살짝 찾아두는 꼼수..
- mid ^ 2 < target 으로 하지 말고 mid < target / mid 로 값을 비교하자
-
(참고) 바빌로니아 법을 이용할 수 있다.
- x_(n+1) = (x_n + a / x_n ) / 2
/*
:: Root Square
*/
#include <stdio.h>
typedef unsigned long long LL;
LL bsearch(LL s, LL e, LL target)
{
LL ans = target, mid;
while (s <= e)
{
mid = (s + e) / 2;
if (mid < target / mid) ans = mid, s = mid + 1;
else e = mid - 1;
}
return ans;
}
int main()
{
freopen("input.txt", "r", stdin);
LL N;
scanf("%llu", &N);
printf ("%llu", bsearch(1, N, N));
return 0;
}-
N 일의 온도가 정수 수열로 주어질 때, 연속된 K일의 온도의 합이 가장 큰 값 알아보기
- 1 <= K <= 100,000
- -100 <= 온도 <= 100
-
해결 방안
- prefix sum 을 psum (누적합) 에 저장
- 첫 K일의 합을 ans 로 가정하거나 매우 작은 값으로 설정해두고
- ans = max (ans, psum[i] - psum[i-K])
- 이와 같은 방법을 sliding window 라고 한다.
/*
:: Temperature ::
*/
#include <stdio.h>
const int MAX = (100000 + 5);
int N, K, in[MAX], psum[MAX];
int ans = -(int)1e9;
// debuging point
// - syntax error(문법적 에러)
// - runtime error (실행 중 에러)
// - logic (논리적 에러) : 부분 점수만 받는 경우
void inputData()
{
scanf("%d %d", &N, &K);
for (int i = 1; i <= N; i++)
{
scanf("%d", in + i);
psum[i] = psum[i - 1] + in[i];
}
}
void process()
{
for (int i = K; i <= N; i++)
{
int sum = psum[i] - psum[i - K];
if (ans < sum) ans = sum;
}
}
int main()
{
freopen("input.txt", "r", stdin);
inputData();
process();
printf("%d\n", ans);
return 0;
}- Maximum subarray problem
- 위 문제와 다른 점은 K 가 정해져 있지 않다는 것이다.
- D[i]를 i번째 수를 마지막으로 하는 연속 부분합의 최대값으로 정의해보자.
- 즉 in[i]를 optimal solution에 포함했을 때, D[i-1]을 이용할 것인지 그렇지 않을 것인지
- D[i-1] > 0 이면 이용하지만, D[i-1] <= 0 이면 이용할 필요가 없다.
- D[i] = max (in[i], D[i-1] + in[i])
- 동적 알고리즘 없이, D[i] 를 sum 으로 바꿔 생각하면, i번째 sum은 i번째 sum은 i번째 수를 마지막으로 하는 연속 부분합의 최대값
/*
:: Max Sub Array ::
*/
#include <stdio.h>
const int SIZE = (100000 + 5);
int N, in[SIZE], sum, ans;
void inputData()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", in + i);
}
void maxSubArray()
{
sum = in[0];
for (int i = 1; i < N; i++)
{
int cur = in[i];
if (sum > 0) sum += cur;
else sum = cur;
if (ans < sum) ans = sum;
}
}
int main()
{
freopen("input.txt", "r", stdin);
inputData();
maxSubArray();
printf("%d ", ans);
return 0;
}
- Two pointer 필수문제
- 정렬 후 A 배열의 양쪽 끝 index 를 low = 0, high = N-1
- sum = A[low] + A[high]
- if (sum == 0) 인 경우 가장 좋은 값이므로 출력하고 종료
- if (sum > 0) 혹은 if (sum < 0)
/*
:: Two Solution ::
*/
#include <stdio.h>
const int SIZE = (100000 + 5);
int N, count, sum, ans[2];
typedef struct sol
{
int data;
int sign = 1;
} SOL;
SOL in[SIZE], trr[SIZE];
int abs(int data)
{
if (data < 0) return data * (-1);
else return data;
}
void inputData()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
{
scanf("%d", &in[i].data);
if (in[i].data < 0)
{
in[i].data *= -1;
in[i].sign = -1;
count++;
}
}
}
void displayData(SOL *arr)
{
printf("\n");
for (int i = 0; i < N; i++)
{
if (arr[i].sign < 0)
printf("-%d ", arr[i].data);
else
printf(" %d ", arr[i].data);
}
printf("\n");
}
void mergeSort(SOL *arr, int s, int e)
{
// 0. base condition
if (s >= e) return;
// 1. divide
int mid = (s + e) / 2;
// 2. conquer
mergeSort(arr, s, mid);
mergeSort(arr, mid + 1, e);
// 3. merge
int i = s, j = mid + 1, k = s;
for (k = s; k <= e; k++)
{
if (mid < i) {
trr[k].sign = arr[j].sign;
trr[k].data = arr[j++].data;
}
else if (e < j) {
trr[k].sign = arr[i].sign;
trr[k].data = arr[i++].data;
}
else if (arr[i].data <= arr[j].data) {
trr[k].sign = arr[i].sign;
trr[k].data = arr[i++].data;
}
else if (arr[i].data > arr[j].data) {
trr[k].sign = arr[j].sign;
trr[k].data = arr[j++].data;
}
}
// 4. copy
for (int i = s; i <= e; i++)
{
arr[i].sign = trr[i].sign;
arr[i].data = trr[i].data;
}
}
void process()
{
ans[0] = in[0].data * in[0].sign;
ans[1] = in[1].data * in[1].sign;
sum = ans[0] + ans[1];
int sign = in[1].sign;
for (int i = 2; i < N; i++)
{
if (sign != in[i].sign)
{
sign = in[i].sign;
int sol = in[i - 1].data * in[i - 1].sign + in[i].data * in[i].sign;
if (abs(sol) < abs(sum))
{
sum = sol;
ans[0] = in[i - 1].data * in[i - 1].sign;
ans[1] = in[i].data * in[i].sign;
}
}
}
}
int main()
{
freopen("input.txt", "r", stdin);
inputData();
displayData(in);
mergeSort(in, 0, N-1);
displayData(in);
process();
if (ans[0] < ans[1])
printf("\n Answer : %d + %d = %d ", ans[0], ans[1], sum);
else
printf("\n Answer : %d + %d = %d ", ans[1], ans[0], sum);
return 0;
}-
prefix sum 을 이용하여 동일한 수가 다시 나오면 그 사이의 sub sum 이 0 이다.
-
동일한 숫자가 나오는 개수를 cnt[] 에 저장하면 될까 ?
-
하지만 1<= N <= 100000 이고 -100 <= A[] <= 100 이므로 부분합의 범위가 -1천만 ~ 1천만 사이다
-
음수 구간 shift 하여 0 ~ 2천만으로 처리하면 해결될 수 있다.
-
하지만 메모리가 64 M 이다.
-
생각해보면 앞의 5만개가 모두 -100 이면 뒤의 5만개가 모두 100 이어야 0 이 되기 때문에
-
subsum 합이 -5백만 혹은 5백만 사이 범위를 벗어나는 것은 만들 수 없다.
-
int 형 배열 크기가 1천만인 cnt[] 를 만들어 문제를 해결하기 !
- 1천만 * 4 (int) / 1048576 (1M) = 약 38 MB
-
cnt를 왜 그냥 더하지 ,, ? combination 해야 하지 않나 ? 1일땐 빼야하지 않나.. !
/*
:: Sub Array Sum Zero
*/
#include <stdio.h>
const int SIZE = (100000 + 5);
const int MAX = SIZE * 100 / 2;
int in[SIZE], psum[SIZE], cnt[SIZE * 100];
int N;
long long sol; // 10만개 이상일 수 있으므로
void inputData()
{
scanf("%d", &N);
for (int i = 0; i < N; i++)
scanf("%d", in + i);
}
void prefixSum(int *arr)
{
psum[0] = arr[0];
for (int i = 1; i < N; i++)
psum[i] = psum[i - 1] + arr[i];
}
int combi(int x)
{
if (x > 1)
return x * (x - 1) / 2;
else
return 0;
}
void countSum(int *arr)
{
int max = 0;
cnt[0 + MAX] = 1;
for (int i = 0; i < N; i++)
{
if (psum[i] > MAX || psum[i] < -MAX)
continue;
cnt[psum[i] + MAX]++;
if (max < psum[i] + MAX)
max = psum[i] + MAX;
}
for (int i = 0; i <= max; i++)
sol += combi(cnt[i]);
}
int main()
{
freopen("input.txt", "r", stdin);
inputData();
prefixSum(in);
countSum(in);
printf("%lld\n", sol);
return 0;
}- 복호화 키 (26개의 소문자로 구성됨) 와 암호 문자를 입력 받아 원문을 구하는 문제
- fgets(문자열 이름, 문자열 길이, 입력 스트림) 을 사용할 수 있다.
- char* fgets(char* buf, int buf_size, FILE*stream);
- char *buf[100];
- fgets(buf, 100, stdin);
- // 최대 99개 문자까지 입력 받고 마지막 널 문자 ('\0' 아스키코드 0) 을 넣는다.
- fgets() 개행문자 ('\r', '\n') 도 입력한다는 점에 주의 .. !
/*
:: Encryption ::
'A' : 65
'a' : 97
*/
#include <stdio.h>
const int SIZE = (100000 + 5);
char in[SIZE], out[SIZE], code[30];
void inputString()
{
// for (int i = 0; i<10; i++)
// scanf("%c", enc + i);
}
int strlen(char *str)
{
int len = 0;
while (*str && *str != '\r' && *str != '\n')
{
str++;
len++;
}
*str = '\0';
return len;
}
void printString(char *str)
{
for (int i = 0; i<10; i++)
printf("%c", str + i);
printf("\n");
}
int isUpper(char c)
{
return (c >= 'A' && c <= 'Z');
}
int isLower(char c)
{
return (c >= 'a' && c <= 'z');
}
int main()
{
freopen("input.txt", "r", stdin);
fgets(code, 30, stdin);
fgets(in, 100, stdin);
//inputString();
printf("code length : %d\n", strlen(code));
printf("string length : %d\n", strlen(in));
int len = strlen(in);
for (int i = 0; i < len; i++)
{
char c = in[i];
if (isUpper(c)) in[i] = code[c - 'A'] - 32;
else if (isLower(c)) in[i] = code[c - 'a'];
}
puts(in); // printf("%s\n", buf);
return 0;
}#else
// cin, getline
#include <iostream>
using namespace std;
char code[30], in[100];
int isUpper(char c)
{
return (c >= 'A' && c <= 'Z');
}
int isLower(char c)
{
return (c >= 'a' && c <= 'z');
}
int main()
{
freopen("input.txt", "r", stdin);
cin.getline(code, 30);
cin.getline(in, 100);
for (int i = 0; in[i]; i++)
{
char c = in[i];
if (isUpper(c))
in[i] = code[c - 'A'] - 32;
else if (isLower(c))
in[i] = code[c - 'a'];
}
cout << in;
return 0;
}
#endif- c++ 의 iostream 을 이용하면 문자열 입력 출력을 더 간단히 할 수 있다.
- cin.getline(in, 100);
- cout << in;
- 여기다가 #include 을 하면
- string in; : string 은 동적 메모리 할당을 하기 때문에 문자열 크기를 지정하지 않아도 된다.
- getline(cin, code);
#include <string>
int main()
{
freopen("input.txt", "r", stdin);
getline(cin, code);
getline(cin, in);
for (char &c:in)
{
if (isUpper(c))
c = code[c - 'A'] - 32;
else if (isLower(c))
c = code[c - 'a'];
}
cout << in;
return 0;
}- **필수 문제 **
- 임의의 문장을 입력 받아 각 단어 별로 나눈 후 단어들의 중복되는 개수를 구하는 프로그램
- 입력된 스트링은 글자 제한이 없음. 즉 공백이나 ',' 도 입력 가능
- 입력된 문장에서 각 단어 사이의 구분은 공백
- 단어에는 공백을 제외한 단어들 만이 포함
- 문장 단위 단어들의 발생 빈도를 오름차순으로