남남이루의 고군분투 🌳

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

문제 문제링크 로봇은 90도 회전하거나, 평행이동을 한다 한 번 이동할 때 시간이 1씩 증가한다 n,n에 도착했을 때의 시간을 구해라 아이디어 q에서 꺼내서 if 끝 : 횟수 out 이동 조건 맞으면 q에 (좌표, 횟수) 넣기 평행이동 회전 가로 => 세로 세로 => 가로 알고리즘, 시간복잡도 BFS 시간 복잡도 O(V+E)? 자료구조 q = [[x1,y1,x2,y2], 횟수] hist = [[x1,y1,x2,y2], [...], ...] # q에 들어갔던 좌표인지 확인, x1 y1 x2 y2 => 왼오상하 순서로 넣고 뺀다 함수 move : 이동후 좌표 리스트 반환 bfs : 큐돌기 ''' 회고 블록의 회전이 꽤나 까다로웠다. 블록 회전 부분을 for 반복문으로 하면 코드가 더 간결해질 거 같다. 회전..

문제 트리 순회 출력하기 + 순회란, 노드와 간선(방향)으로 이루어진 트리를 어떤 순서로 탐색하는 지를 말한다. 이진 트리의 경우 꼭 가계도처럼 생겼는데, 가지의 상위에 있는 정점(노드)을 부모 노드라고 하고, 아래에 딸려있는 노드들이 짜-식들이다. 전위 순회는 기본적으로 부모 -> 왼쪽 자식 -> 오른쪽 자식 순서로 탐색한다. 중위 순회는 왼쪽자식 -> 부모 -> 오른쪽 자식, 후위 순회는 왼쪽 자식 -> 오른쪽 자식 -> 부모 순이다. 제일 깊은 데까지 가서 출력하는데, 진행 경로를 선으로 이어서 그려보면 이해하기 쉽다. import sys sys.stdin = open('input.txt','rt') input = sys.stdin.readline n = int(input()) dic = {} fo..