알고리즘 Algorithm

[프로그래머스] Lv.3 가장 먼 노드 (BFS) + 시간초과, 메모리초과 해결

가장 먼 노드 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 1번 node 에서 모든 node 로 가는 길이를 구한다. 이 때 모든 edge 의 가중치는 1이다. 즉 1 > 2 = 1 , 1 > 2 >5 = 3 , 1 > 3 > 6 = 3, ... 이다. BFS인 이유 한 지점에서 갈 수 있는 위치 (동일 depth) 를 순차적으로 방문해야 한다. 따라서 가능한 경우의 수를 queue 에 쌓아서 동일 depth 에서 처리해줘야 한다. [프로그래머스] Lv.2 게임 맵 최단거리 (BFS) + 반례 14개, 연습용 좌표판 PDF 게임 맵 최단거리 시작 지점부..

[프로그래머스] Lv.2 배달 (다익스트라)

배달 1번 node 에서 모든 node 로 이동할 때, cost K 보다 적게 이동할 수 있는 마을의 갯수를 구하는 문제이다. 한 점(1) 에서 모든 점으로 가는 cost 를 구하는 문제이며, cost 는 양수이므로 다익스트라 이다. 풀이 코드 구조 갈 수 있는 node 를 먼저 구한다. (candidates) 그리고 그 node 까지 갈 수 있는 path 들을 모두 구한다. (pq). 그리고 거기서 최단거리만을 뽑아 계산한다. 코드 let totalCost; let adjacent; let N; function solution(n, roads, K) { N = n; totalCost = new Array(n); adjacent = new Array(n); // Infinity 로 초기화 totalCos..

[프로그래머스] Lv.2 게임 맵 최단거리 (BFS) + 반례 14개, 연습용 좌표판 PDF

게임 맵 최단거리 시작 지점부터 도착 지점까지 최단거리로 방문했을 때, 얼마나 걸리는지를 물어보는 문제이다. 예제의 경우 11 이다. 최단거리가 DFS 가 아닌 BFS 인 이유 한 지점에서 갈 수 있는 위치 (동일 depth) 를 순차적으로 방문해야 한다. 따라서 가능한 경우의 수를 queue 에 쌓아서 동일 depth 에서 처리해줘야 한다. DFS 는 동일 depth 를 순차적으로 방문하는 것이 아니라, depth 를 파고들어간다. (계속해서 함수를 호출한다) 따라서 최단경로가 아님에도, 이미 간 길을 그대로 가버린다. 풀이 코드 구조 한 위치(0, 0)에서 시작한다. 다음 위치로 갈 수 있는지 검사한다. (가지치기) 갈 수 있는 위치들에 대해서 후보 리스트(candidates) 를 만든다. 이 때 c..

[프로그래머스] Lv.2 N-queen (DFS) + 연습용 체스판

N-queen queen 을 겹치지 않게 놓는 문제이다. 시간복잡도는, 모든 row 에서 모든 column 에 대해 검사하므로, O(N^N) 이다. 풀이 코드 구조 queen 을 놓기 전에, 이전 queen 들의 위치와 비교하여 놓아도 되는지 검사한다. 되면 queen 을 놓는다 (함수 호출, DFS 탐색) 안되면 더 이상 함수호출을 하지 않는다 (끝 = 가지치기) 가지치기는 어떻게 되는가 check 함수에서 여기(newRow, newCol) 에 queen 을 놔도 되는지 검사를 한다. 이때 queen 을 놓아도 된다고 판단되면 계속해서 함수 호출을 하고 (DFS 탐색), queen 을 놓으면 안된다고 판단되면 거기서 끝낸다. 따라서 그 상태에서는 더 이상의 함수 호출이 없으므로, 가지치기가 된다. qu..

[프로그래머스] Lv.2 모음사전 (완전탐색)

모음사전 최대 시간복잡도: O(n^5) 5 + 5*5 + 5*5*5 + 5*5*5*5 + 5*5*5*5*5 = 3905 최대 시간복잡도는 n^5 이지만, 워낙 최대 횟수가 적어서 완전탐색으로 빠르게 풀기로 했다. 풀이 1 (완전탐색, for 문) function solution(word) { const str = ['','','','','']; const alphabet = ['A','E','I','O','U']; const n = 5; let cnt = 0; for(let i0=0; i0