학습내용
- 어레이
- 링크드리스트
- 클래스로 데이터 관리하기
- 이진 탐색
- 재귀 함수
어레이(Array)
길이와 순서가 정해져 있는 배열
읽기 : O(1)
배열의 길이에 상관 없이 특정 요소를 읽어내는 속도는 동일하기 때문에 많은 자료를 읽기에 적합
검색 : O(N)
최악의 경우 모든 자료를 다 조회해봐야 하므로 배열의 길이만큼의 시간이 소요
ex) 선형검색
삽입 및 삭제
데이터를 마지막에 삽입/삭제하는 경우에는 간단히 처리 가능하지만 그 외에는 데이터를 삽입하기 위해 공간을 마련하거나 빈 공간을 제거해야 하므로 다른 데이터들의 이동이 필요
링크드리스트(Linked List)
크기가 정해지지 않은 데이터의 공간. 이 공간을 노드라고 지칭하며 노드를 이어주는 것을 포인터라고 부른다. 노드 안에는 노드에 해당되는 데이터와 노드가 가리키는 포인터 정보가 들어있다.
읽기 : O(N)
특정 요소에 접근하기 위해선 포인터를 따라 탐색. 최악의 경우 모든 노드를 탐색해야 하므로 배열의 길이만큼의 시간이 소요
삽입 및 삭제 : O(1)
다른 데이터를 이동시킬 필요 없이 포인터의 앞뒤만 변경하면 되기 때문에 삽입/삭제 작업에 용이
클래스로 데이터 관리하기
노드 생성
노드에는 칸에 있는 데이터와 다음 칸 정보가 담겨 있어야 하는데 클래스를 사용하면 두 가지 데이터를 한꺼번에 생성하고 관리할 수 있다.
class Avenger:
def __init__(self, info):
self.info = info
self.next = None
firstAvenger = Avenger("아이언맨")클래스를 사용해서 아이언맨을 가진 Node를 생성했다. 다음에 이어진 노드가 없으므로 self.next의 값은 None인 상태다.
💡 자바스크립트에서는 생성자 함수가
new+(대문자로 시작하는 이름)으로 이뤄졌지만 파이썬에서는__init__으로 고정되어있다.
secondAvenger = Avengers("캡틴아메리카")
firstAvenger.next = secondAvengersecondAvenger를 생성 후 firstAvenger와 연결해준 상태. 이런식으로 노드를 무한히 생성할 수 있지만 매번 이 과정을 반복해야 하기 때문에 비효율적이다.
링크드리스트로 관리하기
시작하는 노드, 즉 헤드노드만 저장 후 next로 다음 노드를 조회하는 방식. 이 방식으로 관리하면 노드에서 했던 번거로운 작업을 생략할 수 있다.
-
헤드노드 생성
class Marvel: def __init__(self, info): self.head = Avenger(info) avengers = Marvel("아이언맨") print(avengers.head.info) > 아이언맨 -
노드 추가
append함수를 사용해서 링크드리스트 마지막에 새로운 노드를 추가한다.class Marvel: def __init__(self, info): self.head = Avenger(info) def append(self, info): if self.head is None: self.head = Avenger(info) return cur = self.head while cur.next is not None: cur = cur.next cur.next = Avenger(info)새로운 노드를 추가하려면 헤드가 마지막 노드까지 도달해야 한다. 그러나 헤드노드자체는 변경이 불가능하므로
cur이라는 변수를 지정해서 이동한다.cur.next의 값이None이라면 다음 노드가 없다는 의미이므로 이때 노드를 추가한다.avengers = Marvel("아이언맨") avengers.append("캡틴아메리카") avengers.append("토르") avengers.append("헐크")아이언맨👉🏻캡틴아메리카👉🏻토르👉🏻헐크 -
모든 요소 반환
def printAll(self):
cur = self.head
while cur is not None:
print(cur.info)
cur = cur.next노드 추가 원리와 비슷하다. cur라는 변수로 노드를 이동하면서 데이터를 출력한다.
index 관리하기
-
index번째 요소 반환
def getAvenger(self, index): avneger = self.head count = 0 while count < index: avenger = avenger.next count += 1 return node print(avengers.getAvenger(2).info) > 토르 -
index번째 요소 추가
def addAvenger(self, index, newAvenger): new_avenger = Avenger(newAvenger) # 0번째 요소에 추가할 경우 if index == 0: new_avenger.next = self.head self.head = new_avenger return # index번째 요소와 기존 요소간 교통정리 작업 avenger = self.getAvenger(index-1) nextAvenger = avenger.next avenger.next = new_avenger new_avenger.next = nextAvenger avengers = Marvel("아이언맨") avengers.append("캡틴아메리카") avengers.append("토르") avengers.append("헐크") avengers.addAvenger(2, "블랙위도우") avengers.printAll() > 아이언맨 캡틴아메리카 블랙위도우 토르 헐크self.getAvenger(index)를 호출시 데이터가index번째가 아닌 그 다음에 추가되기 때문에self.getAvenger(index-1)를 호출해야 한다.
또한 0번째 요소에 추가하는 경우엔get_node(-1)이 호출되므로self.head에 새로운 요소를 할당하고 나머지 요소의 순서를 한 칸씩 뒤로 미룬다. -
index번째 요소 제거
def deleteAvenger(self, index): if index == 0: self.head = self.head.next return avenger = self.getAvenger(index-1) avenger.next = avenger.next.next avengers = Marvel("아이언맨") avengers.append("캡틴아메리카") avengers.append("토르") avengers.append("헐크") avengers.addAvenger(2, "블랙위도우") avengers.addAvenger(3, "호크아이") avengers.deleteAvenger(3) avengers.printAll() > 아이언맨 캡틴아메리카 블랙위도우 토르 헐크
이진탐색(Binary Search)
탐색하고자 하는 데이터를 전체 데이터의 중간값과 비교해서 탐색하는 방법. 정렬된 배열에서만 사용 가능하기 때문에 데이터를 삽입/삭제할 때 오랜 시간이 소요되지만 대신 정렬 작업이 끝나면 빠른 검색이 가능하다.
재귀 함수
자기 자신을 호출하는 함수. 특정 구조가 반복되는 양상을 띄는 문제 해결에 효과적이다. 단, 탈출 조건을 생성해줘야 한다. 그렇지 않으면 무한루프에 빠지게 된다.
이론을 이해하는 데에는 문제가 없지만 적용은 여전히 힘들다. 그렇지만 이제는 완벽히 이해하려는 욕심을 버리기로 했다. 전공자 출신인 팀원분 말로는 지금 배우고 있는 내용이 대학에서 한 학기동안 가르치는 과정이고 전공자들도 어려워하는 내용이라고 한다. 비전공자인 내가 단박에 이해하는 게 애초에 불가능한 일이다. 그래서 너무 스트레스 받지 않고 일단은 이론을 이해하는 정도로만 공부하고 문제를 해결할 때 해당 이론을 어떤식으로 적용해야 하는지 생각하는 연습을 하려고 한다. 대신 현재 내 수준에 맞게 백준에서 쉬운 난이도부터 매일 조금씩 문제를 풀어나갈 생각이다.
