오늘 한 일
아침 2시간 동안 알고리즘 강의를 들었다. 오늘부터 3일 동안 실시간 알고리즘 강의를 듣게 된다.
내가 기대하는 알고리즘 강의는 문제를 해결하는 방식을 배우는 것인데... 정답 해설만 해주는 정도라 아직은 잘 모르겠다.
어제처럼 알고리즘 공부한 것에 대해서 수도 코드(pseudo code, 의사 코드)를 작성하는 방식으로 정리를 해보려고 한다. 알고리즘 문제를 처음 보고 풀이를 고민할 때는 솔직히 답답하지만, 푸는 방법을 정리할 땐 나름 재밌다!
최빈값 구하기
Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오
"hello my name is sparta"
먼저 반복문으로 해당 문장의 알파벳을 하나씩 불러와야 한다는 것까지는 감이 오는데...
그 다음이 막막했다.
가장 먼저 해야할 일은,
1. 문장 속 알파벳의 개수를 구하는 것이다.
그러기 위해서는 우선 알파벳의 개수(26개)만큼 요소가 담긴 배열을 만든 다음,
문장에 속한 알파벳을 불러와서 배열에 개수를 담는다.
# 총 26개의 0이 담긴 배열을 만드는 코드
alphabet_occurrence_array = [0] * 26여기서 처리해야할 몇 가지 로직이 더 있다.
1) 해당 문장의 공백을 제거해주고,
2) 알파벳을 아스키코드(ascii code)로 변환시켜줘야 한다는 점이다. (ord() 함수 사용)
3) 그런 다음 반복문을 이용해서 알파벳이 나올 때마다 해당 알파벳의 순서에 1씩 더해줘야 한다.
그게 바로 다음 코드다.
[모범 답안]
def find_alphabet_occurrence_array(string):
alphabet_occurrence_array = [0] * 26
for char in string:
if not char.isalpha(): # 문자열을 구성하는 문자가 알파벳이 아니라면 (공백 제외)
continue # 다음 코드로 점프해라
# 아스키 코드로 변환해서 각 알파벳의 인덱스를 구하고
arr_index = ord(char) - ord('a')
# 1씩 더해줘라
alphabet_occurrence_array[arr_index] += 1
return alphabet_occurrence_array가장 이해가 안된 부분은 배열의 인덱스를 구하는 부분이었다.
이걸 어떻게 이해해야 하냐면...
알파벳의 아스키코드는 a가 가장 작고(97) z까지 갈수록 1씩 커진다.
따라서, 특정 알파벳의 인덱스를 구하려면 해당 알파벳에서 a의 아스키코드 값을 빼야 한다.
# 내장 함수 ord() 이용해서 아스키 값 받기
print(ord('a')) # 97
print(ord('a') - ord('a')) # 97-97 -> 0
print(ord('b') - ord('a')) # 98-97 -> 1끙... 이 부분은 발상 자체도 못했지만, 이해하는 것도 너무 힘들었다.
어쨌든! 이제 첫 번째 단계가 끝났으므로 두 번째다.
2. 최댓값 구하는 것처럼 반복문 돌리면서 가장 큰 수(=많이 나온 알파벳 개수)를 구하면 끝!
def find_max_occurred_alphabet(string):
alphabet_occurrence_array = [0] * 26
for char in string:
if not char.isalpha():
continue
arr_index = ord(char) - ord("a")
alphabet_occurrence_array[arr_index] += 1
max_occurrence = 0
max_alphabet_index = 0
for index in range(len(alphabet_occurrence_array)):
alphabet_occurrence = alphabet_occurrence_array[index]
if alphabet_occurrence > max_occurrence:
max_occurrence = alphabet_occurrence
max_alphabet_index = index
return chr(max_alphabet_index + ord('a'))
result = find_max_occurred_alphabet
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))역대급 어려운 문제였다...
숫자 UP & DOWN 맞추기
- 프로그램이 1~100의 숫자 중 하나를 랜덤으로 정합니다.
- 사용자는 이 숫자를 맞추어야 합니다!
: 입력한 숫자보다 정답이 크면 → “UP” 아니면 → “DOWN”, 정답이면 → “CORRECT” 출력- 지금까지 숫자를 입력한 횟수를 알려줍니다.
[나의 답안]
import random
# 1~100 숫자 중 하나를 랜덤으로 발행
random_num = random.randint(1, 100)
# 입력 유도 문구 출력한다.
print("1~100 중 랜덤 숫자 하나를 정하였습니다. 과연 당신이 맞출 수 있을까요?")
# 사용자에게 값을 입력을 받는다.
input_num = int(input("숫자 입력: "))
# 사용자가 입력한 숫자와 랜덤 숫자의 일치, 불일치 여부에 따라 다른 문구 출력
if input_num == random_num:
print("CORRECT")
if input_num < random_num:
print("UP")
if input_num > random_num:
print("DOWN")문제는 여기서 끝내면 결과값이 CORRCT, UP, DOWN 중에 하나만 출력되고 프로세스가 종료된다는 것이다.
사용자에게 input_num을 반복적으로 실행하고 정답을 맞혔을 경우에는 지금까지 숫자를 입력한 횟수를 알려줘야 한다.
조금 더 생각해보니 힌트를 얻었다!
- '반복적으로 실행' -> 반복문이 필요하다.
- 지금까지 숫자를 입력한 횟수 -> 반복문을 한번 실행할 때마다 횟수를 나타내는 변수를 +1 해준다.
문제는 for 문을 사용하면 정해진 횟수 안에서만 반복문이 진행된다는 것이다.
따라서 조건에 이를 때까지 반복을 실행하는 while 문으로 작성하면 다음과 같이 답이 나온다.
[모범 답안]
import random
answer = random.randint(1, 100)
count = 0
print('1~100 중 랜덤 숫자 하나를 정하였습니다. 과연 당신이 맞출 수 있을까요?!')
while True:
count += 1
guess = int(input('숫자 입력: '))
if guess > answer: # 사용자가 입력한 값보다 랜덤 숫자가 작으면 DOWN 출력!
print('DOWN')
elif guess < answer: # 사용자가 입력한 값보다 랜덤 숫자가 크면 UP 출력!
print('UP')
elif guess == answer: # 사용자가 입력한 값과 랜덤 숫자가 같으면 CORRECT 출력 후 종료
print('CORRECT')
break
print('숫자 입력한 횟수: %d번' % count)여기서 한 가지 더 중요한 포인트는, if 조건문으로 분기할 때 CORRECT가 출력되는 조건(답이 일치)을 가장 마지막으로 처리해줘야 한다는 것이다.
왜냐하면 답이 일치할 때(guess == answer)까지 조건문을 반복하는 것이기 때문이다.
elif guess == answer 이 True가 되는 순간 break로 반복문을 빠져나오게 된다.
반복해줄 대상은 반드시 반복문 아래의 scope에 들어가 있어야 한다.
너무 기초적인 내용들인데... 놓치지 말자!
To-do list
- 알고리즘 1주차 숙제 완벽 이해
- 알고리즘 2주차 실시간 강의 듣고 복습
