코딩 테스트/알고리즘 (14) 썸네일형 리스트형 [알고리즘 파이썬] 우선순위 큐(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 이것이 코딩 테스트다 :: 그래프 이론 크루스칼 알고리즘 -> 그리디 위상 정렬 알고리즘 -> 큐, 스택 자료구조 노드와 노드 사이에 연결된 간선의 정보를 가지고 있는 자료구조 노드의 개수 V 간선의 개수 E 플로이드 워셜 알고리즘은 인접 행렬을 이용하는 방식 ! 노드의 개수가 적은 경우 플로이드 워셜 알고리즘 이용 ! 노드와 간선의 개수가 모두 많으면 우선순위 큐를 이용하는 다익스트라 알고리즘 이용 [서로소 집합 자료구조] union-find 자료구조 [신장 트리(Spanning Tree)] 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 성립 조건 [크루스칼 알고리즘] 최소한의 비용으로 신장 트리를 찾는 경우 최소 신장 트리 .. [알고리즘 파이썬] DFS/BFS 탐색(Search) 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정 자료구조(Data Structure) 데이터를 표현하고 관리하고 처리하기 위한 구조 그 중 스택과 큐는 자료구조의 기초 개념으로 삽입, 삭제의 핵심 함수로 구성된다. [알고리즘 파이썬] sort(), sorted() 차이 sort(), sorted() 차이 sort 함수는 list.sort() 형식으로 "리스트형의 메소드" 이며 리스트 원본값을 직접 수정. sorted 함수는 파이썬의 "내장 함수"이며 리스트 원본 값은 그대로이고 정렬 값을 반환한다. [알고리즘 파이썬] 다이나믹 프로그래밍 다이나믹 프로그래밍 * 큰 문제를 작은 문제로 나눠서 푸는 알고리즘 * Dynamic은 아무 의미가 없다. 1. DP (중복O) 2. 분할 정복 : Divide & Conquer (D&C) (중복X) overlapping subproblem : 부분문제가 겹치는 경우 -> 피보나치 수 optimal substrucure : 최적부분 구조 -> 문제의 정답을 작은 문제의 정답에서 구할 수 있다. -> 서울 대전 대구 부산 갈 때, 대전에서 부산가는 빠른 길은 대구를 거쳐야 한다. Top-down Bottom-up [알고리즘 파이썬] input 속도 높이기 input 자체가 굉장히 많기 때문에 input 함수로 풀면 시간 초과가 날 수 있다. 따라서 sys.stdin.readline()으로 바꿔서 푼다. # input 대신 사용 sys.stdin.readline() # 개행문자 제거, 한 줄 입력받아 출력하는 소스코드 sys.stdin.readline().rstrip() # input으로 가져온 값 형태 변환 map(int, sys.stdin.readline().split()) # String으로 받아서 한번에 map으로 형변환 하기 map(int, sys.stdin.readline().split()) [알고리즘 파이썬] 인접 행렬과 인접 리스트 그래프 용어 정리 경로 : 정점 A에서 B로 가는 경로 사이클 : 정점 A에서 다시 A로 돌아오는 경로 단순경로(사이클) : 같은 정점을 두 번 이상 방문하지 않는 경로(사이클) 차수 : 정점과 연결되어 있는 간선의 수 In-degree : 들어오는 간선의 수 Out-degree : 나가는 간선의 수 인접 행렬과 인접 리스트 1. 인접행렬 (Adjacency-matrix) - 인접 행렬이란, 이름 그대로 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식을 의미한다. - 대각 성분을 기준으로 대칭인 성질을 갖는다. - Adj_mat[i][j] : 노드i 에서 노드j로 가는 간선이 존재할 경우 1이고 아니면 0이다. 2. 인접 리스트 (Adjacency-list) - 각 노드에 연결된 노드를.. 이전 1 2 다음