내배캠 2022.11.14 (알고리즘 2주차)
04. 링크드 리스트 구현 -1
링크드 리스트 모든 원소 출력
링크드 리스트 원소 찾기/추가
링크드 리스트의 노드에는 들어간 값과 다음 연결된 노드가 무엇인지 (포인터)에 대해 속성을 넣어준다.
Node class 생성
class Node:
def __init__(self, data):
self.data = data
self.next = None
box_1 = Node(3)
box_2 = Node(4)
box_1.next = box_2
print(box_1)
print(box_1.data)
print(box_1.next)
print(box_1.next.data)
클래스를 만들면 노드에 정보를 넣는일을 일일이 반복하지 않아도 된다.
단순 반복을 줄여주는 링크드 리스트 클래스를 만들어보자
꼭 가지고 있어야할 정보는 맨 앞칸 정보이다. head node 만 가지고 있다.
그 외에는 옆으로 옆으로 넘어가면서 확인할 수 있기 때문이다.
1) linkedlist는 self.head에 시작하는 노드를 저장한다
2) 다음 노드를 보기위해서는 각 노드의 next를 조회해서 찾아간다.
줄 옮기기 단축기 ctrl + shif + 방향
링크드 리스트 class 생성
1. 위에 생성된 클래스 Node로 객체 속성을 data 와 next를 만들어준다.
2. 그 노드를 다시 클래스 linkedlist로 head라는 객체속성을 만든다.
프린트 해보면 linked 클랙스 객체속성 안에 Node 객체 속성이 들어있고 그것 안에 데이터가 있다는 것을 확인해볼 수있다.
append 메소드 링크드 리스트 클래스에 만들기
return은 함수가 종료되었다는 의미, 함수내의 변수나 어떤 값을 돌려주는 역할을 한다.
해당함수를 정상적으로 끝내고 운영체제에 값을 반환하고 현재 실행중이 해당함수를 벗어나겠다는 뜻
메소드 1. 새로운 노드를 만드는 append
메소드 2. 모든 노드들을 프린트해주는 print_all
링크드 리스트 원소 찾기 / 원소 추가/원소 삭제하기
index가 0일 경우에 index가 -1이 되버리는데 그 때는 어떻게 해야하나?
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self, value):
self.head = Node(value)
def append(self, value):
cur = self.head
while cur.next is not None:
cur = cur.next
cur.next = Node(value)
def print_all(self):
cur = self.head
while cur is not None:
print(cur.data)
cur = cur.next
def get_node(self, index):
node = self.head
count = 0
while count < index:
node = node.next
count += 1
return node
def add_node(self, index, value):
new_node = Node(value)
if index == 0:
new_node.next = self.head
self.head = new_node
return
node = self.get_node(index -1)
next_node = node.next
node.next = new_node
new_node.next = next_node
def delete_node(self, index):
if index == 0:
self.head = self.head.next
return
node = self.get_node(index -1)
node.next = node.next.next
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.add_node(0,3)
linked_list.delete_node(1)
linked_list.print_all()
06. 링크드 리스트 문제
9) ✍️ 두 링크드 리스트의 합 계산
에러가 났을 때 파란색으로 나온 줄을 선택하면 에러가 난 줄로 갈 수 있다.
클래스 내부 함수를 이용할 때
self.함수명() 을 쓰면 된다.
def get_linked_list_sum(linked_list_1, linked_list_2):
sum_1 = 0
head_1 = linked_list_1.head
while head_1 is not None:
sum_1 = sum_1*10 + head_1.data
head_1 = head_1.next
sum_2 = 0
head_2 = linked_list_2.head
while head_2 is not None:
sum_2 = sum_2 * 10 + head_2.data
head_2 = head_2.next
return sum_1 + sum_2그런데 여기서 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):
sum = 0
head = linked_list.head
while head is not None:
sum = sum*10 + head.data
head = head.next근데 sum이라는 이름이 별로 좋은 이름이 아님 (내장함수에도 있어서 그런듯)
아래는 다른이름으로 바꿔주었다.
def get_linked_list_sum(linked_list_1, linked_list_2):
linked_list_sum_1 = _get_linked_list_sum(linked_list_1)
linked_list_sum_2 = _get_linked_list_sum(linked_list_2)
return linked_list_sum_1 + linked_list_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_sum07. 이진 탐색
이진 탐색 binary search vs 순차 탐색 sequential search
이진 탐색은 중간을 숫자를 찍어서 업 다운 해가면서 목표 숫자찾기
순차 탐색은 처음부터 하나하나 비교해가면서 찾기
순차탐색 코드
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):
for number in array:
if target == number:
return True
return False
result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result) # True이진탐색 코드
// 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있습니다.
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)
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 = array[current_guess] + 1
else:
current_max = array[current_guess] -1
current_guess = (current_min + current_max) //2
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)
순차탐색과 이분탐색의 시간 복잡도 비교
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):
for number in array: # 배열 길이 N만큼 연산
if target == number: 비교 1
return True
return False
result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result) # TrueO(N)을 가진다.
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 대입 1
current_max = len(array) 대입 1
current_guess = (current_min + current_max) // 2 대입 1
while current_min <= current_max: 비교 1
if array[current_guess] == target: 비교 1
return True
elif array[current_guess] < target: 비교 1
current_min = array[current_guess] + 1 대입 1
else:
current_max = array[current_guess] -1 대입 1
current_guess = (current_min + current_max) //2 대입 1
return False
result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)O(상수)
N/2k= 1
N = 2k
k = log2 N
O(logN) 아래의 조그만 2는 상수라서 의미 없기 때문에 이렇게만 표기한다.
티스토리 html 모드에 들어가서
<sup></sup> - 윗첨자
<sub></sub> - 아랫 첨자
무작위 수 찾기
Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 2이 존재한다면 True 존재하지 않는다면 False 를 반환하시오.
이 문제를 통해 이진 탐색의 전제 조건은 순서대로 배열 되어 있을 때라는 것을 깨달았다.
finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]
sorting_numbers = sorted(finding_numbers)
def is_exist_target_number_binary(target, array):
current_min = 0
current_max = len(array)
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 = array[current_guess] + 1
else:
current_max = array[current_guess] - 1
current_guess = (current_min + current_max) // 2
return False
result = is_exist_target_number_binary(finding_target, sorting_numbers)
print(result)
08. 재귀 함수 - 1
재귀란? recursion
어떠한 것을 정의할 때 자기 자신을 호출하는
Q. 60에서 0까지 숫자를 출력하시오.
근데 무한 루프에 빠지면 recursion error 이라고 띄워주면서 파이썬에서 자동으로 멈춰준다.
def count_down(number):
if number > 0:
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60)
count_ down 안에 count_down 들어있는 걸 볼 수 있다.
09. 재귀 함수 - 2
팩토리얼
3! 3*2*1
4! = 4 * 3!
factorial(n) = n* Factorial(n-1)
def count_down(number):
if number < 0:
return
print(number) # number를 출력하고
count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
count_down(60)함수 안에 자기 자신을 이용하는 것
일반 반복문 썻던 답
def factorial(n):
total = 1
while n > 0:
total = total * n
n -= 1
return total
print(factorial(6))재귀함수 이용한 답
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
print(factorial(6))회문 검사
일반 반복문으로 쓴 코드
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))
재귀함수를 이용한 코드
input = "abcba"
def is_palindrome(string):
if len(string) <= 1:
return True
if string[0] != string[-1]:
return False
return is_palindrome(string[1:-1])
print(is_palindrome(input))
재귀함수는 반복되는 것이 있고 줄어든다는 특징이 있다.
티스토리 임시저장 기능 좀 거지 같다... 어제만 해도 3번은 날려먹은듯
한번 발행하고 나서는 임시저장 안되는것도 불편
임시저장한걸 불러오는게 자동으로 되는거 말고, 그냥 내가 선택해서 임시저장 불러오기가 있었으면 좋겠는데
자꾸 빈 화면 자동으로 불러오고 내가 임시저장한건 날라가있다. 네이버에서는 됐었던 것 같은데
10. 2주차 끝 & 숙제 설명
Q1. 링크드 리스트 끝에서 K 번째 값 출력하기
Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오.
Q2. 배달의 민족 배달 가능 여부
Q. 배달의 민족 서버 개발자로 입사했다. 상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다. 그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.
Q3. ✍️ 더하거나 빼거나
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이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.