Algorithm
-
프로그래머스 데브코스 - [3단계] 입국심사Algorithm 2023. 6. 14. 17:35
문제 설명 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다. 모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다. 입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요. 제한사항 입국심사..
-
프로그래머스 데브코스 - 알고리즘 문제를 접근하는 방식Algorithm 2023. 6. 14. 16:58
문제를 읽기전에 먼저 입출력 제한을 보자 문제를 자세히 읽기전에 입출력 제한을 보는것이 중요하다. 특히 입력 제한을 보면 어떤 시간복잡도 내에 풀어야 하는지 알 수 있다. 예를 들어, 입력이 100 이하인 경우 높은 확률로 완전 탐색 문제이다. 시간복잡도 O(n^3) 까지도 감당이 가능하기 때문에 플로이드 워셜과 같이 시간복잡도가 높은 알고리즘도 사용이 가능하다. 입력이 100 이하인 경우 완전 탐색 백트래킹 입력이 10,000 이하인 경우 최대 O(n^2) 이내로 끝내야하는 문제 문제에 따라 O(n^2 log n)까지는 허용 n*n 2차원 리스트를 모두 순회해야하는 문제가 많음 입력이 1,000,000 이하인 경우 최대 O(n log n)으로 끝내야하는 문제 힙, 우선순위 큐 정렬 동적 계획법 위상 정..
-
프로그래머스 데브코스 - [3단계] 여행경로Algorithm 2023. 6. 13. 17:34
문제 설명 주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다. 항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요. 제한사항 모든 공항은 알파벳 대문자 3글자로 이루어집니다. 주어진 공항 수는 3개 이상 10,000개 이하입니다. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다. 주어진 항공권은 모두 사용해야 합니다. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다. 입출력 예 tickets return [["ICN"..
-
프로그래머스 데브코스 - [3단계] 가장 먼 노드Algorithm 2023. 6. 12. 19:21
문제 설명 n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다. 노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요. 제한사항 노드의 개수 n은 2 이상 20,000 이하입니다. 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다. vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다. 입출력 예 ㄹㅇㄴㅁ n ..
-
프로그래머스 - 하노이 탑Algorithm 2023. 6. 7. 18:46
문제 풀이 하노이 탑은 원판의 수 n, 시작하는 기둥 start, 중간의 거치는 기둥 mid, 도착할 기둥 end 총 4개의 요소가 필요하다 원판의 수가 1일 경우에는 start에서 바로 end로 넘기면 된다 아닐 경우에는 n-1개의 원판을 start에서 mid로 옮겨준다 n번째 원판을 start에서 end로 옮겨준다 mid에 있던 n-1개의 원판을 end로 옮겨준다 이 과정을 재귀함수를 통해 구현해준다 function solution(n) { let answer = []; let hanoi = (n, start, mid, end) => { if(n === 1) answer.push([start, end]); else { // n-1개의 원판을 start에서 mid로 옮김 hanoi(n-1, start,..
-
프로그래머스 - 구명보트Algorithm 2023. 6. 7. 18:16
문제 풀이 사람들을 담은 배열 people을 몸무게가 가벼운 순인 오름차순으로 정렬시킨다 보트에 people 배열에서 가장 무거운 사람을 태운 뒤, people 배열에서 가장 가벼운 사람을 태울 수 있는지 확인한다 두 사람이 탈 수 있다면 두 사람을 태워 보내고 불가능하다면 다음으로 무거운 사람을 태운 뒤 확인한다 이 과정을 people 배열에 아무도 남지 않을 때 까지 반복한다 function solution(people, limit) { let answer = 0; let boat = []; people.sort((a, b) => a - b); while(people.length) { boat.push(people.pop()); // 보트에 탄 사람의 무게 + 가장 가벼운사람의 무게가 limit보다 ..
-
프로그래머스 - 게임 맵 최단거리Algorithm 2023. 5. 30. 13:22
문제 풀이 큐에 x, y의 좌표값과 방문한 칸의 개수 answer을 초기값으로 각각 0, 0, 1씩 넣어준다 큐에 현재 좌표의 상하좌우의 좌표값과 answer+1이 든 배열을 push해준다 shift()로 큐에서 하나씩 빼내서 해당 좌표가 갈 수 없는 길이라면 다음 요소를 확인하고 갈 수 있는 길이라면 큐에 남은 요소가 없어질 때 까지 이 과정을 반복한다 반복하는 과정중 x, y 좌표가 상대 진영에 도달하면 answer을 리턴한다 큐에 남은 요소가 없어진다면 상대 진영에 도착하지 못한다는 의미이기에 -1을 리턴한다 function solution(maps) { let xLength = maps[0].length; let yLength = maps.length; let xGoal = xLength-1; l..
-
프로그래머스 - 바탕화면 정리Algorithm 2023. 5. 26. 11:00
문제 풀이 이 문제는 드래그를 시작할 좌표와 드래그를 마칠 좌표를 구하는게 관건이다 wallpaper 배열의 요소들 중에서 '#' 문자가 나온 가장 첫번째 요소의 인덱스가 드래그를 시작할 좌표의 y좌표가 된다 wallpaper 배열의 요소에서 가장 첫번째로 존재하는 '#' 문자가 몇 번째 인덱스에 있는지 확인하고 그중 최솟값이 드래그를 시작할 좌표의 x좌표가 된다 wallpaper 배열의 요소들 중에서 '#' 문자가 나온 요소들 중 마지막 요소의 인덱스 + 1 이 드래그를 마칠 좌표의 y좌표가 된다 wallpaper 배열의 요소에서 마지막에 존재하는 '#' 문자가 몇 번째 인덱스에 있는지 확인하고 그중 최댓값 + 1 이 드래그를 마칠 좌표의 x좌표가 된다 function solution(wallpaper..