01-2. 그리디 알고리즘 문제풀이

0. 오류 및 헷갈리는 문법🧐

- 오류

어제는 파이썬 idle을, 오늘은 옛날에 수업에 사용했던 파이참 프로그램을 이용해서 코드를 작성했다. 오랜만이라 그런지 파이참이 run되지 않고 오류가 발생했다. 다른 블로그를 보며 해결할 수 있었다. System interpreter 설정 관련 문제였다.

- 문법

n, m = map(int, input().split())

-> split의 결과를 모두 int로 변환해준다.
나는 자꾸 input뒤에 ()을 까먹고 안써서 오류가 발생한다.

-> input().split()의 결과가 문자열 리스트라서 map을 사용할 수 있는 것이다. 이 문장은 문자열 리스트를 map을 이용해 정수로 변환해주는 문장이다.

a, b = map(int, input('숫자 두 개를 입력하세요: ').split(','))

-> 이 경우에는 입력받은 값을 콤마를 기준으로 분리하게 된다.

리스트에 맵 사용하기
map은 리스트의 요소를 지정된 함수로 처리해주는 함수이다. map은 원본 리스트를 변경하지 않고 새 리스트를 생성한다.

실수가 저장된 리스트가 있을 때 이 리스트의 모든 요소를 정수로 변환하려면 어떻게 해야 할까?

a = [1.2, 2.5, 3.7, 4.6]
for i in range(len(a)):
	a[i] = int(a[i])

-> 번거로운 방법이다. for 반복문으로 반복하며 요소를 변환하니 번거롭다. 이 때 map을 사용하면 편리해진다.

a = [1.2, 2.5, 3.7, 4.6]
a = list(map(int, a))

-> 한 줄만으로 변환이 끝났다. map에 int와 list를 넣으면 리스트의 모든 요소를 int를 사용해 변환한다. 그 다음에 list를 사용해 map의 결과를 다시 리스트로 만들어준다.


map에는 list뿐만 아니라 반복 가능한 객체를 넣을 수 있다.

a = list(map(str, range(10)))

-> range로 0-9 숫자를 만들고, str을 이용해 모두 문자열로 변환한다. 출력하면 각 요소가 작은 따옴표로 묶인 것을 볼 수 있다.

// : 나누기 연산 후 소수점 이하의 수를 버리고, 정수 부분의 수만 구함
% : 나누기 연산 후 몫이 아닌 나머지를 구함

---

📝문제1. 모험가 길드 문제

한 마을에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다. 모험가 길드장은 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모험가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다. 길드장은 최대 몇 개의 모험가 그룹을 만들 수 있는지 궁금하다. N명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성해라.

그리디 알고리즘 첫번째 포스팅의 문제 4번으로, 자세한 설명은 생략한다.

- 나의 코드💻

- 정답 코드💻

n = int(input()) #모험가의 수 n
fear = map(int, input().split()) #n명의 공포도의 값
fear.sort() #공포도 오름차순 정렬

group = 0 #총 그룹의 수
person = 0 #현재 그룹 내 모험가의 수

for i in fear: #공포도를 낮은 것부터 하나씩 확인하며
  person += 1 #현재 그룹에 해당 모험가를 포함시키기
  if person >= i: #현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
      group += 1 #총 그룹의 수 증가시키기
      person = 0 #현재 그룹에 포함된 모험가의 수 초기화

print(group) #결과 출력

- 비교 분석📖

해결하지 못했다. 정렬을 해야 한다는 것까지는 생각해냈지만 앞에서부터 공포도를 하나씩 확인하며 '현재 그룹에 포함된 모험가의 수' 가 '현재 확인하고 있는 공포도'보다 크거나 같다면 이를 그룹으로 설정하면 된다는 것을 생각해내지 못했다. 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하는 것임을 제대로 파악하지 못한 것 같다.

---

📝문제2. 곱하기 혹은 더하기

각 자리가 숫자(0-9)로만 이루어진 문자열 S가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성해라. 단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다.

