개발_TIL
개발_TIL | 2022-07-19 (63)
by Hee94
2022. 7. 19.
알고리즘 Algorithm 공부 1일차
🤖 알고리즘이란?
- 어떤
문제의 해결을 위하여, 입력된 자료를 토대로 원하는 출력을 유도하여 내는 규칙의 집합
- 여러 단계 유한 집합으로 구성되는데, 각 단계는 하나 또는 그 이상의 연산을 필요로 한다
- 알고리즘(영어: algorithm), 셈법은 수학과 컴퓨터과학, 언어학 또는 엮인 분야에서 어떠한 문제를 해결하기 위해 정해진 일련의 절차이다. 계산을 실행하기 위한 단계적 절차를 의미하기도 한다. 즉, 문제 풀이에 필요한 계산절차 또는 처리과정의 순서를 뜻한다.
📚 알고리즘을 공부해야 하는 이유
- 좋은 개발자가 되기 위해
- 좋은 개발자란
좋은 프로그램을 구현할 줄 알아야함
- 좋은 프로그램이란?
적은 공간을 이용 빠른 속도로 수행하는 프로그램
- 즉 좋은 프로그램을 위해선
특정자료구조나 접근방법을 사용해야 함
- 좋은 회사에 취직하기 위해
- 유망 IT기업 외에도 많은 스타트업까지
코딩테스트를 개발자의 필수 관문으로 삼고있음
- 기초적인
지식과 해결책으로 적절한 사고를 할 수 있는지에 대한 검증
📌 최대값 찾기
- Q. 다음과 같이
숫자로 이루어진 배열이 있을 때 , 이 배열 내에서 가장 큰 수를 반환하시오
[3, 5, 6, 1, 2, 4]
input = [3, 5, 6, 1, 2, 4]
def find_max_num(array):
for num in array:
for compare_num in array:
if num < compare_num:
break
else:
return num
result = find_max_num(input)
print(result)
input = [3, 5, 6, 1, 2, 4]
def find_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- 알파벳 별로 빈도수를 리스트에 저장하기
# [0,0,0,0,0,0,...,0,0]
alphabet_occurrence_array = [0] * 26- 컴퓨터는 0과 1숫자 밖에 모름, 때문에
문자도 숫자로 기억함
- 이때
어떤 숫자와 어떤 문자를 대응시키는가에 따라 여러가지 인코딩 방식이 있는데 통상 아스키 코드 방식을 많이 사용함
- 참고! 문자를 아스키 코드로 변환하는 법
# 내장 함수 ord() 이용해서 아스키 값 받기
print(ord('a')) - 황영상님의 풀이
- 필요한것
- 문자를 숫자로 변경하는 방법
- 알파벳이 몇 번 들어올 지 저장할 방법
- 어떤 알파벳이 가장 많이 들어왔는지 확인할 방법
- 가장 많이 들어온 알파벳을 리턴
- 필요한 코드 작성법
- 문자를 숫자로 변경하는 방법
- 컴퓨터는 문자를 아스키코드로 인식한다!
- 아스키코드 번호(정수)로 변경하는 파이썬 메서드
ord("알파벳") 을 사용한다
alphabet = "a"
ord_alphabet = ord(alphabet)
print(ord_alphabet)
- 알파벳이 몇 번 들어올 지 저장할 방법
- 이 중에서 알파벳이 몇 번 들어있는지 확인하려면 뭔가 저장해줄 공간이 필요하다
- 알파벳 a-z를 예시로 26개의 각 공간을 담고 있는 리스트를 만들어 본다
alphabet_list = ["a", "b", "c", "d", "e", "f", "g",
"h", "i", "j", "k", "l", "m", "n", "o", "p",
"q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]- 이렇게 알파벳이 들어있는 리스트를 일일이 알파벳을 달면서 만든다면, 어떤 알파벳인지 확인하는 것은 그렇다 치더라도, 어디에 저장할 것이냐는 물음이 생긴다.
- 그렇다면 0이 a이고, 25가 z라고 상정한 0이 들어있는 리스트를 만들어 알파벳이 있을 때마다 1을 더해줘 기록하는 리스트를 만들어 본다면?
alphabet_list = [0] * 26- 간단하면서 저장할 수 있는 공간이 마련되었다.
- 어떤 알파벳이 가장 많이 들어왔는지 확인할 방법
- 알파벳이 얼마나 들어올지 저장할 수 있는 리스트가 만들어진 상태에서 확인할 알파벳이 몇 번째 인덱스에 해당하는지 확인하여 1을 더해주면 카운트가 되는 셈이다.
- 확인한 알파벳은 몇 번째 숫자인지 확인하기 —> ord() 사용
- ord() 를 사용하여 확인한 정수를 index로 활용하기
- 리스트[인덱스] 의 값을 1 더해주기
- 가장 많이 들어온 알파벳을 리턴
- 리스트에 가장 많이 담긴 값이 몇 번째 인덱스인지 가져가야 한다
- 필요한 것은 몇 번째 알파벳인지이다. 몇 번 들어왔느냐가 아니다!
- 최댓값을 구하는 알고리즘을 구해서 그 값에 해당하는 인덱스를 구하자
- 인덱스를 구하는 메서드는
리스트.index(값) 이다.
list_fruits = ["사과", "배", "체리"]
favorite_fruit = "배"
index_num = list_fruits.index(favorite_fruit)
- 알고리즘 작성 및 코딩
- 알고리즘 작성
- 입력받은 문자를 알파벳 단위로 잘라내기
- 입력받은 문자는 공백을 포함하여 단어로 묶여있다. 한 글자 단위로 자르자
list() 메서드를 사용하면 글자 단위로 분해할 수 있다.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"))
