자료구조와 알고리즘 - 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

목표 : 피보나치 수열 구현

• 재귀

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

• 반복문

  	```python
  	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)