분류 전체보기 (18) 썸네일형 리스트형 C++ STL sort() - 정렬6 물론 나는 대회 발끝에도 닿아보지 못한 사람이다 하지만 나는 상당히 이상적인 사람이다. 이상적인 사람의 특징은 지금 당장은 쓸모가 없어도 나중에 필요할거 같다면서 요긴해 보이면 모든지 가져간다는 것이다. (적어도 나는 그렇다) 아무튼 오늘 배운 STL sort()도 그런것이다. 나의 은사 동빈나 선생님이 말씀하시길 알고리즘 대회에서 자신이 직접 정렬 알고리즘을 짜는것은 시간 낭비라고 하셨다. 유튜브에서 그대로 배껴온 내 정렬 알고리즘 대신 몇 십년간의 진화를 거듭해온 컴퓨터과학의 로니콜먼같은 사람이 먼저 만들어 놓은 C++ 표준라이브러리의 sort()를 사용하는것이 현명하다. 기본적인 사용법이다 #include #include //STL 함수들을 사용하려면 꼭 추가해 주어야 한다 using namespa.. C++ 병합 정렬(합병 정렬) - 정렬5 이 정렬 알고리즘은 대단하다 평균 O(nlogn)이 나오는 아주 대단한 정렬이라고 볼 수 있다. 병합 정렬. 나는 비록 합병 정렬이라고 부르지만. 아무튼 이 대단한 합병 정렬은 분할 정복법의 교과서 같은 알고리즘이라고 볼 수 있다 병합 정렬의 아이디어는 1. 배열의 모든 원소를 분할 시킨다 2. 분할된 모든 원소를 합병하면서 정렬한다 합병 정렬에서 합병은 실제 정렬이 일어나는 부분이다 1. i, j 로 합병할 두 배열의 첫원소를 가르킨다 (이때 두 배열 이미 정렬이 되어있는 상태이다) 2. i와 j를 비교하여 더 작은 원소를 sorted 배열에 추가하고 + 1을 해준다 3. i 또는 j가 합병할 배열의 끝에 도달했다면 4. 나머지들을 sorted 배열에 추가한다 5. 마지막으로 sorted 배열의 내용물.. C++ 퀵정렬 - 정렬4 퀵 정렬은 대놓고 이름에다가 퀵을 붙여놓은 아주 대담한 정렬이다 그동안의 정렬과 다른 점은 시간 복잡도에 있는데 평균적으로 O(n²)의 시간 복잡도를 가지고 있는 선택, 버블, 삽입과 달리 퀵 정렬은 평균적으로 O(nlogn)의 시간 복잡도를 가지고 있다. 퀵 정렬이 log시간을 가질 수 있는 이유는 분할 정복 알고리즘이기 때문이다 퀵 정렬의 아이디어는 1. 피봇을 정하고 (대부분의 경우 가장 앞의 원소) 2. 왼쪽부터 차례로 피봇보다 큰 값을 3. 오른쪽부터 차례로 피봇보다 작은 값을 찾는다 4. 두 값을 찾았다면 서로 자리를 바꾼다 5. 만약 피봇보다 큰 값의 인덱스와 피봇보다 작은 값의 인덱스가 작아지면 (엇갈리면) 6. 피봇보다 작은 값과 피봇의 자리를 바꾼다 7. start ~ 작은 값 인덱스-.. C++ 삽입 정렬 - 정렬3 삽입 정렬은 O(n²) 정렬 알고리즘 중 가장 효율적인 알고리즘이다 삽입 정렬은 한 원소를 선택하여 그 원소를 알맞은 위치에 삽입하는 알고리즘이다 아이디어는 1. 한 원소를 선택하여 2. 선택한 원소보다 작은 원소를 만날때까지 앞의 원소와 비교한다 3. 앞의 원소가 선택한 원소보다 작다면 선택한 원소와 자리를 바꾼다 4. 선택한 원소보다 작은 원소를 만나면 멈춘다 언뜻 보면 버블 정렬과 유사해 보이지만 다른 점은 정렬을 멈추는 지점을 알기 때문에 선택 정렬이나 버블 정렬과 다르게 불필요한 정렬을 하지 않는다 선택 정렬에서는 왼쪽의 원소들은 이미 정렬이 되어있다는 가정을 하기 때문에 왼쪽으로 탐색했을 때 자기 자신보다 작은 원소가 있다면 거기서 멈추면 된다 int* InsersionSort(int* arr.. C++ 버블정렬 - 정렬2 두번째로 가장 간단한 정렬 알고리즘이다 아이디어는 1. 바로 옆의 값과 비교하여 큰값을 오른쪽으로 보낸다 2. 옆으로 한칸 이동하여 배열 끝까지 반복한다 3. 끝까지 반복하면 가장 큰 수가 가장 오른쪽에 위치하게 된다 1~3까지가 1회전 4. 배열의 개수만큼 회전한다 int* BubbleSort(int* arr, int size){ for(int i=0; i arr[j+1]){// 이미 정렬이 되어 있기 때문이다 && 추가적으로 -1을 해주는 이유는 // 원소들을 비교할때 j+1을 하기 때문이다. int temp = arr[j]; arr[.. C++ 선택정렬 - 정렬1 정렬중에서 가장 간단하고 직관적인 정렬이다 아이디어는 1. 배열중에서 가장 작은 숫자를 선택한다 2. 선택한 숫자와 가장 앞에있는 숫자를 교체한다 int* SelectionSort(int* arr, int size){ int min, index = 0, temp; for(int i=0; i < size; i++){ min = 10000; for(int j=i; j < size; j++){ //~i 까지 정렬이 되어있으므로 i에서 부터 시작 if(arr[j] < min){// 배열의 최소값을 찾는다 min = arr[j]; index = j; } } temp = arr[i];//최솟값과 가장 앞의 값을 교체한다 arr[i] = arr[index]; arr[index] = temp; } return arr;.. C++ 이중배열 이중 배열의 구조적인 모습은 배열을 가르키는 포인터의 배열 이다 int** b = new int*[3]; 스트링 이중배열의 경우 조금 신경쓸것이 있다면 널 문자이다 그렇기 때문에 사용할 문자의 길이 + 1을 해 주어서 null(\0)문자의 자리를 만들어 주어야 한다 char** a = new char*[3+1]; for(int i=0; i 왜 미래의 스마트시티는 블록체인으로 지어질까? - Why will smart cities of the future be built on the blockchain? Why will smart cities of the future be built on the blockchain? 최근 급격한 도시화와 함께 통합 서비스와 스마트 인프라 대한 시민들의 수요가 높아지면서 많은 도시들이 이런 시설들을 마련하기 위한 분주한 움직임을 보이고 있다. 스마트함과 효율적인 인프라를 향한 시민들의 요구가 담긴 스마트 시티를 개발하는데에 있어 과연 블록체인은 어떤 일을 할까? How rapid urbanization is driving the need for smart cities 어떻게 급격한 도시화는 스마트 시티에 대한 수요를 촉발할까? 놀랍게도 1950년대에는 세계인구의 불과 30%만이 도시에 살았다고 한다. 그렇지만 The World Bank에 따르면 현대에 들어서는 전체인구의 .. 이전 1 2 3 다음
