내배캠 TIL 14일차

1. 알고리즘 특강

1) 자료구조 - 빅 오 표기법(Big O Notation)에 따른 효율성

(1) 배열

- 검색 : O(1) -------------> 최악의 경우에도 자료를 단번에 찾는다.
- 추가/삭제 : O(N) ------> 최악의 경우 자료를 찾는데 길이만큼 시간이 소요된다.

numpy array는 처리 속도가 굉장히 빠르다.
pickle이 파이썬에서 굉장히 유명하며 속도도 빠른편이다.

하지만 장점이 있으면 다른 부분에서 단점이 동반된다.

 

(2) 연결리스트

- 검색 : O(N) ----------> 최악의 경우 자료를 찾는데 길이만큼 시간이 소요된다.
- 추가/삭제 : O(1) ----> 최악의 경우에도 자료를 단번에 찾는다.

배열의 단점(추가, 삭제)을 해결하기 위해 고안 - 우열을 가리지는 않음.
추가/삭제 연산은 빠르지만 검색이 느리다.

 

(3) 큐(Queue)

- Queue는 줄서기.
- 먼저 들어온 값이 먼저 나감.

 

(4) 스택(Stack)

- 먼저 들어온 값이 나중에 나감.
- Stack 은 쌓기.
- 값 들어오는 것을 push.
- 빼는 것을 pop이라 함.

 

 

 

 

2. 개인과제

스택 - 올바른 괄호

주어진 문자열이 올바른 괄호면 True.
아니면 False를 리턴하는 함수를 짜라.

def solution(s):
    answer = True
    open = []
    close = []
    
    for letter in s:
        if letter == '(':
            open.append(letter)
        else:
            close.append(letter)
        
        if len(close) > len(open):
            answer = False
            break
    
    if len(open) > len(close):
        answer = False
        
    return answer​

 

이리 해서 프로그래머스는 통과 했지만 .
스택을 사용한 것은 아니기 때문에 조금 더 고심.

def solution(s):
    case = []
    
    for letter in s:
        if letter == '(':
        	case.append(letter)
       	else:
            if len(case) == 0:
                return False
            del case[-1]
            
    answer = True if len(case) == 0 else False
    
    return answer​

 

스택 강의 자료에서 제시했던  pop()을 사용해서
쌓고 지우는 방식을 차용해서 만들어 봤다.