[Algorithm 개념] Greedy Algorithm

Greedy 알고리즘 ?

1. 현재 상황에서 지금 당장 좋은 것만 고르는 방법.

2. 문제를 풀기위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구

3. 정당성 분석이 중요. 단순히 가장 좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토.

 

문제 . 1이 될때까지

n , k = map(int, input().split()) # N = 25, K = 3
res = 0

while True: #시간 복잡도 : O(log(n))
    target = (n // k) * k 
    res += (n - target) 
    n = target 

    if n < k : # 더이상 나눌 수 없으면 종료
        break

    res += 1 # 횟수 count 
    n //= k

# 마지막으로 남은 수에 대해 1씩 빼기
res += (n-1)
print(res)

 

구현(implementation) ?

구현이란? 머리속에 있는 알고리즘을 소스코드로 바꾸는 과정. 하지만, 풀이는 떠올리기는 쉽지만 소스코드로 옮기기 어려운 문제를 지칭.

1. 일반적으로 알고리즘 문제에서의 2차원 공간은 행렬의 의미로 사용. e.g. 어떠한 캐릭터가 어느 방향으로 몇칸 움직임..

2. 시뮬레이션 및 완전 탐색 문제에서는 2차원 공간에서의 방향 벡터가 자주 활용됨.

 

문제 1. 상하좌우

N = int(input())
A = map(str, input().split())
x, y = 1, 1

# L,R,U,D에 따른 이동 방향
move_d = ['L', 'R', 'U', 'D']
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

for direc in A:
    for i in range(len(move_d)):
        if direc == move_d[i]:
            nx = x + dx[i]
            ny = y + dy[i]
    if nx < 1 or ny < 1 or nx > N or ny > N : #예외처리(공간 벗어나는 움직임 제외)
        continue
    
    x, y = nx, ny
    
print(x, y)

 

문제 2. 왕실의 나이트

input_pos = input()
row = int(input_pos[1]) #c4
col = int(ord(input_pos[0])) - int(ord('a')) + 1

steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2,1), (1,2), (-1,2), (-2,1)]

#8가지 방향에 대해 각 위치로 이동이 가능한지 확인
cnt = 0
for step in steps:
    #이동하고자 하는 위치 확인
    next_row = row + step[0]
    next_col = col + step[1]
    # 해당 위치로 이동이 가능하면 cnt 증가
    if next_col >= 1 and next_row <= 8 and next_row >= 1 and next_col <= 8:
        cnt+=1
print(cnt)