이숭간 공부기록

www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net 문제유형 : 우선순위큐, 자료구조 문제 풀이 neomindstd.github.io/%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4/boj7662/ [백준/파이썬] 7662번 이중 우선순위 큐 풀이 파이썬을 이용한 백준 온라인저지 문제풀이 neomindstd.github.io 처음에 우선순위 큐 하나를 두고(최소힙), 최소값삭제는 최소힙그대로 빼고, 최대값 삭제일때는 최소힙의 모든 원소에 접..

출처 : gmlwjd9405.github.io/2018/05/10/data-structure-heap.html를 참고하여 작성하였습니다. " 우선순위 큐를 위해 만들어진 자료구조 " (우선순위 큐가 뭔데요? 우선순위의 개념을 큐에 도입한 자료구조로서, 우선순위가 높은 데이터가 큐에서 먼저 나가게 된다.) 1. 힙이란? 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조 여러개의 값중 최댓값이나 최솟값을 빠르게 찾아내도록 고안됨 부모노드의 키값이 자식노드의 키값보다 항상 크거나(혹은 작은) 이진트리이다. 힙 트리에서는 중복된 값을 허용한다. 2. 힙의 종류 최대힙 (Max Heap) key(부모) >= key(자식) 숫자로 생각하면 큐에서 나가는 순서가 내림차순이 되는것이다. 최소힙 (Min H..

모든노드에서 다른 모든노드까지의 최단경로를 계산한다. 다익스트라와 마찬가지로 단계별로 거쳐가는 노드를 기준으로 알고리즘을 수행한다. 다만 매 단계마다 방문하지 않은 노드중 최단거리를 갖는 노드를 찾는 과정이 필요없다. 2차원 테이블에 최단거리 정보를 저장한다. DP유형에 속한다. 플로이드 워셜 알고리즘 노드의 개수가 많은경우에는 플로이드워셜보다 다익스트라를 사용하는것이 좋다. 시간복잡도는 O(n^3)임 행은 출발노드, 열은 도착노드를 의미함. k값만 바꿔가면서 모든a,b를 반복하며 전부 확인해주면 된다. k = 1일때(1번노드를 거치는) 모든 a,b에 대해서 확인하고 갱신한다. 소스코드 import sys input = sys.stdin.readline INF = int(1e9) n = int(input..

www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제유형 : 다익스트라 문제풀이 : 다익스트라 알고리즘 구현 단 노드의 개수가 10000개이상이므로 힙 자료구조를 써서 우선순위큐로 구현해야한다. 정답코드 import sys import heapq input = sys.stdin.readline INF = int(1e9) v, e = map(int, input().split()) start = int(input()) graph = [..

최단경로 알고리즘이란, 가장 짧은 경로를 찾는 알고리즘 다양한 문제상황 한지점에서 다른 한지점 한 지점에서 다른 모든지점 모든 지점에서 다른 모든지점 각 지점은 그래프에서 노드로 표현하고 지점간 연결된 도로는 간선으로 표현함 ex ) 마을과 마을을 있는 도로, 도시를 있는 통로 등등 1. 다익스트라 알고리즘 특정한 노드(출발노드)에서 다른모든 노드로 가는 최단경로를 계산 (음의간선이 없을때) 매 상황에서 가장 비용이 적은 노드를 선택해 임의의 과정을 반복한다. (일종의 그리디 알고리즘) 동작과정 출발노드를 설정 최단거리 테이블을 초기화 (자기자신을 제외한 모든노드까지의 거리를 무한대로 설정, 자기자신은 0) 방문하지 않은 노드 중 최단거리가 가장 짧은 노드를 선택 ( 이 과정을 통해 특정 노드까지의 최단..

www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제유형 : 수학, 그리디, 문자열 문제풀이 : 괄호를 적절히 넣어 최솟값을 만드는 방법이므로 - 를 만나면 앞에 괄호를 넣는다. 언제 괄호를 닫아주는가? 그다음 - 를 만나면 괄호를 닫고 다시 괄호를 열여준다. +일때는 계속 지나간다. 만약 배열이 모두 끝났는데 아직 괄호가 열려있는 상태라면 맨 마지막에 괄호를 추가하여 닫아준다. 괄호가 열려있냐 닫혀있냐의 여부는 flag변수를 통해 수행한다. 위 과정을..