솔

https://www.acmicpc.net/problem/5430  뒤집기와 삭제(R과 D) 명령과 숫자 배열을 입력받은 뒤,명령에 따라 배열을 뒤집거나 삭제하는 문제이다.  이 문제를 보고 배열을 숫자만 입력받는게 아닌데 어떻게 처리해야하지?  라는 생각이 들었다. 생각을 하면서 두 가지 과정을 거치면 해결할 수 있을 것 같았다.1. 배열의 처음과 끝은 무조건 대괄호이므로 이를 먼저 제거한다.2. 문자열에서 쉼표를 찾아 쉼표 이전의 문자열을 숫자로 변환  아래 코드에서 tmp는 입력받은 배열을 저장한 string 이고, d는 int를 저장하는 deque이다.deque를 사용한 이유는 아래서. tmp = tmp.substr(1, tmp.size() - 2); //대괄호를 제거 size..

이번에는 c++ 표준 라이브러리인 std::map, std::unordered_map 에 대해 알아보겠습니다. 라이브러리의 이름이 map 이라고 지어진 이유는 mapping 과 관련이 있기 때문입니다.  std::map (Ordered Map)map 은 BST (이진탐색트리) , RedBlackTree(레드블랙트리) 로 구현되어 있어서키의 순서가 자동으로 정렬되고O(log N) 을 기대할 수 있습니다. 또, 트리의 형태를 유지하기 위해 추가적인 메모리를 사용하지만 Unordered_mapd 에 비하면 적고,중복된 값은 허용하지 않습니다. ( 덮어쓰기 ) std::unordered_map (Unordered Map)unordered_map 은 해시테이블로 구현되어 있어서키의 순서가 정렬되지 않고평균적으로 ..

레드블랙 트리는 스스로 균형을 잡는 이진트리 라는 점에서  앞에서 살펴본 AVL과 비슷합니다.https://sol248.tistory.com/61 AVL TreeAVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데sol248.tistory.com 또한, 레드블랙 트리는 실제로 키값을 2개 가지진 않지만 2-3트리의 성질도 가지고 있습니다.https://sol248.tistory.com/63 2-3Tree (2-3트리)다음에 알아볼 레드블랙트리를 더 쉽게 이해하기 위해, 2-3트리에 대해 먼저 알..

AVL트리는 발명자의 이름인 Geory Adelson-Velsky and Evgeii LanDis을 따서 지어졌습니다. 스스로 균형을 맞추는 이진 탐색 트리여서 self-balancing binary search tree 라고 부르기도 합니다.  이진 트리에서, 데이터가 마치 연결리스트처럼 한줄로 쭉 나열되는 최악의 경우 트리의 이점을 살리지 못한다는 단점이 있었습니다바로 아래의 그림처럼 말이죠.  이런 일이 발생하지 않기 위해서는 데이터를 추가할 때 한쪽으로 몰리지 않게 조절해주는 기능이 필요합니다. 이것을 가능하게 한 것이 바로 AVL 트리 입니다. 먼저 이진탐색트리의 코드부터 보겠습니다. 이진탐색트리 클래스)연습을 위해 동일한 기능을 하는 함수를 재귀를 사용한 것과 사용하지 않은 것 둘다 구현했습니..

백준 1074번 문제입니다.    행렬에서 z모양으로 탐색하는 문제입니다. 이 문제는 입력받은 행(r)과 열(c)의 크기에 따라 위치를 판단할 수 있습니다. 위 행렬을 사분면 나누듯 4등분을 하며 재귀적으로 문제를 해결할 수 있을 것 같습니다. ( 입력받은 행과 열이 어디에 위치한지 찾고 또 4등분하고를 반복 )  코드)입력받은 행과 열이1.좌상단2.우상단3.좌하단4.우하단중 어디에 있는지 파악하고, 재귀를 이용하여 그 부분으로 다시한번 쪼개는 방식을 사용.(위치에 따라 return 할 떄 재귀함수에 더해지는 값이 달라지는 것 중요 -> 2의 거듭제곱을 이용하여 표현 가능)#include #include int Z(int n, int r, int c) { if (n == 0) return 0; int..

