python 코딩테스트 - 그리디, 구현

그리디(Greedy Algorithm)

그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 그리디 해법은 단순히 가장 좋은 걸 선택하면 그것이 최적의 해인지 그 정당성을 판단하는 것이 매우 중요.

 

예제)

출처 : 유튜브 동빈나

처음 든 생각

- 큰 놈이 중요한가, 작은 놈이 중요한가

- 일단 정렬을 해야겠다

- 그룹을 많이 만들어야되니깐 일단 작은 놈들부터 최대한 그룹을 짓는 게 유리하겠다

 

나의 답안

n = list(map(int, input().split()))
n.sort()

result = 0 
count = 0
for i in n:
  count+=1
  if count >=i:
    result +=1
    count = 0
print(result)

 

공포도가 1이라면 빠르게 1명만 그룹으로 판단하는 것이 그룹 수를 늘리기 위한 방법이라고 생각했다. 즉, 공포도가 작은 애들을 빠르게 그룹 지어주어 count를 증가시켜주는 것으로 알고리즘을 구성하였다. 그룹에 한 명씩 넣어주면서 그 인원수를 공포도와 비교하여 만약 같아지거나 커졌다면 count를 초기화시키고 result에 1을 더해준다. 정렬을 이미 했기 때문에 그 그룹의 최대 공포도는 i 자기자신이 될 것이다. 그래서 비교를 i와 count수만 해주면 된다.

 

---

 

구현

구현은 머릿 속에 있는 알고리즘을 코드로 바꾸는 과정이다. 즉, 인간의 논리를 코드로 풀어낼 수 있는지 없는지를 확인하는 것이다. 

이러한 유형은 풀이를 떠올리는 것은 쉽지만 코드로 옮기기 어려운 문제를 말한다.

 

- 알고리즘은 간단한데 코드가 지나치게 길어지는 문제

- 실수 연산을 다루고, 특정 소수점 자리까지 출력해야 하는 문제

- 문자열을 특정한 기준에 따라서 끊어 처리해야 하는 문제

- 적절한 라이브러리를 찾아서 사용해야 하는 문제 (ex. itertools의 순열,조합)

 

일반적으로 2차원 공간은 행렬로 다뤄야한다. 이러한 2차원 공간에서의 시뮬레이션 및 완전 탐색 문제는 방향벡터를 활용해야 한다.

dx, dy를 통해 수평, 수직 방향의 basis 벡터를 만들어 좌표의 변화를 계산한다. 

 

출처 : 유튜브 동빈나

처음 든 생각

- 시작점을 [1,1]이라는 리스트로 불러온 다음

- 조건문으로 R, L, U, D인지 구별하여 그 때 마다 점을 움직여야겠다.

- 그리고 조건마다 계산한 좌표값을 N가 비교하도록 하여 유효한지 검사해야겠다.

 

나의 답안

n= int(input())
plans = list(input().split())
dx = [0,0,-1,1]
dy = [-1,1,0,0]

start = [1,1]

def main(n,k):
  for i in k:
    if i == "R":
      start[0]+=dx[0]
      if start[0]<1 or start[0]>n:
        start[0] -= dx[0]
    elif i == "L":
      start[0]+=dx[1]
      if start[0]<1 or start[0]>n:
        start[0] -= dx[1]
    elif i == "D":
      start[1]+=dy[2]
      if start[1]<1 or start[1]>n:
         start[1] -= dy[2]
    elif i == "U":
      start[1]+=dy[3]
      if start[1]<1 or start[1]>n:
        start[1] -= dy[3]
 
  return start[0], start[1]
  
  print(main(n,k))

방향벡터를 설정한 후 조건문을 4개 작성하였다. 조건문마다 먼저 이동시킨 후 그다음 유효한지 검사하여 유효하지 않을 경우 다시 원래값으로 되돌리는 조건문을 추가하였다. 아주 지저분하기 짝이 없다.

 

예시 답안

n= int(input())
plans = list(input().split())
dx = [1,-1,0,0]
dy = [0,0,-1,1]
x,y = 1,1
move_type = ["L","R","U","D"]

