코딩테스트 필수로직

• lower_bound와 upper_bound
• 시계방향과 반시계방향 회전
• 배열의 합(accumulate), 배열 중 가장 큰 요소(max_element), 배열 부분 회전
• 함수인자로 전달해서 변수 수정하기
• n진법 변환
• 내림차순 정렬 & 커스텀 정렬
• 2차원 배열을 회전하는 함수

1. lower_bound와 upper_bound

• 정렬된 배열에서 어떤 값이 나오는 지점이나 어떤 값이 나오기 전의 위치를 반환하려고 할 때 사용
• 그림
  (1) lower_bound : 0번째 배열의 원소부터 찾아서 어떠한 값의 '이상이 되는 위치'를 반환
  (2) upper_bound : 그 값이 시작되기 전의 위치를 반환(뒤에서부터라고 생각)
  $\to$ 1, 2, 2, 3, 4에서 upper_bound(2)를 하면 3을 return
  $\to$ 반환되는 값은 이터레이터이기 때문에 v.begin() 또는 a[0]을 빼주어서, int형으로 몇번째인지를 파악
• 찾고자 하는 수가 없는 경우
  (1) "1, 2, 3, 5"에서 lower_bound(a.begin(), a.end(), 4) - a.begin()은 3을 반환(5를 가르키는 인덱스)
  (2) "2, 3, 4, 5, 7"에서 범위의 양 끝단을 벗어나는 경우

cout << upper_bound(v.begin(), v.end(), 6) - v.begin() << endl; // 4(7을 가르킴)
cout << lower_bound(v.begin(), v.end(), 6) - v.begin() << endl; // 4(7을 가르킴)
cout << upper_bound(v.begin(), v.end(), 9) - v.begin() << endl; // 5
cout << lower_bound(v.begin(), v.end(), 9) - v.begin() << endl; // 5
cout << upper_bound(v.begin(), v.end(), 0) - v.begin() << endl; // 0
cout << lower_bound(v.begin(), v.end(), 0) - v.begin() << endl; // 0

2. 시계방향과 반시계방향 회전

• rotata(first, middle, last)
• first와 last 사이에 있는 부분배열에서, middle이 가리키는 요소가 first로 가며 회전한다고 생각

rotate(v.begin(), v.begin() + v.size() - 1, v.end()); // 시계 방향 
rotate(v.begin(), v.begin() + 1, v.end()); // 반시계 방향 

3. 배열의 합(accumulate), 배열 중 가장 큰 요소(max_element), 배열 부분 회전

1. 배열의 합(accumulate)
   accumulate(v.begin(), v.end(), 0);
2. 배열 중 가장 큰 요소(max_element)
   max_element(v.begin(), v.end());
3. 배열 부분 회전

• 아래 코드는 반시계방향으로 회전이고, 응용을 하면 시계방향으로도 가능

int temp = v[i];
v[i] = v[i + 1];
v[i + 1] = v[i + 2];
v[i + 2] = v[i + 3];
v[i + 3] = temp;

4. 함수인자로 전달해서 변수 수정하기

(1) void ch1(int %a) a = 2; $\to$ ch1(a)로 함수 호출
(2) void ch2(int *a) *a = 3; $\to$ ch1(&a)로 함수 호출

5. n진법 변환

#include <bits/stdc++.h>
using namespace std;
vector<int> v;

int main(){
	int n = 100;
	int b = 2; // 바꿀 진법
	 
	while(n > 1){
		v.push_back(n % b);
		n /= b;
	}
	
	if(n==1) v.push_back(1);
	reverse(v.begin(), v.end());
	for(int a : v){
		if(a >= 10)
			cout << char(a + 55);
		else
			cout << a;
	}
	
	return 0;
}

6. 내림차순 정렬 & 커스텀 정렬

sort(v.begin(), v.end(), greater<int>());
sort(v.begin(), v.end(), greater<pair<int, int>>());

sort(v.begin(), v.end(), cmp);

7. 2차원 배열을 회전하는 함수

// 왼쪽으로 90도
void rotate90(vector<vector<int>> &key){
	int m = key.size();
	vector<vector<int>> temp(m, vector<int>(m, 0));
	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			temp[i][j] = key[j][m - i - 1];
		}
	}
	key = temp;
	return;
}
// 오른쪽으로 90도
void rotate90(vector<vector<int>> &key){
	int m = key.size();
	vector<vector<int>> temp(m, vector<int>(m, 0));
	for(int i = 0; i < m; i++){
		for(int j = 0; j < m; j++){
			temp[i][j] = key[m - j - 1][i];
		}
	}
	key = temp;
	return;
}

이 글은 큰돌님의 '10주완성 C++코딩테스트 | 알고리즘 IT취업'을 수강하고 정리한 내용입니다.