소수점 이하 첫째 자리에서 반올림

#include < cmath >
round(3.8)

결과: 4

배열 VS 연결 리스트

• 추가하고 싶은 위치의 주소를 알고 있을 경우, 임의 위치에 원소 추가/제거가 O(1)이 걸림. 알고 있지 않은 경우(ex 3번째 원소 뒤에 84를 추가), 해당 위치까지 찾아가는 시간이 걸리기 때문에 O(1)이 아님.

• 연결리스트에서는 각 원소가 다음 원소, 혹은 이전과 다음 원소의 주소값을 가지고 있어야함. 따라서 32비트 컴퓨터면 주소값이 32비트(=4바이트) 단위이니 4N 바이트가 추가로 필요함. (64비트 컴퓨터면 8N) 즉, N에 비례하는 만큼의 메모리를 추가로 쓰게 된다.

손코딩 문제

1. 원형 연결 리스트 내의 임의의 노드 하나가 주어졌을 때, 해당 List의 길이를 효율적으로 구하는 방법?

• 동일한 노드가 나올 때까지 계속 다음 노드로 가면 됨. 공간복잡도는 O(1), 시간복잡도는 O(N)

2. 중간에 만나는 두 연결 리스트의 시작점들이 주어졌을 때, 만나는 지점을 구하는 방법?

• 일단 두 시작점 각각에 대해 끝까지 진행시켜서 각각의 길이를 구함.
• 그 후 다시 두 시작점으로 돌아와서 더 긴 쪽을 둘의 차이만큼 앞으로 먼저 이동시켜놓고 두 시작점이 만날때까지 두 시작점을 동시에 한 칸씩 전진시키면 됨. 공간복잡도 O(1), 시간복잡도 O(A+B)

3. 주어진 연결 리스트 안에 사이클이 있는지 판단하라

• Floyd’s cycle-finding algorithm, 공간복잡도 O(1), 시간복잡도 O(N)
• 내가 생각한 답: 연결리스트의 개수를 구한 다음에 각 노드의 next값을 봤는데 -1이 나오지 않으면 사이클 존재 ( -> 안됨. 왜냐하면 사이클이 있는경우에는 연결 리스트의 개수를 제대로 구할 수 없다)
• 정답: 한 칸씩 가는 커서와 두 칸씩 가는 커서를 동일한 시작점에서 출발시키면 사이클이 있는 경우, 두 커서는 반드시 만나게 된다. 반대로 사이클이 없으면 두 커서가 만나지 못하고 연결 리스트의 끝에 도달함.

백준 10816번 문제를 풀다가 map으로 구현한 뒤, 이분 탐색(lower_bound)으로 풀었을 때는 시간초과가 나고, 배열을 sort한 후 이분 탐색 (lower_bound, upper_bound)으로 풀었을 때는 성공함. -> 왜 이런 결과가 났을까?

map은 red black tree로 구현이 되어있다. 따라서 이진 탐색 트리와 red black tree 비교해보자.

이진 탐색 트리

개념

• 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값을 가진 노드들로 이루어짐
• 각 노드의 오른쪽 서브 트리에는 해당 노드의 값보다 큰 값을 가진 노드들로 이루어짐

탐색

• leaf 노드를 만날 때까지 혹은 원하는 값을 찾을 때까지 이진 탐색 트리를 내려가며 탐색한다.
• 탐색의 시간 복잡도는 O(h) : 트리의 높이(루트 노드에서 leaf 노드에 이르는 엣지의 수의 최대값)
• 그러므로 이진 탐색 트리가 균형 상태라면 O(h) = O(logN), 불균형 상태라면 O(h) = O(N) 시간이 걸린다.

삽입

• 새 노드는 항상 leaf 노드에 삽입된다.
• 시간 복잡도는 O(h) : 삽입할 위치를 찾는데 걸리는 시간, O(1): 삽입 시간

삭제

• 시간 복잡도는 (3) 삭제할 노드에 값이 둘 있는 경우에 해당하는 계산량을 따른다.
• 삭제할 노드의 레벨이 d일 때, 1단계에서 d 번의 비교 연산이 필요하므로 O(d) -> 2단계에서 삭제 대상 노드의 서브 트리 높이(h-d)에 해당하는 비교 연산이 필요하므로 O(h-d) -> 총 O(d+h-d) = O(h)

