알고리즘
-
[프로그래머스]>힙>더맵게 [C++]알고리즘 2020. 6. 17. 02:41
문제링크 : https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같�� programmers.co.kr 힙 문제는 우선순위 큐를 사용하는게 좋다해서 우선순위 큐를 찾아보고 풀었습니다. priority_queue pq; 타입, 포함된 타입, 정렬방법 이렇게 생성할 수 있습니다. 문제에서 최소 몇번을 해야하냐고 물었기 때문에, 정렬을 하여 작은 값들 부터 계산해 나갑니다. 우선순위큐의 top()는 마지막 원소를 확인합니다. 따라서 내림차순..
-
[프로그래머스]>완전탐색>모의고사알고리즘 2020. 6. 15. 00:19
문제링크 https://programmers.co.kr/learn/courses/30/lessons/42840 코딩테스트 연습 - 모의고사 수포자는 수학을 포기한 사람의 준말입니다. 수포자 삼인방은 모의고사에 수학 문제를 전부 찍으려 합니다. 수포자는 1번 문제부터 마지막 문제까지 다음과 같이 찍습니다. 1번 수포자가 찍는 �� programmers.co.kr 완전 탐색은 가능한 모든 경우의 수를 진행하여 결과를 찾아내는 방식입니다. 반복문을 사용한 방식과 재귀호출을 사용한 방식이 있습니다. 이 문제에선 수포자 1은 1,2,3,4,5로 규칙을, 수포자 2는 2,1,2,3,2,4,2,5로, 수포자 3은 3,3,1,1,2,2,4,4,5,5로 규칙이 정해져있습니다. 저는 이 규칙을 배열에 저장해두고, 원형 큐..
-
[프로그래머스] > DFS/BFS > 타겟넘버 [C++]알고리즘 2020. 5. 7. 02:16
문제링크 : https://programmers.co.kr/learn/courses/30/lessons/43165 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr #include #include int answer = 0; using namespace std; void dfs(vector numbers, int target, int i, int num) { if(num==target && i==numbers.size()) { answer++; return; } if(i
-
[프로그래머스] > 스택/큐 > 기능개발 [C++]알고리즘 2019. 11. 12. 23:02
문제 링크 https://programmers.co.kr/learn/courses/30/lessons/42586?language=cpp 코딩테스트 연습 - 기능개발 | 프로그래머스 프로그래머스 팀에서는 기능 개선 작업을 수행 중입니다. 각 기능은 진도가 100%일 때 서비스에 반영할 수 있습니다. 또, 각 기능의 개발속도는 모두 다르기 때문에 뒤에 있는 기능이 앞에 있는 기능보다 먼저 개발될 수 있고, 이때 뒤에 있는 기능은 앞에 있는 기능이 배포될 때 함께 배포됩니다. 먼저 배포되어야 하는 순서대로 작업의 진도가 적힌 정수 배열 progresses와 각 작업의 개발 속도가 적힌 정수 배열 speeds가 주어질 때 각 배포마다 몇 programmers.co.kr #include #include #incl..
-
백준 14916 거스름돈 [C++] - 동적 계획법알고리즘 2019. 5. 28. 21:39
문제 링크 : https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net #include using namespace std; #define MAX 100000 #define infinity 9999999 int coin_change(int w[], int m) { int c[MAX] = { 0 }, i, k; c[1] = infinity+1; for (i = 2; i = w[k] && c[i - w[k]] + 1 < c[i]) c[i] = c[i - w[k]]+1; } } if (c[m] == infinity) return -1; return c[m]; } int main..
-
백준 11050 이항 계수 1 [C++] - 동적 계획법알고리즘 2019. 5. 27. 21:18
문제 링크 : https://www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 소스코드 #include using namespace std; #define MAX 100 int binomial_coefficient(int n, int k) { int C[MAX][MAX]; int m; for (int i = 0; i n >> k; cout
-
Kruskal 알고리즘 구현 과제알고리즘 2019. 5. 14. 19:27
프로그램 개요 욕심쟁이 방법은 최적화 문제를 해결하기 위한 방법이다. 가능한 모든 대안 중에서 가장 좋은 해답을 고르는 문제에 대표적인 최소 비용 신장 트리 구하기를 보다 구체적으로 이해하기 위해, 최소 비용 신장 트리의 구현 방법 중 Kruskal의 알고리즘을 선택. 알고리즘의 필요한 init_set(), find_set(), union_set() 함수를 구현. 프로그램 구조 아래 조건을 만족하는 최소 비용 신장 트리를 만들어 최소 비용을 구한다. 간선의 가중치의 합이 최소. 반드시 (n-1)개의 간선만을 사용. 사이클이 포함되어서는 안 된다. 오름차순(퀵 정렬을 이용)으로 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선을 선택하여 현재의 최소 비용 신장 트리의 집합에 추가한다. 집합을 구..