알고리즘/탐욕법

문제 설명크기가 N인 배열 A가 있다. 배열에 있는 모든 수는 서로 다르다. 이 배열을 소트할 때, 연속된 두 개의 원소만 교환할 수 있다. 그리고, 교환은 많아봐야 S번 할 수 있다. 이때, 소트한 결과가 사전순으로 가장 뒷서는 것을 출력한다.https://www.acmicpc.net/problem/1083      제한 사항      풀이문제를 요약하면, 내림차순으로 정렬할 때 S번만 이동시켰을 때의 결과를 구해야 한다. 문제를 읽어보면 버블 소트와 유사하다는 것을 알 수 있다.버블 소트는 숫자 N개를 읽어 위치가 정해지지 않은 가장 큰 수의 위치를 정해가는 것이다.하지만 해당 문제에서는 S번이라는 제약이 있기 때문에 가장 큰 수를 올바른 위치로 이동시키지 못할 경우가 생긴다.그렇다면 이때 다음 큰 ..

문제 설명민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1339   ..

문제 설명0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)https://www.acmicpc.net/problem/1080      제한 사항      풀이문제를 요약하면, NxM의 크기의 행렬을 3x3만큼 뒤집는 연산을 통해 원본 행렬에서 결과 행렬로 몇 번의 연산만에 변환할 수 있는지 알아내야 한다. 처음에는 dfs혹은 bfs를 떠올렸다.하지만, 시간이나 메모리에서 문제가 있을 거라 생각했지만 일단 구현해 봤다.구현을 해보니 역시 메모리를 초과하여 에러가 발생했다. 해답은 간단했다.(0,0)에..

문제 설명N개의 강의가 있다. 우리는 모든 강의의 시작하는 시간과 끝나는 시간을 알고 있다. 이때, 우리는 최대한 적은 수의 강의실을 사용하여 모든 강의가 이루어지게 하고 싶다.물론, 한 강의실에서는 동시에 2개 이상의 강의를 진행할 수 없고, 한 강의의 종료시간과 다른 강의의 시작시간이 겹치는 것은 상관없다. 필요한 최소 강의실의 수를 출력하는 프로그램을 작성하시오.https://www.acmicpc.net/problem/1374      제한 사항      풀이문제를 요약하면, N개의 강의를 진행하기 위해 사용해야 하는 최소한의 강의실의 개수를 구해야 한다. 해당 문제와 비슷한 문제로 강의실 예약 문제가 있다.강의실 예약 문제는 하나의 강의실을 최대한 많은 강의에 사용한다면 몇 개의 강의에 사용할 수..

문제 설명웅찬이는 과제가 많다. 하루에 한 과제를 끝낼 수 있는데, 과제마다 마감일이 있으므로 모든 과제를 끝내지 못할 수도 있다. 과제마다 끝냈을 때 얻을 수 있는 점수가 있는데, 마감일이 지난 과제는 점수를 받을 수 없다.웅찬이는 가장 점수를 많이 받을 수 있도록 과제를 수행하고 싶다. 웅찬이를 도와 얻을 수 있는 점수의 최댓값을 구하시오.https://www.acmicpc.net/problem/13904      제한 사항      풀이문제를 요약하면, 주어진 과제들을 하루에 하나씩 적절히 풀어 얻은 점수의 최댓값을 구해야 한다. 해당 문제를 처음에는 DP로 접근했었다.i번째 과제를 j번째 날에 해결했을 때 얻을 수 있는 최대 점수를 기록했다.이렇게 진행하면 i번째 과제를 제외한 j-1번째 날의 최..

문제 설명2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번 방, …, N번 방으로 부른다. 통로는 정확히 N-1개가 발견되었는데, 각각 서로 다른 두 방 사이를 연결시켜 주며 중간에 다른 통로와 이어지는 경우는 없다고 한다. 또한 이 통로들을 이용하여 임의의 두 방 사이를 이동하는 것이 가능하며, 임의의 두 방 사이를 이동할 때 같은 통로를 두 번 이상 지나지 않는 경로는 유일한 것으로 밝혀졌다.새로 발견된 동굴을 조사하기 위해 동굴 탐사 로봇 두 대를 이용하기로 하였다. 두 로봇은 어떤 시점이 되면 각자가 획득한 정보를 공유하기 위해 통신을 해야 한다...

