알고리즘 코테준비 6

[dfs] 프로그래머스 피로도 문제 풀이

1. 재귀방식 DFS(깊이 우선 탐색) 활용DFS를 사용하면 모든 방문 순서의 경우를 탐색할 수 있습니다.현재 던전을 방문할 수 있는지 확인합니다.방문했다면 피로도를 갱신하고 다음 던전 탐색을 진행합니다.탐색이 끝난 후 원래 상태로 되돌리는 백트래킹을 수행합니다.2. 반복문을 활용한 DFS (스택을 사용한 방법)재귀 호출 없이 반복문과 스택을 활용하여 DFS를 구현할 수도 있습니다.stack을 사용하여 DFS 탐색 상태(현재 피로도, 방문한 던전 개수, 방문 여부)를 저장합니다.DFS처럼 탐색을 진행하되, 탐색 상태를 스택에 저장하면서 모든 경로를 탐색합니다.최대로 방문할 수 있는 던전 개수를 구합니다.DFS 재귀 풀이function solution(k, dungeons) { let maxVisitCo..

[프로그래머스]정수를 나선형으로 배치하기

https://school.programmers.co.kr/learn/courses/30/lessons/181832 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.krfunction solution(n) { //1. 배열초기화 const answer = new Array(n).fill(0).map(()=>[...Array(n).fill(0)]) let dir = 'r' //2. 채우기 //위치 변경해가면서 채우기 // rdlu let x = 0; let y = 0; for(i=1;i=1 && answer[y][x-1] == 0){ ..

[프로그래머스] 게임 맵 최단거리 - BFS

문제 ROR 게임은 두 팀으로 나누어서 진행하며, 상대 팀 진영을 먼저 파괴하면 이기는 게임입니다. 따라서, 각 팀은 상대 팀 진영에 최대한 빨리 도착하는 것이 유리합니다. 지금부터 당신은 한 팀의 팀원이 되어 게임을 진행하려고 합니다. 다음은 5 x 5 크기의 맵에, 당신의 캐릭터가 (행: 1, 열: 1) 위치에 있고, 상대 팀 진영은 (행: 5, 열: 5) 위치에 있는 경우의 예시입니다. 위 그림에서 검은색 부분은 벽으로 막혀있어 갈 수 없는 길이며, 흰색 부분은 갈 수 있는 길입니다. 캐릭터가 움직일 때는 동, 서, 남, 북 방향으로 한 칸씩 이동하며, 게임 맵을 벗어난 길은 갈 수 없습니다. 아래 예시는 캐릭터가 상대 팀 진영으로 가는 두 가지 방법을 나타내고 있습니다. 첫 번째 방법은 11개의 ..

다이나믹 프로그래밍

연산속도와 메모리공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야한다. 보텀업, 탑다운으로 나뉜다. DP의 예시: 피보나치 수열 점화식: 인접 삼항간 점화식. function fibonacci(x){ if(x==1 or x==2) return 1 return fibonacci(x-1) + fibo(x-2) } 그러나, 이렇게 작성하면 O(2^n)의 지수시간 소요. N=30이면 약 10억 가량의 연산 수행. 이를 DP로 해결해보자. DP 로 해결할 수 있는 문제의 조건 큰 문제를 작은 문제로 나눌 수 있다 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 피보나치 수열은 이러한 문제를 만족한다. 메모이제이션(Memoization)기법을 사용하여 해결할 수 있다. 한번 구현한 ..