본문 바로가기

전체 글50

[백준/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.
폴라보는 이미지를 이렇게 최적화합니다. 서비스 소개 폴라보는 DDD 웹 1팀에서 진행하고 있는 프로젝트로, 친구 혹은 연인들끼리 "보드"를 만들어 폴라로이드를 붙이면서 보드를 꾸미고 추억을 공유하는 서비스입니다. 제가 이미지 관련된 기능 개발을 담당하게 되면서, 어떤 식으로 이미지를 최적화했는지 소개해보려고 합니다.  이미지 압축을 통한 로딩 시간 개선1. browser-image-compression압축 없이 이미지를 업로드하면서 보드에서 폴라로이드 사진을 로딩하는 시간이 너무 오래 걸리는 문제가 있었습니다. 이를 해결하기 위해 S3에 이미지를 업로드하기 전에 먼저 압축하는 방법을 선택했고, 이 과정에서 browser-image-compression이라는 라이브러리를 사용했습니다.const file = event.target.files[0].. 2024. 8. 28.
Module System 목차1. JavaScript 모듈이 왜 등장했을까2. 모듈 시스템의 발전 흐름 (CommonJS > AMD -> UMD -> ESM)3. 마치면서.. (다음 글 예고) 1. JavaScript 모듈이 왜 등장했을까 모듈이 왜 등장했는지부터 알아보자. 그러려면 초창기 JavaScript가 어떤 식으로 사용되었는지부터 알아야 한다. 초기에는 작은 규모의 스크립트만 작성했기 때문에 전역 스코프가 기본적으로 적용되었다. 모든 변수와 함수는 기본적으로 전역 공간에 저장되었고, 이에 따라 서로 다른 스크립트에서 같은 이름의 변수나 함수를 정의하게 되면, 하나가 다른 것을 덮어쓰는 문제가 발생했다. 그러다 보니 유지보수가 심각하게 어려워졌다.  나도 vanilla js로 개발한 첫 프로젝트에서 같은 문제를 맞닥뜨린 .. 2024. 8. 20.

티스토리툴바