본문 바로가기

공부78

그래프 & DFS/BFS 문제 풀이 지난 게시물에서 그래프와 그래프 순회에 대한 강의를 듣고 내용을 정리하여 포스팅했었다. 이번에는 강의 내용을 활용하여 풀었던 문제들을 짧게 공유한다. 문제들은 대부분 백준 문제집의 DFS+BFS 필수 문제 에 속한 문제들이다. 백준 2178번 이차원 배열 형태의 미로를 탐색하며, 출발점부터 도착점까지의 최소 거리를 구하는 문제이다. BFS/DFS 문제를 제대로 푸는게 처음이라, 공부한 개념을 적용하기 조금 어려웠는데 다음과 같이 풀었다. BFS로, 시작점(0, 0)에서부터 순회를 시작한다. 미로는 길이 존재하고, 현재 접점과 인접한 사방의 접점으로만 진행할 수 있다. 따라서 순회 시 이를 전부 체크한다. 위의 조건을 만족하며 아직 방문하지 않은 인접점은 방문 처리 후 BFS 탐색 큐에 넣어줌으로써, 다.. 2023. 11. 19.
그래프 + 그래프 순회 정리 요즘 소소한 알고리즘 스터디를 하고 있다. 매주 주제를 정해서 하루에 하나씩 문제를 풀고 있는데, 이번주 주제가 DFS/BFS였다. DFS/BFS 공부를 할 겸, 그래프와 순회 강의를 들으며 정리한 것을 간략히 기록한다. 강의는 Udemy에 있는 JavaScript 알고리즘 & 자료구조 마스터클래스 이다. 그래프 (Graph) : 노드/점들의 집합으로 구성된 데이터 구조 → 간단히 말해, 노드와 노드 간의 연결(Connection)로 이루어진 구조이다 어디에 사용되나? 그래프는 다양한 곳에 사용된다. 밑의 리스트는 한 번쯤 주변에서 경험해봤을, 그래프의 사용처들이다. SNS: Facebook이나 인스타그램 등. 사용자 간의 팔로우 관계가 그래프로 나타난다. Location Mapping 각종 추천 시스.. 2023. 11. 17.
유클리드 호제법 백준의 정수론 문제를 살펴보다, 유클리드 호제법에 대해 알게 되었다. 어떤 것인지 간단하게 파악하고, 이를 이용해 문제를 푼 것에 대해 짤막히 기록한다. 유클리드 호제법 자연수 혹은 정수 사이의 최대공약수(Greatest Common Denominator: GCD)를 구하기 위한 알고리즘. a와 b의 최대공약수는, a / b의 나머지 r과 b의 최대공약수와 같다. 이를 실제 함수로 구현하면 재귀 혹은 반복을 통해 구현할 수 있다. 나는 아래와 같은 코드를 작성해 문제풀이에 활용하였다. const getGCD = (a, b) => { if (a === b) return a; if (a === 1 || b === 1) return 1; if (b === 0) return a; return getGCD(b, .. 2023. 10. 29.
백준에서 JS로 문제 풀이하기 + 이런저런 메모(+추가: 2023.11.22) 앞서 올린 백트래킹 게시물에서 언급했듯, 얼마 전부터 시간이 날 때 조금씩조금씩 알고리즘 문제 풀이를 하고 있다. 주로 백준에서 문제를 풀고 있는데, 백준에서 문제를 풀 때 어떻게 풀고 있는지 + 문제 풀 때 개인적으로 알아두면 좋을 것 같은 점을 간단하게 기록해두려 한다. 백준에서 JS로 문제를 풀기 위한 세팅 예전에 백준에서 문제를 풀 때는 C++를 사용했는데, 이제는 거의 잊어버리기도 했고 업무를 JS로 하다 보니 JS로 문제를 풀어야겠다는 생각으로 아무 생각 없이 언어 설정을 살펴보았다. 하지만 자바스크립트는 목록에 보이지 않았고... node.js만 덩그러니 있어서 뭔가 싶던 도중 검색을 통해 JS는 node.js를 선택해야 함 + 입력값을 직접 처리해야 함 이라는 정보를 얻게 되었다. JS로의.. 2023. 10. 23.
백트래킹 근래에 꾸준한 공부 습관을 다시금 들이고자 틈틈이 알고리즘 문제를 풀고 있다. 그러던 와중, '백트래킹'에 대해 조금 공부하게 되어 개념과 푼 문제를 간단하게 정리해보려 한다. 백트래킹(Backtracking) 현재 상황에서 탐색 가능한 모든 경로를 다 탐색하다, 조건에 맞지 않는 경로를 탐색하게 될 경우 다시 뒤로 돌아가서 다른 경로를 탐색하는 알고리즘. 이 때 해결하려는 문제는 트리 구조로 표현되며, 이를 탐색하는 데에는 깊이 우선 탐색을 사용한다. DFS와는 달리 조건(한정 조건이라고 하는 듯)에 맞지 않는 해가 나오면 이전으로 돌아가기 때문에 최종적으로 탐색 시간이 줄어든다는 특징이 있음. 백트래킹을 접하며 참고했던 어느 블로그에서 DFS와 백트래킹을 유사점(교차점)이 있는 교집합 관계같다 표현한.. 2023. 10. 15.
Notifee 정리 React Native에서 로컬 알림을 보낼 수 있게 해주는 패키지는 대표적으로 react-native-notifications, react-native-push-notifications, notifee 등이 있다. 이중 널리 쓰이는 것으로는 react-native-push-notifications 이 있는데, 깃허브를 살펴보니 현재 패키지가 활발히 관리되고 있는 상태가 아니기 때문에 다른 패키지 사용을 고려해보라는 내용이 적혀있었다. 대체안으로써 추천된 것 중 하나가 Notifee인데, 과거엔 유료였으나 얼마 전부터 완전 무료로 풀린 것으로 보인다. 해서 기본적인 사용법을 기록해둔다. 설치 npm install --save @notifee/react-native yarn add @notifee/reac.. 2023. 5. 20.

티스토리툴바