본문 바로가기

알고리즘/백준15

백준 1525번 퍼즐 - 문제 설명 퍼즐에 어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 정리된 퍼즐을 만들기 위해 필요한 최소 이동 횟수를 구하는 프로그램을 작성하시오. * 퍼즐이 정리된 상태 1 2 3 4 5 6 7 8 - 입력 1) 세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다. - 출력 1) 첫째 줄에 최소의 이동 횟수를 출력한다. *이동이 불가능한 경우 -1을 출력한다. * 문제 풀이의 핵심 1. BFS 이 문제는 퍼즐의 빈칸을 채우기 위해 상하좌우의.. 2020. 12. 5.
백준 13913번 숨바꼭질 4 - 문제 설명 수빈이는 현재 점 N 에 있고, 동생은 점 K 에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. - 입력 1) 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. (0 ≤ N ≤ 100,000), (0 ≤ K ≤ 100,000) - 출력 1) 첫째 줄에 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. 2) 둘째 줄에 어떻게 이동해야 하는지 공백으로 구분해 출력한다. * 문제 풀이의 .. 2020. 12. 1.
백준 1208번 부분수열의 합 2 - 문제 설명 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오. - 입력 1) 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 2) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. * 주어지는 정수의 절댓값은 100,000을 넘지 않는다. - 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. * 문제 풀이의 핵심 1. 브루트포스 부분수열의 합 2 문제는 주어진 집합의 모든 부분수열을 구한 뒤 더한 값이 S가 되는지 되지 않는지에 대해서 검사해야하는 문제 입니다. N의 제한은 1에서 시작해 최대 40 이기 때문에 집.. 2020. 11. 26.
백준 1182번 부분수열의 합 - 문제 설명 N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오 - 입력 1) 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 2) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. * 주어지는 정수의 절댓값은 100,000을 넘지 않는다. - 출력 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다. * 문제 풀이의 핵심 1. 브루트포스 부분수열의 합 문제는 주어진 집합의 모든 부분수열을 구한 뒤 더한 값이 S가 되는지 되지 않는지에 대해서 검사해야하는 문제 입니다. N의 제한은 1에서 시작해 최대 20 이기 때문에 집합을 .. 2020. 11. 8.
백준 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.

티스토리툴바