남남이루의 고군분투 🌳

다익스트라가 사용되는 때알고리즘 접근법 중 다익스트라는 가중치가 있는 그래프에서 최소 비용 경로를 구할 때 주로 사용한다. 파이썬에서의 다익스트라는 큐에서 가장 최소값을 꺼내기 위해 내장 라이브러리인 heapq를 사용하면 됐었지만 기본 자바스크립트에서는 heap을 지원하지 않기 때문에 직접 구현해서 쓸 수 있다.다익스트라의 구현큐에서 가장 최소값을 꺼내기 위해 heap이 아닌 우선순위큐를 구현해서 할 수도 있지만, 두 방식은 시간 복잡도에 큰 차이가 있다.구체적인 구현 방식을 서술해보자면, 우선순위 큐(Priority Queue)는 요소의 추가(삽입, push) 혹은 제거(꺼내기, pop)때 마다 정렬을 새로 해줘야 한다. 자바스크립트의 내장 sort는 N*logN 의 비용이 들고, 제거할 때 조차 배열..

lv.2 뒤에 있는 큰 수 찾기 문제 바로가기 다른 분 풀이.. # def solution(numbers): # answer = [-1]*(len(numbers)) # stack = [] # for i in range(len(numbers)): # while stack and numbers[stack[-1]] < numbers[i]: # answer[stack.pop()] = numbers[i] # stack.append(i) # return answer * 다시 써보기.. 어렵다..... def solution(numbers): long = len(numbers) answer = [-1] * long stack = [] # for i in range(long): while stack and number..

다익스트라는, 단일 시작점 최단 경로 알고리즘으로, 시작 정점 s에서부터 다른 정점들까지의 최단 거리를 계산한다. (출처: 책 알고리즘문제해결전략) 알고리즘 특징 우선순위 큐(파이썬에서는 heapq 사용)에 정점의 번호와 함께 지금까지 찾아낸 해당 정점까지의 최단 거리를 쌍으로 넣는다. 정점까지의 최단거리를 기준으로 정점을 배열함으로써 아직 방문하지 않은 정점 중 시작점으로부터의 거리가 가장 가까운 점을 찾는 과정을 간단하게 한다. 유의할 점은, 각 정점까지의 최단 경로가 갱신될 수 있다는 점이다. 핵심 구조 import heapq g = [[] for _ in range(노드수 + 1)] for _ in range(노드수): 출발노드, 도착노드, 가중치 = map(int, input().split())..

2차원 DP를 푸는 게 아직 너무 어색하다, 어려웠던 점 누적합 데이터를 쌓아가는 부분 누적합 그래프를 바탕으로 일부 값을 계산하는 식을 짜는 부분 참고한 블로그 [python/파이썬] 백준 11660 구간 합 구하기 5 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경 sodehdt-ldkt.tistory.com [백준] 11660 구간 합 구하기 5 (python) - 누적 합 (2차원) 정리 문제 링크 : https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의..

문제 문제 | 지원자가 지원서에 입력한 4가지의 정보와 획득한 코딩테스트 점수를 하나의 문자열로 구성한 값의 배열 info, 개발팀이 궁금해하는 문의조건이 문자열 형태로 담긴 배열 query가 매개변수로 주어질 때, 각 문의조건에 해당하는 사람들의 숫자를 순서대로 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 시도 방법1. 문자들을 다 숫자 코드로 바꿔서 일치하는 거 찾으려고 했음 결과 답은 맞으나,, 효율성에서 실패. 딕셔너리 썼는데, 각 utils를 고유값으로 해서 그런가봐 ㅍㅅㅍ ((문풀후 추가 : 딕셔너리까진 맞음, 치환도 괜찮을듯, 다만 점수 찾는 부분이 시간 오래걸리는 원인이었음)) # ''' # 조건에 맞는 지원자는 몇 명? => 탐색? # 언어 : cpp java ..

[ 문제 바로가기 ] 수도코드 내 답안 def solution(users, report, k): report = set(report) report = [text.split() for text in report] history = {x[0]:[] for x in report} reported_cnt = {key:0 for key in users} reported_who = {key:[] for key in users} # block for content in report: whom = content[1] reported_cnt[whom] += 1 reported_who[whom].append(content[0]) blocked = [i for i, cnt in reported_cnt.items() if c..