§ Intro

main.cpp 와 user.cpp 로 구성
강의 코딩 스타일 : IDE : VS2019 (보조 codeblocks(
#define LM 1000 보다는 const int LM = 1000
식별자 : ClassName 은 대문자로 시작

§ (06/23) Divide and Conquer

Merge Sort

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)
다시 보기

Binary Search

정렬된 리스트에서 특정 값의 위치를 찾는 알고리즘
리스트 중간 값을 선택하여 찾고자 하는 값과 비교하는 방식
찾는 값이 아니면 탐색 범위를 절반으로 줄일 수 있음
문제 유형
- 최적화 문제 (최소값, 최대값) 를 결정 문제로 바꿔서 생각하는 경우
- 이분 검색으로 가장 최적의 해를 탐색하는 방법으로 해를 구한다.
- 답의 후보들이 정렬되어 있는 경우 유용하게 사용 가능
이진 검색 과정
- 현재 탐색 구간의 가운데 배열 번호 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;
}

§ (06/24) 구현

수열

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;
}

Kadane's Algorithm

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

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;
}

합이 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;
}

§ (06/25) String

암호 풀기

복호화 키 (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;
}

단어 세기

**필수 문제 **
임의의 문장을 입력 받아 각 단어 별로 나눈 후 단어들의 중복되는 개수를 구하는 프로그램
- 입력된 스트링은 글자 제한이 없음. 즉 공백이나 ',' 도 입력 가능
- 입력된 문장에서 각 단어 사이의 구분은 공백
- 단어에는 공백을 제외한 단어들 만이 포함
- 문장 단위 단어들의 발생 빈도를 오름차순으로

SW Academy - jjin-choi/study_note GitHub Wiki

§ Intro

§ (06/23) Divide and Conquer

Merge Sort

수열 복원

다시 보기

Binary Search

제곱근

§ (06/24) 구현

수열

Kadane's Algorithm

Two pointer

합이 0이 되는 연속 구간 세기

§ (06/25) String

암호 풀기

단어 세기

변장

공통 부분 문자열

⚠️ GitHub.com Fallback ⚠️

SW Academy - jjin-choi/study_note GitHub Wiki

§ Intro

§ (06/23) Divide and Conquer

Merge Sort

수열 복원

다시 보기

Binary Search

제곱근

§ (06/24) 구현

수열

Kadane's Algorithm

Two pointer

합이 0이 되는 연속 구간 세기

§ (06/25) String

암호 풀기

단어 세기

변장

공통 부분 문자열

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️