코드잇의 [좋은 알고리즘이란?] 강의를 수강 후 학습한 내용을 정리한 포스팅입니다.
선수 과제
알고리즘의 정석 수업을 듣기 위해서는 기본적인 파이썬 문법과 컴퓨터적 사고력을 갖추고있어야 하기때문에
먼저 선수 과제가 주어졌어요.
펠린드롬인지 검사하는 함수를 만드는 문제였네요!
def is_palindrome(word):
# 여기에 코드를 작성하세요
# 테스트 코드
print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))문제는 위와 같고, 아래와 같이 결과가 나와야 했어요
True
False
True
True
False저는 먼저 단어의 길이가 홀수일 경우, 짝수일 경우를 나눈 후
맨 앞의 단어와 맨 뒤의 단어,
그 다음 단어와 그 앞의 단어,
이런식으로 하나하나 비교하도록 구현했어요.
비교할 단어의 인덱스가 더했을 때 n-1 이라는 규칙이 있어, 이걸 이용했어요.
제 코드는 다음과 같습니다.
def is_palindrome(word):
n = len(word)
if (n % 2) == 0:
# 짝수
print('짝수')
for i in range(0, n//2):
if word[i] == word[n-1-i]:
continue
else:
return False
return True
elif (n % 2) == 1:
# 홀수
for i in range(0, (n-1)//2):
if word[i] == word[n-1-i]:
continue
else:
return False
return True
# 테스트 코드
print(is_palindrome("racecar"))
print(is_palindrome("stars"))
print(is_palindrome("토마토"))
print(is_palindrome("kayak"))
print(is_palindrome("hello"))중간에 들여쓰기를 잘못해서 답이 틀렸었는데, AI 코칭 서비스가 도와줘서 해결할 수 있었어요.
하지만 더 효율적인 코드가 있는지 찾아봤어요.
저처럼 문자열을 2번 반복하지 않고 문자열을 단순히 뒤집어서 원래 문자열과 비교하는 방식이 있더라구요.
코드는 다음과 같습니다.
def is_palindrome(word):
# 문자열을 모두 소문자로 변환하여 대소문자 구분 없이 검사합니다.
word = word.lower()
# 문자열을 반대로 뒤집은 후 원래 문자열과 비교합니다.
return word == word[::-1]
# 테스트 코드
print(is_palindrome("racecar")) # True
print(is_palindrome("stars")) # False
print(is_palindrome("토마토")) # True
print(is_palindrome("kayak")) # True
print(is_palindrome("hello")) # False코드가 간결해지고 실행 시간도 줄어들었네요.
[::-1] 은 문자열의 처음부터 끝까지 거꾸로 나타낸다는 것을 기억해야겠어요.
선형 탐색
선형 탐색 알고리즘에 대해서 배워보았어요.
선형 탐색이란, 리스트의 처음부터 끝까지 순서대로 하나씩 탐색을 진행하는 알고리즘 입니다.
제가 작성한 코드는 다음과 같아요.
def linear_search(element, some_list):
for x in some_list:
if element == x:
return some_list.index(x)
return None
print(linear_search(2, [2, 3, 5, 7, 11]))
print(linear_search(0, [2, 3, 5, 7, 11]))
print(linear_search(5, [2, 3, 5, 7, 11]))
print(linear_search(3, [2, 3, 5, 7, 11]))
print(linear_search(11, [2, 3, 5, 7, 11]))그냥 단순히 리스트에 있는 값들을 하나씩 element 와 비교하다가
만약에 같은게 나오면 리스트에서의 x 의 인덱스
결과는 다음과 같이, 알맞게 나왔습니다.
0
None
2
1
4이진 탐색
이번에는 이진탐색에 대해서 알아보았어요.
이진탐색은 선형탐색 알고리즘과 달리 '정렬된 리스트' 를 전제로 해야합니다.
아니면 적용이 불가능해요.
이진탐색을 위해서는 왼쪽 인덱스와 오른쪽 인덱스를 계속 업데이트 해주면서 진행을 하는 식으로 구현했어요.
def binary_search(element, some_list):
left, right = 0, len(some_list) - 1
while left <= right:
mid = (left + right) // 2 # 중간 인덱스 계산
if some_list[mid] == element:
return mid # 요소를 찾았을 때 인덱스 반환
elif some_list[mid] < element:
left = mid + 1 # 중간 값보다 큰 범위에서 다시 탐색
else:
right = mid - 1 # 중간 값보다 작은 범위에서 다시 탐색
return None # 요소가 리스트에 없을 때
# 테스트 코드
print(binary_search(2, [2, 3, 5, 7, 11])) # 0
print(binary_search(0, [2, 3, 5, 7, 11])) # None
print(binary_search(5, [2, 3, 5, 7, 11])) # 2
print(binary_search(3, [2, 3, 5, 7, 11])) # 1
print(binary_search(11, [2, 3, 5, 7, 11])) # 4선택정렬
선택정렬을 하는 방법은 다음과 같다
1. 제일 작은 값을 리스트에서 찾는다.
2. 찾으면 맨 앞으로 보낸다.
3. 맨 앞 값을 제외한 그 다음 값 부터의 리스트에서 다시 제일 작은 값을 찾는다.
(반복)
아래는 이해하기 쉬운 이미지이다
두개의 for 문을 쓰기 때문에 O(n^2) 이다.
삽입 정렬
이건 좀 다르게, 값들을 올바른 위치에 삽입하는 개념이다.
앞에서 하나씩 보는데,
그 값보다 왼쪽에 있는 값들과 비교하며, 알맞은 위치에 넣는 방법이다.
이것도 worst 로는 O(n^2) 시간이 걸린다.
알고리즘 평가를 할 때 주의할 점
Big-O 표기법에서 n 에 대해서
트리나 그래프 같은 특수한 자료구조가 인풋으로 들어올 수 있다.
(리스트처럼 선형적이지 않기 때문)
꼭짓점의 개수가 V 고 변의 개수가 E 라면 BFS 알고리즘의 시간 복잡도는 O(V+E) 이다
주로 많은 경우에 n 을 사용할 것이다.
코드의 모든 줄은 O(1) 인가?
인풋 크기와 상관없이 실행되는 코드만 O(1) 임!
sorted 함수나 sort 메소드를 사용하면 내부적으로 O(n log n) 의 정렬이 이루어짐
또 리스트에서 in 키워드를 쓰면 내부적으로 O(n) 의 선형 탐색이 이루어짐
리스트 기능
리스트의 길이가 n 일 때
정렬은 O(n log n)
끝에 요소를 추가하거나, 인덱싱, 길이를 구하는 것은 O(1)
나머지 대부분은 O(n) 정도 걸린다.
딕셔너리 기능
딕셔너리는 위와 같다.
리스트에 비해 딕녀서너리를 사용하는게 유리할 경우가 많을 것이다.
유용한 파이썬 기능 정리
- 데이터 타입을 리턴하는 type : O(1)
- max, min : O(n)
- 숫자를 문자열로 바꿔주는 str : O(log n)
- append : O(1)
- insert, del, index, reverse : O(n)
- sort, sorted : O(n log n)
- 리스트 슬라이싱 : 슬라이싱 범위 길이에 비례
- len : O(1)
여기까지 <좋은 알고리즘이란?> 수업을 완강해보았습니다!
각 세션 당 걸리는 시간이 길지 않아서
가볍게 훑어볼 수 있는 유익한 시간이었어요!
다음으로 <알고리즘 패러다임> 수업을 수강해봐야겠습니다.
아래에 구독 플랜 결제시 할인받을 수 있는 쿠폰번호 공유드립니다 😀
===============================
👩🏻💻 코드잇 앰배서더 전용 쿠폰
- 쿠폰명 : 내가만든쿠폰~너를위해구웠지~
- 쿠폰 코드 : AMBSDR1J
- 할인율 : 15% (1개월/12개월 둘다 적용 가능)
- 유효 기간 : 2023/11/30 까지
===============================
본 포스팅은 '코드잇 앰배서더 1기' 자격으로 작성된 글입니다.
