코딩 공부하는 코딩류

배추밭에 필요한 배추흰지렁이의 최소 갯수를 구하는 문제 문제의 조건 1. 배추를 해충으로부터 보호하기 위해 배추밭에 배추흰지렁이를 놓을 것이다. 2. 지렁이는 상하좌우에 인접한 배추에게 이동할 수 있다. 3. 배추는 한 번에 많이 몰려있지 않고 밭 전체에 퍼져서 심어져 있다. 아파트 단지처럼 배추도 단지별로 심어져 있음 4. 필요한 지렁이의 최소 갯수 구해서 출력하기 5. 테스트 케이스가 여러 개 주어질 수 있다. 풀이 과정 1. BFS로 배추밭을 탐색하는데 전체 밭을 탐색해야 하기 때문에 2중 for문으로 [0, 0]번째부터 탐색한다. 2. 배추 한 칸을 대상으로 상하좌우에 또 배추가 있는지 검사해서 연결된 배추가 있으면 다음에 방문할 큐에 추가 3. 하나의 배추 단지 검사가 끝나고 나면 정답 카운트를..

진영 주식회사의 신입 사원 선발을 도와주는 문제 문제의 조건 1. 진영 주식회사는 신입 사원 지원자들의 서류 점수와 면접 점수를 매겼다. 2. 진영 주식회사에서 신입 사원을 선발하는 기준은 어떤 지원자가 다른 지원자보다 적어도 한 가지는 더 높은 순위를 받아야 한다는 것이다. 서류 점수라도 더 높던가 면접 점수라도 더 높던가 그렇지 않고 둘 다 다른 지원자보다 낮으면 탈락 3. 테스트 케이스가 여러 개 주어질 때 각 케이스별로 최대한 많이 선발할 수 있는 신입 사원의 수를 구해서 출력하기 풀이 과정 처음엔 서류 점수를 기준으로 오름차순 정렬을 하면 되겠다 까지는 생각을 했는데 그 뒤로 비교 조건을 어떻게 해야할 지 감이 잘 안 와서 힌트를 봤습니다. 과정 1. 지원자들의 점수를 pair 구조체를 이용해서..

전자레인지 버튼을 몇 번 누르면 가장 적은 횟수로 T초를 정확하게 맞출 수 있는지 구하는 문제 문제의 조건 1. 전자레인지에 데울 냉동식품의 조리시간 T가 주어진다. 2. 전자레인지에는 A, B, C 버튼 세 개가 있다. 각 버튼을 누르면 5분, 1분, 10초 타이머가 설정된다. 3. 세 버튼만 이용해서 정확하게 T초를 맞춰야 한다. 4. 세 버튼을 이용한 횟수를 모두 출력하는데 누른 적 없는 버튼은 0 출력하면 된다. 만약 정확하게 T초를 만들 수 없으면 -1만 출력한다. 풀이 과정 전형적인 그리디 문제입니다. 출처에 초등부라고 되 있길래 초딩들도 푸는데 혹시 못 푸면 어쩌지..^^;; 했는데 다행히 통과했습니다. 과정 1. 전자레인지 버튼들에 지정된 시간을 저장할 배열과 각 버튼을 누른 횟수를 저장할..

서로 연결되어 있는 컴퓨터 중에서 바이러스에 감염된 컴퓨터가 몇 개인지 구하는 문제 문제의 조건 1. 컴퓨터의 갯수 N, 서로 연결된 쌍 M개가 주어진다. 2. 1번 컴퓨터는 바이러스에 걸렸는데 이 바이러스는 네트워크를 통해서 전파된다. 3. 1번 컴퓨터부터 시작해서 서로서로 연결되어 있는 컴퓨터들은 연결된 컴퓨터에게서 바이러스가 옮았다. 4. N개의 컴퓨터 중에서 1번 컴퓨터를 빼고 몇 개의 컴퓨터가 바이러스에 걸렸는지 출력 풀이 과정 쉽게 생각하고 시작했는데 생각보다 오래 걸린 문제 ㅠ.ㅠ 아직 dfs/bfs가 완벽하지 않아서 그런가 봅니다. 단순하게 모든 정점을 탐색하는 코드는 쉽게 짤 수 있지만 조금만 응용되어 나오면 방문할 필요가 없는 정점을 어떻게 거르나 고민하면서 시간을 많이 썼습니다. 풀이..

