[이코테 2021] 2. 그리디 & 구현

https://www.youtube.com/watch?v=2zjoKjt97vQ

---

1. 그리디

(1) 그리디 알고리즘

- 탐욕법: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요

- 정당성 분석 => 최적의 해를 구할 수 있는가?

그리디 = 매 순간 단순히 가장 큰 값을 고르는 방식

- 최적의 해를 보장할 수 없을 때가 많음

But 그리디 알고리즘 문제의 경우 그리디 알고리즘의 결과 = 최적의 해가 되는 경우가 많음

 

(2) 그리디 알고리즘 문제

1번: 거스름 돈

- 해결 아이디어: 가장 큰 화폐 단위부터 거슬러주기

- 정당성 분석: 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유는?

=> 큰 단위가 항상 작은 단위의 배수이기 때문에

- 소스코드(Python)

N = 1260
coin = [500, 100, 50, 10]
count = 0

for i in coin:
  count += N//i
  N %= i

print(count)

- 시간 복잡도 분석: 화폐의 총 종류 K -> 시간 복잡도 O(K)

---

2번: 1이 될 때까지

2번: 문제 조건

- 문제 풀이

1. 강의 풀이

- 해결 아이디어: N에 대해 최대한 많이 나누기

- 소스코드(Python)

2번: 시간 복잡도 최소화 코드

- 정당성 분석: N이 아무리 큰 수라도 K로 계속 나누면 기하급수적으로 빠르게 줄일 수 있음

- 시간 복잡도 분석: 무조건 N을 나누는 연산이 있으므로 => O(logN)

 

2. 내 풀이

N, K = map(int, input().split())
count = 0

while N > 1:
  if N % K == 0:
    N //= K
    count += 1
  else:
    N -= 1
    count += 1

print(count)

---

3번: 곱하기 혹은 더하기

3번: 문제 조건

- 문제 풀이

1. 강의 풀이

- 해결 아이디어: + 보다는 x 가 더 값을 크게, 다만 두 수 중에서 하나라도 0 or 1인 경우 곱하기보다는 더하기

=> 두 수 중에 하나라도 1 이하인 경우 +, 두 수가 모두 2 이상인 경우 x

- 소스코드(Python)

 

2. 내 풀이

- 해결 아이디어: 0, 1을 제외하면 다 곱하기

- 정당성 분석: 더하기보다는 곱하기가 증가폭이 훨씬 크기 때문에

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

result = 0

for i in range(len(N)):
  if result <= 1 or N[i] <= 1:
    result += N[i]
    continue
  result *= N[i]

print(result)

---

4번: 모험가 길드

4번: 문제 설명

4번: 문제 조건

- 문제 풀이

1. 강의 풀이

- 해결 아이디어: 오름차순 정렬 + 현재 그룹 포함 모험가 수와 공포도 비교

- 소스코드(Python)

2. 내 풀이

- 해결 아이디어: 공포도가 낮은 사람부터 그룹 만들기

N = int(input())
L = list(map(int, input().split()))

L.sort() # 오름차순 정렬
group = 0 # 모험가 수
count = 0 # 그룹 수

for i in L:
  group += 1 
  if group >= i:
    count += 1
    group = 0 # 모험가 수 초기화
    
print(count)

---

2. 구현(implementation)

(1) 구현

- 머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정

- 구현 유형 문제: 풀이를 떠올리는 것은 쉽지만 소스코드로 옮기는 어려운 문제

- 예시

  알고리즘 간단

  코드 길이 길어지는 문제

  실수 연산, 특정 소수점 자리까지 출력

  문자열을 특정한 기준에 따라 끊어 처리

  적절한 라이브러리를 찾아서 사용

 

(2) 행렬

- 2차원 공간 = 행렬(Matrix)

- 방향 벡터: 특정 위치에서 이동할 수 있는 경우

(3) 구현 문제

1번: 상하좌우 문제 설명

1번: 문제 조건

- 문제 풀이

1. 강의 풀이

- 해결 아이디어: 일련의 명령에 따라 개체를 차례대로 이동시킨다는 점에서 시뮬레이션 유형으로 분류 가능

=> 시뮬레이션 유형, 구현 유형, 완전 탐색 유형은 유사한 점이 많음

- 풀이 코드

---

2번: 시각

2번: 문제 조건

- 문제 풀이

1. 강의 풀이

- 해결 아이디어: 완전 탐색(Brtue Forcing) 문제

- 단순히 1씩 증가하면서 3이 하나라도 포함되어 있는지 확인

- 가능한 경우의 수를 모두 검사해보는 탐색

- 파이썬 = 1초 당 2천만번 연산 가능

- 소스코드(Python)

2. 내 풀이

N = int(input())
count = 0

for i in range(0, N+1):
  for j in range(0, 60):
    for k in range(0, 60):
      time = str(i) + ":" + str(j) + ":" + str(k)
      if '3' in time:
        count += 1

print(count)

---

3번: 왕실의 나이트

3번: 문제 조건

- 문제 풀이

1. 강의 풀이

- 요구사항대로 충실히 구현하면 되는 문제

-  소스 코드

2. 내 풀이

- 문제 해결 아이디어: dx, dy 쓰기

N = list(input())

dx = [-1, -1, 1, 1, -2, -2, 2, 2]
dy = [-2, 2, 2, -2, -1, 1, -1, 1]

count = 0

for i in range(len(dx)):
  x, y = int(N[1]), ord(N[0])%97+1
  nx = x + dx[i]
  ny = y + dy[i]
  if nx < 1 or ny < 1:
    continue
  count += 1
  
print(count)

---

4번: 문자열 재정렬

4번: 문제 조건

- 문제 풀이

1.  강의 풀이

- 요구사항대로 충실히 구현하면 되는 문제

- 문자열이 입력되었을 때 문자를 하나씩 확인

=> 숫자인 경우 따로 합계 계산

=> 알파벳인 경우 별도의 리스트에 저장

- 리스트에 저장된 알파벳을 정렬해 출력하고, 합계를 뒤에 붙여 출력

2. 내 풀이

import string

N = input()
M = list(N)

M.sort()
print(M)

hap = 0
for i in M:
  if i.isalpha():
    continue
  else:
    M.remove(i)
    hap += int(i)

print(''.join(M)+str(hap))