: Algorithm (7) 썸네일형 리스트형 [C/C++] quicksort 오랜만에 하려니 기억이 안나서 올림 void quicksort(int l, int r, int* arr) { if (l >= r)return; int i = l - 1; int j = r + 1; int s = arr[(l + r) / 2]; while (1) { while (arr[++i] s); if (i >= j)break; int t = arr[i]; arr[i] = arr[j]; arr[j] = t; } quicksort(l, i - 1, arr); quicksort(j + 1, r, arr); } [C/C++] 제곱 최근에 친구랑 같이 풀었던 알고리즘 문제 문제) 입력으로 자연수 a가 주어진다. 이 때, 자연수 k를 곱한 결과가 거듭제곱수가 되는 최소의 k를 구하는 프로그램을 작성하여라. 인풋 예제) 5 // 데이터 입력 갯수 2 // 첫번째 인풋 4 // 두번째 잇풋 12 // 세번째... 14 919451 코드에 수도코드도 안지워서 코드로 봐도 되지만 간단히 설명하면 1. 필요한 범위까지의 소수를 구한다. 2. 지금 값이 소수인지 확인한다. 3. 아니라면, (while) 가장 작은 소수부터 k로 나눠 본다. 3-1. 홀수로 나눠지면, k를 곱한다. 3-2. 짝수로 나눠지면, 그대로 둔다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 2.. [C/C++] 큰 수의 곱셈 (karatsuba, 카라츄바) 개념은 별로 안 어려운거 같은데, 막상 짜려니 너무 힘들다.. 개념 속도 O(n^log3) B진법의 m자릿 수를 가진 X와 Y라는 수가 주어질 때, 마지막 결과 값에서 보면 곱셈은 총 3번이다. 우리가 흔히 아는 곱셈으로하면 곱을 4번 연산해야하는데, 1회줄어들었다. 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85.. [C/C++] vector 구현 특정 알고리즘 대회에서는 lib제한이 있을 수 있다. 그런 경우를 대비해서 vector 구현방법에 대해서 알아보자. 물론 전체 기능을 구현할 수는 없으니, 주요한 기능인 push_back 에 대해서만 작성하였음. #include 간단하게 구현해보자. template class Vector { private: T *values; int size; int cap; public: Vector() { values = new T[4]; size = 0; cap = 4; } Vector(int default_capacity) { values = new T[default_capacity]; size = 0; cap = default_capacity; } ~Vector() { delete[] values; } void.. [C/C++] 트라이 (Trie) 문자열 탐색을 위한 트리 구조를 가진 알고리즘 문자 탐색 트리(Tree) 탐색 속도 O(log_2(n)) 사이즈 문자열길이^len children[index]) { current->children[index] = new TrieNode; } current = current->children[index]; } current->valid = true; } bool Trie::find(const char* str) { TrieNode *current = head; int i = -1; while(str[++i] != 0) { int index = convertCharToIndex(str[i]); if(!current->children[index]) { return false; } current = curren.. 알고리즘 사이트 추천 국내 사이트 [추천] 프로그래머스 programmers.co.kr 너무 급떡상해서, 알고리즘에 테스트 케이스가 부적합한게 좀 있다던데, 난 모르겠고~~~ 채용 공고 관련보여줘서 보여줘서 좋음 알고리즘 뿐만 아니라, 다른 기술 문제도 있어서 좋음 백준 www.acmicpc.net 문제많고 괜찮아서 쓴 듯 백준님... 더블릿 www.dovelet.com 혼자 공부하기에 좋음 알고리즘별로 정리가 잘 되어있어서 좋음 TMI, 난 여기서 처음 시작했음 코드업 codeup.kr 무료 온라인 IDE 제공, 온라인치고 괜찮았음 피시방 코딩 쌉가능 정올 http://jungol.co.kr 알고스팟 https://algospot.com 해외 사이트 LeetCode https://leetcode.com 가장 큰 사이트 Co.. [C++] 더블 링크드 리스트 (Double Linked List) 1. Why 만약, 배열에 데이터가 있을 때, 중간에 삭제하게 되면, 삭제한 부분을 어떻게 메꿔야 할까? 만약, 배열의 시작 지점(arr[0]) 앞에 데이터를 삽입할 경우가 생긴다면 어떻게 해야할까? 이러한 문제를 해결 할 수는 없을까? 2. What / How 순차적으로 하나씩 입력이 가능한 배열이다. 리스트의 장점은 중간에 새로운 데이터를 삽입할 때, 기존 데이터를 전부 다 뒤로 한칸씩 미룰 필요가 없다. (이유는 포인터로 주소값을 가지기 때문) 링크드 리스트 비용 삽입 (Insert) 삭제 (Remove) 탐색 (contains or search) 링크드 리스트 O(1) O(n) O(n) 각 함수의 설명은 코드로 대신하겠습니다. void init(int size); void insert(Type v.. 이전 1 다음