각각 견딜 수 있는 중량이 다른 로프들을 이용해서 들 수 있는 최대 무게를 구하는 문제 문제의 조건 1. N개의 밧줄이 주어진다. 2. 이 밧줄들은 각각 동일한 무게로 나눠서 한 물체를 들게 된다. 100kg 짜리 물체를 4개의 밧줄로 나눠 든다면 25kg씩 나눠 든다. 3. 모든 밧줄을 사용하지 않아도 되고 가장 많은 무게를 들 수 있는 밧줄 몇 개만 골라서 써도 된다. 4. 주어진 밧줄들을 이용해서 가장 많이 들 수 있는 무게를 출력하기 풀이 과정 처음에는 단순하게 밧줄 중 최솟값을 구해서 모든 밧줄의 갯수만큼 곱하면 되겠다고 생각했습니다. 하지만 실패 ㅠ.ㅠ 그러고 다시 생각해 보니까 1kg 짜리만 5개 있다가 100kg 짜리 하나 있으면 100kg 짜리 하나만 썼을 때 가장 많이 들 수 있으니까 ..

거스름돈에 포함되는 잔돈의 갯수가 몇 개인지 구하는 문제 문제의 조건 1. 1원 이상 1000원 미만의 지불해야 하는 금액이 주어진다. 2. 잔돈의 종류는 500, 100, 50, 10, 5, 1원이 있다. 2. 1000원 짜리를 냈을 때 받을 거스름돈에서 각 잔돈을 몇 개를 써서 받으면 최소로 받는지 구해서 출력 풀이 과정 앞서 풀었던 몇 문제와 비슷하게 남은 돈에서 가능한 가장 큰 액수의 잔돈을 먼저 뺀 다음에 그 다음 작은 액수의 잔돈과 비교해서 또 빼고 하는 방식으로 잔돈의 갯수를 구했습니다. #include #include using namespace std; int main(int argc, const char * argv[]) { int N; cin >> N; vector changes{50..

전형적인 BFS 문제로 정사각형 맵에서 연속되어 붙어 있는 집(1)들의 덩어리 갯수와 덩어리 안에 집이 몇개나 들어있는지 구하는 문제 문제의 조건 1. NxN 크기를 가진 정사각형 2차원 배열이 주어진다. 2. 2차원 배열에는 0과 1이 들어있다. 0은 아무것도 없는 곳을 뜻하고 1은 집이 있다는 것을 나타낸다. 3. 1들이 상하좌우로 연속해서 붙어 있으면 같은 단지로 친다. 주어지는 2차원 배열에는 단지가 여러개 있다. 4. 첫 번째 줄에 주어진 2차원 배열에 들어 있는 단지의 갯수를 출력하고 두 번째 줄부터 각 단지 안에 있는 집의 갯수를 오름차순으로 정렬해서 출력하기 풀이 과정 DFS 카테고리에 있긴 했지만 BFS로 풀어도 될 거 같아서 큐를 이용해 BFS로 풀었습니다. 한 타일을 기준으로 상하좌우..

세준이는 +, -와 괄호를 이용해서 식을 만들었는데 실컷 만들고 나서 괄호를 지워버렸다. 근데 세준이는 괄호를 다시 쳐서 이 식의 최솟값을 구하고 싶어짐... 괄호를 적당히 쳤을 때 얻을 수 있는 최솟값을 구하는 문제 문제의 조건 1. +와 -로 구성된 식이 문자열로 주어진다. 2. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 3. 두 개 이상 연속해서 연산자(+, -)가 나타나지 않으며 5자리보다 많이 연속되는 숫자도 없다. 4. 식에서 얻을 수 있는 최솟값을 구해서 출력 풀이 과정 처음 문제를 봤을 땐 풀이가 떠오르지 않아서 10분정도 고민하다가 질문 게시판을 봤습니다. 거기서 -를 만나면 그 이후로 나오는 숫자는 모두 뺀다는 말을 보고 풀이..