N = int(input()) stk = [] for i in range(N): stk.append(N-i) while stk: if len(stk) > 1: stk.pop() stk.insert(0, stk.pop()) else: print(stk.pop()) 이렇게 풀었는데 시간 초과였다. 스택이라고 생각하고 만들었지만 실상은 배열이기 때문에 시간복잡도가 N^2이 넘는다. 2초 안에 절대 안풀림. deque 모듈을 써보자. from collections import deque N = int(input()) dq = deque(range(1, N+1)) while len(dq) > 1 : dq.popleft() dq.append(dq.popleft()) print(dq.pop()) 이렇게 하면 224m..
알고리즘 문제풀이/Python3
T = int(input()) for i in range(T): stk = [] isVPS = True for ch in input(): if ch == '(': stk.append(ch) else: if len(stk) > 0: stk.pop() else: isVPS = False break if len(stk) > 0: isVPS = False print('YES' if isVPS else 'NO') 괄호가 쌍을 이루면 VPS다. 스택구조로 생각해야 한다. 여는 괄호가 무조건 먼저 들어가야 VPS를 이룰 수 있다. 여는 괄호가 들어가 있는 상태에서 닫는 괄호를 만나면 스택에 들어있는 여는 괄호를 삭제해준다. 스택이 비어있는데 닫는 괄호가 들어오면 isVPS를 False로 바꿔주고 반복문을 탈출하면 된..
1. Priority queue 파이썬은 min-heap이다. root-node에 최소값이 위치한다는 뜻. 삽입/삭제 시간복잡도는 logN이다. heapq 모듈은 thread-safe한 모듈은 아니지만 빠르다. import heapq pq = [] heapq.heappush(pq, 6) heapq.heappush(pq, 10) heapq.heappush(pq, -7) heapq.heappush(pq, 15) heapq.heappush(pq, -4) heapq.heappush(pq, 0) print(pq) while pq: heapq.heappop(pq) print(pq) 보면 최상단에 최소값이 위치할 뿐 나머지는 정렬이 되어있지 않다. 2. Dictionary key, value의 쌍을 이루는 구조. 다..
1. 배열 (Array) *삽입/삭제의 시간복잡도 O(N) -N개의 인덱스가 있을 때 맨 앞에 삽입할 경우 하나씩 전부 뒤로 밀려야 하기 때문에 N *탐색의 시간복잡도 O(1) -원하는 인덱스에 바로 접근이 가능하기 때문에 상수. *파이썬에서는 size 변경이 가능. 2. 연결 리스트 (Linked list) 두 부분으로 이루어진 리스트. data가 저장되어 있는 부분과 다음 데이터를 가리키는 포인터가 저장되어있는 link 부분으로 나뉘어 있다. 단순 연결 리스트, 이중 연결 리스트, 원형 연결 리스트가 있다. *삽입/삭제의 시간복잡도는 O(1) - 연결부분만 명시하면 된다. *탐색의 시간복잡도 O(N) - 어떤 자료를 찾으려면 링크를 타고타고 들어가야 한다. 3. 스택 (Stack) - 후입선출 구조 ..
import sys T = int(sys.stdin.readline()) for i in range(T) : a, b = map(int, sys.stdin.readline().split()) print(a+b) 빠른 입력을 위해 input 대신 sys.stdin.readline()을 사용해줘야 한다.