(1) 삭제할 노드가 leaf 노드인 경우

• 해당 노드 삭제해주면 됨

(2) 삭제할 노드에 자식이 하나 있는 경우

• 삭제할 노드의 부모와 자식을 연결해주면 됨

(3) 삭제할 노드에 자식이 둘 있는 경우

• successor 노드 값과 삭제할 노드의 값을 바꿔준 뒤, successor 노드를 삭제
• successor 노드?
  • 삭제할 노드의 오른쪽 서브 트리에서 최소값
  • 즉, inorder(중위) 순회에서 다음 노드를 말함
• 과정
  • 1단계) 삭제 대상 노드의 오른쪽 서브 트리를 찾는다.
  • 2단계) Successor 노드를 찾는다.
  • 3단계) 2에서 찾은 successor의 값을 삭제 대상 노드에 복사(바꿈)
  • 4단계) Successor 노드를 삭제

한계점

• 이진 탐색 트리의 연산은 O(h)이다. 그러나 불균형한 이진 트리의 경우, O(h) = O(n)이 되기 때문에 결론적으로 이진 탐색 트리의 계산복잡도는 O(n)이 된다.
• 따라서, 트리 전체의 균형을 맞추는 AVL Tree 제안됨

Red Black Tree

개념

• 이진 탐색 트리의 일종이다. 단 아래의 속성을 만족해야함.
  • 1. 모든 노드는 빨간색, 검은색 둘 중 하나이다.
  • 2. 루트 노드는 검은색이다.
  • 3. 모든 leaf 노드는 검은색이다.
  • 4. 어떤 노드가 빨간색이라면 두 개의 자식 노드는 모두 검은색이다.
  • 5. 각 노드로부터 그 노드의 자손인 leaf 노드로 가는 경로들은 모두 같은 수의 검은색 노드를 포함한다.

탐색

• 이진 탐색 트리의 탐색 방법과 같음
• 시간 복잡도 O(logN)

삽입

• 1단계) 이진 탐색 트리의 특징대로 삽입 후, 삽입 노드의 색깔을 빨간색으로 설정한다.

• 2단계) 삽입 후, Red Black Tree의 특징을 위반할시, 노드의 색깔을 조정하고, Black-Height가 위배되었다면 restructuring을 통해 height를 조정

• 새로 삽입할 노드를 z라고 가정

• 시간복잡도는 O(logN)

(1) z의 삼촌이 빨간색 -> Recoloring

• 1단계) z의 부모와 z의 삼촌 노드를 red -> black으로 변경하고, z의 할아버지 노드를 black -> red로 변경
• 2단계) z의 할아버지 노드의 부모 노드가 빨간색인 경우, 위의 과정을 반복한다.
• 3단계) z의 부모가 검은색을 만날 때 종료되며, 루트까지 올라가게 되면 루트 노드를 검은색으로 바꾸고 종료

(2) z의 삼촌이 없거나 검은색 -> Rotation & Restructuring

• 1단계) z 노드, z 노드의 부모, z 노드의 할아버지 노드를 오름차순으로 정렬
• 2단계) 중앙값을 부모 노드로 만들고 나머지 노드를 자식으로 변환
• 3단계) 부모 노드가 된 노드를 검은색으로, 나머지 노드를 빨간색으로 변경

삭제

• 삽입 연산과 유사한 방식으로 rotation을 구현함으로써 해결 가능
• 빨간색 노드를 삭제할 때는 그냥 삭제를 수행하면 됨
• 시간복잡도는 O(logN)

특징

• AVL 트리가 Red Black Tree보다 탐색이 빠르다.
  • AVL 트리가 더 엄격한 균형을 유지하기 때문
• Red Black Tree는 AVL 트리보다 빠른 삽입과 제거를 제공

백준 문제와 비교해서 생각해보기

• map이나 set은 red black tree 자료구조를 사용하는데 이는 시간복잡도는 log를 보장해주지만 상수가 매우 큰 자료구조이다.
• 특히 삽입/삭제 연산에서 상당히 많은 작업이 들어갈 수 있음.
• 따라서, 입력을 한 번에 받고 나중에 정렬하는 것이 훨씬 빠르다.

