알고리즘 회고(코딩테스트) -2

🔥이 시리즈는 한빛 미디어-'이것이 코딩 테스트다'의 모든 문제를 풀고, 회고합니다!

생각보다 짧은 실력에 깜짝 놀랄수도 있습니다..

이제 발등에 불떨어진 막학기 대학생이 뭐라도 해보는 중 입니다. 최대한 하루에 하나씩 올리는 것을 목표로 하고 있습니다.

1. 그리디 알고리즘

지난 회고 - 1 에서 그리디 알고리즘의 '큰 수의 법칙'문제와 '숫자 카드 게임'을 풀어봤습니다.

✏️ 1이 될 때까지

어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두 번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.

입력

1. 첫째 줄에 N과 K가 공백으로 구분되며 각각 자연수로 주어진다. 이때 입력으로 주어지는 N은 항상 K보다 크거나 같다.

출력

첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력한다.

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

result = 0

while True:
    if n % m == 0 :
        n /= m
        result += 1
    else:
        n -= 1
        result += 1

    if n == 1: 
        break

print(result)

알고리즘을 떠오르는데 오랜시간이 걸리지 않았고 구현 역시 쉬웠던 문제였다.

✨ 핵심 부분

if n % m == 0 :
        n /= m
        result += 1
    else:
        n -= 1
        result += 1

1. n % m == 0 으로 나눗셈 가능여부를 찾는다.
2. 나눗셈이 가능하다면 나눗셈을 진행하고, 그렇지 않다면 n= n-1 해준다.
3. 만약 n값이 1이면 반복문을 탈출하고 결과를 출력한다.

2. 구현

구현이란 '머릿속에 있는 알고리즘을 소스코드로 바꾸는 과정'이다.

✏️ 상하좌우

여행가 A는 N x N 크기의 정사각형 공간위에 있으며 가장 왼쪽 위 좌표를 (1,1)로 한다. 계획서에는 하나의 줄에 띄어쓰기로 L,R,U,D 중 하나의 문자가 반복적으로 적혀있다.

• L: 왼쪽으로 한 칸 이동
• R: 오른쪽으로 한 칸 이동
• U: 위쪽으로 한 칸 이동
• D: 아래쪽으로 한 칸 이동

이때 여행가 A가 N x N크기의 정사각형 공간을 벗어나는 움직임은 무시됩니다. 예로 (1,1)에서 U 이동은 무시됩니다.

입력

1. 첫째 줄에 공간의 크기를 나타내는 N이 주어진다.
2. 여행가 A가 이동할 계획서 내용이 주어진다.

출력

첫 째줄에 여행가 A가 최종적으로 도착할 지점의 좌표 (X,Y)를 공백으로 출력한다.

n = int(input())

m = input().split()
x = 1
y = 1

for i in range(len(m)):
    if m[i] == "R" and y < n:
        y +=1
    elif m[i] == "L" and y > 1:
        y -= 1
    elif m[i] == "U" and x > 1:
        x -= 1
    elif m[i] == "D" and x < n:
        x += 1

print (x, y)      

이 문제에 대해서 생각해 보던 중에 '굳이 2차원 배열을 구현해야 하나?' 라는 생각이 들었다. 가상의 좌표값 x,y 를 설정하고 R,L 연산에서는 x값을 조정하고, U,D 연산에서는 y값을 조정하되, 정사각형 공간에 대한 제한을 줄 수 있다면 2차원 배열을 구현하지 않아도 된다고 생각하였습니다.

✨ 핵심 부분

for i in range(len(m)):
    if m[i] == "R" and y < n:
        y +=1
    elif m[i] == "L" and y > 1:
        y -= 1
    elif m[i] == "U" and x > 1:
        x -= 1
    elif m[i] == "D" and x < n:
        x += 1

1. R은 y < n 일 경우에 실행가능하다.
2. L은 y > 1 일 경우에 실행가능하다.
3. U는 x > 1 일 경우에 실행가능하다.
4. D는 x < n 일 경우에 실행가능하다.

다음과 같은 방법으로 배열구현없이 문제를 풀었습니다.

✏️ 시각

정수 N이 입력되면 00시 00분 00초 부터 N시 59분 59초까지의 시각 중에서 3이 하나라도 초함되는 모든 경우의 수를 구하는 프로그램을 작성합니다.

입력

첫째 줄에 정수 N이 입력된다.

출력

00시 00분 00초 부터 N시 59분 59초 까지의 시각중 3이 하나라도 포함된 모든 경우의 수를 출력한다.

h = int(input())

count = 0 

for i in range(h+1):
    for m in range(60):
        for s in range(60):
            if '3' in str(i) + str(m) + str(s):
                count += 1

print(count)

문제 자체의 난이도는 매우 낮았지만 구현 과정에서 어떠한 수로 3을 인식하는가에 대해 구현하는데 오래걸렸던 문제이다. 구글링을 통해서 해결하였다.

다음 포스트에서는 남은 구현문제를 풀어볼 것이다.