어서와! 자료구조와 알고리즘은 처음이지? 정리 (1)

프로그래머스의 어서와! 자료구조와 알고리즘은 처음이지? 2-10강을 정리한 글입니다.

---

2강 선형배열

• 리스트의 연산: append , pop , del , index , insert

3강 정렬, 탐색

• 정렬
  • sorted(), .sort()
    • sorted는 함수, sort는 리스트의 메서드
  • reverse = True로 정렬 순서 뒤집기
  • lambda 함수를 통한 정렬: key = lambda x: len(x)
• 탐색
  • 선형탐색
  • 이진탐색
    • 탐색하려는 리스트가 이미 정렬되어 있는 경우에만

4-5강 재귀 알고리즘

• 종결 조건을 잘 설정해야 한다!
• 활용: 이진탐색, 팩토리얼, 피보나치
• 계속 함수를 호출하기 때문에 효율성이 떨어진다.

6강 알고리즘의 복잡도

• 시간복잡도, 공간복잡도

7-9강 연결리스트(Linked List)

• 추상적 자료구조: 원래 있는 데이터 타입은 아니지만, 데이터를 저장하고 특정한 방법의 연산을 제공하는 것
• 연결리스트: 다음 노드를 가리키고 있는 노드들의 배열

기본 구현

# 빈 노드
class Node:
    def __init__(self,item):
        self.data = item
        self.next = None

# 빈 연결리스트
class LinkedList:
    def __init(self):
        self.nodeCount = 0
        self.head = None # 첫 번째 노드를 가리킴
        self.tail = None # 마지막 노드를 가리킴
        self.head.next = self.tail # 맨 앞에 dummy node 추가할 수 있다

10강 양방향 연결리스트(Doubly Linked List)

• 뒤로는 이동 못하는 기존 연결리스트의 단점 극복한 것

기본 구현

class Node:
  def __init(self,item):
    self.data = item
    self.next = None 
    self.prev = None #추가

class DoublyLinkedList:
  def __init(self,item):
    self.nodeCount = 0
    self.head = None
    self.tail = None
    self.head.prev = None # 맨 앞, 맨 뒤에 dummy node 추가
    self.head.next = self.tail
    self.tail.prev = self.head
    self.tail.next = None