[TIL] Day 1 - 자료구조와 알고리즘(1)

정렬 내장함수

1. list.sort() or sorted(list) 시간복잡도

O(N log N)
※ 병합 정렬 (merge sort), 힙 정렬(heap sort)과 동일

2. lambda key 값 정렬

# 문자열 길이 순으로 정렬
sorted(L,key = lambda x : len(x) )

# 특정 key값으로 정렬
L = [ {'k' : 1} , {'k' : 2 } ]
L.sort(key = lambda x : x['k'] )

재귀 함수 (Recursive Fn)

항상 종결 조건(Trivial case) 중요(★)

ex) 사탕 담기

# m = 총 담을 수 있는 크기, weight 각 캔디 무게
def candy(m, weights):
	
    # 종결 조건
    if m < 0 or len(weights) == 0 :
    	return 0
    if m == 0 :
    	return 1
    
    # 캔디 중 지금 제일 앞에 있는 캔디를 담는 경우 + 안 담는 경우
    return candy(m-weight[0], weights[1:]) + candy(m, weights[1:])

연결리스트 (Linked List)

• 추상적 자료구조로 연결리스트
  ex) 아이폰 최근 어플 리스트처럼 삭제 및 연결/추가 용이함
• 구현하기 편하도록 head에 dummy node 생성
• 정리 너무 잘해놓으신 링크 -> https://bit.ly/3vjYdJ1
• 양방향 연결리스트 개념 이해
  구현하기 편하도록 head, tail에 dummy node 생성

스택 (Stack)

1. 값을 꺼내지 않고 제일 위에 있는 값 알고 싶을 때

top = stack.peek()

2. 후위표현 수식 계산 중 '문자로 받은 숫자를 숫자로 변환'

def splitTokens(exprStr):
    tokens = []
    val = 0
    valProcessing = False
    for c in exprStr:
        if c == ' ':
            continue
        if c in '0123456789':
            val = val * 10 + int(c)
            valProcessing = True
        else:
            if valProcessing:
                tokens.append(val)
                val = 0
            valProcessing = False
            tokens.append(c)
    if valProcessing:
        tokens.append(val)

    return tokens

# eval() = 문자열이 식으로 들어오면 결과를 반환
# print( eval("1+2") ) -> 3

3. 짝을 맞추거나 괄호를 맞춰야 하는 문제는 스택으로 거의 풀이됨

# ex) 올바른 괄호 True or False
def solution(s):
    match = {
        ')' : '(',
        ']' : '[',
        '}' : '{'
    }
    stack = []
    for c in s :
        if c in '([{' :
            stack.append(c)
        else:
            if len(stack) == 0:
                return False
                
            temp = stack.pop()
            if temp != match[c] :
                return False
                
    return len(stack) == 0