본문 바로가기

C++11

백준 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.
백준 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.
백준 1655번 가운데를 말해요 - 문제 설명 수빈이는 동생에게 '가운데를 말해요' 게임을 가르쳐주고 있다. 수빈이가 정수를 하나씩 외칠때마다 동생은 지금까지 수빈이가 말한 수 중에서 중간값을 말해야한다. 만약, 그동안 수빈이가 외친 수의 개수가 짝수개라면 중간에 있는 두 수 중에서 작은 수를 말해야 한다. - 입력 첫째 줄에는 수빈이가 외치는 정수의 개수 N (1 > N; int i; for (i = 0; i > arr[i]; } q_max.push(arr[0]); cout q_min.top()) { int t1 = q_min.top(); q_min.pop(); int t2 = q_max.top(); q_max.pop(); q_min.push(t2); q_max.push(t1); } cout 사용언어 :.. 2020. 8. 12.
백준 12015번 가장 긴 증가하는 부분 수열 2 - 문제 설명 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램 작성 ex) A = {10,20,10,30,20,50} 인 경우 가장 긴 증가하는 부분 수열은 {10,20,30,50} 이다. 길이는 4이다. - 입력 첫째 줄에 수열 A의 크기 (1 > A[i]; } lis.push_back(A[0]); int l_idx = 0; for (i = 1; i 에디터 : Visual Studio 2017 > 궁금한점은 댓글.. 2020. 8. 10.
백준 2565번 전깃줄 - 문제 설명 두 전봇대 A와 B의 전깃줄이 임의로 연결되어 있을 때, 서로 겹치지 않도록 전깃줄들을 배치할 때 없애야 하는 전깃줄의 최소 개수를 구하는 프로그램 작성 - 입력 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. (전깃줄의 개수는 100 이하의 자연수) 둘째 줄에는 한 줄에 하나 씩 A전봇대와 B전봇대가 연결되는 위치의 번호가 주어진다. (위치의 번호는 500 이하의 자연수, 같은 위치에 두 개 이상의 전깃줄이 연결될 수 없다.) - 출력 모든 전깃줄이 서로 교차하지 않게 하기 위해 없애야 하는 전깃줄의 최소 개수 * 문제 풀이의 핵심 0. 알고리즘 : LIS 알고리즘 모든 전깃줄이 연결된 상태에서 없애는 것이 아니라, 어떤 전깃줄을 선택하면 서로 교차하지 않고 가장 많이 연결할 수.. 2020. 8. 7.
백준 1300번 K번째 수 - 문제 설명 배열 A는 크기가 N*N 인 2차원 배열, 배열 B는 크기가 N*N 인 1차원 배열 A[i][j] = i * j 로 이루어진 2차원 배열의 모든 원소를 배열 B에 넣고 오름차순 정렬했을 때 B[k]의 값을 구하는 문제 ※ 배열 A와 B의 인덱스는 1부터 시작한다. - 입력 첫째 줄에 배열의 크기 N (1 k; long long left = 1; long long right = (N * N); while (left = k) { right = mid; } else { left = mid + 1; } } cout 사용언어 : C++ > 에디터 : Visual Studio 2.. 2020. 8. 6.

티스토리툴바