어떤 문제의 해결을 위하여, 입력된 자료를 토대로 원하는 출력을 유도하여 내는 규칙의 집합
여러 단계 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다
알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다.
📚 알고리즘을 공부해야 하는 이유
좋은 개발자가 되기 위해
좋은 개발자란 좋은 프로그램을 구현할 줄 알아야함
좋은 프로그램이란? 적은 공간을 이용 빠른 속도로 수행하는 프로그램
즉 좋은 프로그램을 위해선 특정자료구조나 접근방법을 사용해야 함
좋은 회사에 취직하기 위해
유망 IT기업 외에도 많은 스타트업까지 코딩테스트를 개발자의 필수 관문으로 삼고있음
기초적인 지식과 해결책으로 적절한 사고를 할 수 있는지에 대한 검증
📌 최대값 찾기
Q. 다음과 같이 숫자로 이루어진 배열이 있을 때 , 이 배열 내에서 가장 큰 수를 반환하시오
[3, 5, 6, 1, 2, 4]
첫번째 방법 문제풀이 (다중 포문으로 풀기)
input = [3, 5, 6, 1, 2, 4]
deffind_max_num(array):for num in array:
for compare_num in array:
if num < compare_num:
breakelse:
return num
result = find_max_num(input)
print(result)
두번째 방법 문제풀이 (지정 변수로 풀기)
input = [3, 5, 6, 1, 2, 4]
deffind_max_num(array):
max_num = array[0]
for num in array:
if num > max_num:
max_num = num
return max_num
result = find_max_num(input)
print(result)
🔠 최빈값 찾기
Q. 다음과 같은 문자열을 입력받았을 때, 어떤 알파벳이 가장 많이 포함되어 있는지 반환하시오
def find_max_occurred_alphabet(string):
# 이 부분을 채워보세요!
return "a"
result = find_max_occurred_alphabet(input)
print("정답 = a 현재 풀이 값 =", result("Hello my name is sparta"))
print("정답 = a 현재 풀이 값 =", result("Sparta coding club"))
print("정답 = s 현재 풀이 값 =", result("best of best sparta"))
참고! 문자인지 확인하는 방법
파이썬의 내장함수 str.isalpha()를 이용
print("a".isalpha())
print("1".isalpha())
s = "abcdefg"
print(s[0].isalpha()) # True
source_sentence = "go go coding of co! 0719-2022"
source_list = list(source_sentence)
이렇게 작성하면 리스트 안의 데이터가 알파벳, 특수문자, 숫자, 공백 등이 다양하게 들어오게 된다.
알파벳 검사 메서드 str.isalpha(값) 을 사용해서 알파벳인 값만 리스트에 담아주자
source_list = []
for char in list(source_sentence):
if str.isalpha(char):
source_list.append(char)
이렇게 입력받은 문자를 알파벳 단위로 잘라 리스트로 저장까지 했다!
알파벳 리스트 작성
다음은 위의 입력 알파벳들을 한 번씩 확인하면서 각 알파벳을 카운트할 공간이 필요하다
alphabet_list = [0] * 26
입력받은 알파벳이 A-Z까지 있을 가능성이 있기에 26개의 알파벳을 모두 저장할 공간을 만든 것이다
알파벳 카운트
입력 받은 문자를 알파벳으로 담아둔 source_list
알파벳 a-z 카운트할 수 있는 26길이의 리스트 alphabet_list
두 가지의 리스트를 가지고 알파벳이 몇 번 들어갔는지 카운트한다
반복문으로 source_list를 슬라이싱하여 어떤 알파벳인지 확인하고
for char in source_list:
# 알파벳을 번호로 만들기
ord(char)
# 알파벳을 0~25 사이의 숫자로 만드려면 a~z의 값에서 a를 빼주면 된다!
target_index = ord(char) - ord("a")
알파벳에 해당하는 번호를 찾아 alphabet_list에 카운트한다
for char in source_list:
target_index = ord(char) - ord("a")
alphabet_list[target_index] += 1
알파벳 최댓값, 최빈값 찾기
이제 source_list의 알파벳을 alphabet_list 리스트에 카운트했다.
카운트가 가장 많이 된 최대수를 찾고 나서 해당 값의 인덱스를 찾자
max_num = alphabet_list[0]
for num in alphabet_list:
if num > max_num:
max_num = num
# 최대수를 값으로 인덱스 찾아내기
target_index = alphabet_list.index(max_num)
# chr을 사용해서 다시 문자로 변환
target_char = chr(target_index)
코드
source_sentence = "go go coding of co! 0719-2022"
source_list = []
for char in list(source_sentence):
if str.isalpha(char):
source_list.append(char)
alphabet_list = [0] * 26
for char in source_list:
target_index = ord(char) - ord("a")
alphabet_list[target_index] += 1
max_num = alphabet_list[0]
for num in alphabet_list:
if num > max_num:
max_num = num
target_index = alphabet_list.index(max_num)
target_char = chr(target_index)
튜터님의 풀이
첫번째 풀이
각 알파벳마다 문자열을 돌며 몇 글자가 나왔는지 확인
먄약 그 숫자가 저장한 알파벳 빈도 수보다 크면, 그 값을 저장하고 제일 큰 알파벳으로 저장
이 과정을 반복!
def find_max_occurred_alphabet(string):
# 알파벳 리스트를 만듦
alphabet_array = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s",
"t", "u", "v", "x", "y", "z"]
# 초기의 최빈값은 0, 리스트의 0번째 인덱스값(즉, "a")은 max_alphabet으로 설정
max_occurrence = 0
max_alphabet = alphabet_array[0]
# a-z 에서 a를 alphabet으로 돌림 (발생빈도는 0)
for alphabet in alphabet_array:
occurrence = 0
# 우리가 넣고 싶은 문자열의 첫 글자 넣기(H..e..l..l.o..m.....a!)
# alphabet과 같으면 발생빈도를 1 올리고 다시 for 돌림
for char in string:
if char == alphabet:
occurrence += 1
if occurrence > max_occurrence:
max_alphabet = alphabet
max_occurrence = occurrence
return max_alphabet
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"))
두번째 풀이
각 알파벳의 빈도수를 alphabet_occurrence_list라는 변수에 저장
각 문자열을 돌면서 해당 문자가 알파벳인지를 확인
알파벳을 인덱스화 시켜 각 알파벳의 빈도수를 업데이트
알파벳의 빈도수가 가장 높은 인덱스를 알아냈죠
여기서 max_alphabet_index가 0이기 때문에 인덱스를 문자로 변경해야 함!
아스키 코드번호를 실제 문자로 변환하려면 chr()함수를 사용
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"))