for plan in plans:
  nx = x
  ny = y
  for i in range(0,4):
    if plan == move_type[i]:
      nx += dx[i]
      ny += dy[i]
  if nx < 1 or ny<1 or nx >n or nx>n:
    continue
  x,y = nx,ny
print(x,y)

방향 벡터 선언까지는 똑같다. 하지만 값을 굳이 리스트로 하지 않고 그냥 x,y 두개의 변수로 따로 두어 취급을 하는 것이다. 또한 리스트이 인덱스와 방향벡터의 인덱스 순서를 일치시킨다. 예를 들어 i가 2라면 U인지 아닌지 확인한 후 dx,dy의 2번 인덱스를 가진 값을 x,y 좌표에 각각 더해주는 방식이다. 인덱스 순서를 일치시켰기 때문에 추가적으로 몇번째인지 작성해줄 필요가 없어 훨씬 간단하게 작성된다. 또한 유효성 검사도 맨 마지막에 해주어 임의의 nx, ny를 x,y에 할당할 것인지 아닌지 결정해준다.

 

예제)

출처 : 유튜브 동빈나

 

처음 든 생각

- 가능한 방향 벡터가 총 8가지네

- 다 써야 하나...? 다 써야겠지...?

- 8가지를 다 해보고 유효한지 아닌지 판단해야겠다 

 

나의 답안

p = input()
chars=  {"a":1,"b":2, "c" :3, "d":4, "e":5, "f":6, "g":7,"h":8}
x= chars[p[0]]
y = p[1]

w = [[2,1],[2,-1],[-2,1],[-2,-1],[1,2],[-1,2],[1,-2],[-1,-2]]
count= 0
for way in w:
  nx = x+way[0]
  ny = x+way[1]
  if nx<1 or nx>8 or ny<1 or ny>8:
    continue
  count += 1
print(count)

체스판이 x축은 알파벳, y축은 숫자로 되어있으므로 계산의 편의를 위하여 x축을 숫자로 변경시키기 위한 딕셔너리를 만들었다. 그리고 나서 위에서 살펴봤던 예제와 같이 x,y값을 구별하여 계산하였다. 

 

8가지 경우의 수를 담은 방향 벡터를 리스트 형태로 선언하고 반복문을 통하여 유효성을 검사한다. 방향벡터를 리스트로 썼지만 튜플로 써도 무방할 것 같다. 기타 유효성 검사나 카운팅은 위의 예제문제와 매우 흡사하므로 설명은 생략한다.

 

예제)

출처 : 유튜브 동빈나

처음 든 생각

- 알파벳 따로 숫자 따로

- 숫자들은 문자열로 처음에 연산되지만 나중에 정수형으로 바꿔줘야겠다

 

나의 답안

n = input()

str = []
num = 0
for i in n:
  if i.isdigit():
    num += int(i)
  else:
    str+=i

str.sort()
s = "".join(str)

answer = f'{s}{num}'

print(answer)

문자열은 iterable하기 때문에 바로 for 문이 사용가능하다. 알파벳, 숫자를 관리하기 위한 변수를 따로 불러온다. 알파벳은 정렬을 해야되기 때문에 리스트로 선언한다.

isdigit 메서드를 통해 숫자인지 아닌지 판단한 후 맞으면 바로 num에 더해주어 처리를 끝낸다. 아니면 알파벳이기 때문에 리스트에 넣어준다. 그 다음 sort를 통해 알파벳 순서로 정렬하고 join을 사용하여 한개의 단어로 만들어준다. 답 포맷을 일치시키위해 f''를 사용하였다.

---

그리디는 그 상황이 과연 최적의 해를 구하면 되는지 확신을 갖는데 조금 시간이 걸렸다. 그 판단을 조금 더 빠르게 할 수 있다면 체감 난이도가 많이 내려갈 듯.

 

구현은 사실 케이스가 너무 다양하여 연습만이 살 길이라는 생각 밖에 안 든다. 다만, 2차원 공간에서는 방향 벡터라는 개념을 통해 코드의 가독성과 효율성을 동시에 올릴 수 있기 때문에 이 부분은 꼭 기억해야겠다. 또한 문자열에서 isdigit, 리스트이 join와 같은 메서드들에 대해서 기억을 좀 더 확실하게 해야될 것 같다.