📜 알고리즘
:: ✍ LinkedList 구현
화물칸 : 노드
연결고리 : 포인터Node에 들어가는 두가지 정보
- 들어있는 데이터가 무엇인지 : data, value..
- 다음 노드는 무엇인기 : next
class로 묶기
- 클래스 생성자에 data를 인자로 받아 self.data에 저장
- 다음 노드는 없기 때문에 포인터 아무것도 가르키지 않음
∴ self.next = None
class Node:
def __init__(self, data):
self.data = data
self.next = NoneLinkedList 만들기
- 노드를 하나하나 만들어 연결하면 너무 번거롭기 때문에 LinkdeList 만들어 연결
- linked맨 앞 칸, 즉 head node만 들고 있으면 됨
- self.head에 시작하는 노드 저장
- 다음 노드를 보려면 각 노드 next를 조회해 찾아가야함
class LinkedList:
def __init__(self, data):
self.head = Node(data)
liked_list = LinkedList(3)
print(liked_list.head.data) # 3
print(liked_list.head.next) # Noneappend 함수
- 뒤에 있는 data가 Node로 생성되어 붙이는 함수
- 모든 node 뒤에 새로운 data 들어있는 노드를 붙이고 싶은 것
∴ 맨 뒤 node까지 이동해야함 - head따라 이동, head.next에 Node(new) 넣으면 됨
→ cur = self.head // 칙칙폭폭 시작 - cur = cur.next, cur = cur.next .. 계속 추가하면 한칸씩 이동
- 마지막은 None이기 때문에 while문 사용해 None 직전까지 이동
→ cur.next == None //칙칙폭폭
head → → → → → → → → → None- cur에 처음 탐색할 self.head 넣기
- while문 통해 next가 None 아닐 때 까지 cur = cur.next 통해 이동
- while문 빠져나와 다음 새로운 노드 만들어 연결
→ cur.next = Node(data) - 만일 head가 None일 경우 error 나기 때문에 새로운 노드에 넣어 대입하도록 예외처리
def append(self, data):
if self.head is None:
self.head = Node(data)
return
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(data)
linked_list.append(4)
linked_list.append(5)모든 원소 출력하기
- cur에 self.head 넣고 칙칙폭폭 시작
- while문 통해 next가 None이 아닐 때 까지 cur = cur.next 통해 이동
- 이동하면서 next가 None이 아닐때 까지만 print(cur.data)로 출력
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
linked_list.print_all()원소 찾기
Q. index번째 원소 찾기
index번째 : next node로 가는 것을 index번 해야된다라는 의미- head부터 시작해서 index만큼 이동해야 하기 때문에 그것을 위한 변수 지정
→ node = self.head - index만큼 옮겨야 하기 때문에 count로 숫자 세기 위한 변수 사용
→ count = 0 - while문으로 count가 index보다 작다면 계속 움직여야 하니
→ cur = cur.next처럼 node = node.next - 그리고 이동시 마다 카운트 +1씩
→ count += 1 - return으로 node값 반환하면 원하는 값 얻을 수 있음
→ return node
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
linked_list = LinkedList(5)
linked_list.append(12)
print(linked_list.get_node(0).data) # -> 5를 들고 있는 노드를 반환해야 합니다!원소 추가
Q. index번째 새로운 원소 추가
몇번째에 무슨 값을 넣을지 알아야함
∴ index, data 모두 받음★클래스 내부 다른 함수 부르기 = self.해당함수명★
-
사이에 넣을 앞쪽 칸을 하나의 변수로 저장
현재 노드를 구하기 위해서는 get_node 사용
→ index -
뒤쪽 칸을 임시로 저장
→ next_node -
새로운 추가할 칸
→ new_node -
index.next = new_node 로 지정
-
new_node.next = next_node로 지정
-
get_node로 index번째를 하다보니 (1, 6)하면 뒤칸에 붙음 (넣을자리, 넣을데이터)
-
index번째에 넣기 위해서는 index -1번째 노드를 찾아야 함
→ index – 1 -
index 노드를 잡아온 다음 새노드 붙이기 때문에 원하는 자리에 원하는 노드 넣을 수 있음
즉, index가 1 이기 때문에 -1을 해서 0번째인 5를 가져오는 것
index가 1인 것은 그렇게 get_node에서 설정했기 때문임 -
현재 index - 1이라고 되어 있는데 어느 코드에서나 -1이라는 코드가 있으면 0은 어떻게 되는지 고민하고 -1에 대해 예외처리 해야함
→ if문으로 -
새로운 노드를 헤드노드로 넣기
→ new_node.next = self.head
def add_node(self, index, data):
new_node = Node(data) # 새로운 노드 추가 [6]
if index == 0:
new_node.next = self.head # [6] -> [5]
self.head = new_node # heda ->
return
node = self.get_node(index -1) # 앞쪽 노드 변수로 저장 [5]
next_node = node.next # 뒤쪽 노드 임시저장 [12]
node.next = new_node # [5] -> [6]
new_node.next = next_node # [6] -> [12]
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
linked_list.add_node(1, 6) # 5와 12 사이에 6 추가하기 (넣을자리, 넣을것)
linked_list.print_all()원소 삭제
Q. index번째 원소 제거
index만 인자로 받으면 됨- 삭제할 앞칸을 index - 1번째 칸을 가져온 후
- 삭제할 뒤칸을 next_node로 저장
- 앞칸의 다음칸을 next_node.next로 연결
def delete_node(self, index):
if index == 0:
self.head = self.head.next # head 바꾸기
return
node = self.get_node(index -1)
node.next = node.next.next
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
linked_list.add_node(0, 3) # 5와 12 사이에 6 추가하기 (넣을자리, 넣을것)
linked_list.print_all()
linked_list.delete_node(0) # 삭제할 자리 수
linked_list.print_all():: ✍ 문제
두 링크드 리스트 합 계산
Q. 다음과 같은 두 링크드 리스트를 입력받았을 때, 합산한 값을 반환하시오.
예를 들어 아래와 같은 링크드 리스트를 입력받았다면,
각각 678, 354 이므로 두개의 총합 678 + 354 = 1032 를 반환해야 한다.
단, 각 노드의 데이터는 한자리 수 숫자만 들어갈 수 있다.- head 따라가며 각 값을 더하며 합계 내주면 됨
- 자릿수에 맞게 더하기
→ 총액 X 10 + 현재 노드 값
def get_linked_list_sum(linked_list_1, linked_list_2):
linked_list_sum_1 = 0
head_1 = linked_list_1.head
while head_1 is not None:
linked_list_sum_1 = linked_list_sum_1 * 10 + head_1.data
head_1 = head_1.next
linked_list_sum_2 = 0
head_2 = linked_list_2.head
while head_2 is not None:
linked_list_sum_2 = linked_list_sum_2 * 10 + head_2.data
head_2 = head_2.next
return linked_list_sum_1 + linked_list_sum_2
linked_list_1 = LinkedList(6)
linked_list_1.append(7)
linked_list_1.append(8)
linked_list_2 = LinkedList(3)
linked_list_2.append(5)
linked_list_2.append(4)
print(get_linked_list_sum(linked_list_1, linked_list_2))함수 쪼개기
- 위와 같이 풀면 반복이 많으므로 좋은 코드가 아님
- 하단에 함수 하나 만들어 중복되는 것 (_1, _2) 지운 후 return sum
- 상단 원래 함수에서 1, 2 각각 호출
def get_linked_list_sum(linked_list_1, linked_list_2):
sum_1 = _get_linked_list_sum(linked_list_1)
sum_2 = _get_linked_list_sum(linked_list_2)
return sum_1 + sum_2
def _get_linked_list_sum(linked_list):
linked_list_sum = 0
head = linked_list.head
while head is not None:
linked_list_sum = linked_list_sum * 10 + head.data
head = head.next
return linked_list_sum:: ✍ 이진탐색
이진 탐색 vs 순차 탐색
up down game- 이진탐색은 절반 뚝! 절반 뚝! ...
- 순차탐색은 1번부터 순서대로
이진탐색
- 정렬이 되어 있지 않으면 이진탐색 불가
- 이진탐색은 일정한 규칙으로 정렬되어 있는 데이터만 가능
- 최소, 최댓값 찾기(indexr값)
- current_min = 0
- current_max = len(array) -1
- 시도값 찾기
- current_guess = (current_min + current_min) // 2
- 최소값이 최대값보다 작거나 같아질 때 까지 반복
- while문
- 반복하며 if문으로 검사
- current_min == target : True
- current_min < target :
- 타겟이 더 크니까 up!
- 최솟값을 다시 지정 : 시도값+1
- current_min > target :
- 타겟이 더 크니까 down!
- 최댓값을 다시 지정 : 시도값-1
- 시도값 업데이트
- while문이 끝날 때 까지 한번도 발견되지 않는다면 없다는 것 ∴False
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
current_min = 0
current_max = len(array) - 1
current_guess = (current_min + current_max) // 2
while current_min <= current_max:
if array[current_guess] == target:
return True
elif array[current_guess] < target:
current_min = current_guess + 1
else:
current_max = current_guess - 1
current_guess = (current_min + current_max) // 2
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)시간복잡도
1. 몇번 탐색하는지 알기 위해 find_count라는 변수 두기
2. 각 for문, while 문에서 검색할 때마다 +1씩 추가
3. True 위에서 print하기1. 순차탐색
- 시간복잡도: O(N)
- 1~14까지 순차적으로 탐색했기 때문에 검색 횟수 14
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_sequential(target, array):
find_count = 0
for number in array:
find_count += 1
if target == number:
print(find_count) # 14
return True
return False
result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)2. 이진탐색
- 시간복잡도 : O(logN)
- 3단계를 통해서 찾았으므로 검색횟수 3
finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]
def is_existing_target_number_binary(target, array):
current_min = 0
current_max = len(array) - 1
current_guess = (current_min + current_max) // 2
find_count = 0
while current_min <= current_max:
find_count += 1
if array[current_guess] == target:
print(find_count) # 3
return True
elif array[current_guess] < target:
current_min = current_guess + 1
else:
current_max = current_guess - 1
current_guess = (current_min + current_max) // 2
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)이진탐색과 순차탐색 차이
:: ✍ 재귀함수
- 자기 자신을 계속해서 반복해서 호출하는 함수
- 간결하고 효율성 있는 코드 작성 가능
- 반드시 빠져나가는 지점을 명확하게 정해줘야함
- 탈출구 만들어주지 않으면 무한루프에 빠져 에러
Q. 60에서 0까지 숫자를 출력하시오. (보신각 카운트다운)
def count_down(number):
if number < 0: # 만약 숫자가 0보다 작다면, 빠져나가자!
return
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60)팩토리얼
- 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것
- 3팩토리얼
- 3! = 3 2 1 = 6
- 4팩토리얼
- 4! = 4 * 3! = 24
구조
Factorial(n) = n * Factorial(n - 1)
Factorial(n - 1) = (n - 1) * Factorial(n - 2)
.
.
.
Factorial(1) = 1
즉, Factorial(n) = = n * n – 1 * Factorial(n - 2)…
def factorial(n):
if n == 1:
return 1 # 1이 되면 빠져나가자
return n * factorial(n-1)
# 1차 5일 때 1과 같지 않으므로 5 *
# 2차 4일 때 1과 같지 않으므로 4 *
# 3차 3일 때 1과 같지 않으므로 3 *
# 4차 2일 때 1과 같지 않으므로 2 *
# 5차 1일 때 빠져 나가자! 5 * 4 * 3 * 2 * 1
print(factorial(5)) # 5! = 5 * 4 * 3 * 2 * 1회문검사
회문 : 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장
Memo
range = 간단히 정수 범위 표현- 맨 앞과 맨 뒤 같아야 하고, 그 뒤와 그 앞, 그 뒤와 그 앞이 다 같아야 함
- 마지막 남은 가운데 글자는 뭐가 오든 상관 없음
Q. 다음과 같이 문자열이 입력되었을 때, 회문이라면 True 아니라면 False 를 반환하시오.
- 문자열 길이 저장할 변수 n 지정
- string[n – 1 - i] == string[문자열 길이 – 1 - 문자열길이] == 즉, -1
input = "abcba"
def is_palindrome(string):
n = len(string) # 문자열 길이 저장
for i in range(n):
if string[i] != string[n - 1 - i]: # 문자열 맨 앞과 뒤가 같은지 비교
return False
return True
print(is_palindrome(input))재귀함수로 해결하기
- 재귀함수의 목적은 문제를 좁혀 나가는 것
- 반띵해서 또 반띵 또 반띵
is_palindrome(문자열) = 맨 앞뒤 검사를 했다면 is_palindrome(문자열[1, -1]) 로 문제가 축소되는 것input = "소주만병만주소"
def is_palindrome(string): # input값 들어감
# 1. is_palindrome("소주만병만주소") True
# 2. is_palindrome("주만병만주") True
# 3. is_palindrome("만병만") True
if string[0] != string[-1]:
return False
# 처음부터 틀렸을 때!
if len(string) <= 1:
return True # 4. is_palindrome("병")
# 글자가 하나만 남았을 때!
return is_palindrome(string[1:-1])
# 첫번째 인덱스 ~ -1 인덱스 전까지
# 첫번째로 본 인덱스 한칸 뒤 ~ - 뒤에서 한칸 앞 인덱스까지
print(is_palindrome(input))재귀함수 풀기 위해서는?
- 문제가 축소되는 특징이 보여야함
- 특정 구조가 반복되는 것 같은 양상을 보여야 함
- 탈출 조건 필수
🤢 숙제
- 주말에 풀어보기
링크드 리스트 끝에서 K 번째 값 출력하기
Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오.
배달의 민족 배달 가능 여부
Q. 배달의 민족 서버 개발자로 입사했다.
상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때,
유저가 ["오뎅", "콜라", "만두"] 를 주문했다.
그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.
배열의 정렬 = .sort()더하거나 빼거나
Q. 음이 아닌 정수들로 이루어진 배열이 있다.
이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다.
예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.
-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3
사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때
숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.
