[Programmers | Level 3] 이중우선순위큐 (Python) https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr import heapq def solution(operations): max_heap = [] min_heap = [] for i in operations: a, b = i.split(" ") b = int(b) if a == 'I': heapq.heappush(max_heap, -b) heapq.heappush(min_heap, b) if a == 'D' and b == 1: if not max_heap or not min_heap: continue min_heap.remove(-heapq.heappop(max_heap)) elif a .. Algorithm | SQL/Programmers 2021. 5. 19. 19:08
[Python] 이진 탐색 (Binary Search) 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 정렬된 데이터에서 원하는 데이터를 빠르게 찾을 수 있다는 장점이 있다. 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다. 이진 탐색은 위치를 나타내는 변수 3개를 사용한다. 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게 이진 탐색이다. 한번 확인할 때마다 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)이다. 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 접근하는 것을 고려해보면 좋다. 구현하는 방법에는 두가지가 있다. 1. 재귀 함수로 구현 # 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(ar.. Algorithm | SQL/개념 2021. 5. 17. 23:34
[BOJ 1238] 파티 (Python) https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 이용하여 최단거리로 X번 마을을 반환점으로 하여 왕복했을 때 가장 많은 시간을 소비하는 학생을 구하는 문제. N이 1000이기 때문에 N^3인 플로이드워셜은 사용할 수 없을 것이라 판단하였다. heapq를 이용한 다익스트라 알고리즘을 N번 돌려서 모든 출발점으로부터 X까지의 최단 경로를 구하였고, X번 마을에서 다른 마을들까지의 최단거리 테이블을.. Algorithm | SQL/BOJ 2021. 5. 15. 22:49
[Python] 최소 스패닝 트리(MST), 크루스칼 알고리즘 (Kruskal Algorithm) 신장 트리 (Spanning Tree) 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 N개의 노드로 만드는 스패닝 트리는 N-1개의 노드로 구성되어 있다. 유니온 파인드 알고리즘을 활용하여 사이클을 검사할 수 있고, 이를 활용하여 스패닝 트리를 만들 수 있다. 이중 최소한의 비용으로 구성된 스패닝 트리를 최소 스패닝 트리 (MST) 라고 한다. 최소 스패닝 트리를 구하는 알고리즘으로 크루스칼, 프림 알고리즘이 있는데 크루스칼 알고리즘을 다뤄보겠다. 크루스칼 알고리즘 (Kruskal Algorithm) 핵심 원리 가장 거리가 짧은 간선부터 차례대로 집합에 추가하면 된다. 다만 사이클을 발생시키는 간선은 제외하고 연결한다. [1] 간선 비용에 따라 오름차순으로 정렬 [2.. Algorithm | SQL/개념 2021. 5. 15. 21:58
[Python] n진법으로 표기된 문자열을 10진법 숫자로 변환하기 n진법으로 표기된 문자열을 10진법 숫자로 변환하는 문제가 주어졌을 때, 가장 간결하게 해결하는 방법으로 int()함수를 활용하는 것이다. parameter가 하나인 경우로만 사용했었는데, 새로운 사용법을 알게 되었다. int(문자열로 표현된 숫자, n진법의 n) : n진법으로 표현된 숫자를 10진법의 숫자로 리턴해준다. num = '3212' base = 4 answer = int(num, base) print(answer) 진법과 관련된 문제가 출제됐을 때 빠르고 간결하게 푸는데 도움이 될 것 같다! 카테고리 없음 2021. 4. 28. 22:18
[Python] lambda, map, reduce, filter 1. lambda 익명함수 (이름이 없는 함수) 코드의 간결함 + 메모리의 절약 가능 1-1. 일반적인 리터럴 표기법에 따른 함수 생성 방법 def 함수이름(매개변수): retrun 결과 1-2. lambda를 사용하여 표현한 방법 lambda 매개변수 : 결과 1-3. 적용 예시 이러한 함수 표현을 def sum(a, b): return a+b sum(10,20) # 30 아래와 같이 한줄에 표현할 수 있다. (lambda a, b: a+b)(10,20) # 30 2. map() 리스트로 부터 원소를 하나씩 꺼내서 함수를 적용시키고 새로운 리스트에 담아준다. # 사용법 map(함수, 리스트) # -------------------------------------- list(map(lambda x: x .. Python/파이썬을 파이썬답게 2021. 4. 26. 23:01
[BOJ 1194] 달이 차오른다, 가자 (Python) from collections import deque import sys input = sys.stdin.readline dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] def bfs(): while q: x, y, key, cnt = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0 Algorithm | SQL/BOJ 2021. 4. 21. 16:43
