oVeron

이분 탐색(Binary Search) : 정렬된 원소들에 특정 원소가 존재하는지를 O(log N) 시간에 확인하는 알고리즘 아래 코드는 배열 arr에서 찾고자 하는 값의 index를 확인하는 알고리즘이다. #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef tuple tiii; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int arr[10] = {1, 2, 4, 7, 10, 20, 20, 20, 99, 1010}; int x{99}; //찾고자 하는 값 int left{0}, right{10}; while (left ..

알고리즘/algorithm 2023. 4. 24. 14:43

우리가 자주 쓰는 헤더 파일들을 모두 include한 것 설치 방법 : https://miniolife.tistory.com/11 Visual Studio에서 사용하기 처음에 알고리즘 문제를 풀다보면 귀찮?까다로운? 점이 include일 것이다. 어떤 헤더 파일에 어떤 함수가 들어있는지도 익숙하지 않고, 컴파일러는 include를 하라고 오류를 뱉어댄다. 어느 헤더 파 miniolife.tistory.com 입출력 속도 빠르게 하기 ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); //main함수 맨 위에 작성해놓자. 또한, endl은 "\n"보다 느리므로 "\n"을 쓰는 것이 좋다. 사전에 주어지는 데이터의 양을 알 수 없을 때 while(cin >> x) { /..

알고리즘/algorithm 2023. 4. 5. 09:57

정렬(sort) 알고리즘 말 그대로 저장된 원소를 정렬하는 알고리즘이다. 버블 정렬 연달아 있는 원소를 맞바꾸는 과정을 반복하는 정렬 시간복잡도 : O(N^2) #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef tuple tiii; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int arr[5] = {4, 3, 5, 2, 1}; for (int i{1}; i arr[j + 1]) swap(arr[j], arr[j + 1]); } for (int j{0}; j < 5; j++) cout

알고리즘/algorithm 2023. 4. 3. 22:49

set 특정한 순서에 따라 고유한 값을 저장하는 자료구조 각 요소는 고유한 값을 지니기에, set 내에서는 중복되는 요소가 없다. 각 요소의 값은 변경할 수 없다. 하지만 요소의 삽입과 삭제를 할 수 있다. set 내의 값은 언제나 정렬되어 있다. default로 오름차순으로 정렬된다. 헤더 파일 : #include iterator : bidirectional iterator 많이 쓰이는 method들 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; typedef tuple tiii; auto cmp = [](int x, int y) { return x > y; }; // 내림차순 정렬 int m..

알고리즘/algorithm 2023. 4. 2. 22:43

reference(참조), pointer(포인터) #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); int a = 1; int &ref = a; //data type &(variable) = variable // a의 메모리 주소를 &ref에 할당하겠다는 뜻이다. // 이때 ref는 int형 변수, &ref는 int형 변수 ref의 주소를 나타낸다. // 즉, '&'연산자(참조 연산자)는 해당 변수의 주소를 의미한다.(reference) // a와 ref의 주소가 같으므로 당연히 a와 r..

알고리즘/algorithm 2023. 3. 30. 23:47

vector 저장 공간의 크기를 바꿀 수 있는, 배열과 비슷한 연속적인 저장 공간 요소의 삽입, 삭제는 맨 뒤에서만 가능하다. 요소의 접근은 index, iterator, pointer 모두 가능하다. deque와 다르게 메모리 공간이 연속적이기에 pointer를 이용해 저장된 요소들 간의 이동이 가능하다. 헤더 파일 : #include 초기화 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); // vector 선언 방법 vector v; // 비어있는 vector 생성 vector v(..

알고리즘/algorithm 2023. 3. 30. 22:09

deque (double-ended queue) 앞, 뒤 양쪽에서 자료구조의 크기를 확장하거나 축소할 수 있는 연속적인 저장 공간 요소의 삽입과 삭제는 deque의 맨 앞, 뒤에서 가능하다. 요소의 접근은 index, iterator 두 가지 모두 가능하다. 단, deque에 저장된 각 요소의 메모리는 연속적이지 않을 수 있어, pointer 연산을 통해 한 요소에서 다른 요소로 이동하는 행위는 하지 말아야 한다. 헤더 파일 : #include 초기화 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int main() { ios::sync_with_stdio(0); cin.tie(0), cout...

알고리즘/algorithm 2023. 3. 30. 21:33

stack 요소를 오직 뒤에서만 삽입, 제거할 수 있는 자료구조 요소의 접근 역시 뒤에서만 가능하다. 헤더 파일 : #include 대표적인 method들 #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; int main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); stack st; // 선언 : stack variable name for (int i{1}; i

알고리즘/algorithm 2023. 3. 30. 15:50