그리디 알고리즘 첫번째 포스팅의 문제 3번으로, 자세한 설명은 생략한다.

- 나의 코드💻

s = list(map(int, input()))

result = s[0]

for i in (1, len(s)-1):
  next = s[i]

  if result <= 1 or next <= 1:
      result += next

  else :
      result *= next

print(result)

- 정답 코드💻

data = input()

#첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])

for i in range(1, len(data)):
  #두 수 중 하나라도 0 혹은 1인 경우, 곱하기보다는 더하기 수행
  num = int(data[i])
  if num <= 1 or result <= 1:
      result += num
  else:
      result *= num

print(result)

- 비교 분석📖

해결하지 못했다. 1이나 0인 경우 곱하기 말고 더하기를 수행해야 한다는 아이디어까지는 도달했는데, 코드 구현 부분에서 잘못된 것 같다.

---

📝문제3. 문자열 뒤집기

다솜이는 0과 1로만 이루어진 문자열 s를 가지고 잇다. 다솜이는 이 문자열 s에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 s에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
문자열 s가 주어졌을 때, 다솜이가 해야 하는 행동의 최소 횟수를 출력해라.

예를 들어 s = 0001100일 때는 다음과 같다.
1. 전체를 뒤집으면 1110011이 된다.
2. 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 두 번 만에 모두 같은 숫자로 만들 수 있다.

하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번만에 모두 같은 숫자로 만들 수 있다.

입력 조건 : 첫째 줄에 0과 1로만 이루어진 문자열 s가 주어진다. s의 길이는 100만보다 작다.
출력 조건 : 첫째 줄에 다솜이가 해야 하는 행동의 최소 횟수를 출력한다.
입력 예시 : 0001100
출력 예시 : 1

- 나의 코드💻

#미완
s = list(map(int, input()))

zero = 0
one = 0

for i in s:
  if i == 0:
      zero += 1
  if i == 1:
      one +=1

for i in len(s)-1:
  if i != s[i+1]:
      if i == 0:
          s[i + 1] = 0
          zero +=1
      else:
          s[i + 1] = 1
          one +=1

- 정답 코드💻

data = input()
count0 = 0 #전부 0으로 바꾸는 경우
count1 = 0 #전부 1으로 바꾸는 경우

#첫 번째 원소 처리
if data[0] == '1': #첫번째 원소가 1이라면 전부 0으로 바꾸는 경우에 포함되어 1 증가
  count0 += 1
else : #첫번째 원소가 0이라면 전부 1로 바꾸는 경우에 포함되어 1 증가
  count1 +=1

#두 번째 원소부터 모든 원소를 확인하며
for i in range(len(data) - 1):
  if data[i] != data[i+1]:
      #다음 수에서 1로 바뀌는 경우
      if data[i+1] == '1':
          count0 += 1
      else:
          count1 +=1

print(min(count0, count1))

- 비교 분석📖

모든 숫자를 전부 같게 만드는 것이 목적이므로 전부 0으로 바꾸는 경우와 전부 1로 바꾸는 경우 중 더 적은 횟수를 가지는 경우를 계산하는 것이 이 문제의 핵심이다.
나는 0과 1의 갯수를 세어 더 적은 개수의 숫자를 바꾸는 식으로 처음에 잘못된 접근을 했다. 그래서 계속 잘못된 시도를 하다 정답 코드를 보고 문제를 이해할 수 있었다.

---

#. 보완할 점🔨

1. 코드를 간결히 구현하려고 노력하기
2. 정답 코드를 빨리 보지 말고 충분한 시간을 가지고 문제를 풀기
3. 문제를 제대로 분석하기

생각보다 많이 어렵고 잘 풀리지 않는다.. 😥 오래 걸리는 거에 비해 내 코드 수준이 낮은 것 같고 문제가 잘 해결되지 않는다. 앞으로 꾸준히 하다보면.. 괜찮아지겠지? 💪

---

문제 출처 : 이것이 코딩 테스트다 with 파이썬(나동빈)