시간복잡도 정리 최악 평균 최선 1. 삽입정렬 n^2 n^2 n 2. 선택정렬 n^2 n^2 n^2 3. 버블정렬 n^2 n^2 n^2 4. 퀵정렬 n^2 nlog(n) nlog(n) 5. 힙정렬 nlog(n) nlog(n) nlog(n) 6. 병합정렬 nlog(n) nlog(n) nlog(n) 1. 삽입정렬 - 앞에서 부터 순차적으로 선택하고 적절한 위치에 삽입 하는 정렬 방법 - 시간복잡도 최악 평균 최선 n^2 n^2 n 2. 선택정렬 - 가장작은(혹은큰) 값부터 선택해서 순차적으로 나열하는 것 - 시간복잡도 최악 평균 최선 n^2 n^2 n^2 3. 버블정렬 - 인접한 두 값을 서로 비교하여 교체하는 작업을 앞에서 부터 순차적으로 진행 - 시간복잡도 최악 평균 최선 n^2 n^2 n^2 4. 퀵정..

heap의종류 2가지 최대힙 : 부모노드가 자식노드보다 크거나 같음(root node에 최댓값) 최소힙: 부모노드가 자식노드보다 작거나 같음(root node에 최솟값) ​ * 직접 구현한 힙 # unsorted : heap으로 만들고자하는 리스트 # index : 아래로 내려가며 heap을 만들기 시작하는 노드 (해당 index의 자식노드들은 모두 heapify된다) def heapify(unsorted, index, heap_size): smallist = index left_index = 2 * index + 1 right_index = 2 * index + 2 if left_index < heap_size and unsorted[left_index] < unsorted[..

1. 아래가 없거나 ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ​ 2. "\n"대신 endl이 들어가면 시간초과 #include #include #include using namespace std; int N, M, temp; set s; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> N; for (int i = 0; i > temp; s.insert(temp); } cin >> M; for (int i = 0; i > temp; cout

1. M에서 글자가 들어오면 index를 찾는 방식으로 구현했을때 시간초과가 발생. import sys N,M=map(int,input().split()) L=[] for i in range(N): L.append(sys.stdin.readline().rstrip()) for i in range(M): temp=sys.stdin.readline().rstrip() try: temp=int(temp)-1 print(L[temp]) except: print(L.index(temp)+1) 2. dictionary를 이용하여 key를 찾는 형식으로 했을 때 통과 import sys N,M=map(int,input().split()) dic1={} dic2={} for i in range(N): name=sys...

list는 set과 dictionary 보다 요소를 찾는 속도가 느리다. ​ 1. list(시간초과) N,M=map(int,input().split()) L=[] for i in range(N): L.append(input()) ans=0 ansL=[] for i in range(M): temp=input() if temp in L: ans+=1 ansL.append(temp) L.remove(temp) print(ans) for i in sorted(ansL): print(i) 2. set(통과) N,M=map(int,input().split()) s=set() for i in range(N): word=input() s.add(word) ans=0 ansS=set() for j in range(M):..

0. 기억해 실버3 이지만, stack을 생각하지못하면 풀 수 없는 문제임. 커서가 나오면 보통 스택을 쓴다고 하니 유념할것 ​ 1. 리스트 하나 (시간초과) (1) cursur변수를 따로두고, 리스트하나로 풀때. (2) insert와 del를 위해 리스트를 처음부터 끝까지 탐색해야하기 때문에 시간초과. import sys T=int(input()) for t in range(T): word = sys.stdin.readline().rstrip() size = len(word) cursur = 0 nowWord=[] for i in range(size): if word[i]=="": if cursur0: del nowWord[cursur-1] cursur-=1 else: if cursur==len(now..

1. 생각 수열의 연속합 중에서 특정 숫자를 만족하는 연속합을 찾는다. (1) 수열의 요소들이 모두 양수가 아니기 때문에, 투포인터는 쓸 수 없고, (2) N이 최대 200,000이므로 O(N)으로 끝내야한다. ​ 2. 풀이 (1) 수열의 누적합을 계속해서 구한다. (S[i] : 0에서부터 i까지의 누적합) ​ (2) i번째 숫자를 포함하는 연속합 중 K값이 되는 경우의 수는 S[i]-S[x]=K 를 만족하는 x의 개수와 같다. (즉 S[x]=S[i]-K 를 만족하는 x의 경우의 수.) ​ (3) d라는 map을 관리하여 이를 바로 찾아준다 (d[a]=c : 누적합이 a가 되는 경우가 c개) ​ 3. 소스코드 N,K=map(int,input().split()) L=list(map(int,input().s..