본문 바로가기

알고리즘34

백준 14501번 퇴사 - 문제 설명 상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다. 오늘부터 N+1일째 되는 날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다. 각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다. 상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오. (퇴사일 이후에 일을 끝마치는 경우 금액을 얻을 수 없음) - 입력 1) 첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다. 2) 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 5, 1 ≤ Pi ≤ 1,000) - 출력 첫째 줄에 백준이가 얻을 수 있는 최대 이익을.. 2020. 11. 6.
백준 14888번 연산자 끼워넣기 - 문제 설명 N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)으로만 이루어져 있다. 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C++14의 기준을 따른다. N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하시오 - 입력 1) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 2) 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 3) 셋째 줄에는 합이 N-1인 4개의 정수가 .. 2020. 10. 31.
백준 1759번 암호 만들기 - 문제 설명 암호는 L개의 알파벳 소문자들로 구성되며, 최소 한개의 모음(a,e,i,o,u)과 두개의 자음으로 구성되어 있다. 암호를 이루는 알파벳은 증가하는 순서로 배열되었을 것으로 추측된다. 암호로 사용했을 법한 문자의 종류는 C가지일 때 가능성 있는 모든 암호들을 구하여라 - 입력 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. - 출력 사전식으로 가능한 암호를 모두 출력 * 문제 풀이의 핵심 1. 브루트포스 이 문제는 브루트포스 방법을 사용해 모든 경우의 수를 구한뒤 조건에 맞는 암호를 찾는 방식으로 해답을 구해야 풀 수 있는 문제입니다. 브루트포스 문제는 순열의 구해야 하는 수가 모든 순열을 구하는 시간복잡도가 O.. 2020. 10. 30.
백준 1463번 1로 만들기 - 문제 설명 정수 X 에 사용할 수 있는 연산은 3가지 이며, 정수 N 이 주어졌을 때 연산을 적절히 사용해서 1을 만드려고 한다. 연산을 사용하는 횟수의 최솟값을 구하여라 연산 1. X 가 3 으로 나누어 떨어지면, 3 으로 나눈다. 2. X 가 2 로 나누어 떨어지면, 2 로 나눈다. 3. 1 을 뺀다. - 입력 첫째 줄에 1 보다 크거나 같고, 106 보다 작거나 같은 정수 N 이 주어진다. - 출력 연산을 하는 횟수의 최솟값 출력 * 문제 풀이의 핵심 동적 계획법을 사용해서 어떻게 큰 문제를 작은 문제로 나누어서 해결 할 것인지, 점화식은 어떻게 세울 것인지를 할 수 있어야 풀 수 있는 문제입니다. 1. 동적 계획법 동적 계획법 문제를 풀기 전에 확인해야할 사항 2가지가 있습니다. 1) 부분 문.. 2020. 10. 22.
백준 2357번 최솟값과 최댓값 - 문제 설명 N 개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 범위 중에서 제일 작은 정수 또는 제일 큰 정수를 찾아보자. - 입력 1) N (1 n; int i; for (i = 0; i > input[i]; } init(0, n - 1, 1); cout end || right < start) return INT_MAX; if (left = end) return tree[node].min; int mid = (start + end) / 2; return min(queryMin(start, mid, node * 2, left, right), queryMin(mid + 1, end, node * 2 + 1, left, right)); } int queryMax(i.. 2020. 10. 1.
백준 17420번 깊콘이 넘쳐흘러 - 문제 설명 기프티콘 N개 선물 받은 정우는 기한 연장을 최소 횟수로 연장을 하면서 기프티콘을 다 쓸 수 있도록 하고 싶다. - 조건 1) 한 기프티콘을 한 번 연장할 때마다 기한이 30일씩 늘어난다. 2) 남은 기프티콘 중 기한이 가장 적게 남은 기프티콘만 사용할 수 있다. 3) 하루에 여러 기프티콘을 사용하거나 연장하는 것 모두 가능하다. - 입력 첫 째 줄에 기프티콘의 수 N 이 주어진다. (1 N; int i; for (i = 0; i > A[i]; } for (i = 0; i > B[i]; } for (i = 0; i < N; i++) { arr.push_back({ A[i], B[i] }); } // 32 비트 정수 초과 경우 고려.. 2020. 9. 28.
프로그래머스 징검다리 - 문제 설명 출발지점부터 distance 만큼 떨어진 도착지점이 있습니다. 그 사이에 바위 중 몇개를 제거했을 때 각 지점 사이의 거리의 최솟값 중에 가장 큰 값을 return 하도록 하는 solution 함수를 작성 - 입력 1) 출발지점부터 도착지점까지의 거리 (1 2020. 9. 17.
프로그래머스 섬 연결하기 - 문제 설명 n개의 섬 사이에 다리를 건설하는 비용이 주어질 때 모든 섬이 서로 통행 가능하도록 만들 때 필요한 최소 비용을 return 하도록 하는 solution 작성 - 입력 1) 섬의 개수 n (1 사용언어 : C++ > 에디터 : Visual Studio 2017 > 궁금한점은 댓글로 남겨주세요 - 참고 1) gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html 2) gmlwjd9405.github.io/2018/08/31/algorithm-union-find.html 2020. 9. 6.
프로그래머스 순위 - 문제 설명 n명의 권투선수의 1:1 경기 기록을 가지고 있을 때, 주어진 경기기록을 가지고 정확한 순위를 매길 수 있는 권투선수의 수를 return 하는 solution 함수 작성 - 입력 1) 선수의 수 : 1 2020. 9. 3.

티스토리툴바