일단 파이썬의 heapq 모듈은 min-heap이기 때문에 루트노드에 최소값이 위치하게 된다. **튜플 정렬을 이용. 예를 들어 arr = [(3, 4), (3, 1), (8, 5), (3, 2), (8, 7)] 이 있으면 arr.sort() 했을 때 튜플들의 0번째 기준으로 오름차순으로 먼저 정렬한 다음 1번째 인덱스 기준으로 정렬한 다음 보여준다. print(arr) >>> [(3, 1), (3, 2), (3, 4), (8, 5), (8, 7)] 이다. (적용과 해결) import heapq as hq, sys N = int(sys.stdin.readline()) pq = [] for i in range(N): x = int(sys.stdin.readline()) if x: hq.heappush(pq..
전체 글
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..
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()을 사용해줘야 한다.
import {useEffect, useState} from "react"; function App() { const [loading, setLoading] = useState(true); const [coins, setCoins] = useState([]); const [availMoney, setAvailMoney] = useState(0); const [selectedCoin, setSelectedCoin] = useState(0); const inputChange = (event) => setAvailMoney(event.target.value); const onChange = (event) => setSelectedCoin(event.target.value); useEffect(()=>{ fet..
간단한 ToDoList를 만들건데 .map 메서드의 기능을 사용할 것이다. 을 통해 toDo를 받을 것이고 얘네는 toDos란 array에 저장된다. form에 onSubmit을 줘서 기존 array를 ...array로 복사하고 맨 앞에 새로운 toDo를 추가해준다. toDos Array는 이렇게 만들어지고 이를 출력하기 위해 아래에 .map함수를 사용한다. map 함수는 배열 안의 각각의 항목에 대해 처리를 한 다음 다시 새로운 배열로 돌려준다. 이 예제를 예로 생각해보면 1,2,3,4,5를 toDo에 순서대로 추가해줬다고 치자. toDos = [5, 4, 3, 2, 1] 이렇게 되어있을 것이고 toDos.map( (toDo, index) => {toDo})를 실행하면 toDos안의 항목이 하나씩 돌면..