백준3 [백준/Node.js] 1987 알파벳 #DFS #백트래킹 #Set 이 문제는 DFS와 백트래킹을 조합하여 간단히 풀 수 있는 문제이다. 시작점은 0, 0이고, 말이 지나는 칸은 시작점도 포함이므로 초기 count는 1이다visitedWord에 알파벳을 기록해서 다시는 방문하지 않게 했다. DFS 탐색 중에 새롭게 방문한 칸의 알파벳이 visitedWord에 없으면 방문하고, 이미 있으면 탐색하지 않고 다른 방향으로 이동한다. 백트래킹 과정에서, 탐색이 끝난 후에는 visitedWord에서 해당 알파벳을 지워줘야 한다. 다른 경로에서 같은 알파벳을 다시 사용할 수 있어야 하기 때문이다. 이렇게 백트래킹을 통해 탐색이 끝난 후에는 원래 상태로 돌아가서 다른 경로를 탐색할 수 있게 한다. 탐색 중에 count 값을 갱신하면서 최대 칸 수를 기록.. 2024. 10. 13. [백준/Node.js] 3197 백조의 호수 배운 점- BFS에서 shift() 사용으로 인한 성능 저하(O(n)) => Queue는 직접 구현하자 (O(1)) Queue 지금까지 BFS를 풀며 queue는 다음과 같이 shift()로 사용했었다. const queue = [];queue.push([x, y]);const [x, y] = queue.shift(); 그런데 이번엔 시간초과가 떴다.. 왜그런지 알아보자.성능 영향 분석1. shift()의 시간 복잡도shift()는 배열의 첫 번째 요소를 제거하고, 나머지 모든 요소를 앞으로 한 칸씩 이동시킨다. 이 이동 연산이 배열의 크기만큼 발생하므로 O(n)의 시간 복잡도를 가진다.이는 배열 크기가 커질수록 이 연산이 반복되기 때문에 비효율적이다. 2. BFS에서 큐를 사용하는 경우BFS에서는 큐(.. 2024. 10. 13. [백준/Node.js] 17071 숨바꼭질 5 문제 접근이 문제는 BFS와 시간에 따른 위치 변화를 동시에 고려해야 하는 문제이다. 수빈이가 매초 이동할 수 있는 경로를 BFS 방식으로 탐색하면서, 동생이 매초 가속하는 위치에 도달할 수 있는지 체크해야 한다. 하지만 단순 BFS로는 문제가 풀리지 않는다. 수빈이의 이동:- 매초 X-1, X+1, X*2로 이동할 수 있다. => BFS로 탐색하며 매초 어디로 이동할 수 있는지 추적 동생의 이동- 매초 가속하며 이동한다. => t초 후의 위치는 K + t(t+1)/2 짝수/홀수 시간 체크:수빈이와 동생이 같은 시간에 같은 위치에 있어야만 만날 수 있다. 다시 말해, 수빈이가 어떤 위치에 도착하는 시간이 짝수 시간인지, 홀수 시간인지에 따라 그 시간에 동생이 있는 위치가 다르다. ex) 수빈이와 동생이.. 2024. 10. 12. 이전 1 다음
