삼성 알고리즘 기출문제들을 몇 개 풀어보았다. 이전에 풀었을 때는 손도 못댔던 문제들을 이번엔 혼자의 힘으로 모두 풀었다!! 가끔 느끼는 일인데 과거에 몰랐던 것도 쿨하게 넘어갔다가 다시 돌아올 때 급격히 이해가 되는 경우가 있다. 이럴때마다 성장했다는 느낌이 너무 좋다.

어제 DP 문제들을 복습하고 아래 문제들을 풀었다. 하루종일 알고리즘만 풀어서 머리가 아프지만 해결했을때의 도파민은 사람을 미치게한다.. 그럼 내일도 화이팅!

BOJ. 13458 시험 감독

N = int(input())
lst = list(map(int, input().split()))
B, C = map(int, input().split())

ans = N         # 총감독관은 시험장의 개수만큼..
for n in lst:
    if n-B>0:   # 총감독관이 감독한 인원외의 인원을 부감독관에게 할당
        ans += (n-B+C-1)//C
print(ans)

BOJ. 14503 로봇 청소기

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

r, c, d = map(int, input().split())

graph = [list(map(int, input().split())) for _ in range(n)]

dy = [-1, 0, 1, 0]
dx = [0, 1, 0, -1]
flag = False
count = 0

def is_surround_clean(y, x):
    for k in range(4):
        ny = y + dy[k]
        nx = x + dx[k]

        if 0 <= ny < n and 0 <= nx < m:
            if graph[ny][nx] == 0:
                return False

    return True

def dfs(y, x, d):
    global flag
    global count

    if flag:
        return

    if graph[y][x] == 0:
        graph[y][x] = 2
        count += 1

    if is_surround_clean(y, x):

        ny = y + dy[(d + 2) % 4]
        nx = x + dx[(d + 2) % 4]
        if 0 <= ny < n and 0 <= nx < m:
            if graph[ny][nx] == 0 or graph[ny][nx] == 2:
                dfs(ny, nx, d)
            else:
                flag = True
                return
    else:
        ny = y + dy[(d-1+4) % 4]
        nx = x + dx[(d-1+4) % 4]

        if 0 <= ny < n and 0 <= nx < m:
            if graph[ny][nx] == 0:
                dfs(ny, nx, (d-1+4) % 4)
            else:
                dfs(y, x, (d-1+4) % 4)

dfs(r, c, d)

print(count)

과거엔 못풀었는데 혼자서.. 그것도 아주 빠른시간에 풀었다... 왜 되는거지,,?

BOJ. 14888 연산자 끼워넣기

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
a = list(map(int, input().split()))
add, sub, mul, div = map(int, input().split())

_max = -1_000_000_001
_min = 1_000_000_001

def recur(idx, value, add, sub, mul, div):
    global _max, _min

    if idx == n:
        _max = max(value, _max)
        _min = min(value, _min)
        return

    if add > 0:
        recur(idx+1, value + a[idx], add-1, sub, mul, div)
    if sub > 0:
        recur(idx+1, value - a[idx], add, sub-1, mul, div)
    if mul > 0:
        recur(idx+1, value * a[idx], add, sub, mul-1, div)
    if div > 0:
        result = int(value / a[idx])
        recur(idx+1, result, add, sub, mul, div-1)

recur(1, a[0], add, sub, mul, div)

print(_max)
print(_min)

BOJ. 14889 스타트와 링크

def dfs(n, alst, blst):
    global ans

    if n==N:
        if len(alst)==len(blst): 
            asm = bsm = 0
            for i in range(M):
                for j in range(M):
                    asm += arr[alst[i]][alst[j]]
                    bsm += arr[blst[i]][blst[j]]
            ans = min(ans, abs(asm-bsm))
        return

    dfs(n+1, alst+[n], blst)
    dfs(n+1, alst, blst+[n])

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

M = N//2
ans = 100*M*M
dfs(0, [], [])
print(ans)

BOJ. 14891 톱니바퀴

# 맞닿아 있는 부분이 다르면 회전
# N극 : 0, S극 : 1
# 방향 1 : 시계, -1 : 반시계
n = 4
wheels = [list(int(i) for i in input()) for _ in range(n)]

k = int(input())
rotates = [list(map(int, input().split())) for _ in range(k)]
for rotate in rotates:
    rotate[0] -= 1

def rotate(idx, dr):
    wheel = wheels[idx]
    if dr == 1:
        last = wheel.pop()
        wheel.insert(0, last)
    else:
        first = wheel.pop(0)
        wheel.append(first)

def check_pole(idx):
    left_pole = []
    left_idx = idx
    while left_idx > 0:
        cur_wheel = wheels[left_idx]
        left_wheel = wheels[left_idx-1]
        left_pole.append(cur_wheel[6] != left_wheel[2])
        left_idx -= 1

    right_pole = []
    right_idx = idx
    while right_idx < n-1:
        cur_wheel = wheels[right_idx]
        right_wheel = wheels[right_idx+1]
        right_pole.append(cur_wheel[2] != right_wheel[6])
        right_idx += 1

    return left_pole, right_pole

def sum_of_score():
    _sum = 0
    for i in range(n):
        pole = wheels[i][0]

        if pole == 1:
            _sum += 1 << i

    return _sum

for i in range(k):
    idx, dr = rotates[i]

    left_pole, right_pole = check_pole(idx)

    for j in range(len(left_pole)):
        if not left_pole[j]:
            break

        if j % 2 == 0:
            rotate(idx-1-j, -dr)
        else:
            rotate(idx-1-j, dr)

    for j in range(len(right_pole)):
        if not right_pole[j]:
            break

        if j % 2 == 1:
            rotate(idx+1+j, dr)
        else:
            rotate(idx+1+j, -dr)

    rotate(idx, dr)

print(sum_of_score())

지인짜 오랜시간동안 혼자 풀었다.. 결국 해냈다..!
다른 사람들의 풀이를 보니 복잡하게 풀었지만 나만의 논리를 가지고 코드로 구현한 것에서 만족한다. 다음에 풀 때는 다른 사람들의 풀이법을 확인했으니 그 방법으로 다시 풀어보아야겠다.

BOJ. 15686 치킨 배달

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

graph = [list(map(int, input().split())) for _ in range(n)]

chs = []
homes = []

for i in range(n):
    for j in range(n):
        if graph[i][j] == 1:
            homes.append((i, j))
        if graph[i][j] == 2:
            chs.append((i, j))

_min = 10000000
def recur(idx, ch):
    global _min

    if idx == len(chs):
        if len(ch) == m:
            total_min_dist = 0
            for home in homes:
                min_dist = 10000000
                for c in ch:
                    min_dist = min(abs(c[0] - home[0]) + abs(c[1] - home[1]), min_dist)
                total_min_dist += min_dist

            _min = min(_min, total_min_dist)
        return

    recur(idx+1, ch + [chs[idx]])
    recur(idx+1, ch)


ch = []
recur(0, ch)

print(_min)