정렬 알고리즘 + 예시 문제 풀이 (33 ~ 39강)
배열 또는 벡터 안에 무작위로 배치되어 있는 수들을 오름차순 또는 내림차순으로 배치할 때 정렬이 쓰인다. 정렬하는 방법에는 대표적으로 선택정렬, 버블정렬, 삽입정렬 등이 있다
선택정렬: 해당 수와 선택한 자리에 있는 수를 조건에 맞게 바꾸는 방법 ex) 가장 큰 숫자를 앞에서부터 차곡차곡 채우는 방식으로 배열을 정렬한다.
for (int i=0; i<n-1; i++) {
idx = i;
for(int j=i+1; j<n; j++) {
if(a[j] < a[idx]) idx = j;
}
temp = a[i];
a[i] = a[idx];
a[idx] = temp;
}
버블정렬: 이웃한 두 수를 비교해 조건에 충족하면 자리를 바꾸는 방법
삽입정렬: 조건에 해당하기 전까지 배열 또는 벡터 안에서 해당 값을 앞 또는 뒤로 땡긴 다음, 조건에 맞을 때 그 자리에 해당 값을 집어넣는 방식.
for(i=1; i<n; i++) {
tmp = a[i];
for(j=i-1; j>=0; j--) {
if(a[j] > tmp) a[j+1] = a[j];
else break;
}
a[j+1] = tmp;
}
이분검색(결정알고리즘) + 예시 문제 풀이 (39 ~ 46강)
배열 또는 벡터 안에서 어떤 조건에 맞는 값을 찾는 문제일 때는 이분검색방법을 먼저 의심해봐야 한다.
이분검색: 배열 또는 벡터의 구간을 시행할수록 찾고자 하는 값의 위치를 기준으로 반씩 줄여서 적은 횟수만으로도 값을 쉽게 찾는 알고리즘 ← 사용하기 위해선 배열 또는 벡터가 이미 정렬되어 있어야 한다.
while(lt <= rt) {
mid = (lt+rt)/2;
if(a[mid] == key) {
printf("%d", mid+1);
return 0;
}else if(a[mid] > key) rt = mid - 1;
else lt = mid + 1;
}
투포인트 알고리즘
2차원 배열을 다룬 문제들 풀기(47 ~ 52강)

for(int i=0; i<9; i++) {
sum = 0.0f;
for(int j=0; j<9; j++) {
sum += v[i][j];
}
ave = round(sum/9);
printf("%d ", ave);
flag = false; lt = 0; rt = 8;
while(lt <= rt) {
mid = (lt+rt)/2;
if(v[i][mid] == ave) {
printf("%d\\n", v[i][mid]);
flag = true;
break;
}else if(v[i][mid] > ave) rt = mid - 1;
else lt = mid + 1;
}
if(flag == false) {
if(v[i][mid] > ave) {
if(v[i][mid]-ave > ave-v[i][mid-1]) printf("%d\\n", v[i][mid-1]);
else printf("%d\\n", v[i][mid]);
}else {
if(v[i][mid+1]-ave > ave-v[i][mid]) printf("%d\\n", v[i][mid]);
else printf("%d\\n", v[i][mid+1]);
}
}
}
스택: LIFO 구조. 프로그램의 작동 방식이 스택 구조를 이용한다.(프로그램이 작동될 때, 스택 안에 스택메모리가 쌓이고, 가장 위에 있는 스택메모리를 먼저 처리한다.) 재귀함수, DFS 등 여러 알고리즘 기법들을 이해하려면 스택에 대해서 이해하는 것이 먼저 필요하다
-스택을 직접 짜는 방식 ←push()와 pop()함수를 직접 만든다.
void push(int x) {
stack[++top]=x;
}
int pop() {
return stack[top--];
}
-C++에서는 #include <stack>을 통해 제공되는 STL을 사용할 수도 있다.
재귀함수: 함수 안에서 자기 자신을 다시 호출하는 함수.
재귀함수를 구현할 때 스택 방식을 사용하여 구현한다. 다음과 같은 구조로 구현하는 것이 좋다
void D(int x) {
if(/*재귀루틴을 벗어나는 조건*/) return;
else {
//재귀함수가 작동하는 코드
D(x+1);
}
}
if와 else를 나누어 if 안에는 재귀루틴을 끝내는 조건을 적고 나머지 코드는 else 안에다 적는다.
스택 & 재귀함수 관련 문제들 풀이(57~62강)
인상깊었던 문제 예시와 풀이 코드

int main() {
stack <int> s;
int i, j=1, n, m;
scanf("%d", &n);
vector<char> str;
for(i=1; i<=n; i++) {
scanf("%d", &m);
s.push(m);
str.push_back('P');
while(1) {
if(s.empty()) break;
if(j==s.top()) {
s.pop();
j++;
str.push_back('O');
}else break;
}
}
if(!s.empty()) printf("impossible\\n");
else {
for(i=0; i<str.size(); i++) printf("%c", str[i]);
}
return 0;
}
<DFS와 관련된 여러 알고리즘 개념과 문제들 풀이>
이진트리 깊이우선탐색: 이진트리 구조의 자료구조를 탐색할 때 쓰이는 방법
-전위순회 출력: 부모 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드
-중위순회 출력: 왼쪽 자식 노드 → 부모 노드 → 오른쪽 자식 노드
-후위순회 출력: 왼쪽 자식 노드 → 오른쪽 자식 노드 → 부모 노드
(62 ~ 66강)
병합정렬 ← divide and conquer가 핵심. 재귀적으로 배열의 크기를 나눈 다음에 나눠진 배열들을 병합하면서 정렬하는 방식.(67강)