내배캠 2022.11.09 (알고리즘 1주차)
어제 저녁에 내일배움캠프 스카우트 선서문 이메일로 받아 서명하였다.
01. 오늘 배울 것
알고리즘이란
어떤 문제가 있을 때 그것을 해결하기 위한 여러 동작의 모임이다
문제를 해결하는 가장 효율적인 방법을 찾으려 한다
알고리즘을 공부하는 이유
1. 좋은 개발자 되려고
좋은개발자가 되려면 좋은 프로그램을 구현할 줄 알아야한다.
특정 자료구조나 접근방법을 사용하면 좋은 프로그램을 만들 수 있다.
이건 배워야 할 수 있는 거다. 개발과는 별개
2. 좋은 회사 취직하려고
코딩테스트를 통과하려고
이번 강의를 다 들으면 충분히 해결할 수 있을 것
하지만 취업하고 나서는 만들어진거 가져다 쓴다
1~5주차 배울것
1. 시간/공간 복잡도/ 알고리즘 구현력기르기
2.어레이, 링크드 리스트(코딩테스트 단골주제)/ 이분탐색, 재귀
3.정렬, 스택, 큐, 해쉬
4. 힙, BFS, DFS, Dynamic Programming
5. 종합 알고리즘 문제풀이
03. 파이참으로 코딩하기
파이참에서 파일만들 때 그냥 파일 선택해주고 확장자?를 써주면 원하는 형식의 파일을 만들 수 있다.
컴퓨터는 특수 문자 싫어한다. 띄어쓰기도 특수문자에 해당한다. 그래서 _ 언더바로 표시함.
경로란 폴더이다
경로 만들기 = 폴더 만들기
04. 알고리즘과 친해지기 (1)
최댓값 찾기
def find_max_num(array):
return max(array)
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))이중반복문 구조로 구현하였다. break는 for 문을 빠져나온다 for else 구문을 이용해주었다. if else 아니다
def find_max_num(array):
for num in array:
for compare_num in array:
if num < compare_num:
break
else:
return num #반복문 두개를 만들어서 모든 데이터들을 서로서로 비교할 수 있도록 한다
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))else를 바깥의 if절에 놓지 않고 안쪽의 if절에 놓아서 원하는 결과가 나오지 않았었다.
# 강창민 튜터님의 특강에서 상세히 설명을 들었는데, num으로 뽑아준 데이터 하나에 compare num로 뽑아준 모든 데이터를 다 비교해본다. 그리고 num의 마지막 데이터까지 이 일을 반복한다. 그니까 6개 데이터에 6번씩 비교를 해주니까
총 36 비교를 해주는 것
맞나?
#노란줄은 왜 나오나
PEP(파이썬 기본 포매팅 규칙)에 맞지 않아서 - 이쁘게 쓰기 위한 규칙
파란색 reformat file(파일형식 다시 지정) 눌러주면 고쳐진다.
두번째 방법= max_value를 리스트 안의 데이터와 비교한다 return 들여쓰기를 얼마나 해야하는지 잘 몰라서 자꾸 틀린 답이 나왔다.
def find_max_num(array):
max_num = array[0]
for a in array:
if a > max_num:
max_num = a
return max_num
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([3, 5, 6, 1, 2, 4]))
print("정답 = 6 / 현재 풀이 값 = ", find_max_num([6, 6, 6]))
print("정답 = 1888 / 현재 풀이 값 = ", find_max_num([6, 9, 2, 7, 1888]))두번째 방법이 더 효율적이다.
컴퓨터가 비교를 덜 해도 결과가 나오기 때문이다.
뭔가 어렵다...
05. 알고리즘과 친해지기 (2)
이건 더 어렵다... 알고리즘과 친해지는게 아니라 멀어지는 기분이 든다...
알파벳에서 아스키코드로
ord()
아스키코드에서 알파벳으로
chr()
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')
alphabet_occurrence_array[arr_index] += 1
return alphabet_occurrence_array
print("정답 = [3, 1, 0, 0, 2, 0, 0, 0, 1, 0, 0, 2, 2, 1, 1, 1, 0, 1, 2, 1, 0, 0, 0, 0, 1, 0] \n현재 풀이 값 =",
find_alphabet_occurrence_array("Hello my name is sparta"))
print("정답 = [2, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0] \n현재 풀이 값 =",
find_alphabet_occurrence_array("Sparta coding club"))
print("정답 = [2, 2, 0, 0, 2, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 1, 3, 3, 0, 0, 0, 0, 0, 0] \n현재 풀이 값 =",
find_alphabet_occurrence_array("best of best sparta"))
# continue 키워드는 조건에 해당하는 것을 빼고 실행해준다.
if not char.isalpha():
continue이부분을
if char.isalpha():이렇게 써주어도 같은 기능을 한다 그래서 왜 굳이 위처럼 썼는지 궁금했는데, 어떤 분이 같은 의문을 가지고 질문 하셨고 설명을 공유하셨다.
# if char.isalpha()로 작성하여도 동일하게 작동은 할 수 있으나, 필터링이라는 본질적인 목적에는 부합하지 않습니다.
필터링은 담지 않을 것들을 거르는 행위임으로 필터링의 본질적인 기능(언어적인 의미&기능적인 의미)에 맞게 사용해야 합니다.따라서 if not으로 '담지 않을 것'(해당 케이스에서는 " ")을 거르는 방향으로 설계하는 것이 필터링의 본질에 맞게 코드를 작성하는 것입니다.
가장 많이 나온 알파벳 구하기
내가 쓴 답
input = "hello my name is sparta"
occured_alphabet_array = [0]*26
def find_max_occurred_alphabet(string):
for s in string:
if not s.isalpha():
continue
arr_index = ord(s) - ord('a')
occured_alphabet_array[arr_index] += 1
return occured_alphabet_array
def find_max_num(array):
max_num = array[0]
for a in array:
if a > max_num:
max_num = a
return max_num
o_list =find_max_occurred_alphabet(input)
result = find_max_num(o_list)
index = o_list.index(result)
print(chr(97 + index))# index라는 내장함수를 써서 풀었는데, 알고리즘 공부할 때는 내장 함수 많이 안 써준다.
A1. 첫 번째 방법
각 알파벳마다 문자열을 돌면서 몇 글자 나왔는지 확인합니다. 만약 그 숫자가 저장한 알파벳 빈도 수보다 크다면, 그 값을 저장하고 제일 큰 알파벳으로 저장합니다. 이 과정을 반복하다보면 가장 많이 나왔던 알 파벳을 알 수 있습니다.
input = 'hello myname is seonhyeong'
def find_max_occured_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"]
max_occurence = 0
max_alphabet = alphabet_array[0]
for alphabet in alphabet_array:
occurence = 0
for char in string:
if char == alphabet:
occurence += 1
if occurence > max_occurence:
max_occurence = occurence
max_alphabet = alphabet #occurence가 가장 커졌을 때 alphabet에 들어있던 알파벳을 max_alphabet으로 만들어줘
return max_alphabet
result = find_max_occured_alphabet(input)두번째 방법
각 알파벳의 빈도수를 alphabet_occurrence_list 라는 변수에 저장합니다. 그리고 각 문자열을 돌면서 해당 문자가 알파벳인지 확인하고, 알파벳을 인덱스 화 시켜 각 알파벳의 빈도수를 업데이트 합니다. 이후, 알파벳의 빈도수가 가장 높은 인덱스를 찾습니다.
range() 어떠한 숫자가 있으면 0부터 그 숫자까지 리스트로 만들어서 넣어주는 함수
len() 리스트의 값의 수를 세어주는 함수
input = 'hello myname is spartabbbbb'
def find_max_occured_alphabet (string):
alphabet_occurrence_array = [0] * 26
for char in string:
if char.isalpha():
arr_index = ord(char) - ord('a')
alphabet_occurrence_array[arr_index] += 1
max_occurence = 0
max_alphabet_index = 0
for index in range(len(alphabet_occurrence_array)):
# index 0 -> alphabet_occurence 3
alphabet_occurence = alphabet_occurrence_array[index]
if alphabet_occurence > max_occurence:
max_occurence = alphabet_occurence
max_alphabet_index = index
max_alphabet = chr(97 + index)
return max_alphabet
result = find_max_occured_alphabet(input)
print(result)
first one is more effective
06. 시간 복잡도 판단하기
시간 복잡도란?
입력값과 문제를 해결하는데 덜리는 시간과의 상관관계
입력값이 2배로 늘어났을 때 걸리는 시간은 얼마나 늘어났나?
입력값이 늘어나도 시간이 덜 늘어나는 알고리즘이 좋은 알고리즘
강창민 튜터님 특강
코딩을 즐려야 한다.
왜 그런가 궁금증을 가져야한다
자기객관화해야한다
많은 것을 검색해서 하면 되긴하지만 자주 쓰이는 건 외우는게 낫다
코딩테스트 언어는 원하는 것을 선택할 수 있다
top3 코테 언어
파이썬
자바스크립트
C++
파이썬으로 알고리즘하는 이유
파이썬 (쉬워요, 코드가 짧게 나온다) - 시간 제약에서 유리하다
코테는
input의 set이 있다 최소 5개 20개까지
output set이 있다
테스트 케이스 1, 2, 3에대한 데이터 쎗이 모두 통과되어야 성공!
성능평가 테스트 케이스도 있습니다. 몇만건의 데이터를 넣어서 성능테스트도 한다
인풋을 받아서 원하는 아웃풋내기 위해서는 알고리즘, 자료구조는 필수
코테 칠 때 라이브러리 많이 못 쓰게 한다. 기본 테크닉이 엄청 중요한다.
주어진 문제를 얼마나 쉽고 빠르게 간결하게 깔끔하게 해결하는지가 프로그래밍이다
재료 및 도구가 자료구조 레시피기 알고리즘
문제를 풀기 전에 논리적으로 생각하는 시간을 가진다
인지부하를 줄이기 위해서 익숙하지도 않은 말을 바로 외국어로 하려면 인지부하가 온다요
항상 한국말로 먼저하기
주석으로 쭈르륵 쓰고 코드 시작하기
list comprehension이란 기능이 짱좋다.
리스트 컴프리헨션은 쉽게 말해 ‘리스트를 쉽게, 짧게 한 줄로 만들 수 있는 파이썬의 문법’이다
코드 제네레이트
비트맵 자료구조 Bitmap
비트맵 자료구조라고 한다 .[0,0,0,0,0,0,0,0]
비트를 지도처럼 쭉 늘여놓아서 비트맵이다.
OR can be used to set a bit = 11101110
이양임 매니저님 공지
선발대 - 심화학습 (코딩테스트 준비 반)
후발대 - 보충수업
권장이 있을 수 있지만, 선택은 자유다.
퀴즈,타임어택,다면평가 등등을 반영하여 선택한다.