문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/10809 문제 해결 과정:- 문자열을 받고 앞에서부터 한 알파벳씩 체크한다- 알파벳 개수가 총 26개 이므로 크기가 26인 배열을 만들고 0번째는 a이다.- 문자열에서 받은 알파벳이 처음 나온 알파벳이면 해당 배열에 위치를 넣는다.- 만약 처음 나온 알파벳이 아니라면 지나간다. 123456789101112131415161718192021222324252627#include#includeusing namespace std; int main() {..
C++
문제 정수 4를 1, 2, 3의 조합으로 나타내는 방법은 총 7가지가 있다.1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 문제 해결 과정:- 경우의 수를 계산하면 된다-예를 들어 n=4일때는 1,2,3을 뺀 정수 3,2,1의 경우의 수를 더하면 된다.- 즉 Dp[n] = Dp[n-3] + Dp[n-2] + Dp[n-1] 이다. 123456789101112131415161718192021222324252627#includeusing namespace std; int main() { int Dp[12]; Dp[1] = 1; Dp[2] = 2; Dp[3] = 4; for (int i = 4; i > ..
문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 보관하는 격자모양의 상자들의..
문제 영어 대소문자와 띄어쓰기만으로 이루어진 문장이 주어진다. 이 문장에는 몇 개의 단어가 있을까? 이를 구하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/1152 문제 해결 과정:-string에서 띄어쓰기(\n)까지 같이 입력 받기 위해서 cin대신 getline(cin,sent)를 쓴다-시작 지점과 마지막 지점에 빈칸이 있을경우 카운트를 하나 내린다- 단어의 갯수는 띄어쓰기 수 +1이므로 마지막에 1을 더한다. 123456789101112131415161718192021222324252627#include#includeusing namespace std; int main() { string sent = {}; getline(cin, sent); int cnt..
문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 21을 넘지 않는 한도 내에서, 카드의 합을 최대한 크게 만드는 게임이다. 블랙잭은 카지노마다 다양한 규정이 있다.한국 최고의 블랙잭 고수 김정인은 새로운 블랙잭 규칙을 만들어 상근, 창영이와 게임하려고 한다.김정인 버젼의 블랙잭에서 각 카드에는 양의 정수가 써져있다. 그 다음, 딜러는 N장의 카드를 모두 숫자가 보이도록 바닥에 놓는다. 그런 후에 딜러는 숫자 M을 크게 외친다.이제 플레이어는 제한된 시간 안에 N장의 카드 중에서 3장의 카드를 골라야 한다. 블랙잭 변형 게임이기 때문에, 플레이어가 고른 카드의 합은 M을 넘지 않으면서 M과 최대한 가깝게 만들어야 한다.N장의 카드에 써져있는 숫자가 주어졌을 때, M을 넘지않..
문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/1697 문제 해결 과정:- 백트랙킹 문제- 처음에 재귀를 이용한 dfs로 풀다가 안되서 bfs사용- 3가지 경우를 각각 큐에 넣어서 하나씩 꺼내서 체크한다- K보..
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 출처:https://www.acmicpc.net/problem/1931 문제 해결 과정:- 그리디 알고리즘- 시작 시간과 끝나는 시간을 pair로 만들어서 벡터에 저장- 첫번째 방법: - stl을 사용하여 정렬- iter에 벡터 맨 앞에 값을 저장..
문제준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.동전을 적절히 사용해서 그 가치의 합을 K로 만드려고 한다. 이 때 필요한 동전 개수의 최소값을 구하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/11047 문제 해결 과정:- 내야하는 값보다 작은 값을 지닌 동전을 뺸다- 뺀값이 빼는 동전값 보다 작아질때까지 빼고 만약 동전값보다 작다면 그 동전값보다 작은 동전값에 대해서 위 과정을 반복한다.- 우선순위 큐를 사용하여 동전 값중 가장 큰값부터 시작한다. 12345678910111213141516171819202122232425262728293031323334#include#include#includeusing namespace ..
