본문 바로가기

Algorithm/Greedy

[백준] 9237 이장님 초대 (Python 파이썬) https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 문제 설명 농부 상근이는 마당에 심기 위한 나무 묘목 n개를 구입했다. 묘목 하나를 심는데 걸리는 시간은 1일이고, 상근이는 각 묘목이 다 자라는데 며칠이 걸리는지 정확하게 알고 있다. 상근이는 마을 이장님을 초대해 자신이 심은 나무를 자랑하려고 한다. 이장님을 실망시키면 안되기 때문에, 모든 나무가 완전히 자란 이후에 이장님을 초대하려고 한다. 즉, 마지막 나무가 다 .. 더보기
[백준] 1339 단어 수학 (Python 파이썬) https://www.acmicpc.net/problem/1339 문제 설명 단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다. 예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다. N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오. 풀이 과정 단어에 등장하는 알파벳을 0~9중의 숫자 중 .. 더보기
[백준] 1080 행렬 (Python 파이썬) 문제 설명 https://www.acmicpc.net/problem/1080 0과 1로 이루어진 행렬 A 와 행렬 B가 주어질 때, 행렬 A를 행렬 B로 전환하는데 필요한 횟수를 구하는 문제이다. 이 때, 1회 전환하다는 것은 3x3의 행렬을 뒤집는 것이다. 예를 들어, 000 111 010 101 111 을 뒤집으면 000 이 된다. 풀이 과정 이 문제는 그리디 알고리즘으로 접근할 수 있다. 변환 전의 행렬을 A, 전환 후의 행렬을 B라고 하자. 현재 A 행렬의 내 위치에서 B 행렬과 일치하지 않는 부분이 있다면 그 부분부터 3x3 범위안의 행렬을 뒤집어주면 된다. 즉, 현재 내 위치만 보고 내 위치의 원소가 같은 위치에서의 B행렬과 일치하지 않는다면 뒤집는 것이기 때문에 그리디 알고리즘이라고 볼 수 .. 더보기
[백준] 2847 게임을 만든 동준이 (Python 파이썬) www.acmicpc.net/problem/2847 2847번: 게임을 만든 동준이 학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어 www.acmicpc.net 문제 설명 첫째 줄에 레벨의 수 N이 주어지고, 다음 줄부터 N+1줄까지 게임 레벨의 난이도가 주어진다. 이전 게임의 레벨은 반드시 다음 게임의 레벨보다 낮아야 하는데, 입력의 상태는 이전 게임이 다음 게임보다 레벨이 높은 경우가 존재한다. 최소한의 횟수로 레벨을 오름차순으로 나타내어야 하며, 레벨 1감소가 1회이다. 풀이 과정 현재 게임이 다음 게임보다 레벨이 낮게 하려면 어떻게 해야할까? 다음 게임의 레벨.. 더보기
[백준] 1449 수리공 항승 (Python 파이썬) www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 문제 설명 수리공이 물이 새는 파이프를 테이프로 수리한다. 테이프는 무한 개 갖고 있으며, 최소한의 테이프를 사용하여 수리해야 한다. 물이 새는곳을 막을 때, 그 위치의 좌우로 0.5만큼씩을 더 막아줘야 물이 새지 않는다. 테이프는 자를 수 없으며, 겹칠수는 있다. 또, 물이 새는 곳의 위치는 자연수이다. 풀이 과정 최소한의 개수로 최대의 이익을 취해야 하는 그리디 알고리즘 문제이다. 먼저 테이.. 더보기
[백준] 1439 뒤집기 (Python 파이썬) www.acmicpc.net/problem/1439 1439번: 뒤집기 다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모 www.acmicpc.net 문제 설명 0과 1로만 이루어진 문자열 S이 주어진다. 이 문자열S을 모두 같은 숫자로 이루어진 문자열로 바꾸려고 하는데, 연속된 하나 이상의 숫자를 뒤집을 수 있다. (0을 1로, 1을 0로) 예를 들어, 1001001이 있으면 1001001 -> 1111001 -> 1111111 과 같이 바꿀 수 있다. 주어진 문자열을 바꾸는데 필요한 최소 횟수를 출력하면 된다. 풀이 과정 문제를 보고, 가장 먼저 떠올랐던.. 더보기
[백준] 4796 캠핑 (Python 파이썬) www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 문제 설명 입력으로 L, P, V를 입력받는다. ( 1 < L < P < V ) 이는 총 V일간의 휴가기간동안 캠핑장을 연속하는 P일 중, L일동안 이용할 수 있다는 뜻이다. 예를 들어, V = 20, P = 8, L = 5 이면, 총 휴가기간 20일 중 캠핑장을 연속하는 8일중 5일간 이용할 수 있다는 뜻이다. 그래서 처음 5일을 이용하고 그 뒤 3일은 이용을 못하고 다시 5일을 이용하고 이런 식으로 전.. 더보기
[백준] 1783 병든 나이트 (Python 파이썬) www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 설명 병든 나이트는 보통 체스의 나이트와는 다르게 아래의 네가지 방법으로만 움직일 수 있다. 2칸 위로, 1칸 오른쪽 1칸 위로, 2칸 오른쪽 1칸 아래로, 2칸 오른쪽 2칸 아래로, 1칸 오른쪽 이 때, 맵의 크기가 N * M으로 주어질 때, 병든 나이프가 방문할 수 있는 칸의 최대 개수를 구하면 된다. (단, 이동 횟수가 4번 이상이라면, 4가지 방법을 한 번씩 모두 사용해야 한다.) 풀이 과정 병든나이트는 이동 시, 무조건 오른쪽으로는 이동을 하게 되어있고, 위 아.. 더보기

티스토리툴바