머직타드

문제 추천 시스템 Version1 문제 보기 1. 문제 정의 "문제번호, 난이도"로 정의된 아이템들을 가지고 아래의 3가지 명령어에 대해 처리해 주는 문제 입니다. 명령어 상세 내용 비고 recommend x(x = ±1) x = 1: 가장 어려운 문제의 번호를 출력 가장 어려운 문제가 여러개면, 가장 큰 문제 번호 출력 x = -1: 가장 쉬운 문제의 번호를 출력 가장 쉬운 문제가 여러개면, 가장 작은 문제 번호 출력 add P L 난이도 L인 문제 번호 P를 추가 1. 리스트에 없는 문제번호 P만 add 2. 이전에 있던 문제번호 P가 다른 난이도로 add 가능 solved P 문제 번호 P를 제거 리스트에 있는 문제 번호 P만 delete 2. 풀이 방법 탐색 "문제번호, 난이도" 쌍(Pair)을 ..

옥상 정원 꾸미기 문제 보기 1. 문제 정의 높이가 h(1), h(2), h(3) ... h(N)인 빌딩 N개가 있을 때, 각 빌딩에서 다른 빌딩의 옥상을 관찰 가능한 갯수를 구해야 하는 문제입니다. 문제에서의 빌딩들을 예시로 들자면, 위와 같이 6개의 빌딩이 있고 각각 높이가 주어져 있습니다. 각 빌딩에서 오른쪽을 바라 볼 때 옥상이 관찰 가능한 빌딩을 카운팅 해보면 됩니다. 1번째 빌딩에서는 2, 3, 4 빌딩을 볼 수 있고, 2번 빌딩에서는 볼 수 있는 빌딩이 없으며, 3번 빌딩에서는 4번 빌딩을 볼 수 있습니다. 2. 풀이 방법 탐색 이 문제의 핵심은 i번째 빌딩의 높이 h(i)를 기준으로 이전 빌딩들 중, i번째 빌딩의 높이 h(i)보다 낮은 빌딩은 체크할 필요가 없다는 점 입니다. 위의 예시에..

합승택시요금 문제보기 다익스트라, 플로이드 와샬 알고리즘 보기 1. 문제 정의 노드와 무향 간선이 포함된 그래프가 주어졌을 때, 동일한 출발점에서 시작하여 서로 다른 도착점으로 이동하는데 소비하는 최소 비용을 구하는 문제 입니다. 문제에서 주어지는 포인트는 "출발점 s / 도착점 a / 도착점 b" 총 3가지 입니다. 2명이 동일한 출발점 s에서 시작해 임의의 i 지점까지 같이 이동하고, 이후 쪼개져서 각자 도착점 a와 도착점 b로 도착하는 모든 경로 합의 최소 값을 구해야 합니다. 2. 풀이 방법 탐색 s: 출발점 i: 임의의 지점(같이 택시를 탑승하는 종점) a: a가 도착점 b: b의 도착점 s, i, a, b가 위와 같다고 했을 때, 이 문제에서 구해야하는 경로는 3가지 입니다. 1) s -> i..

거스름돈 문제 보기 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사 www.acmicpc.net Greedy 알고리즘 설명은 여기 를 참고하세요. 1. 문제 정의 입력으로 주어지는 X엔이 있을 때, (1000-X)엔을 500/100/50/10/5/1 엔으로 조합해 '몇 개로 잔돈을 줄 것인가'를 결정해야 합니다. 즉 최소한의 개수로 잔돈을 줄지 결정해야 하는 문제입니다. 2. 풀이 방법 탐색 '최소한'의 개수로 거스름돈을 줘야 한다면, 가장 큰 500엔부터 줘도 되는지 따져봐야 합니다. 500엔 1개로 주나, 100..

https://www.acmicpc.net/problem/2748 2748번: 피보나치 수 2 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 1. 문제 정의 피보나치 수열은 학창시절에 많이 봐왔던 일종의 '점화식'으로 정의되는 수열입니다. F(n) = F(n - 1) + F(n - 2) (단, n >= 2) 이 문제에 나와 있듯이, n=2 부터 점화식이 성립하고 n=0일 때 F(0) = 0, n = 1일 때 F(1) = 1 입니다. 2. 풀이 방법 탐색 예를 들어, n = 5라고 가정하고 점화식에 대..

출처 : https://www.acmicpc.net/problem/6603 1. DFS(재귀함수)를 이용한다. 2. input배열과 뽑은 숫자를 임시로 저장할 temp배열이 필요하다. 3. idx_1 : input배열의 인덱스 / idx_2 : temp배열의 인덱스 4. 로또의 문제 특성상 K개중 6개만 뽑으면 된다. 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 #include using namespace std; int input[13]; int temp[13]; int K; void dfs(int idx_1, int idx_2) { if (idx_2== 6) { for (int i = 0; i