[알고리즘] 구현 기초 (2)

동빈나쌤 강의 참고: https://youtu.be/2zjoKjt97vQ

 

✔️ 구현문제 풀어보기 2

 

출처:https://youtu.be/2zjoKjt97vQ

 

위의 문제에서 고려해야할 사항은 다음과 같다고 생각했다.

 

1) 분과 초의 첫 번째 자리는 0부터 5까지이다.

2) 분과 초의 두 번째 자리는 0부터 9까지이다.

3) 시는 0부터 23까지 가능하다.

 

위의 예시를 수학적으로 풀었을 때는 3이 고정되었을 때,

올 수 있는 경우의 수가 5x9x5x9와 5x5x5x9 두가지가 된다고

생각했고 각각 시를 고정했을 때의 4가지 경우의 수와

5가 올 수 있는 3가지의 경우의 수를 조합하여

2025x4 + 1125x3 = 11475라는 수를 도출해낼 수 있었다.

 

하지만, 코드로 옮기기 위해서는

어떻게 해야할 지 제대로 된 감이 잡히지 않았다.

경우의 수가 적기 때문에 모든 경우의 수를 탐색하는

문제라고 생각이 들어서 3중 for문으로 구성해야겠다는

생각을 하게 되었고 해당 구문을 작성해보았다.

 

import time

n = int(input())
result = 0

# 시작
start_time = time.time()

for i in range(0, n+1):
    for j in range(0, 60):
        for k in range(0, 60):
            if '3' in str(i) or '3' in str(j) or '3' in str(k):
                result += 1

print(result)

# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

이렇게 모든 경우의 수를 탐색하는 것을

완전 탐색(Brute Forcing) 문제 유형이라고 불린다.

가능한 경우의 수를 모두 검사해보는 탐색 방법이다.

 

처음에는 3중 for문을 작성하지 않고 푸는 방법은 없을까라는

생각을 했지만, 생각이 나지 않았고 모범 답안을 보면서

완전 탐색을 구현하는 문제는 경우의 수가 적다면

3중 for문 등으로 구성하는 것이 가능하다는 생각을 하게 되었다.

 

import time

# 모범답안
h = int(input())
count = 0

# 시작
start_time = time.time()

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

print(count)

# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

모범 답안은 다음과 같다.

어차피 range는 0부터 시작하기 때문에 적지 않아도 되며,

or 연산자보다 + 연산자를 통해서 확인할 수 있다.

 

 

✔️ 구현문제 풀어보기 3

 

출처:https://youtu.be/2zjoKjt97vQ

 

위 문제에서는 주어진 문자는 정렬하여 나열하고,

숫자는 모두 더해서 정렬한 문자열 뒤에 붙히면 되는 문제이다.

 

생각한 풀이는 다음과 같다.

 

1) 입력받은 문자열 S를 list 형태로 쪼개어 각 문자를 저장한다.

2) 숫자로 된 문자열은 int형으로 형 변환하여 list에 다시 저장한다.

3) 리스트를 돌면서 각 데이터의 타입을 확인하여,

int이면 count에 값을 저장하고 str이면 문자열을 합친다.

4) 새로 만든 문자열과 count 값을 str로 형 변환하여 합치고 출력한다.

 

위에 나온 풀이에 대한 파이썬 코드는 다음과 같다.

 

import time

data = list(input())

# 시작
start_time = time.time()

num = '123456789'
data.sort()

for i in range(len(data)):
    if data[i] in num:
        data[i] = int(data[i])
    else:
        continue

count = 0
string = ''

for i in range(len(data)):
    if type(data[i]) == int:
        count += data[i]
    else:
        string += data[i]

print(string + str(count))


# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

위와 같은 방법으로 진행하게 되면,

 

 

입력 예시와 출력 예시에 맞게 동작하는 것을 확인할 수 있다.

그렇다면 모범 답안은 어떻게 되어있을지 확인해보았다.

 

import time

# 모범답안
data = input()

# 시작
start_time = time.time()

result = []
value = 0

for x in data:
    if x.isalpha():
        result.append(x)
    else:
        value += int(x)

result.sort()

if value != 0:
    result.append(str(value))

print(''.join(result))

# 종료
end_time = time.time()
print("time:", end_time-start_time)

 

해당 모범 답안의 경우에서 생각해보면 좋을 것이

 

1) isalpha 라는 함수를 적절하게 사용할 수 있는가?

2) list의 내장 함수를 적절하게 사용하고,

list에서 string 형태로의 변환을 할 수 있는가?

 

라고 생각이 들었다. 위의 초기 풀이처럼 리스트를 쪼개어서

정렬하고 for문을 돌리는 것도 나쁜 방법은 아니지만,

모범 답안은 역시 효율적이고 가장 간략하게 간단하게 정리한

풀이라는 생각이 들었다. 여기서 isalpha 라는 함수를 사용하면

코드가 더욱 간결해지고, 리스트를 쪼개어 사용하는 것이 아니라

리스트에 추가로 삽입하고 해당 리스트를 최종적으로

문자열 형태로 변환하여 출력하는 것이 핵심이라는 것이다.

 

이처럼 내장 함수를 많이 알고 사용하는 것이

코드의 시간 복잡도와 효율을 동시에 잡을 수 있는 것이므로

파이썬 공부를 더 열심히 하는 것이 좋을 것 같다는 생각이다.

 

화이팅 💪