문제 눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다. 이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어진다.예를 들어 M=5, N=7 인 모눈종이 위에 과 같이 직사각형 3개를 그렸다면, 그 나머지 영역은 와 같이 3개의 분리된 영역으로 나누어지게 된다.와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이 몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오. 출처:https://www.acmicpc.net/pr..
C++
문제N(1≤N≤100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다. 단, 각각의 로프는 한 개씩만 존재한다. 출처:https://www.acmicpc.net..
문제김진영이 듣도 못한 사람의 명단과, 보도 못한 사람의 명단이 주어질 때, 듣도 보도 못한 사람의 명단을 구하는 프로그램을 작성하시오.출처: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; //플로이드 워셜 알고리즘, 모든 정점에 대해 모든 다른 정점에 대한 최단 경로를 구해준다. ..
