솔

문자열을 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..

이진 탐색이란, 정렬되어있는 데이터가 주어졌을 떄 사용 가능한 정렬 방식입니다. 이러한 배열이 주어졌을 때, 7이라는 숫자를 이진 탐색으로 찾는 과정을 살펴봅시다.가장 첫번쨰 인덱스 (0번) 과 가장 마지막 인덱스(9번)의 평균 4 ((0+9)/2) 번 인덱스를 봅니다. 찾고자하는 7은 5보다 크기 때문에, 왼쪽 절반을 다 탐색 범위에서 없앱니다.  그리고, 새로운 탐색 범위의 중간값을 살펴봅니다.7은 8보다 작기 때문에 8을 기준으로 오른쪽 부분도 없앱니다.또, 새로운 범위의 중간값을 봅니다.6보다 7이 더 크기 때문에 6을 탐색범위에서 없앱니다.이제, 탐색이 끝났습니다. 만약 찾을 수 없는 숫자를 탐색하고자 한다면, 위와 같이 숫자가 1개 남아도 탐색이 완료되지 않겠죠.  이것까지 고려해서 코드를 짜..

순차 탐색이란, 배열이 주어졌을 때, 앞에서부터 순차적으로 찾는 탐색입니다. 이런 배열이 주어졌을 때, 9를 찾으려면 어떻게 해야할까요? 우리가 눈으로 보기에 그냥 바로 9가 보이겠지만 컴퓨터는 그렇게 할 수 없습니다. 배열의 크기가 100만개, 1000만개 이렇게 기하급수적으로 커지면 우리의 눈으로도 한번에 찾을 수 없겠죠.  순차 탐색의 과정을 살펴보겠습니다.이렇게, 첫 번째 칸부터 9인지 아닌지 판단하며 나아갑니다. 결국 9번째 칸까지 도달하고서야 9라는 숫자를 찾을 수 있겠죠. 이를 프로그래밍 언어로 어떻게 구현할 수 있을까요?  코드)int SequentialSearch(int* arr, int size, int n) { int i; for (i = 0; i  순차 탐색 함수입니다.배열, 배..

삽입 정렬이란, 배열이 주어졌을 때, 앞에서부터 값을 골라 적절한 자리에 넣는 정렬 방식이다.  코드)#include void InsertionSort(int* arr, int size);void Print(int* arr, int size);int main(void) { int arr[] = {8, 1, 1, 3, 2, 5, 1, 2, 1, 1}; int size = sizeof(arr) / sizeof(arr[0]); InsertionSort(arr, size); return 0;}void InsertionSort(int* arr, int size) { for (int i = 1; i 0 && arr[j - 1] > key; j--) { arr[j] = arr[j - 1]; ..

버블정렬은 많은 사람들이 알 것이라 생각한다. 배열이 주어졌을 때, 앞에서부터 하나하나 비교해서 정렬하는 방식이다. 하나하나 비교해야하기 때문에 시간이 오래 걸린다는 단점이 있지만, (O(n^2)) 정렬해야 할 것이 별로 없을 때는 빠르다는 특징이 있다.  코드)#include void BubbleSort(int* arr, int size);void PrintArr(int* arr, int size);int main(void) { { int arr[] = {5, 1, 4, 2, 3}; int size = sizeof(arr) / sizeof(int); BubbleSort(arr, size); } return 0;}void BubbleSort(int* arr, int..

선택 정렬이란, 배열에서 가장 작은 값을 찾아서 앞으로 가져오는 방식을 반복하는 정렬 방법입니다. 글로만 보면 이해가 안될수도 있으니 그림으로 살펴봅시다.  이렇게 가장 작은 수를 찾아서 정렬을 완료합니다.   코드)#include #include bool CheckSorted(int* arr, int size); // 정렬되었는지 확인할 함수void PrintArr(int* arr, int size); // 배열을 출력하는 함수int main(void) { int arr[] = {8, 3, 2, 5, 1, 1, 2, 5, 8, 9}; int size = sizeof(arr) / sizeof(int); assert(size > 0); // 배열의 크기가 1보다 작으면 오류 발생하도록. ..

두개의 값이 주어졌을 때 , 서로 값을 바꾸는 것을 swap 이라고 한다.  방법 1) 포인터를 이용하는 방식이다.#include void MySwapPrt(int* a, int* b);int main(void){ int x = 10; int y = 5; std::cout    방법 2) 포인터 대신 & 를 이용하는 방법도 있다. 이 방법을 사용하면 *를 사용하지 않아 보기에 깔끔해 보인다.#include void MySwapRef(int &a, int &b);int main(void){ int x = 10; int y = 5; std::cout   방법 3) swap 을 할 때 반드시 temp 를 사용해야 한다고 생각했는데, 아니었다. 사칙연산을 이용하면 temp를 사용하지 않고도 가..