ALGORITHM_PRACTICE (44) 썸네일형 리스트형 [C++] 머지 소트(Merge Sort) 구현 크기를 절반씩 나누어 가장 작은 크기부터 정렬을 한 다음 정렬한 배열을 합쳐 다시 정렬하는 분할정복 방식의 알고리즘입니다. 그림과 같은 방식으로 정렬이 이루어 집니다. using namespace std; template class algorithm{ private: void swap(T& a, T& b){ T tmp = a; a = b; b = tmp; } void sort(T* array_list, int left, int mid, int right){ T sorted[right - left]; int low = left; int high = mid; int index = 0; while(low array_list[hig.. [C++] 퀵 소트(Quick Sort) 구현 정렬 알고리즘 중 빠른 속도를 자랑하는 퀵소트 알고리즘 정렬을 하는 알고리즘을 구현했습니다. #include template class QuickSort{ private: int sort(T* array_list, int left, int right){ int pivot = left; int low = left + 1; int high = right; while(low = array_list[pivot]) high--; if(low > high){ this->swap(array_list[pivot], array_list[high]); } else{ this->swap(array_list[low], array_list[high]); } } return high; }; void swap(T& a, T& b).. [C++] 계산기 구현 보호되어 있는 글입니다. 최대공약수(gcd), 최소공배수(lcm) 알고리즘 문제를 풀다보면 가끔 최대공약수, 최소공배수를 구하라는 문제가 나온다. 자주 있는 문제 유형이 아니다보니 항상 문제를 풀때마다 구하는 방법을 찾는 것 같아서 정리할 필요가 있어서 작성한다. 유클리드 공식이라고 하여 최대공약수에는 다음과 같은 성질이 있다. 0과 n의 최대공약수는 n이다 a와 b의 최대공약수는 b와 a를 b로 나눈 나머지의 최대공약수와 같다 위와 같은 성질이 있다고 한다. 이 공식을 토대로 코드를 작성하면 다음과 같다 int gcd(int a, int b){ // 큰 숫자를 a에 둔다 if(a < b){ int t = a; a = b; b = t; } while(b!=0){ int n = a % b; a = b; b = n; } return a; } 작은 수가 0이 될때까지 반복을.. [프로그래머스] 최고의 집합 [프로그래머스] 최고의 집합 코딩테스트 연습 - 최고의 집합 | 프로그래머스 자연수 n 개로 이루어진 중복 집합(multi set, 편의상 이후에는 집합으로 통칭) 중에 다음 두 조건을 만족하는 집합을 최고의 집합이라고 합니다. 각 원소의 합이 S가 되는 수의 집합 위 조건을 만족하면서 각 원소의 곱 이 최대가 되는 집합 예를 들어서 자연수 2개로 이루어진 집합 중 합이 9가 되는 집합은 다음과 같이 4개가 있습니다. { 1, 8 }, { 2, 7 }, { 3, 6 }, { 4, 5 } 그중 각 원소의 곱이 최대인 { 4, 5 } programmers.co.kr 자연수1 + 자연수2 + ... + 자연수n = S 이면서 자연수1 * 자연수2 * ... * 자연수n 이 최대가 되는 집합 자연수를 중복해서 .. [프로그래머스] 방문 길이 [프로그래머스] 방문 길이 코딩테스트 연습 - 방문 길이 | 프로그래머스 programmers.co.kr 캐릭터가 좌우 10칸짜리 공간을 이동하는데 새로운 길을 지나가는 수를 세는 문제이다 방문노드가 아닌 방문 선분이 필요한데 check[x][y][dx][dy]라는 체크 변수를 만들었다 x, y 좌표에서 dx, dy 좌표로 이동하는 것을 체크하는 변수이다. 음수 좌표는 코드가 귀찮아지니까 전부 5씩 더해 -5,-5 좌표를 0,0으로 두고 시작좌표를 5,5로 바꾸어 진행했다. 주의할 점은 새로운 길을 찾을 때 카운트를 하는데 x,y 좌표에서 dx, dy 좌표를 체크했으면 반대로 dx, dy 에서 x, y로의 좌표도 체크를 해줘야한다. 방향만 다를 뿐 같은 길이기 때문이다. #include using nam.. [프로그래머스] 라면공장 [프로그래머스] 라면공장 코딩테스트 연습 - 라면공장 | 프로그래머스 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량 programmers.co.kr 우선순위 큐를 사용하면 쉽게 풀 수 있는 문제였지만, 나느 전혀 생각하지 못하였다. 내가 처음에 생각했던 방식은 현재 재고에서 공급받을 수 있는 날짜 .. [프로그래머스] 땅따먹기 [프로그래머스] 땅따먹기 코딩테스트 연습 - 땅따먹기 | 프로그래머스 땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다. 예를 들면, | 1 | 2 | 3 | 5 | | 5 | 6 | 7 | 8 | | 4 | 3 | 2 | 1 | 로 땅이 주어졌다면 programmers.co.kr 단순히 DFS나 단순 for문으로 모든 경우를 탐색하는 경우에는 시간초과가 일어난다. 행의 갯수가 100000개라고 가정했을 때 4 * 3 * 3 * .. 이전 1 2 3 4 ··· 6 다음
