본문 바로가기

공부78

다익스트라 알고리즘 정리 지난 알고리즘 글에서 다익스트라 알고리즘을 정리한 글을 작성한다 예고했었다. 다익스트라 알고리즘의 구현 방법 및, 실제 문제 풀이를 정리해보고자 한다. 다익스트라 알고리즘(Dijkstra's Algorithm) : 그래프 상의 두 정점 사이의 최단거리를 구하는 알고리즘. GPS, 네트워크 라우팅 등의 다양한 분야에서 활용된다. 다익스트라 알고리즘 구현 다익스트라 알고리즘은 다음과 같은 과정을 거친다. 시작점에서 탐색을 시작한다. 새 노드에 방문할 때마다, 가장 작은 거리(가중치)를 갖는 노드를 골라서 방문한다. 방문한 노드의 각 인접점에 대해, 시작점까지의 거리를 계산한다. → 이 때, 새로운 최단거리가 나오면 최단거리를 업데이트 한다. 이전에 다른 글에서 정리한 그래프와 달리, 다익스트라 알고리즘의 구.. 2023. 12. 28.
[JavaScript] 실행 컨텍스트에 대하여 자바스크립트를 써온지도 몇 년, 당장 원하는 기능의 코드를 짜낼 수는 있어도 정작 언어 자체를 깊이 공부해본 적이 없다는 생각이 들었다. 지금이라도 부족했던 기본을 다지기 위해, 책과 이런저런 문서를 참고하며 조금씩 공부를 하고 있다. 블로그에서는 책을 읽으며 공부한 것을 요약하여 정리하고자 한다. 책의 경우, 코어 자바스크립트를 보고 있다. 조만간 모던 자바스크립트 Deep Dive 또한 참고하며 이런저런 내용을 공부할 예정이다. (책을 나눔해준 버블버블에게 무한한 감사...) 실행 컨텍스트(Execution Context)란? : 실행할 코드에 제공할 환경 정보들을 담아둔 객체. 클로저를 지원하는 대부분의 언어에 이것 비슷한 개념들이 존재한다고. → 어떠한 컨텍스트가 실행되면, 호이스팅 발생/외부 환.. 2023. 12. 23.
이진 힙(Binary Heap) 정리 알고리즘 문제 풀이를 진행하다 다익스트라 알고리즘 문제를 접하게 되었다. 다익스트라 알고리즘이 유명한 알고리즘이기도 하고, 이번 기회에 다익스트라 알고리즘 구현에 잘 쓰이는 이진 힙 및 우선순위 큐에 대해 알아보는 것이 좋겠다 싶어 강의를 들은 내용을 간략히 기록한다. 강의는 Udemy에 있는 JavaScript 알고리즘 & 자료구조 마스터클래스 이다. 힙 (Heap) : 트리와 비슷한 자료구조. 다만 트리와 달리 부모와 자식 노드 사이의 관계에 대한 조건이 존재한다. 이 조건은 힙의 종류에 따라 다름. 최대 힙(Max Heap): 부모가 늘 자식보다 큰 값을 지닌다. 최소 힙(Min Heap): 부모가 늘 자식보다 작은 값을 지닌다. 이진 힙(Binary Heap) : 힙 중에서도 오직 2개의 자식 노.. 2023. 12. 19.
문자열 문제 풀이 알고리즘 5주차 주제는 문자열이었다. 역시나 기억에 남는 문제 위주로 푼 문제를 정리해본다. 백준 4889번 문제가 어째 익숙한 느낌이 들었는데, 예전에 풀었던 4949번 균형잡힌 세상 문제와 비슷한 괄호 문제였다. 다만 약간의 차이가 존재하는데, 4949번은 괄호가 포함된 문자열을 탐색하고, 괄호가 올바른지(균형 잡혔는지)의 여부를 확인하는 문제였다면, 이 문제는 올바르지 않은(안정적이지 않은) 괄호 문자열을 최소 몇 번 수정해야 옳게 만들 수 있는지를 확인해야 한다. 따라서 4949번처럼 괄호를 스택에 넣고 빼며, 첫째로 괄호로 이루어진 문자열이 안정적인지 확인한다. 만약 스택에 남은 요소가 없다면 이미 괄호 문자열은 안정적인 상태이므로 수정할 필요가 없음을 의미한다. 만약 스택에 남은 요소가 있다면.. 2023. 12. 11.
구현 문제 풀이 알고리즘 스터디 4주차 주제는 구현이었다. 기억에 남는 문제 위주로 풀이 내용을 정리한다. 백준 2174번 다수의 로봇들 (1≤N≤100) 이 존재하는 공간에서 각 로봇들에 명령을 내리고, 해당 명령을 문제 없이 수행할 수 있는지 파악하는 문제. 명령은 총 3가지인데, ‘로봇이 향하는 방향을 기준으로’ 왼쪽/오른쪽으로 90도 회전/앞으로 한 칸 움직이기이다. 따라서 각 로봇들의 위치 뿐 아니라, 로봇이 현재 향하고 있는 방향 또한 고려해야하는 문제였다. 로봇이 다수 존재하기 때문에, 입력받은 순서대로 로봇에 번호를 붙여 객체에 위치 및 방향을 저장해두고, 각 로봇의 정보에 접근하기 용이하게끔 하였다. 이후로는 순서대로 들어오는 명령을 처리하기만 하면 된다. const readline = require(".. 2023. 12. 4.
React Testing에 대하여 Udemy의 React - The Complete Guide 강의의 Section 27: Testing React Apps(Unit Tests)를 듣고 공부한 내용을 간략히 정리. Automating Testing (테스트 자동화) 테스트는 왜 해야할까? 개발자가 개발하는 도중, 수동으로 작동 등을 확인하는 것은 '수동 테스트(Manual Test)'이다. 다만, 테스트를 수작업으로 진행할 경우 가능한 모든 테스트 케이스(시나리오)를 테스트할 수 없기 때문에 예상치 못한 에러가 발생할 수 있다. 이에 반해, 자동화된 테스트는 모든 시나리오를 자동적으로 테스트할 수 있다. 개발자가 하나하나 손으로 하는 것보다 시간도 절약할 수 있다. 따라서 수동 테스트만 진행하는 것 보다, 자동 테스트를 같이 병행함으로.. 2023. 11. 22.

티스토리툴바