본문 바로가기

전체 글45

너비 우선 탐색 BFS 알고리즘 - 그래프 탐색 너비 우선 탐색 (BFS)으로 그래프를 탐색해보자. 그래프 탐색 하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다. 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다. 너비 우선 탐색 BFS BFS는 그래프에서 넓게 우선적으로 탐색하는 알고리즘이다. 깊이 우선 탐색 (DFS)은 스택(stack)을 사용하지만, 너비 우선 탐색 (BFS)은 큐(queue)를 사용한다. 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 사용한다. DFS보다 빠르지만 복잡하다. 어떤 노드를 방문했는지 검사해야한다. BFS의 동작 방식 자신과 인접한 노드를 전부 queue에 넣는다. queue에 들어있는 노드들을 .. 2021. 9. 11.
깊이 우선 탐색 DFS 알고리즘 - 그래프 탐색 깊이 우선 탐색(DFS)으로 그래프를 탐색해보자. 그래프 탐색 하나의 정점으로 시작하여, 차례대로 모든 정점을 한 번씩 방문하는 것이다. 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 알아볼 수 있다. 깊이 우선 탐색 DFS DFS는 탐색에서 깊은 것을 우선적으로 탐색하는 알고리즘이다. 너비 우선 탐색 (BFS)는 큐(queue)가 사용되지만, 깊이 우선 탐색 (DFS)는 스택(stack)이 사용된다. 사실 컴퓨터는 함수 호출을 스택의 원리를 사용하기 때문에, 재귀를 사용하면 DFS를 구현할 수 있다. 모든 노드를 방문하고자 하는 경우에 이 방법을 선택한다. 모든 경우의 수를 보기 좋다! BFS보다는 속도가 느리다. 어떤 노드를 방문했는지 검사하.. 2021. 9. 11.
JavaScript 예습 | [deep dive] 10 ~ 12장 10장 객체 리터럴 10.1 객체란? Object 자바스크립트는 객체기반의 프로그래밍 언어다. 자바스크립트를 구성하는 거의 모든 것이 객체다. (함수, 배열, 정규 표현식 ...) 원시 타입 객체 타입 단 하나의 값만 나타냄. 다양한 타입의 값을 하나의 단위로 구성한 복합적인 자료구조다. 원시 타입의 값(원시 값)은 변경 불가능한 값 immutable value 객체는 변경 가능한 값 mutable value 객체는 0개 이상의 프로퍼티로 구성된 집합이다. 프로퍼티 구성요소 키 key 값 value 여기서 특별하게, 값이 함수인 경우 프로퍼티 대신 메서드 method 라고 부른다. 프로퍼티 : 객체의 상태를 나타내는 값 (data) 메서드 : 프로퍼티(상태 데이터)를 참조하고 조작할 수 있는 동작(beh.. 2021. 9. 9.
다익스트라 Dijkstra 알고리즘 정리할 예정 출처 : https://blog.naver.com/ndb796/221234424646 2021. 9. 9.
플로이드 와샬 Floyd Warshall 알고리즘 다이스트라(Dijkstra) : 하나의 점에서 출발했을 때 다른 모든 정점으로의 최단 경로(최소비용)를 구하는 알고리즘. 플로이드 와샬 : 모든 정점에서 모든 정점으로의 최단 경로(최소비용)를 구하고 싶을 때 사용한다. 거쳐가는 정점을 기준으로 최단 거리를 구하는 것 문제를 직접 풀어보며 알아보자. N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때, 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값을 구하라. ✔️ 입력 - n : 도시의 수 (N 정점 5 일 때 최소비용을 고려하면 자동으로 정점 3을 거치게 된다는 것이다. 이를 javascript 코드로 구현하면 다음과 같다. function solution(n, edges) { let answer =.. 2021. 9. 9.
JavaScript 질문 정리 | 6 ~ 9장 6장 데이터타입 데이터타입이란? 타입이 필요한 이유. 더보기 데이터 타입은 값의 종류를 말한다. 데이터 타입은 원시 타입과 객체 타입으로 구별할 수 있으며, 원시 타입엔 숫자, 문자열, 불리언, undefined, null, symbol 타입이 있다. 동적타이핑 할당될 때 값의 타입이 결정되는 것. 심벌 테이블 컴파일러, 인터프리터는 심벌 테이블이라고 부르는 자료구조를 통해 식별자를 키로 바인딩된 값의 메모리 주소, 데이터 타입, 스코프를 관리한다. 원시타입이란? (immutable value) 더보기 한번 생성되면 변경 불가능한 값. immutable value 숫자, 문자열, undefined, null, boolean, symbol vs 객체타입 자바스크립트가 정수를 처리하는 방법? 더보기 실수 부.. 2021. 9. 9.

티스토리툴바