버킷 정렬이란?bucket은 바구니를 의미합니다. 말 그래도 버킷 정렬은 바구니에 데이터를 담는 형태를 닮았다 하여 이름 붙여졌습니다.위 그림과 같이 숫자를 카테로리별로 나눠 바구니에 담은 뒤,그 바구니 안을 정렬해주는 방식입니다. 바구니 안을 정렬할 때는 앞에서 배웠던 정렬 방식 중 아무거나 사용하셔도 상관 없습니다. 저는 삽입 정렬을 이용해서 버킷 정렬을 구현해보았습니다.  코드)디버깅, 실행할 때 보기 편하도록 버킷을 출력해주는 함수를 추가해주었습니다.#include #include void Print(std::vector& v) { for (auto& a : v) { std::cout >& v) { for (int i = 0; i & v) { for (int i = 0; i = 0 &&..

DFS ( 깊이 우선 탐색 ) 와BFS ( 너비 우선 탐색 ) 에 대한 문제입니다. DFS는 그래프가 있을 때 인접한 vertex중 값이 작은 것부터 깊게 탐색하는 것이고,BFS는 그래프가 있을 때 인접한 모든 vertex를 값이 작은 순으로 탐색하고 그 다음에 깊게 들어가는 방식입니다. 따라서,DFS는 Stack 혹은 재귀를 사용하여 구현할 수 있고 (LIFO)BFS는 Queue 를 사용하여 구현할 수 있습니다. (FIFO) 코드)main함수입니다.문제에 맞는 조건의 수를 입력받아 그래프를 만들고 탐색하도록 작동시킵니다.int main(void) { int N, M, V; std::cin >> N >> M >> V; AdjMatGraph m(N + 1); for (int i = 1; i > u ..

이번에는 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 배열을 두 부분으로 나누고 다시 합치는 과정에서 병합 정렬과 비슷한 면이 있지만,  배열을 절반으로 자르는 병합 정렬과는 달리 퀵정렬은 pivot 값을 중심으로 배열을 두 개로 나눕니다. 이떄 pivot 값은 어떤 값이 되어도 상관 없습니다. (pivot 값에 따라 시간 복잡도가 달라집니다) -퀵정렬 코드(난수x)int Partition(int* arr, int low, int high, int n) { int pivot = arr[size_t(floorf((high - low) / 2.0f)) + low]; int i = low; int j = high; while (true) { while (arr[i] pivot) j--; if (..

Karatsuba Algorithm은 큰 문제를 잘게 쪼개서 하나씩 하나씩 결합하는 분할&정복 알고리즘 중에 하나입니다. 먼저, 문제를 어떻게 잘게 쪼개는지 살펴보겠습니다. 1234*5678을 예시로 살펴보죠.이런 식으로 곱해야 하는 수가 한자리 수가 될 때까지 위와 같은 방법으로 분할시킵니다. 그럼 합칠 때는 어떻게 해야할까요? 위의 과정을 볼 때, 어떤 두 수의 곱셈을 3개의 부분으로 분할시키고 있습니다. 가장 왼쪽에 위치하는 어떤 수들의 앞부분끼리 곱하고 있는 부분. (이를 a라 칭하겠습니다)중간에 위치한 각 수를 분할한 값끼리 더하고 곱셈하는 부분. (이를 b라 칭하겠습니다)가장 오른쪽에 위치한 어떤 수들의 뒷부분들끼리 곱하고 있는 부분. (이를 c라 칭하겠습니다) 원래의 식 1234*5678을 ..

문자열을 n번 ,m번 입력받아서 겹치는 문자열과 그 개수를 출력하는 문제입니다. 단순하게 문자열을 입력받아서 하나하나씩 비교하게 되면 시간이 너무 오래걸려 시간 초과가 날 것입니다. 그렇다면 어떻게 해야할까요?? 해시를 기반으로 하는 탐색을 이용하면 됩니다. 해시는 고유값을 가지기에  데이터의 삽입, 삭제, 탐색 모두 평균적으로 O(1) 입니다. 이번에는 unordered_set 을 이용해보겠습니다. #include #include #include #include #include using namespace std;int main(void) { ios::sync_with_stdio(false); cin.tie(NULL); int n = 0, m = 0; cin >> n >> m; unordere..