코딩 테스트 (29) 썸네일형 리스트형 [알고리즘 파이썬] 우선순위 큐(Priority Queue) - 데이터 추가는 어떤 순서로 해도 상관이 없음 - 제거될 때는 가장 작은 값부터 없앤다. - 내부적으로 데이터를 정렬된 상태로 보관하는 매커니즘 존재 (heapq 모듈 사용) - O(log n) 시간 복잡도 [클래스 임포트] => queue 내장 모듈에서 제공 from queue import PriorityQueue [우선순위 큐 생성] => 생성자를 이용해 우선순위 큐 초기화 que = PriorityQueue() * 우선순위 큐의 사이즈는 무한대 이므로 특정 크기를 설정하고 싶다면 maxsize=n 인자 추가 [우선순위 큐 원소 추가] => put 메서드를 통해 원소 추가 que.put(4) que.put(1) [우선순위 큐 원소 삭제] => get() 메서드를 이용해 원소 삭제 que.get() .. x만큼 간격이 있는 n개의 숫자 - JAVA class Solution { public long[] solution(int x, int n) { long[] answer = new long[n]; int temp = 0; for (int i=0; i 윈도우 함수 (Window Function) 행과 행 간의 관계 정의 순위, 합계, 평균, 행 위치 조절 Group by와 병행은 어려움 PARTITION 구문과 GROUP BY 구문은 둘 다 파티션을 분할 rows = 부분인 윈도우 크기를 물리적 단위로 행의 집합 지정 range = 논리적 주소에 의해 행 집합 지정 between ~ and = 윈도우 시작, 끝 unbounded preceding = 윈도우 시작 위치가 첫 번째 행 unbounded following = 윈도우 마지막 위치가 마지막 행 current row = 윈도우 시작 위치가 현재 행 [정렬 알고리즘 정리] [정렬] 선택정렬(Selection Sort) : -> 한바퀴를 돌며 가장 작은 수를 선택해 맨 앞으로 보낸다 -> 두 번째 값부터 한바퀴 돌며 가장 작은 수를 찾아 두 번째로 보낸다. 삽입정렬 : 데이터를 하나씩 확인하여 적절한 위치에 삽입하기 -> 필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 훨씬 효율적이다. 퀵정렬 : 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾼다. 계수정렬(counting sort) : * 각 데이터가 몇 번 등장했는지 그 횟수가 기록된다. * 인덱스값을 늘리고, 데이터 최댓값의 크기만큼 반복을 수행해야 한다. => 데이터의 범위만 한정되어 있다면 효과적으로 사용할 수 있으며 항상 빠르게 동작한다. * 기수행렬(Radix sort)과 .. 이것이 코딩 테스트다 :: 그래프 이론 크루스칼 알고리즘 -> 그리디 위상 정렬 알고리즘 -> 큐, 스택 자료구조 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 노드의 개수 V 간선의 개수 E 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식 ! 노드의 개수가 적은 경우 플로이드 워셜 알고리즘 이용 ! 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘 이용 [서로소 집합 자료구조] union-find 자료구조 [신장 트리(Spanning Tree)] 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건 [크루스칼 알고리즘] 최소한의 비용으로 신장 트리를 찾는 경우 최소 신장 트리 .. [프로그래머스 SQL] SQL_JOIN 1. 없어진 기록 찾기 [Inner Join] * select ~ from TABLEA a inner join TABLEB b on a.key = b.key => 입양 보낸 기록은 유실되지 않았기 때문에, ANIMAL_OUTS 테이블을 필수 테이블로 사용한다. [중첩 쿼리문] * select ~ from aniaml_outs where aninal_id not in ( select animal_id from aninal_ins ) [알고리즘 파이썬] DFS/BFS 탐색(Search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조(Data Structure) 데이터를 표현하고 관리하고 처리하기 위한 구조 그 중 스택과 큐는 자료구조의 기초 개념으로 삽입, 삭제의 핵심 함수로 구성된다. [알고리즘 파이썬] sort(), sorted() 차이 sort(), sorted() 차이 sort 함수는 list.sort() 형식으로 "리스트형의 메소드" 이며 리스트 원본값을 직접 수정. sorted 함수는 파이썬의 "내장 함수"이며 리스트 원본 값은 그대로이고 정렬 값을 반환한다. 이전 1 2 3 4 다음