문제 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오.출처:https://www.acmicpc.net/problem/2743 문제 해결 과정:-String 라이브러리 사용- cin으로 String 값을 입력 받은 다음 length()로 길이를 구한다.123456789#include#includeusing namespace std; int main() { string s; cin >> s; cout
알고리즘
문제가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/11403 문제 해결 과정: -플로이드 워셜 알고리즘 또는 bfs를 이용하여 풀 수 있다.- a->b 정점간의 직접적인 연결과 a->c->b처럼 간접적인 연결이 있다.- 세번의 반복문을 통하여 간접적인 연결또한 표시해준다. 12345678910111213141516171819202122232425262728293031323334353637383940#include using namespace std; //플로이드 워셜 알고리즘, 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 구해준다. ..
문제 알파벳 소문자로만 이루어진 단어 S가 주어진다. 각각의 알파벳에 대해서, 단어에 포함되어 있는 경우에는 처음 등장하는 위치를, 포함되어 있지 않은 경우에는 -1을 출력하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/10809 문제 해결 과정:- 문자열을 받고 앞에서부터 한 알파벳씩 체크한다- 알파벳 개수가 총 26개 이므로 크기가 26인 배열을 만들고 0번째는 a이다.- 문자열에서 받은 알파벳이 처음 나온 알파벳이면 해당 배열에 위치를 넣는다.- 만약 처음 나온 알파벳이 아니라면 지나간다. 123456789101112131415161718192021222324252627#include#includeusing namespace std; int main() {..
문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다.토마토를 창고에 보관하는 격자모양의 상자들의..
문제 카지노에서 제일 인기 있는 게임 블랙잭의 규칙은 상당히 쉽다. 카드의 합이 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킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그램 봉지와 5킬로그램 봉지가 있다.상근이는 귀찮기 때문에, 최대한 적은 봉지를 들고 가려고 한다. 예를 들어, 18킬로그램 설탕을 배달해야 할 때, 3킬로그램 봉지 6개를 가져가도 되지만, 5킬로그램 3개와 3킬로그램 1개를 배달하면, 더 적은 개수의 봉지를 배달할 수 있다.상근이가 설탕을 정확하게 N킬로그램 배달해야 할 때, 봉지 몇 개를 가져가면 되는지 그 수를 구하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/2839 문제 풀이 방법: -그리디 알고리즘 사용- 먼저 5로 ..
