프로그래머스 강좌, 자료구조와 알고리즘 - 1

자료구조와 알고리즘 - 1 link

1강은 소개로 생략

2강. 선형 배열(Linear Array)

python 의 list는 자료형의 제한이 없음
O(1) 작업

• 원소 덧붙이기 .append()
• 원소 하나를 꺼내기 .pop()

O(n) 작업

• 원소 삽입하기 .insert()
• 원소 삭제하기 .del()

기타

• 원소 탐색하기: .index()

실습1

목표: 리스트 L 에서 오름차순에 맞게 x의 값을 삽입

def solution(L, x):
    for i, v in enumerate(L):
        if v > x:
            L.insert(i, x)
            break
    else:
        L.append(x)
    return L

실습2

목표: 리스트 L 에서 x 값의 index 반환, 부재시 -1 반환

def solution(L, x):
    answer = []
    for i, v in enumerate(L):
        if v == x:
            answer.append(i)
    if len(answer) == 0:
        answer.append(-1)
    
    return answer

3강. 정렬과 탐색(Sorting & Searching)

내장 정렬기능

1. 파이썬 내장 함수 sorted() - 정렬된 리스트 반환(deep copy)
2. 리스트에 쓸 수 있는 메서드 .sort() - 해당 리스트 정렬

역순 정렬(reverse)
reverse=true 를 매개변수로 전달
ex) sorted(L, reverse=true), L.sort(reverse=true)

정렬방식 지정(key)
java의 Comparator 와 유사. sorted(L, key=lambda x: len(x)) 로 사용시 L 리스트의 개체값의 문자열 길이가 짧은 순으로 정렬 진행. dictionary 자료형도 L.sort(key=lambda x:x['score'], reverse=true) 의 형태로 x[‘score’] 값이 큰순으로 정렬가능.

탐색 알고리즘

1. 선형 탐색(linear search) - 순차적으로 탐색과정 진행, O(n)
2. 이진 탐색(binary search) - 정렬되어있는 경우 가능, 절반씩 쪼개며 탐색, O(logn)

실습1

목표 : 효율성을 위해 이진탐색으로 오름차순 정렬된 배열에서 x의 index값을 반환, 부재시 -1 반환

def solution(L, x):
    low=0
    high=len(L)-1
    answer = 0
    while(low<=high):
        mid=(low+high)//2
        if L[mid]==x:
            answer = mid
            break
        elif L[mid]>x:
            high=mid-1
        else:
            low=mid+1
    else:
     return -1
    return answer

4강. 재귀 알고리즘(Recursive Algorithms) 기초

실습1

목표 : 피보나치 수열 구현

• 재귀

  def solution(x):
      answer = 0;
      if x <= 1:
          answer = x
      else:
          answer = solution(x-1) + solution(x-2)
      return answer
  

• 반복문

  def solution(x):
      answer = 0;
      if x <= 1:
          answer = x
      else:
          now = 1;
          before = 0;
          for i in range(1, x):
              answer = before + now
              before = now
              now = answer
      return answer
  

5강. 재귀 알고리즘(Recursive Algorithms) 응용

자원 효율: 재귀적 < 반복적

실습1

목표: 재귀적 이진탐색 구현

def solution(L, x, l, u):
    if x < L[l] or x > L[u]:
        return -1
    mid = (l + u) // 2
    if x == L[mid]:
        return mid
    elif x < L[mid]:
        return solution(L, x, l , mid - 1)

    else:
        return solution(L, x, mid + 1 , u)

6강. 알고리즘의 복잡도 (Comlexity of Algorithms)

점근적 표기법

• Big-θ : 평균적인 복잡도, θ(n) 로 표기
• Big-O : 최악의 경우 복잡도 (주로 사용), O(n) 로 표기
• Big-Ω : 최선의 경우 복잡도, Ω(n) 로 표기

정렬 알고리즘 예시 - 병합 정렬( merge sort)
정렬할 배열들을 각각 최소 비교단위로 분리하여 비교 -> O(logn)
정렬된 최소 비교단위 배열을 병합 - > O(n) => O(nlogn)

6강 실습. X

7강. 연결 리스트(Linked Lists) (1)

단방향 연결 리스트

다음 대상에 대한 주소를 참조하여 리스트를 구조화

• 특정 원소 참조 (k 번째)
• 리스트 순회 (list traversal)
• 길이 얻어내기

실습1

목표: linked list를 순회하며 각 노드값을 리스트로 만들어 반환하는 traverse 함수구현

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

    def getAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None
        i = 1
        curr = self.head
        while i < pos:
            curr = curr.next
            i += 1
        return curr

    def traverse(self):
        returnList = []
        target = self.head
        while target is not None:
            returnList.append(target.data)
            target = target.next
        
        return returnList

8강. 연결 리스트(Linked List) (2)

• 원소의 삽입 (insertion)
• 원소의 삭제 (deletion)
• 두 리스트 합치기 (concatenation)

9강.연결 리스트(Linked List) (3)

dummy node 를 linked list 의 head로 추가

class Node:
 def __init__(self, item):
  self.data = item
  self.next = None
  
class LinkedList:
 def __init__(self):
  self.nodeCount = 0
  self.head = Node(None)
  self.tail = None
  self.head.next = self.tail

 def __repr__(self):
  if self.nodeCount == 0:
   return 'LinkedList: empty'
   
  s = ''
  curr = self.head
  while curr.next:
   curr = curr.next
   s += repr(curr.data)
   if curr.next is not None:
    s += ' -> '
  return s

 def getLength(self):
  return self.nodeCount

 def traverse(self):
  result = []
  curr = self.head
  while curr.next:
   curr = curr.next
   result.append(curr.data)
  return result

 def getAt(self, pos):
  if pos < 0 or pos > self.nodeCount:
   return None
  i = 0
  curr = self.head
  while i < pos:
   curr = curr.next
   i += 1

  return curr

 def insertAfter(self, prev, newNode):
  newNode.next = prev.next
  if prev.next is None:
   self.tail = newNode
  prev.next = newNode
  self.nodeCount += 1
  return True

 def insertAt(self, pos, newNode):
  if pos < 1 or pos > self.nodeCount + 1:
   return False
  if pos != 1 and pos == self.nodeCount + 1:
   prev = self.tail
  else:
   prev = self.getAt(pos - 1)
  return self.insertAfter(prev, newNode)

 def concat(self, L):
  self.tail.next = L.head.next
  if L.tail:
   self.tail = L.tail
  self.nodeCount += L.nodeCount

실습1

목표: 노드를 뽑아내는 함수 구현

def popAfter(self, prev):
    curr = prev.next
    if prev.data is None:
        prev.next = curr.next
        self.tail = curr.next
    elif prev.next == self.tail:
        prev.next = None
        self.tail = prev
    else:
        prev.next = curr.next

    self.nodeCount -= 1
    return curr.data


def popAt(self, pos):
    if pos < 1 or pos > self.nodeCount:
        raise IndexError

    prev = self.getAt(pos - 1)
    return self.popAfter(prev)