알고리즘12 Monotonic Stack에 대하여 알고리즘 문제를 풀다가 처음 마주하는 개념을 알게 되었다. 이름을 알게 된 김에 가볍게 내용을 정리해보았다. Monotonic Stack이란 : 스택 내의 요소들이 단조적으로(Monotonic) 증가/감소하는 스택을 말한다. 아래와 같은 특징을 갖는다고 한다. 한 번 pop된 요소는 다시는 재사용 되지 않는다. 요소를 스택에 추가할 때마나 단조성을 유지한다. → 이러한 특징 때문에 주로 다음/이전의 최소값/최대값(Next/Previous smaller/larger Problem)을 구하는 문제에서 잘 쓰인다. Monotonic Stack의 구현 Monotonic Stack의 구현에는 아래의 과정을 거친다. 아래는 감소하는(Decreasing) 스택을 구하는 과정이다. 기본적으로, 주어진 숫자 목록을 순회.. 2024. 4. 14. 다익스트라 알고리즘 정리 지난 알고리즘 글에서 다익스트라 알고리즘을 정리한 글을 작성한다 예고했었다. 다익스트라 알고리즘의 구현 방법 및, 실제 문제 풀이를 정리해보고자 한다. 다익스트라 알고리즘(Dijkstra's Algorithm) : 그래프 상의 두 정점 사이의 최단거리를 구하는 알고리즘. GPS, 네트워크 라우팅 등의 다양한 분야에서 활용된다. 다익스트라 알고리즘 구현 다익스트라 알고리즘은 다음과 같은 과정을 거친다. 시작점에서 탐색을 시작한다. 새 노드에 방문할 때마다, 가장 작은 거리(가중치)를 갖는 노드를 골라서 방문한다. 방문한 노드의 각 인접점에 대해, 시작점까지의 거리를 계산한다. → 이 때, 새로운 최단거리가 나오면 최단거리를 업데이트 한다. 이전에 다른 글에서 정리한 그래프와 달리, 다익스트라 알고리즘의 구.. 2023. 12. 28. 이진 힙(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. 그래프 & DFS/BFS 문제 풀이 지난 게시물에서 그래프와 그래프 순회에 대한 강의를 듣고 내용을 정리하여 포스팅했었다. 이번에는 강의 내용을 활용하여 풀었던 문제들을 짧게 공유한다. 문제들은 대부분 백준 문제집의 DFS+BFS 필수 문제 에 속한 문제들이다. 백준 2178번 이차원 배열 형태의 미로를 탐색하며, 출발점부터 도착점까지의 최소 거리를 구하는 문제이다. BFS/DFS 문제를 제대로 푸는게 처음이라, 공부한 개념을 적용하기 조금 어려웠는데 다음과 같이 풀었다. BFS로, 시작점(0, 0)에서부터 순회를 시작한다. 미로는 길이 존재하고, 현재 접점과 인접한 사방의 접점으로만 진행할 수 있다. 따라서 순회 시 이를 전부 체크한다. 위의 조건을 만족하며 아직 방문하지 않은 인접점은 방문 처리 후 BFS 탐색 큐에 넣어줌으로써, 다.. 2023. 11. 19. 이전 1 2 다음
