공부하는 스누피

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV141176AIwCFAYD&categoryId=AV141176AIwCFAYD&categoryType=CODE&problemTitle=%EC%82%AC%EC%B9%99%EC%97%B0%EC%82%B0&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1 SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 생각과정 - 연산이 가능한 조건 1: 리프 노드는 무조건 숫자여야 한다. - 연산이 가능한 조건 2:..

이진 탐색 트리가 편향 트리이면 최악의 경우 O(h)의 시간복잡도를 가진다. 항상 O(logh)의 시간복잡도를 유지하려면 트리의 균형을 맞추어야 한다. AVL 트리는 균형 잡힌 트리 중 하나이다. AVL 트리에서는 균형의 정도를 표현하기 위해 균형 인수를 사용한다. 균형 인수는 왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이이다. 균형을 잡기 위해 트리를 재조정할 때, 균형 인수의 절댓값이 크면 클수록 트리의 균형이 무너진 상태이다. 균형 인수의 절대값이 1 이하여야 균형 잡힌 트리라고 할 수 있다. 트리의 균형을 잡는 방법은 Rebalancing, Refactoring 등으로 부른다. 재조정이 필요한 상태는 크게 4가지이다. 1) Left Left 상태 루트 노드의 균형 인수가 +2인 경우. 왼쪽 서브..

선택 정렬 - 가장 작은 데이터를 앞으로 보내는 과정을 N-1번 반복한다. - 시간복잡도는 O(N^2)이다. => 배열 순회하는 반복문(N) + 가장 작은 데이터를 찾는 반복문(N-1+N-2+...+2) = N * (N+1) / 2 1) 바꿀 데이터의 인덱스를 i라 하고, 0(맨 앞)으로 초기화한다. 2) 가장 작은 데이터를 선택해 i 인덱스의 데이터와 바꾼다. 3) 그다음 작은 데이터를 선택해 i+1 인덱스에 있는 데이터와 바꾼다. 4) i가 배열의 마지막에 도착할 때까지 반복한다. def selection(arr): for i in range(len(arr)): min_index = i for j in range(i+1, len(arr)): if arr[i] > arr[j]: min_index = j..

(참고) www.geeksforgeeks.org/trie-insert-and-search/ Trie | (Insert and Search) - 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 Trie는 reTrieval data structure을 의미하며, 검색 복잡도가 최적의 값이 되게 해줍니다. 만약 우리가 k..

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..