공부하는 스누피

(출처) 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가 딕셔너리에 없..

https://nikos7am.com/posts/mutable-default-arguments/ Avoid using an empty list as a default argument to a function A very common error in Python is the use of an empty list as a default argument to a function. This is not the right way to do it and can cause unwanted behavior. See for example below: def append_to_list(element, list_to_append=[]): list_to_append.append( nikos7am.com 함수 인자로 리스트를 ..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 생각과정 - n이 1일 경우 0, 2일 경우 1, 3일 경우 1번의 연산으로 1을 만들 수 있다. - 일차원 배열을 만들어 인덱스값에 대한 최소 연산 횟수를 저장한다. - 4부터 n까지 순회하면서 최솟값을 구한다. (Bottom-Up 방식) - 먼저 3이나 2로 나누어 떨어지는지 확인한다. 나누어 떨어진다면, n/3 또는 n/2의 값에서 1을 더한 값을 배열에 저장한다. 앞에서 n/3의 최솟값을 구해 놓았으니 1을 더하기만 하면 된다. - 1을 빼는 연산은 2나 3으로 나누어 떨어지지 않을 때 수행하거나, 앞의..