sliver__

이분탐색 [조건] 데이터가 정렬 되어있어야 함 N개의 데이터 중 원하는 값을 찾을 때, O(logN)의 시간 내에 찾아야 하는 경우 [흐름] 정렬된 데이터의 start, last, mid(= (start + last) / 2 ) index를 설정 target value와 정렬된 데이터의 mid index 값을 비교 target value > 데이터[index] 인 경우, start = mid+1로 설정 target value 이분 탐색 적용 주어진..

Depth First Search(DFS), 깊이 우선 탐색 그래프의 탐색에 사용되는 알고리즘 모든 경우의 수를 탐색할 때 사용 Vertex의 순서를 고려할 때 사용 백트래킹에 사용 다익스트라 알고리즘 최단 거리 알고리즘 힙 사용(우선순위 큐) 가중치 있는 간선일 때 사용 priority_queue pq; pq.push(make_pair(0, 시작 정점)); // 시작 정점의 가중치는 0 dist[시작 정점] = 0; while(!pq.empty()) { int cur_vertex = pq.top().second; int cur_dist = -pq.top().first; // 넣을 때 -를 붙여서 넣는다. 가장 작은 간선 가중치가 위로 올라오기 때문이다. for(int i=0;i

안녕하세요~ 디벨로퍼입니다~~ 오늘은 프로그래머스 완주하지 못한 선수를 풀어보겠습니다. https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr ======================================================================== [문제] [제한사항] [입출력 예시 설명] ==============================================..

https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 주어진 자연수 n의 분해합을 구하는 문제이다. 분해합은 어떠한 자연수 n과 각자리의 숫자의 합을 의미한다. n이 1,000,000까지이므로 모두 순회하며 구핻조 2초안으로 구할 수 있다. 제출한 코드는 아래와 같습니다. #include using namespace std; int main(void) { int n, sum, temp, res; cin >> n; for ..

https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 숫자의 개수 n, 목표 숫자 m이 주어지고 n개의 숫자 중 3개의 숫자를 선택해 m에 가까운 숫자를 만드는 문제이다. n이 1부터 100까지 이므로 \(100^3\) = 1000000이므로 완전탐색이 가능하다 아래는 제출한 코드입니다. #include #include #include using namespace std; int main() { int n, m, va..

https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 피보나치 수열을 구하는 문제이다. 제출한 코드는 아래와 같습니다. #include using namespace std; int fibo(int n) { if (n == 0) return 0; if (n == 1)return 1; else return fibo(n - 1) + fibo(n - 2); } int main() { int n; cin >> n; cout