그리디 알고리즘에 대해 포스팅한 적이 있었다. 간략하게 개념을 정리해놓은 글이니 필요하다면 읽고오는 것이 좋다.
사실 그리디 알고리즘은 가장 쉬운 알고리즘중에 하나이기 때문에 개념을 이해하는 것도 어렵지 않다. 그러나 항상 활용하여 문제를 풀기는 어렵다. 그래도 다른 알고리즘에 비해 문제들의 난이도는 쉬운 편인듯하다.
각설하고, 그리디 알고리즘문제들을 몇문제 풀어보자.
백준 1343번 폴리오미노
문제
민식이는 다음과 같은 폴리오미노 2개를 무한개만큼 가지고 있다. AAAA와 BB
이제 ‘.’와 ‘X’로 이루어진 보드판이 주어졌을 때, 민식이는 겹침없이 ‘X’를 모두 폴리오미노로 덮으려고 한다. 이때, ‘.’는 폴리오미노로 덮으면 안 된다.
폴리오미노로 모두 덮은 보드판을 출력하는 프로그램을 작성하시오.
입력
첫째 줄에 보드판이 주어진다. 보드판의 크기는 최대 500이다.
출력
첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다.
예제 입력 1 복사
XXXXXX
예제 출력 1 복사
AAAABB
문제는 간단하다. 하지만 나는 처음에 너무 어렵게 접근했다.
소스코드
a = 0
li = list(map(str, input()))
li.append('.')
ans = []
for i in li:
if i == 'X':
a += 1
if a == 4:
ans.append('AAAA')
a = 0
else:
if a % 2 != 0:
ans = [-1]
elif a == 2:
ans.append('BB')
a = 0
ans.append('.')
ans.pop(-1)
for i in ans:
print(i, end='')이렇게 입력값을 리스트에 저장하고 하나씩 반복문으로 돌려가며 조건을 붙이며 풀이했고 이마저도 ‘틀렸습니다.’를 받았다..
고민하던중 한참후에야 raplace함수가 생각났다.
a = input()
a = a.replace("XXXX", "AAAA")
a = a.replace("XX", "BB")
if a.count('X') >= 1:
a = -1
print(a)replace 함수를 이용하여 풀이한 코드이다. 반복문이나 추가적인 배열은 만들지도 않고 간단하게 풀이할 수 있었다. 여러 함수를 적절히 사용하는 것의 중요성을 깨닫게 됐다.
백준 1439번 뒤집기
문제
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,
- 전체를 뒤집으면 1110011이 된다.
- 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
입력
첫째 줄에 문자열 S가 주어진다. S의 길이는 100만보다 작다.
출력
첫째 줄에 다솜이가 해야하는 행동의 최소 횟수를 출력한다.
예제 입력 1 복사
0001100
예제 출력 1 복사
1
이 문제도 간단하다. 바로 제출한 소스코드를 보면
소스코드
s = input()
a = []
for i in range(len(s) - 1):
if s[i + 1] != s[i]:
a.append(s[i])
a.append(s[-1])
print(min(a.count('1'), a.count('0')))나는 우선 문자열을 배열에 저장하고 반복문을 이용해 연속하여 중복되는 값을 제거하였다. 이 과정에서 배열의 마지막 값은 반복문에 들어가면 인덱스 범위를 벗어나기 때문에 반복문에서는 제외하고 이후에 추가해주었다. (어차피 이전까지의 값으로 중복을 제거하고 마지막 수는 한개이기 때문에 별 문제없다.)그리고 ‘1’과 ‘0’중에 배열에 적게 저장된 값을 찾아 뒤집었다.
아주 쉬운 문제들을 풀어보았는데 간단한 입출력 문제와 푸는 방식이 다르지 않다. 그리디 알고리즘의 개념인 가장 적은 횟수로 행동하는 등의 풀이를 요구하기 때문에 그리디 알고리즘으로 분류되는 것 같다. 난이도는 쉽지만 코딩테스트 출제 빈도나 실제 활용도가 높기때문에 연습을 해보면 좋다고 생각한다.