문제 설명오늘은 공주님이 태어난 경사스러운 날이다. 왕은 이 날을 기념하기 위해 늘 꽃이 피어있는 작은 정원을 만들기로 결정했다.총 N개의 꽃이 있는 데, 꽃은 모두 같은 해에 피어서 같은 해에 진다. 하나의 꽃은 피는 날과 지는 날이 정해져 있다. 예를 들어, 5월 8일 피어서 6월 13일 지는 꽃은 5월 8일부터 6월 12일까지는 꽃이 피어 있고, 6월 13일을 포함하여 이후로는 꽃을 볼 수 없다는 의미이다. (올해는 4, 6, 9, 11월은 30일까지 있고, 1, 3, 5, 7, 8, 10, 12월은 31일까지 있으며, 2월은 28일까지만 있다.)이러한 N개의 꽃들 중에서 다음의 두 조건을 만족하는 꽃들을 선택하고 싶다.공주가 가장 좋아하는 계절인 3월 1일부터 11월 30일까지 매일 꽃이 한 가지..

문제 설명백준이는 방 청소를 하면서 필요 없는 전공 서적을 사람들에게 나눠주려고 한다. 나눠줄 책을 모아보니 총 N권이었다. 책이 너무 많기 때문에 백준이는 책을 구분하기 위해 각각 1부터 N까지의 정수 번호를 중복되지 않게 매겨 두었다.조사를 해 보니 책을 원하는 서강대학교 학부생이 총 M명이었다. 백준이는 이 M명에게 신청서에 두 정수 a, b (1 ≤ a ≤ b ≤ N)를 적어 내라고 했다. 그러면 백준이는 책 번호가 a 이상 b 이하인 책 중 남아있는 책 한 권을 골라 그 학생에게 준다. 만약 a번부터 b번까지의 모든 책을 이미 다른 학생에게 주고 없다면 그 학생에게는 책을 주지 않는다.백준이가 책을 줄 수 있는 최대 학생 수를 구하시오.https://www.acmicpc.net/problem/9..

문제 설명한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고기의 수가 줄어들고 있다. 정부에서는 이 문제를 심각하게 생각하여, 물고기를 잡을 수 있는 곳과 여기서 고기잡이 배가 사용할 수 있는 그물의 폭에 제한을 두었다. 물고기는 바다 표면 근처에 살기 때문에, 그물의 높이는 중요하지 않다. 따라서 그물은 길이가 l인 직선으로 생각할 수 있고, 물고기를 잡을 때, 그물은 한 변의 길이가 1 이상 정수인 직사각형 모양으로 치게 된다. 예를 들어, l = 10이라면, 칠 수 있는 그물의 모양은 1×4, 2×3, 3×2, 4×1과 같이 4가지 형태의 직사각형이 된다.고기를 잡을 ..

문제 설명지금 구두 수선공에게는 손님으로부터 주문 받고 제작해야 할 작업이 N개 쌓여있다. 구두 수선공은 하루에 한 작업만 수행할 수 있고, i번째 작업을 완료하는 데 Ti일이 걸린다. 이때 Ti는 정수이고 1 ≤ Ti ≤ 1000이다.i번째 작업을 시작하기 전에 하루가 지연될 때마다 구두 수선공은 보상금 Si센트를 지불해야 한다. 이때 Si는 정수이고 1 ≤ Si ≤ 10000이다. 구두 수선공을 돕기 위해 최저 보상금을 지불하는 작업 순서를 정해야 한다.하루에 2개 이상의 작업을 동시에 수행할 수 없다. 작업 i를 수행하고 있는 경우, 작업 i를 마칠 때 까지 작업 i 외의 다른 작업을 수행할 수 없다.https://www.acmicpc.net/problem/14908      제한 사항      풀..