문제방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/11724 문제 해결 과정:-dfs를 사용-연결 요소의 개수는 요소 가운데 요소 내 모든 노드쌍에 대해 경로가 존재하는 부그래프 s를 g의 연결요소(conected component)라고 한다- 모든 정점에 대해서 dfs를 돌리고 새로운 그래프가 발견 될때마다 카운트를 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include#includeusing namespace std; int map[1002][100..
알고리즘
문제과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. 는 을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/problem/2667 문제 해결 과정: - 입력이 한줄씩 주어지므로 string으로 받아서 하나씩 나누어 map을 만든다- dfs를 사용하여 단지 번호를 붙인다.- map을 만..
문제 알파벳으로만 이루어진 단어를 입력받아, 그 길이를 출력하는 프로그램을 작성하시오.출처: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() {..
문제 정수 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..