문자열 파싱 함수

1. istringstream

• string을 입력받아 다른 형식으로 바꿔주는 기능.
• istringstream은 공백을 기준으로 문자열을 파싱하여 변수의 형식에 맞게 변환해준다.

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main() {
	istringstream iss("test 123 aaa 456");
	string s1, s2;
	int i1, i2;
	iss >> s1 >> i1 >> s2 >> i2; // 공백을 기준으로 문자열을 parsing하고 변수 형식에 맞게 변환
	cout << s1 << endl;
	cout << s2 << endl;
	cout << i1 << endl;
	cout << i2 << endl;
}

2. ostringstream

• ostringstream은 string을 조립하거나, 특정 수치를 문자열로 변환하기 위해 사용한다.
• ostringstream은 문자열을 붙이는 것 외에도 int나 double형과 같은 수치값을 간단하게 string으로 바꿀 수 있다.

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main() {
	ostringstream oss;
	string s1 = "abc", s2 = "gjw";
	int i1 = 198;
	double d1 = 3.591;
	// 문자열 붙이기 
	oss << s1 << "\n" << i1 << "\n" << s2 << "\n" << d1;
	// str() : ostringstream 객체에서 조립된 문자열을 꺼낸다. 
	cout << oss.str() << endl; // str() : ostringstream 객체에서 조립된 문자열을 꺼낸다. 
}

3. string stream

• stringstream은 가지고 있는 string에서 공백과 \n을 제외한 문자열을 차례대로 뻬내는 역할을 수행

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main() {
	string str = "123 456 \nabc\ndef", token;
	stringstream ss(str);
	while (ss >> token) {
		cout << token << endl;
	}
}

• 만약 공백이나 \n이 아닌 다른 문자를 기준으로 문자열을 분리하고 싶다면?
  • getline() 함수 사용

#include <iostream>
#include <sstream>
#include <string>
using namespace std;

int main() {
	string str = "gkg|giew|789", token;
	stringstream ss(str);
	while(getline(ss, token, '|') {
		cout << token << endl;
	}
}

함수의 parameter (매개변수), argument (인수)

call by value : 값을 이용한 전달

• 인수의 값(a)을 함수의 매개변수(num)로 값을 복사해 사용하는 방식
• 계산은 인수의 값에 영향주지 못한다.

void add(int num) {
	num += 10;
}

int main() {
	int a = 10;
	add(a)
}

call by reference : 참조를 이용한 전달

• 인수로 참조를 전달하여 값의 복사를 통한 전달이 아닌 원본 데이터를 직접 전달하는 방법 1

void add(int &num) {
	num += 10;
}

int main() {
	int a = 10;
	add(a)
}

call by reference (const 참조)

• 원본에 직접 접근하지만, 값을 바꿀 수는 없음

void add(const int &num) {
	num += 10; // 에러가 뜬다. 
}

int main() {
	int a = 10;
	add(a)
}

call by address : 주소를 이용한 전달

• 원본 데이터에 직접 접근할 수 있는 방법 2
• 함수 내부에서 포인터의 역참조(*num)를 통해 원본 데이터에 접근할 수 있음
• 배열을 사용할 때 편리함
• (1) 포인터를 역참조할 경우, 직접 접근보다 느리며 (2) null값을 역참조하게 되면 프로그램이 강제 종료됨

void add(const int* num) {
	*num = 12;
}

int main() {
	int a = 10;
	add(&a)
}

// 배열 넘기기 
void print(int* _arr, int length) {
	for (int i = 0; i < length; i++) {
		cout << _arr[i] << " ";
	}
}

int main() {
	int arr[] = {1, 2, 3, 4};
	int length = 4;
	print(arr, length); // 배열의 이름을 인수로 넘겨줄 경우, 주소값이 들어가기 때문에 배열의 모든 원소에 접근 가능 
}

priority_queue, sort에서의 정렬 방법

차이점

1.

• #include < algorithm > : sort에서는 greater가 내림차순
• #include < queue > : priority_queue의 sort에서는 greater가 오름차순

2.

• #include < algorithm > : sort에서는 cmp 함수를 만들 때, 인자의 왼쪽이 기준
• #include < queue > : priority_queue의 sort에서는 cmp 함수를 만들 때, 인자의 오른쪽이 기준

greater 사용하여 정렬

priority_queue

• priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> pq;
• priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

sort 함수

• sort(v.begin(), v.end()); // 오름차순
• sort(v.begin(), v.end(), greater()); // 내림차순

cmp 사용하여 정렬

1. first 큰 값부터 리턴, first 값이 같다면 second 값이 큰 값부터 리턴

priority_queue

• 기본적으로 priority queue 작동 자체가 first 값이 큰 값부터 리턴, 같다면 second 값이 큰 값부터 리턴이 된다.

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second < b.second; // pq는 오른쪽이 기준이기 때문에 second 내림차순 정렬 
    else return a.first < b.first; // first 내림차순 정렬 
}

