이모저모

https://programmers.co.kr/learn/courses/30/lessons/17686 한참 고전한 이 문제를 통해 얻은 교훈(?) 두 가지..! 📝 문제 조건을 확실하게 읽자 : 문제의 요구조건은 나의 나이브한 수준의 상식과 직관과는 다를 가능성이 매우 높다는 것! 📝 re 모듈 사용법을 익혀두자 : 알고리즘/논리에 집중해서 탄력적으로 문제를 풀려면, 도구 사용법에서 헤매고 있으면 안 되겠다..! # 문제 조건들 및 그에 따른 주의점들 # 조건1 ) 문자열 비교시(head) 대소문자 구분을 하지 않는다. # ==> 일괄적으로 lower 해서 비교 # 조건 2) HEAD 가 동일하다면 ==> NUMBER 의 숫자 순 정렬 # 조건 2+) 숫자 맨 앞의 0은 무시 ** 내가 한참동안 잘못 이..

🤔 아직 궁금한 점 문제이름부터 "이중우선순위큐"여서, heap 2개를 사용하라는 것인가보다 싶었다. 일단 heap 2개를 준비해서 하나는 최솟값을 뽑아내는 용도, 다른 하나는 최댓값을 뽑아내는 용도로 사용했다. 그런데 나의 풀이 과정에서는 두 heap간에 매번 같은 상태로의 동기화가 필요하다는 것을 발견하게 되었고, 그래서 어느 하나에서 pop할 때 다른 heap에서도 해당 값을 remove 해주었다. 하지만 이렇게 하면 결국 매번 pop할때마다 remove때문에 O(n)의 시간이 걸릴 것이다. 이렇게 remove하지 않고 더 효율적으로 두 heap이 서로의 상태를 반영해서 작업할 수 있는 방법은 없을까?! 0. 문제 1. 손으로 정리 2. 코드 import heapq def solution(opera..

하이구... 플로이드 와샬이 수월했다고 다익스트라도 괜찮을 줄 알았는데, 생각보다 어려웠다..😂 다익스트라.. 앞으로 이 친구도 많이 만나면서 친해져야겠다..ㅎㅎ 나동빈 저자의 로 열심히 공부공부.. 다익스트라로 풀더라도 최솟값을 얻어내는 과정에서 그저 선형탐색을 하는 것보다 우선순위 큐(여기서 직접적으로 사용한 건 heapq)도 활용해야 훨씬 좋은 시간 복잡도를 가질 수 있다. 오늘은 프로그래머스의 '가장 먼 노드'로 연습해봤는데, 정말 heap 을 사용하지 않으니까 몇 개의 테스트케이스에서 시간초과가 떴다. 다시 heapq를 활용해서 풀이한 이코테 코드를 보면서 다시 쓰고 제출했더니 통과됐다. 자료구조에 따른 시간복잡도를 알고 있는 건 중요하구나라는 사실을 새삼 느꼈다. 1. 손공부 2. 코드 def..

import collections orders = [ [1, 4], [5, 4], [4, 3], [2, 5], [2, 3], [6, 2] ] # 진입차수를 기록할 1차원 배열 마련 및 초기값 채우기 degree = [0] * len(orders) for order in orders: degree[order[1]-1] += 1 # 진입차수 0이지만 이미 큐에 넣어서 처리한 아이들 중복 처리 안하도록 checked = [0] * len(orders) # 진입차수가 0이 된 아이들을 순서대로 처리하기 위한 que que = collections.deque() for i, each in enumerate(degree): if each == 0: que.append(i+1) checked[i] = 1 # 순서대로..

import sys n = int(sys.stdin.readline().rstrip()) dy = [["M"]*n for _ in range(n)] # 자신과의 거리는 0 for i in range(n): dy[i][i] = 0 # 입력 라인이 -1 -1로 종료를 알릴 때까지 연결 정보를 받아온다. while True: i, j = map(int, sys.stdin.readline().split()) if i == -1 and j == -1: break dy[i-1][j-1] = 1 dy[j-1][i-1] = 1 # k 번째 친구를 경유하는 상황을 하나씩 추가해서 고려하면서, 최소 거리를 업데이트. for k in range(n): for i in range(n): for j in range(n): if..

📝 플로이드 와샬(Floyd-Warshall) 알고리즘 경유지로 고려하는 대상(정점/도시)을 하나씩 늘려가면서! 그때마다의 최소거리(비용)를 갱신해가는 동적 프로그래밍 방식이다. 앞으로 다른 문제에서 이 방식이 어떻게 적용될 수 있는지도 많이 접해봐야겠다! 1. 손정리 2. 코드 import sys # n 은 도시(정점) 수, m 은 간선 수 n, m = map(int, sys.stdin.readline().split()) # 2차원 배열 준비 (i 행에서 j 열로 가는데 드는 비용을 적을 곳) dis = [["M"]*n for _ in range(n)] # 입력된 연결 및 비용 정보 반영하기 for _ in range(m): i, j, price = map(int, sys.stdin.readline()..