공부하는 스누피

www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net 생각과정 - 방향이 있고, 사이클이 없는 그래프의 노드들을 정렬한다 -> 위상 정렬 구현 init = input().split() n = int(init[0]) m = int(init[1]) arr = [[] for i in range(n)] degree = [0 for i in range(n)] for i in range(m): l = list(map(int, input()..

(참고) en.wikipedia.org/wiki/Topological_sorting Topological sorting - Wikipedia In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the gra en.wikipedia.org 컴퓨터 과학에서 방향이 있는 그래프의 위상 정렬이란 그래프의 노드를 정렬한 것으로..

(출처) www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/ Kruskal’s Minimum Spanning Tree Algorithm | Greedy Algo-2 - GeeksforGeeks Minimum Spanning Tree for weighted, connected & undirected graph is a spanning tree with weight less than or equal to that of every other spanning tree. www.geeksforgeeks.org 최소 신장 트리는 무엇일까요? 방향이 없이 연결되어 있는 그래프에서 신장 트리(spanning tree)는 그래프의 모..

programmers.co.kr/learn/courses/30/lessons/64062#qna 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr (효율성 통과 x) 생각과정 - 길이가 k인 창문을 움직이는 방식으로 슬라이딩 윈도우를 구현했다. - 처음 위치의 창문 영역의 최댓값, 최솟값을 구한다. - 이동 전 첫번째 값이 최댓값이면 창문 영역의 최댓값을 새로 구한다. - 아니라면, 저장된 최댓값과 영역에 새로 들어온 값을 비교 후 큰 값을 최댓값으로 한다. - 창문 영역의 최댓값과 처음 연산한 최댓값을 비교 후 작은 값을 저장하고, 다음부터는 저장된 값과 비교한다. 구현 import sys def solution(stones..

(참고) www.geeksforgeeks.org/window-sliding-technique/ Window Sliding Technique - GeeksforGeeks A Computer Science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions. www.geeksforgeeks.org 슬라이딩 윈도우 기법 슬라이딩 윈도우 기법은 시간 복잡도를 줄이기 위해 중첩된 반복문을 어떻게 단일 반복문으로 바꿀 수 있는지..

퀵 정렬이란? Quick sort는 Divide and Conquer 알고리즘으로, 평균적으로 매우 빠른 수행 속도를 보여준다. 시간복잡도가 O(NlogN)으로 Merge sort와 동일하지만, 배열을 균등하지 않게 분할하고 추가적인 메모리 공간을 필요로 하지 않는다. 빠르고 메모리도 덜 차지하지만 pivot을 잘못 설정했을 경우, 최악의 경우에는 시간복잡도가 O(N^2)으로 다른 비효율적인 정렬 알고리즘보다 나은 것이 없다. 그래서 pivot의 위치에 큰 영향을 받지 않는 배열에 적합하다. pivot은 배열을 분할하는 기준점으로, pivot으로 나눠진 두 배열의 원소를 순서대로 꺼내 비교하면서 정렬한다. 원리 배열을 정렬하려면 먼저 3가지 변수를 설정해 두어야 한다. left: 배열 맨 왼쪽 인덱스. ..

합병 정렬이란? 합병 정렬(Merge sort)는 정렬 알고리즘으로, 주어진 배열을 두 개의 배열로 계속 분할한 뒤, 분할한 배열을 합치면서 정렬한다. 배열을 분할하는 과정에서 시간 복잡도 O(logN), 합치는 과정에서 O(N)을 가지므로 총 O(NlogN)의 시간 복잡도를 가진다. Quick sort, Heap sort처럼 시간 복잡도가 O(NlogN)이지만, 정렬을 위한 배열을 하나 더 생성하기 때문에 메모리를 더 많이 차지한다는 단점이 있다. 원리 배열 [4, 3, 2, 1]이 있고, 오름 차순으로 정렬한다고 해 보자. Merge sort는 분할을 먼저 수행하는데, 더 이상 나눠지지 않을 때까지 배열을 나눈다. 0: [4, 3, 2, 1] 1: [4, 3] [2, 1] 2: [4] [3] [2] ..

https://programmers.co.kr/learn/courses/30/lessons/17684 코딩테스트 연습 - [3차] 압축 TOBEORNOTTOBEORTOBEORNOT [20, 15, 2, 5, 15, 18, 14, 15, 20, 27, 29, 31, 36, 30, 32, 34] programmers.co.kr 생각과정 - 딕셔너리를 만들어 새로운 문자 패턴을 저장한다. - 주어진 문자열을 순회하면서 현재 입력된 문자가 딕셔너리에 있는지 확인하고, 없으면 추가한다. - 현재 입력된 문자의 다음 문자가 딕셔너리에 있는지 확인하고, 없으면 추가한다. 이때 현재 입력 문자에 다음 문자를 더한 패턴도 딕셔너리에 추가하고 다음 반복으로 바로 넘어간다. ex) 현재:A 다음:B일때, B가 딕셔너리에 없..