BFS(2)
-
[프로그래머스] 타겟 넘버
주어진 리스트 값을 하나씩 접근하며 -, +부호를 달아주는 문제이다. DFS/BFS를 활용한 문제라고 한다. 이 문제를 풀면서 DFS/BFS와 완전탐색의 차이가 무엇인지 궁금해졌다. * 완전탐색을 베이스로 한 그래프 탐색 기법이다..! [1,1,1] 리스트와 [+, -]를 사용해 숫자 1을 만들 수 있는 경우의 수를 구하려면, 모든 방법을 확인해보아야 한다. 1. list의 idx 0의 값에 - 또는 + 부호를 할당하고, 합계를 나타내는 sum에 저장한다. 2. -1 / +1 을 각각 저장한 sum이 2개가 된다. * 이게 cache에 저장한다고 하는건가? 3. 두 sum에 각각 idx 1의 값에 -또는 + 부호를 할당 한 값을 저장한다. 따라서 sum이 4개가 된다. 4. 이를 idx가 끝에 도달할 때..
2023.03.10 -
[프로그래머스] 피로도
완전탐색문제에 도전했다! 1.현재 피로도 2.탐험전: 각 던전의 최소 필요 피로도 3.탐험후: 각 던전의 소모 피로도 위 세 값이 주어지고, 이 때 유저가 탐험할 수 있는 최대 던전 수를 return 던전을 1->2->3 , 2->1->3 처럼 순서없이 돌 수 있다. 모든 던전탐방 경우의 수를 해보고, 가장 많은 던전을 돌 수 있는 경우의 수를 뽑으면 됨 ! function solution(k, dungeons) { let tired =[] // 방문한 던전 수 const n = dungeons.length // 던전의 총 개수 //각 던전 방문여부(방문: 1, 아직: 0) let ch = Array.from({ length: n }, () => 0); function dfs(now, game){ for..
2023.03.03