/ 알고리즘 더 풀어보기 (2)
input = "abadabac"
def find_not_repeating_first_character(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
not_repeating_character_array = []
for index in range(len(alphabet_occurrence_array)):
alphabet_occurrence = alphabet_occurrence_array[index]
if alphabet_occurrence == 1:
not_repeating_character_array.append(chr(index + ord("a")))
## 기존 문자열 순서 보장해주지 않는다
for char in string:
if char in not_repeating_character_array:
## 반복하지않는 알파벳 array에 string을 순서대로 대조해서 일치하면 바로return
return char
return "_"
result = find_not_repeating_first_character
print("정답 = d 현재 풀이 값 =", result("abadabac"))
print("정답 = c 현재 풀이 값 =", result("aabbcddd"))
print("정답 =_ 현재 풀이 값 =", result("aaaaaaaa"))/ 어레이와 링크드리스트
어레이
배열은 각 원소에 즉시 접근할 수 있습니다(상수시간내 접근가능)
, 원소의 순서는 0부터 시작하고 이를 인덱스라고 부릅니다
ex) rooms[0]
배열은 원소를 중간에 삽입/삭제 하려면 모든 원소를 다 옮겨야 합니다
어레이(배열)는 크기가 정해진 데이터의 공간입니다. 한 번 정해지면 바꿀 수 없어요
원소를 새로 추가하려면, 새로운 공간을 할당해야 하므로 매우 비효율적인 자료구조입니다.
링크드 리스트
크기가 정해지지 않은 데이터의 공간이다, 연결 고리로 이어주기만 하면, 자유자재로 늘어날 수 있습니다
특정 원소에 접근하려면 연결 고리를 따라 탐색해야 합니다
최악의 경우에는 모든 화물 칸을 탐색해야 하므로 O(N)의 시간 복잡도를 가집니다
( 연결 고리를 포인터라 부르고, 각 화물 칸을 노드라 부름 )
리스트는 원소를 중간에 삽입/삭제 하기 위해서는 앞 뒤의 포인터만 변경하면 됩니다
따라서 원소 삽입/삭제를 O(1) 상수시간내 의 시간 복잡도 안에 할 수 있습니다
정리
특정원소 조회 -
어레이 : 인덱싱이용 / 상수시간O(1)내에 조회할수 있다
링크드 리스트 : 상수시간O(N) 이 걸림
중간에 삽입,삭제 -
어레이 : 상수시간O(N) 이 걸림
링크드 리스트 : 단순히 포인트만 변화 / 상수시간O(1)걸린다
데이터 추가 -
어레이 : 새로운 공간 할당받아야함 (비효율)
링크드 리스트 : 모든공간이 다 찼어도 맨뒤의 노드만 동적으로 추가하면된다 (효율)
정리 -
어레이 : 데이터에 접근하는 경우 빈번하다면 유리함
링크드 리스트 : 삽입과 삭제가 빈번하다면 유리함
Python 의 list 는 array 로 구현
append 메소드를 사용해 새로운 배열을 생성하게 될때, 내부적으로 동적 배열이라는 걸 사용해서, 배열의 길이가 늘어나도 O(1) 의 시간 복잡도가 걸리도록 설계
파이썬의 배열은 링크드 리스트로 쓸 수도 있고,
배열로도 쓸 수 있게 만든 효율적인 자료구조다! 라고만 생각해주시면 됩니다.
/ 클래스
클래스는, 분류 집합 같은 속성과 기능을 가진 객체를 총칭하는 개념
객체는, 세상에 존재하는 유일무이한 사물
클래스에는 생성자(Constructor)라는 게 있는데 객체를 생성할 때 데이터를 넣어주거나, 내부적으로 원하는 행동을 실행하게 할 수 있습니다
( 파이썬에서 생성자 함수의 이름은 init 으로 고정 / self 는 객체 자기 자신을 가리킵니다)
def __init__(self): self 를 사용해서 객체에 데이터를 쌓을 수가 있습니다.
self.name 에 param_name 을 저장해두겠다는 건
그 객체의 name 이라는 변수에 저장된다는 의미입니다
class Person:
def __init__(self, param_name):
print("hihihi", self)
self.name = param_name
person_1 = Person("유재석") # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
print(person_1.name) # 유재석
person_2 = Person("박명수") # # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!
print(person_2.name) # 박명수 클래스 내부의 함수는 메소드(method) 라고 부릅니다
각 객체의 변수를 사용해서 메소드를 구현할 수 있습니다
class Person:
def __init__(self, param_name):
print("hihihi", self)
self.name = param_name
def talk(self):
print("안녕하세요 저는", self.name, "입니다")
person_1 = Person("유재석") # hihihi <__main__.Person object at 0x1067e6d60> 이 출력됩니다!
print(person_1.name) # 유재석
person_1.talk() # 안녕하세요 저는 유재석 입니다
person_2 = Person("박명수") # # hihihi <__main__.Person object at 0x106851550> 이 출력됩니다!
print(person_2.name) # 박명수
person_2.talk() # 안녕하세요 저는 박명수 입니다링크드 리스트 구현 - 1
노드는 아래 두 가지 정보가 필요합니다.
1) 칸에 있는 데이터 / 2) 다음 칸이 뭔지 ex) ["기관실"] ->
두가지 데이터를 묶기위해 "클래스" 사용
class Node:
def __init__(self, data):
self.data = data
self.next = None
# 3을 가진 Node 를 만드려면 아래와 같이 하면 됩니다!
node = Node(3) # 현재는 next 가 없이 하나의 노드만 있습니다. [3]클래스의 생성자에 data 를 인자로 받아서 self.data 에 저장
현재는 다음 이어진 노드가 없기 때문에 self.next 에는 None
노드를 만들어 연결해보자
first_node = Node(5) # 현재는 next 가 없이 하나의 노드만 있습니다. [5]
second_node = Node(12) # [12] 를 들고 있는 노드를 만듭니다.
first_node.next = second_node # 그리고, [5]의 next 를 [12]로 지정합니다. [5] -> [12]/ LinkedList
이걸 다만들수 없으니 LinkedList 클래스 만들어 사용한다
( self.data에 시작하는 head노드만 지정한다 )
1) LinkdList 는 self.head 에 시작하는 노드를 저장한다.
2) 다음 노드를 보기 위해서는 각 노드의 next 를 조회해서 찾아가야 한다.
class LinkedList:
def __init__(self, value):
self.head = Node(value) # self.data에 시작하는 head노드만 지정한다
linked_list = LinkedList(5)
print(linked_list.head.data) # 5가 출력됩니다!
# 현재 LinkedList 는 (5) 만 존재합니다!/ append 함수
/ 링크드 리스트 모든 원소 출력
LinkedList 의 맨 뒤에 새로운 Node 를 붙이는 append 함수
가지고 있는 데이터 head노드 밖에없음, head노드 따라서 맨뒤노드까지 이동하여 새로운 노드 붙여준다
head
[3] → [5] → [6] → [8]
head를 변경할 수 없으니 cur이라는 변수를 이용한다
cur
[3] → [5] → [6] → [8]
class Node:
def __init__(self,data):
self.data = data
self.next = None
class LinkedList:
def __init__(self,data):
self.head = Node(data)
def append(self,data): ## 원소 추가 append 함수
if self.head is None: # head가 None일때
self.head = Node(data) # head값에 append할 데이터를 넣고 return(위로 돌아가라)
return
cur = self.head
while cur.next is not None: # cur.next가 None이 아닐때까지 실행해라 -> cur.next가 None이면 while문 중단
cur = cur.next # while문 실행중이면 cur는 cur.next로 계속 바꾼다
cur.next = Node(data) # while문 중단되면 cur.next를 Node(data)로 한다
def print_all(self): ## 모든 원소 출력 print_all
cur = self.head
while cur is not None: # cur 가 None이 아닐때까지 실행하라
print(cur.data) # cur의 데이터를 프린트하라
cur=cur.next # while문 실행중이면 cur는 cur.next로 계속 바꾼다
linked_list = LinkedList(3) # [3]
linked_list.append(8) # [3] -> [8]
linked_list.print_all() # 결과 3 8
링크드 리스트 구현 - 2
/ 링크드 리스트 원소 찾기 / 원소 추가
링크드 리스트 원소 찾기
def get_node(self,index): # index번째 원소를 찾아야함
count = 0
Node = self.head
while count < index:
Node = Node.next
count += 1
return Node링크드 리스트 원소 추가
def add_node(self,index,value):
if index == 0: # new node를 head node로 할때 예외처리
new_node = Node(value)
new_node.next = self.head
# new node의 다음으로 head node올 것이라 지정해줌 (안하면 기존head사라짐)
self.head = new_node
# 그 후에 new node를 head node로 지정 (linked_list 클래스는 head node 있어야함)
return
new_node = Node(value) # 새로운 노드 지정
node = self.get_node(index-1)
# 새로운 노드가 붙을 노드 (index-1 번째해야 새로운 노드가 index번째 노드가 된다)
next_node = node.next
# 새로운 노드 다음에 올 노드(기존 노드옆에 있던 노드)
node.next = new_node
# 기존노드 옆에 새노드
new_node.next = next_node
# 새노드 옆에 기존노드옆에 있던 노드
return
linked_list = LinkedList(5)
linked_list.append(12)
linked_list.append(8)
# [5] -> [12] -> [8]
# [5] -> [6] -> [12] -> [8]
linked_list.add_node(1,6)
linked_list.print_all()/ 링크드 리스트 원소 삭제
링크드 리스트 원소 삭제
def delete_node(self, index):
if index == 0 : # (예외처리)
# self.head = self.head.next # 수업에서 알려준 예외처리 깔끔한듯
self.head = self.get_node(1) # 내가한건데 맞는지모르겟음
return
node = self.get_node(index-1) # 제거할 노드가 두번째이면 첫번째 노드선택
node.next = node.next.next # 첫번째 노드의 다음노드(두번째) = 첫번째노드의 다음다음노드(세번째)
return/ 링크드 리스트 문제
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 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 = 10 * sum_1 + 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 = 10 * sum_2 + head_2.data
head_2 = head_2.next
return sum_1 + 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))/ 이진탐색
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)