전체 글

다익스트라 알고리즘은 그래프 상 시작 노드에서 출발하여 다른 모든 노드로 가는 최단 경로를 구해주는 알고리즘. (그래프 간선의 가중치가 항상 양의 정수 값이어야 함.) 시간 복잡도 : O(ElogV) => V: 노드 개수, E: 에지(간선) 개수 개념 이해를 위해 그래프를 하나 예시로 들어보자 각 노드에서 향하는 정점과 가중치를 인접리스트로 정리해보았다. 1. 출발 노드를 설정하고, 그를 제외한 나머지 노드들을 INF(무한대) 값으로 초기화한다. 2. 거리 리스트에서 아직 방문하지 않은 노드 중 가장 작은 노드를 선택(우선순위 큐에서 데이터 뽑아옴) 연결된 노드들의 최단 거리값을 공식을 이용해 업데이트 (테이블 갱신) 3. [선택된 노드의 거리 리스트 값 + 에지 가중치] < [연결 노드 거리 리스트 값..

Recurrent Relation(재귀 관계) 알고리즘에서 특정한 패턴이나 규칙에 따라 값을 반복적으로 계산하는 방법을 나타내는 수학/프로그래밍적 표현. 주로 재귀적인 방법을 사용하여 문제를 해결하거나 순환적인 구조를 다룰 때 사용 예시: 피보나치 수열 피보나치 수열은 재귀 관계를 사용하여 정의된다. F(n) = F(n-1) + F(n-2) ex) F(6)를 계산하려면 F(5)과 F(4)를 계산해야 하는 방식임. F(5)도 마찬가지이다. F(4)와 F(3)을 계산.. def fib(n: int) -> int: if n

문제 Given an m x n 2D binary grid. grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. 섬은 수평과 수직으로 땅이 연결되어있고, 물로 둘러싸여있는 것으로 가정함. 또한 grid 네개의 가장자리는 모두 물로 둘러싸여있다는 것을 가정. 제약조건 m == grid.le..

문제 Given the root of a binary tree, return its maximum depth. A binary tree's maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 주어진 이진트리의 최대 깊이를 찾는 문제 레벨 오더는 BFS와 유사한 방식으로 구현이 됨. 일단 queue로 시작하여 첫번째 root 노드에 대해 큐에 인큐를 함(이 노드에 곧 방문할 예정이라는 의미) 왼쪽 오른쪽에 있는 하위(child) 노드들에 대해 level by level로 방문 depth가 몇인지를 기록해야함 -> 노드들 저장할 때 노드의 값 뿐만 아니라 노드가 ..

최근 webOS 관련 프로젝트를 할 일이 있어 간만에 npm 패키지를 설치할 일이 생겼다. 글로벌로 설치하래서 그렇게 했는데 막상 실행시키려니 다음과 같은 command not found 에러가 뜬다. zsh: command not found: enact 일단 글로벌 옵션으로 설치한 패키지들이 실제로 리스트에 있는지 확인해보았다. 해결 글로벌 관련 경로와 환경변수를 추가 설정하는 방법으로 해결하였다. npm config set prefix '~/.npm-global' vi ~/.zshrc 에 들어가서 아래 경로를 추가해준다. export PATH=~/.npm-global/bin:$PATH source로 변경사항을 적용시켜준다. source ~/.zshrc 정상적으로 실행되는 것을 확인할 수 있다. 찾아보..

Binary 트리 하나와 해당 트리에 속한 두 개의 노드가 주어진다. 이 때, 두 노드의 공통 조상 중 가장 낮은 Node 즉, Lowest common ancestor 를 찾아라. 제약 조건 2

문제 array의 각 element 중 divisor로 나누어 떨어지는 값을 오름차순으로 정렬한 배열을 반환하는 함수 solution을 작성하라. divisor로 나누어 떨어지는 element가 하나도 없다면 배열에 -1을 담아 반환하라. 제한사항 arr은 자연수를 담은 배열 정수 i, j에 대해 i ≠ j 이면 arr[i] ≠ arr[j] 이다. divisor는 자연수 array는 길이 1 이상인 배열 입출력 예 arr divisor return [5, 9, 7, 10] 5 [5, 10] [2, 36, 1, 3] 1 [1, 2, 3, 36] [3,2,6] 10 [-1] 풀이 return의 값이 숫자의 오름차순으로 정렬되어 있기 때문에 sorted() 함수로 배열 내 숫자들을 정렬시켜준다. func so..

문제 어떤 정수들의 절댓값을 차례대로 담은 정수 배열 absolutes와 이 정수들의 부호를 차례대로 담은 불리언 배열 signs가 매개변수로 주어진다. 실제 정수들의 합을 구하여 return 하도록 함수를 완성하라 제한사항 absolutes의 길이는 1이상 1000이하 (absolutes의 모든 수는 각각 1이상 1000이하) signs의 길이는 absolutes의 길이와 같음. (signs[i]가 참이면 absolutes[i]의 실제 정수가 양수임을, 그렇지 않으면 음수임을 의미한다.) 입출력 예 absolutes signs result [4,7,12] [true,false,true] 9 [1,2,3] [false,false,true] 0 풀이 func solution(_ absolutes:[Int]..