CS10 [백준/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. [Network] 소켓 목차- 소켓은 통신에 필요한 데이터를 담는 파일이다!- TCP socket 동작 방식 - UDP socket 동작 방식 1. 소켓은 통신에 필요한 데이터를 담는 파일이다!1.1. L4(전송 계층)와 포트 번호전송 계층(L4)는 네트워크 계층(L3)에서 전송된 데이터를 애플리케이션 계층으로 전달하는 역할을 한다. 여기서 포트 번호를 통해 송신지와 수신지의 특정 애플리케이션을 식별한다. 즉, 포트 번호는 애플리케이션에서 동작하는 부분과 시스템 레벨에서 동작하는 부분을 연결해주는 중요한 역할을 한다. TCP나 UDP 프로토콜은 패킷의 헤더에 포함된 포트 번호를 통해 송신자와 수신자의 애플리케이션을 구분하여 네트워크 상의 데이터를 올바른 애플리케이션에 전달하게 된다. 1.2. 소켓과 애플리케이션 - 시스템.. 2024. 9. 6. [Network] 네트워크 계층 (L3): 멀리 있는 컴퓨터와의 연결 목차- LAN을 넘어선 통신- L3의 프로토콜- 라우팅 테이블 및 전송 과정 1. LAN을 넘어선 통신1.1. 네트워크 계층물리 계층(L1), 데이터 링크 계층(L2)은 주로 LAN 내에서의 통신을 담당한다. 즉, 주로 같은 네트워크 세그먼트 또는 같은 물리적 네트워크 내에서의 통신을 처리한다. L2에서는 MAC 주소를 사용하여 같은 네트워크 내에서 기기 간의 통신이 이루어진다. 여러 네트워크 간에 통신하기 위해서는 L1, L2만으로는 부족하다. 여러 네트워크에 속한 모든 호스트의 MAC 주소를 파악하는 것은 너무나 어려운 일이기 때문이다. 그래서 더 먼 거리의 통신을 위해서는 네트워크 계층(L3)에서의 라우팅 과정이 필요하다. 라우터가 라우팅 테이블과 IP 주소를 사용하여 목적지까지의 최적의 경로를 .. 2024. 8. 19. 정렬 알고리즘의 성능 비교와 상황별 선택 기준 목차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. 이전 1 2 다음
