이것이 코딩테스트다 with 파이썬 86Page ~ 116Page

1. 그리디 알고리즘

 

보통 코딩 테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

 

그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

예제 3-1 거스름돈

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
  count += n // coin
  n %= coin

print(count)

 

그리디 실전문제 2 - 큰 수의 법칙(반복문을 이용한)

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

data = list(map(int, input().split()))

data.sort()

first = data[n - 1]
second = data[n - 2]
count = 0
temp = 0

while (m):
    count += first

    temp = temp + 1
    if (temp == k):
        temp = 0
        count += second
        m = m - 1

    m = m - 1

print(count)

 

그리디 실전문제 2 - 큰 수의 법칙(수식을 이용한)

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

data = list(map(int, input().split()))

data.sort()

first = data[n - 1]
second = data[n - 2]
count = 0

temp = (m // (k + 1))

count += second * temp
count += first * (m - temp)

print(count)

 

그리디 실전문제 3 - 숫자 카드 게임

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

max = 0

for i in range(n):
    temp = min(map(int, input().split()))
    if temp > max: max = temp

print(max)

 

그리디 실전문제 4 - 1이 될 때까지

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

count = 0

while (1):
    if(n==1): break
    if (n % k == 0):
        n = n // k
        count += 1
        continue
    n = n - 1
    count += 1

print(count)

 

그리디 실전문제 4 - 1이 될 때까지(조금 빠른 답안)

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

count = 0

while (1):
    if (n < k): break
    if (n % k == 0):
        n = n // k
        count += 1
        continue
    temp = n - (k * (n // k))
    n = n - temp
    count += temp

print(count)

 

예제 4-1 상하좌우

n = int(input())

x = 1
y = 1

temp = []
temp = input().split(sep=" ")

for i in temp:
    if (i == 'L' and y > 1):
        y = y - 1
    if (i == 'R' and y < n):
        y = y + 1
    if (i == 'U' and x > 1):
        x = x - 1
    if (i == 'D' and x < n):
        x = x + 1

print(x, y)

 

예제 4-2 시각

n = int(input())

i = j = k = 0
count = 0

for i in range(n + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                count = count + 1

print(count)

 

구현 실전문제 2 - 왕실의 나이트

xy = input()
x = int(ord(xy[0]) - ord('a') + 1)
y = int(xy[1])

offsetX = [-2, -1, 1, 2, -2, -1, 1, 2]
offsetY = [-1, -2, -2, -1, 1, 2, 2, 1]

count = 0

for i in range(len(offsetX)):
    nx = x + offsetX[i]
    ny = y + offsetY[i]
    if (nx >= 1 and nx <= 8 and ny >= 1 and ny <= 8):
        count = count + 1

print(count)

나는 평소에 C/C++을 즐겨쓴다. 그래서 C/C++ 문법에 익숙하다.

오늘 파이썬으로 문제를 풀어보기는 처음이었는데, 확실이 진입장벽은 낮다고 느껴졌다. (sort부분)
하지만 C문법을 쓰다가 파이썬 문법이 적응이 잘 안된다.. 특히 아스키 코드를 정수로 바꾸는 처리는 너무 생소했다.(예전에 배운적 있는데..)
파이썬으로 시험볼거면 더 많은 문제를 풀어보아야겠다.

 

이 코드는 조금 신기했다.

for i in range(n + 1):
    for j in range(60):
        for k in range(60):
            if '3' in str(i) + str(j) + str(k):
                count = count + 1

00:00:00 ~ 23:59:59 까지의 시간 중 3이 들어간 시간을 세는 문제였다.

나는 % 했을 때 3, / 했을 때 3 등 많은 고민을 했는데.. 역시 파이썬은 다르다.

str(i) + str(j) + str(k) 로 하나의 문자열을 만든 후 그 중에 '3' 이 있는지 찾으면 된다.

 

실제 시험에서는 이러한 문법이 많이 필요할 것 같다.