1. 문제 반 학생들의 체육복이 도난당했다. 도난당한 학생의 번호와 여유분을 가진 학생의 번호가 주어진다. 여유분을 가진 학생이 도난당한 학생에게 체육복을 빌려줄때 체육복을 최대한 나눠주고, 체육수업을 들을 수 있는 최대 학생수를 구하여라 단, 체육복은 자신의 앞뒤 번호한테만 빌려줄 수 있다. 단, 여유분을 가지고 있던 학생이 도난당했을 수 있다. 그러면 빌려주지 않는다. 2. 자원분배 문제: 네트워크 플로 이 문제는 이분 그래프의 최대매칭 문제로 네트워크 플로로 풀 수 있다. 여유분 그룹에서 도난 그룹으로가는 그래프를 그린 후 네트워크 플로우 알고리즘을 사용하면 문제가 해결된다. 단, 여유분을 가지고 있던 학생이 도난당할경우 그래프를 그리지 않는다. 1 2 3 4 5 6 7 8 9 10 11 12 13..

1. 문제 모든 음식의 스코빌 지수를 K 이상으로 만들어야한다. 섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2) 모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다. 섞으면 새로운 음식이 된다. 가장 작은 섞는 횟수를 구하여라 2. 우선순위 큐- 힙 우선순위 큐로 가장 작은것을 골라낼 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace std; int solution(vector scoville, int K) { int answer = 0; priority_queu..

1. 문제 참가자 명단과 완주한 참가자 명단이 주어질때 완주하지 못한 참가자 한명을 찾아라 단, 동명이인이 존재할 수 있다. 2. map map 의 valu값을 동명이인을 가진 사람의 수로 두었다. 초기값을 1로 설정해두고 참가자의 값을 -1 씩하는 것이다. 그러면 0이 아닌 참가자가 정답이 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 #include #include #include #include using namespace std; string solution(vector participant, vector completion) { map dic; std::pair isFail; for(int i = 0; i

1. 문제 일차선의 다리의 길이, 다리가 견딜 수 있는 무게가 주어진다. 트럭이 주어진 순서대로 1초에 다리 길이 1 만큼 움직인다고 할때 최소 걸리는 시간을 구하여라. 2. 자료구조 queue 제한 무게 10인 다리에 트럭이 다음과 같은 순서로 온다고 해보자 7, 4, 5, 6 그럼 다음과 같이 나타낼 수 있다 7 7 0 7 0 4 7 0 4 5 7 0 4 5 0 7 0 4 5 0 6 7 0 4 5 0 6 0 7 0 4 5 0 6 0 0 답: 8 빨간색 이 다리위에 있는 트럭들을 보여준다. 결과로 나오는 배열 7, 0, 4, 5, 0, 6, 0, 0 의 크기가 정답이 됨을 알 수 있다. 그러므로 주어진 순서에 맞게 큐에 집어넣으면서 만약 무게가 초과되면 0인 더미 값을 집어넣고 길이가 초과되면 pop하..

1. 문제 타일이 주어지면 '.'에 함정을 설치한다고 한다. 이때 함정은 상하좌우 4칸에 다른 함정이 없어야된다. 이때 최대 함정을 설치할 수 있는 갯수와 함정의 위치를 포함한 타일을 출력해야한다. 2. 암시적 그래프 타일을 상하좌우를 간선으로 가지는 암시적인 그래프로 표현할 수 있다. 이를 이용해 이분 그래프의 매칭 문제의 dfs코드를 조금 변형하면 최대한 많은 타일에 함정을 매칭할 수 있다. 이분 그래프로 생각하면 다음과 같다. a그룹 = '#' 이 아닌 타일 전체 b그룹 = 상하좌우중간 으로 묶여진 타일들의 집합. 중간을 기준으로 구별할 수 있다. 3. 이분 그래프의 매칭 dfs 모든 타일을 조사하면서 '.' 인 타일에대해 dfs를 실행한다. (a그룹을 하나씩 조사) 주위에 함정이 없어 함정을 설치..

1. 문제 게임판과 장애물의 위치가 주어진다. 이 게임판 위에서 비숍을 서로 죽일수 없도록 최대한 몇개 배열할 수 있는지 계산하는 문제이다. 2. 이분 매칭 비숍은 대각선으로만 이동할 수 있다. 오른쪽으로 가는 대각선과 왼쪽으로 가는 대각선 두개로 비숍의 위치를 나타낼 수 있다. 그러므로 해당 대각선에 비숍이 두개 있을 경우 서로 죽일 수 있다. 이를 이용하여 오른쪽 대각선과 왼쪽대각선을 a그룹 b그룹으로 나누어 이분 할 수 있으며 최대한 많이 비숍을 배열해야하므로 이는 이분 최대 매칭 문제가 된다. 따라서 그래프만 적절히 표현하면 문제는 쉽게 해결된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 ..