sort 함수

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second > b.second; // sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬 
    else return a.first > b.first; // sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬 
}

2. first 큰 값부터 리턴, first 값이 같다면 second 값이 작은 값부터 리턴

priority_queue

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second > b.second; // second값 기준 오름차순
    else return a.first < b.first; // first값 기준 내림차순 (큰 값 우선)
}

sort 함수

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second < b.second;
		// sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬 
    else return a.first > b.first;
		// sort는 왼쪽이 기준이기 때문에 first 내림차순 정렬 
}

3. first 작은 값부터 리턴, first 값이 같다면 second 값이 작은 값부터 리턴

priority_queue

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second > b.second; // second값 기준 오름차순
    else return a.first > b.first; // first값 기준 오름차순
}

sort 함수

bool cmp (pair<int, int> &a, pair<int, int> &b) {
    if (a.first == b.first) return a.second < b.second;
		// sort는 왼쪽이 기준이기 때문에 second 오름차순 정렬 
    else return a.first < b.first;
}

그래프의 최단거리 구하는 알고리즘

다익스트라 알고리즘

• 하나의 정점에서 출발했을 때, 다른 모든 정점으로의 최단 경로를 구하는 알고리즘
• 다이나믹 프로그래밍 문제임 -> 최단 거리는 여러개의 최단 거리로 이루어져있기 때문
• 현재까지 알고 있던 최단 경로를 계속해서 갱신
• 선형 탐색으로 구현 시, 시간복잡도 = O(N^2)
• 힙으로 구현 시, 시간복잡도 = O(NlogN)

과정

• 1 -> 3 으로 가는데 6의 가중치 존재, 1 -> 2로 가는데 3의 가중치가 존재
  • 이때, 1 -> 3 경로의 최단 경로의 가중치는 <6>
• 2 -> 3 으로 가는데 1의 가중치가 존재
  • 이때, 1 -> 3 경로는 1 -> 2 -> 3 경로가 가장 최단 경로임을 알 수 있고 가중치는 <4>
  • 따라서 1 -> 3 최단 경로를 갱신해준다.

작동 과정

1. 출발 노드를 설정한다.
2. 출발 노드를 기준으로 각 노드의 최소 비용을 저장한다.
3. 방문하지 않은 노드 중에서 가장 비용이 적은 노드를 선택한다.
4. 해당 노드를 거쳐 특정한 노드로 가는 경우를 고려하여 최소 비용을 갱신한다.
5. 위 과정에서 3번 ~ 4번을 반복한다.

• 방문한 노드 != 인접 노드

플로이드 알고리즘

• 모든 정점에서 모든 정점으로의 최단 경로를 구하는 알고리즘
• 다익스트라 알고리즘은 가장 적은 비용을 하나씩 선택해야 했다면, 플로이드 와샬 알고리즘은 기본적으로 거쳐가는 정점을 기준으로 알고리즘을 수행
• 소스코드가 간결
• 시간복잡도 = O(N^3)

작동 과정

1. 노드 1을 거쳐가는 경우
   • X에서 Y로 가는 최소 비용 VS X에서 노드 1로 가는 비용 + 노드 1에서 Y로 가는 비용
   • 즉, 1을 거쳐서 가는 경우가 더 빠른 경우가 존재한다면 빠른 경우로 최소 비용을 계산
