기록공간

그리디 알고리즘 문제이다. 모든 지원자와 비교했을 때 서류심사 성적과 면접시험 성적 중 적어도 하나가 다른 지원자보다 떨어지지 않는 자만 선발한다. 예를 들어 A의 지원자가 B 지원자보다 서류 심사나 면접시험 중 하나라도 더 높다면 선발이 되고, 둘 다 낮다면 절대 선발되지 않는다. 알고리즘은 다음과 같다. 우선 서류 전형 순위를 오름차순으로 정렬한다. 정렬 후 가장 첫번째에 있는 사원은 조건에 무조건 만족하므로 선발한다. 선발된 사원의 면접 순위를 N에 기록하고 다른 지원자들의 면접 점수를 검사한다. 만약 지원자의 면접 순위가 N보다 작은 경우 조건에 만족하므로 선발하고 순위를 다시 N에 기록한다. 코드는 다음과 같다. #include #include using namespace std; struct ..

A가 B보다 작으므로 A를 앞에서 부터 한칸씩 옮기면서 B와 검사한다. 그리고 차이가 최소로 나는 값을 출력하면 된다. 앞이나 뒤에서 추가하는 작업을 할 필요는 없다. 왜냐하면 A에 앞이나 뒤로 B와 알맞은 값을 채워 넣는다고 가정하여, 추가한 위치의 알파벳은 항상 같기 때문이다. 코드는 다음과 같다. #include #include using namespace std; int main() { string A, B; cin >> A >> B; int min = 50; int diffSize = B.size() - A.size(); for (int i = 0; i

최소 값으로 만들기 위해서는 뺄셈 이후에 나오는 모든 더하기 연산에 괄호를 하면된다. 이 말은 즉슨, 최초로 나오는 뺄셈 이후부터 식이 끝날때까지 뺄셈 연산을 해주면 최소 값을 만들 수 있다. #include #include using namespace std; int main() { string input; cin >> input; string temp = ""; bool checkMinus = false; int result = 0; for (int i = 0; i

우선 최대 구성할 수 있는 팀 수를 구한다. 그리고 인턴쉽 프로그램에 참여하는 수를 남은 학생 수와 빼준다. 하지만 그래도 인턴쉽에 참여해야 할 수가 남아 있으면 구성한 팀에 있는 학생에서 채우면 된다. 남은 인턴쉽 참여 인원을 3으로 나누면 인턴쉽을 보내야 할 팀 수가 나오며, 3으로 나누었을때 한 팀이 또 깨지게 되므로 구한 팀 수에서 1을 더한다. 그리고 앞서 구했던 최대 구성 팀수와 빼주면 된다. #include #include using namespace std; int main() { int girl, boy; int intern; cin >> girl >> boy >> intern; int maxTeam = 0; int tGirl = girl; int tBoy = boy; while (tru..

다음 문제를 풀기 위해서는 30의 배수가 되기 위한 규칙을 알아야 한다. 입력받은 숫자들 중 0이 항상 포함되어야 한다. 모든 숫자들의 합이 3의 배수여야 한다. 문자열로 입력을 받고 '0'이 포함되는지와 모든 숫자의 총 합이 3의 배수인지 확인해주기만 하면 된다. 만약 모든 조건을 만족한다면, 숫자들을 내림차순으로 정렬하면 입력받은 수를 이용한 30의 배수인 가장 큰 수가 나온다. #include #include #include using namespace std; bool cmp(char a, char b) { return a > b; } int main() { string str; cin >> str; bool checkZero = false; long long totalNum = 0; for (i..

너비 우선 탐색 (Breadth Firest Search : BFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 모든 간선을 우선적으로 검사하며, 그 중 방문하지 않은 정점을 찾아 순차적으로 방문해 나아간다. 더이상 방문할 수 없을때 까지 반복하며, 인접한 간선을 우선적으로 검사하기 위하여 Queue를 사용한다. 어떻게 진행되는지를 그림을 통해 살펴보자. 1을 방문하면서 인접한 정점인 2, 3, 그리고 7을 큐에 넣어준다. 그리고 큐에 들어간 순서대로 방문하면서 큐가 빌때까지 반복 수행해준다. 이 작업을 모든 정점이 방문되었을때까지 반복해주면 된다. 구현 위 그래프 정보를 바탕으로 깊이 탐색을 구현해보자. #include #include #includ..

깊이 우선 탐색 (Depth First Search : DFS)은 그래프의 모든 정점들을 특정한 순서에 따라 방문하는 알고리즘 중 하나이다. 현재 정점과 인접한 간선들을 검사하다가 방문하지 않은 정점을 발견하면 그 간선을 통해 방문하지 않은 정점으로 이동하는 것이다. 이 과정을 반복하다가 더 이상 방문할 수 있는 정점이 없는 경우 마지막으로 통과한 간선을 통해 뒤로 돌아가서 해당 정점에서 방문할 수 있는 정점을 탐색한다. 그림을 통해 한번 살펴보자. 위 그림의 그래프가 존재하고 한 정점에서 여러 개의 정점으로 이동이 가능할 때 정점의 번호가 더 작은 쪽을 먼저 방문한다고 가정하자. 우선, 정점 1에서 깊이 우선 탐색을 한다고 하자. 먼저, 정점 1에서 연결된 간선들을 통해 연결된 정점을 확인하면 2, 3..

동전 0 문제와 유형이 비슷한 문제이다. 그리디 알고리즘 문제이다. 입력 받은 가격을 1000엔과 빼서 나머지 거스름 돈 값을 구한다. 그리고 500엔부터 차례대로 거스름돈 보다 가치가 적거나 같은 경우 그 가치에 맞는 동전 개수를 구한 후 최종 값에 더해주고, 거스름돈에서 구한 만큼의 가치를 빼주면 된다. 이 작업을 동전 가치가 1엔이 될때까지 혹은 거스름돈이 0엔이 될때까지 반복해주면 된다. 코드는 다음과 같다. #include using namespace std; int main() { int maxMoney = 1000; int coinArr[6] = { 500, 100, 50, 10, 5, 1 }; int change = 0; int changeCoinCount = 0; int price = 0..