코딩뚠뚠

풀이일시 : 2020-08-23 ​ 문제 : 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다. 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다. 각 직원은 최대 두 개의 일을 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다. 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오. ​ 입력: 첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000) 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다. ex) 5 5 2 1 2 2 1 2 2 1 2 2 4 5 ​ 출력: 첫째 줄에 ..

풀이일시 : 2020-08-23 ​ 문제 : 농부 존은 소 축사를 완성하였다. 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다. 첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다. 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다. 농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오. 축사의 번호는 1부터 M까지 매겨져 있다. 입력: 첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200) 둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다. i번째 소가 들어가기 원하는 축사의 수 S..

풀이일시 : 2020-08-19 ​ 문제 : 월드 나라는 모든 도로가 일방통행인 도로이고, 싸이클이 없다. 그런데 어떤 무수히 많은 사람들이 월드 나라의 지도를 그리기 위해서, 어떤 시작 도시로부터 도착 도시까지 출발을 하여 가능한 모든 경로를 탐색한다고 한다. 이 지도를 그리는 사람들은 사이가 너무 좋아서 지도를 그리는 일을 다 마치고 도착 도시에서 모두 다 만나기로 하였다. 그렇다고 하였을 때 이들이 만나는 시간은 출발 도시로부터 출발한 후 최소 몇 시간 후에 만날 수 있는가? 즉, 마지막에 도착하는 사람까지 도착을 하는 시간을 의미한다. 어떤 사람은 이 시간에 만나기 위하여 1분도 쉬지 않고 달려야 한다. 이런 사람들이 지나는 도로의 수를 카운트 하여라. 출발 도시는 들어오는 도로가 0개이고, 도착..

풀이일시 : 2020-08-19 ​ 문제 : 숌 회사에서 이번에 새로운 전략 시뮬레이션 게임 세준 크래프트를 개발하기로 하였다. 핵심적인 부분은 개발이 끝난 상태고, 종족별 균형과 전체 게임 시간 등을 조절하는 부분만 남아 있었다. 게임 플레이에 들어가는 시간은 상황에 따라 다를 수 있기 때문에, 모든 건물을 짓는데 걸리는 최소의 시간을 이용하여 근사하기로 하였다. 물론, 어떤 건물을 짓기 위해서 다른 건물을 먼저 지어야 할 수도 있기 때문에 문제가 단순하지만은 않을 수도 있다. 예를 들면 스타크래프트에서 벙커를 짓기 위해서는 배럭을 먼저 지어야 하기 때문에, 배럭을 먼저 지은 뒤 벙커를 지어야 한다. 여러 개의 건물을 동시에 지을 수 있다. 편의상 자원은 무한히 많이 가지고 있고, 건물을 짓는 명령을 ..

#include #include #include using namespace std; int n; vector v; int getSum(string a) { int n = a.length(); int sum = 0; for (int i = 0; i < n; i++) { if (a[i] - '0' = 0) { //string 중 숫자만 구분해서 더한다. sum += a[i] - '0'; } } return sum; } bool compare(string a, string b) { if (a.length() != b.length()) //첫번째 고려사항 길이가 짧은것이 먼저온다. return a.length() < b.length(); else { //두번째 고려사항 길이가 같다면 합이 작은게 먼저온다. i..

풀이 일시 : 2020-08-04 ​ 문제 : 알파벳 소문자로 이루어진 N개의 단어가 들어오면 아래와 같은 조건에 따라 정렬하는 프로그램을 작성하시오. 1. 길이가 짧은 것부터 2. 길이가 같으면 사전 순으로 ​ 입력: 첫째 줄에 단어의 개수 N이 주어진다. (1≤N≤20,000) 둘째 줄부터 N개의 줄에 걸쳐 알파벳 소문자로 이루어진 단어가 한 줄에 하나씩 주어진다. 주어지는 문자열의 길이는 50을 넘지 않는다. ex) 13 but i wont hesitate no more no more it cannot wait im yours ​ 출력: 조건에 따라 정렬하여 단어들을 출력한다. 단, 같은 단어가 여러 번 입력된 경우에는 한 번씩만 출력한다. ex) i im it no but more wait won..

풀이 일시 : 2020-07-30 ​ 문제 : 동규는 세수를 하다가 정렬이 하고싶어졌다. 숫자 세 개를 생각한 뒤에, 이를 오름차순으로 정렬하고 싶어 졌다. 숫자 세 개가 주어졌을 때, 가장 작은 수, 그 다음 수, 가장 큰 수를 출력하는 프로그램을 작성하시오. ​ 입력 : 숫자 세 개가 주어진다. 이 숫자는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 이 숫자는 모두 다르다. ex) 3 1 2 ​ 출력 : 제일 작은 수, 그 다음 수, 제일 큰 수를 차례대로 출력한다. ex) 1 2 3 ​ 풀이 : 입력을 받은 뒤 알고있는 sort 알고리즘으로 sort 하여 print 한다. 크기가 3으로 정해져있기때문에 a[3]을 잡아놓고 시작한다. #include int main() { int a[3]..

풀이일시 : 2020-08-31 ​ 분할정복 : divide and conquer 로 성질이 똑같은 여러개의 부분문제로 문제를 나누어 해결하는 방법이다. 1. 문제 사례를 하나 이상의 작은 사례로 분할한다. 2. 작은 사례들을 각각 정복(conquer)한다. 재귀를 이용 3. 작은 사례에 대한 해답을 통합하여 원래 사례의 답을 구한다. 장점 - 문제를 나눠 풀어 어려운 문제를 해결할 수 있다. 병렬적으로 문제를 해결. 단점 - 함수를 재귀적으로 호출하여 오버헤드가 발생, 스택 오버플루우가 발생하거나 과도한 메모리사용 가능성 쓰임 - 이분검색, 최대값찾기 및 여러 알고리즘문제풀이에 쓰인다. 아래는 분할&정복 알고리즘의 대략적인 묘사도이다. ​ 문제와 풀이 : dbstndi6316.tistory.com/10..