2. 노드 2를 거쳐가는 경우
3. 위와 같은 방식으로 노드 3과 노드 4에 대해서도 수행해주면 됨
4. 전체 배열이 성공적으로 갱신

Map

# include < map >

정의

인덱스로 int가 아닌 다른 자료형을 사용할 수 있는 배열
(배열이라고 했지만, 내부적인 구조는 각 노드가 unique한 key와 value의 쌍으로 이루어진 트리 (레드 블랙 트리 ))
key를 기준으로 정렬된 상태
같은 key를 갖는 노드를 추가하면, 해당 key값을 갖고 있던 원래 노드의 value값에 덮어씌워지게 된다.
map은 요소에 접근할 때, 반복자(iterator)를 이용하는 방식과 인덱스(key)를 이용하는 방식 두가지 사용 가능

사용법

• m.insert(make_pair(k,v)) : m에 key가 k이고, value가 v인 노드 추가

• m.insert(v.begin(), v.end()) : v에 있는 모든 값 추가

• m.erase(k): m에서 key가 k인 노드 삭제

• m.erase(m.begin()): map의 첫번째 원소 삭제

• m.find(k): m에서 key가 k인 노드를 찾아, 해당 노드를 가리키는 iterator 리턴

• map<char,int> m;

• map<char,int>::iterator it;

• for (it = m.begin(); it != m.end(); it++)

  • cout << it->first << “ “ << it->second;

Set

# include < set >

정의

Kay만 있는 map 혹은 정렬된 집합.
set이 갖는 값들은 중복을 허락하지 않고 정렬되어 있다.

사용 용도

특정 값에 대해 검색을 빠르게 하고 싶은 경우

특정 문자열 삭제

• s.erase(remove(s.begin() + I, s.begin() + I + 1, s[I]), s.end());

• remove()는 # include < algorithm > 에 포함되어 있음

정규표현식

regex

Regex 인스턴스를 생성하여 생성자에 검사할 형식을 인수로 넘긴다.

• regex re(“\d”) -> \d : 10진수 숫자 1개만 입력받는 정규식

  • regex_match(“0”, re) -> match
  • regex_match(“12”, re) -> no match
  • 이때, 0과 12는 string

• \d: 숫자 1개만 받아야 OK

• \d+ : 숫자 1개 이상이면 OK

• \d* : 숫자 0개 이상이면 OK

• \d? : 숫자 0개 혹은 1개여야 OK

• [ab] : a나 b만 된다. 각 1개씩만. a : OK, b : OK, ab : not OK

• [A-Z]+ : A부터 Z까지의 문자가 1개 이상이면 OK

• [A-Z]{1,5} : A부터 Z까지의 문자가 최소 1개 최대 5개면 OK

binary_search

• Binary search 사용할 때, 데이터는 정렬되어 있어야함.

• 선형 탐색은 O(N)에 동작하고 이분 탐색은 O(log N)에 동작한다. 따라서 N이 커질 수 록 속도 차이 커짐

( N개로 이루어진 정수 배열에서 M 개의 key 찾기)

• 만약 M개의 수에 대해 선형 탐색한다면 ? 시간 복잡도 = O(MN)
• 만약 배열을 정렬하고 이분 탐색 수행한다면? 시간 복잡도 = O(NlogN + MlogN)
  (NlogN => 정렬에 필요, MlogN => 이분 탐색에 필요)

a[i] + a[j] + a[k] = a[l]

• 뭔가 2개를 묶거나 한 다음, 어느 한쪽의 값을 이분 탐색으로 찾아서 시간복잡도를 낮추는 아이디어는 이분 탐색 관련 응용문제에서 핵심적으로 많이 사용됨.
• a[i] + a[j] + a[k] = a[l] 는 a[i] + a[j] = a[l] - a[k] 이다. 따라서 a[i] + a[j]를 two[m]으로 만들어서, two[m] = a[l] - a[k] 로 구현 가능
• 이때, a[l] - a[k] 값이 two 배열 내에 있는지 이분 탐색으로 search하면 됨.