본문 바로가기

CS/Data Structure, Algorithm6

[백준/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. Properties to Compare2. 정렬 알고리즘들의 성능 비교3. 특정 상황에서의 정렬 알고리즘 선택 기준 1. Properties to Compare성능을 비교하기에 앞서 고려해야 할 속성들에 대해 간단히 알아보자.  ① Time Complexity Comparison- Best: 가장 효율적으로 동작할 경우의 시간 복잡도- Average: 일반적인 경우의 시간 복잡도- Worst: 최악의 경우의 시간 복잡도 ② Auxiliary Space Complexity Comparison (보조 공간 복잡도)알고리즘이 추가로 필요한 메모리 공간을 의미한다. 예를 들어, In-Place 알고리즘(ex. quick, heap)은 추가적인 공간이 거의 필요하지 않고 입력 데이터 자체를 사용해 정렬을.. 2024. 8. 7.
[자료구조] Hash Table 목차 - Intro - Array vs Hash Table - 어떻게 O(1)을 만들었을까? - Hash function과 Collision - Collision을 최소화해 보자 - JavaScript의 Hash Table - 마치면서Intro코드를 더 빠르게 만들어주는 Hash Table에 대해 배워보자! Hash Table이란 단어를 처음 들어봤어도 개발하다가 이미 써봤을 확률이 매우 높다. Hash Table은 key-value 쌍으로 데이터를 저장하는 자료구조이다. 이 자료구조는 생각보다 똑똑한 방법으로 효율성을 높이는데, 어떤 식으로 구현되어 있는지 뜯어보자. Array vs Hash Table배열은 index를 통해 데이터를 순차적으로 저장한다. 특정 index의 값을 읽거나 추가할 때는 O(.. 2024. 5. 9.
Stack 2개로 Queue, Queue 2개로 Stack 만들기 Stack 2개로 Queue를, Queue 2개로 Stack을 만드는 방법과, 그 시간복잡도에 대해 알아보겠다.  1. Stack 2개로 Queue 만들기 아이데이션inStack과 outStack이 있다. inStack의 입구가 Qin이 되고, outStack의 출구가 Qout이 된다. enqueue 호출 시 1, 2, 3번 공이 순서대로 Stack1에 입력된다. 위에서부터 [3, 2, 1] dequeue 호출 시 outStack이 비어있으면, inStack의 모든 항목을 outStack으로 이동. inStack에서 하나씩 pop해서 outStack에 push한다. 완료되면 outStack은 위에서부터 [1, 2, 3]이 되고, dequeue 호출 시 가장 위에 있는 1부터 제거된다. (그 후의 dequ.. 2024. 5. 7.

티스토리툴바