백준

문제김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.출처:http://wilybear.tistory.com/admin/entry/post/?id=35&type=post&returnURL=%2Fmanage%2Fposts%2F 문제 풀이:- 문제는 듣도 못한 사람의 명단과 보도 못한 사람의 명단 중 중복되는 사람의 수와 사람의 이름을 출력하는 것이다.- 따라서 듣도 못한 사람의 명단을 set안에 차례대로 넣은 뒤 보도 못한 사람의 명단을 중에 중복된 것을 vector에 넣어서 저장한다.- 사전순을 출력하기 위해 sort를 이용하여 정렬한다.123456789101112131415161718192021222324252627282..

문제KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다.또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다.사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다.첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예를 들면, Knuth-Morris-Pratt이다. 이것을 긴 형태라고 부른다.두 번째로 짧은 형태는 만든 사람의 성의 첫글자만 따서 부르는 것이다. 예를 들면, KMP이다.동혁이는 매일매일 자신이 한 일을 모두 메모장에 적어놓는다. 잠을 자기 전에, 오늘 하루 ..

문제방향 없는 그래프가 주어졌을 때, 연결 요소 (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 > ..