본문 바로가기

Programming310

알고리즘 카테고리에 대해... 여러 알고리즘을 다뤄볼 탭입니다. 사용언어는 코테 준비 및 자바스크립트에 대한 학습을 위해서 자바스크립트로 카테고리를 풀어나가볼 예정입니다. 알고리즘 소개 뿐만 아니라 가능하다면 코딩테스트 연습 문제들도 몇 개 실어볼 예정입니다. 2021. 10. 10.
그래프 탐색 - 너비 우선 탐색 BFS 이번에는 그래프 탐색의 다른 방식인 BFS에 대해서 소개해드리겠습니다. 1. 너비 우선 탐색 Breadth First Search, BFS 지난번에 본 깊이 우선 탐색(DFS)는 한 정점에서 시작해서 갈 수 있는 정점까지 방문한 후에 방문하지 않은 인접 정점이 있는 정점으로 돌아와서 진행하는 방식이었습니다. 이번에 배울 너비 우선 탐색은 정점에 인접한 정점들을 모두 한 번씩 방문하고 나서 방문했던 정점들의 인접한 정점들을 다시 한 번씩 방문하는 방식입니다. 또한 정점들마다 너비 우선 탐색을 수행하기 위해서 큐를 이용합니다. 이점도 DFS와 차이점을 보이고있습니다. DFS와 마찬가지로 배열과 큐를 이용하는데 배열에는 방문 정보를 담고 큐에는 방문 기록을 남기기 위해 사용합니다. A에서 시작하도록 하겠습니다.. 2021. 10. 9.
그래프 탐색 - 깊이 우선 탐색 DFS 그래프의 탐색 혹은 그래프의 순회라고 불리우는 개념은 그래프의 모든 정점을 반드시 한 번은 방문하는 것을 말합니다. 그래프의 탐색 방법에는 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 두 종류가 있는 그중에서 깊이 우선 탐색 부터 알아보겠습니다. 1. 깊이 우선 탐색 Depth First Search, DFS 깊이 우선 탐색은 한 정점에서 시작하여 한 방향으로 진행해 갈 수 있는 정점까지 최대한으로 탐색합니다. 그러다가 더이상 진행할 수 없다면 가장 최근에 만난 갈림길이 있는 정점으로 돌아가서 다른 방향의 간선으로 진행할 수 있는지 탐색하는 방식입니다. 깊이 우선 탐색에서는 탐색한 경로의 정보를 담기 위해서 스택을 이용하고, 정점에 대해 방문한 정보를 기록하기 위해서배열을 이용합니다. 말로했을 때.. 2021. 10. 8.
그래프 구현2 - 인접 리스트로 그래프 구현하기 지난번엔 순차 자료구조인 2차원 배열을 이용한 인접 행렬 기반 그래프를 구현했습니다. 이번에는 연결 자료구조를 이용해서 그래프를 구현해보도록 하겠습니다. 1. 인접 리스트 인접 리스트 방식은 한 정점에 대해서 인접한 리스트를 연결 리스트로 연결한 것입니다. 다음과 같은 그래프를 인접 리스트로 표현해보면 다음과 같습니다. 그림을 보고나면 대충 감이 잡히실겁니다. 각 정점에 대해서 노드는 간선의 갯수만큼 연결되어있습니다. 맨 처음의 A, B, C, D 노드를 헤드 포인터라고 하며, 이 헤드 포인터는 그래프의 정점의 갯수만큼을 필요로합니다. 즉, 무방향 그래프의 노드의 수 만큼의 연결 리스트가 만들어지고 각 연결 리스트는 정점이 가진 간선의 갯수(차수, degree)만큼의 길이를 가지게 됩니다. 만약 방향 그.. 2021. 10. 5.
[Javascript] 모듈 Module ES2015가 등장하면서 자바스크립트에서도 모듈 기능을 지원하기 시작했습니다. 1. 모듈 모듈이란 특정 기능을 가진 함수나 변수들을 모아둔 것을 말합니다. 예를 들면 수학적 계산을 하는 함수들을 모아둔다 던가, 문자열과 관련한 다양한 기능들을 모아두고 모듈이라고 할 수 있습니다. 이렇게 비슷한 기능을 가진 함수와 변수들을 모아두었기 때문에 한 프로그램에서 뿐만이 아니라 다른 프로그램에서도 이용할 수 있는 기능의 모임이 될 수도 있습니다. 그렇기에 모듈은 함수처럼 하나당 한 파일을 만들기 보다는 비슷한 기능끼리 여러개를 모아서 하나의 파일을 구성합니다. 2. 모듈 만들어보기 간단하게 덧셈, 뺄셈을 하는 모듈을 만들어보겠습니다. 우선 html 파일인데, 다음은 모듈입니다. 간단하게 덧셈만을 하는 모듈을 만들.. 2021. 10. 5.
그래프 구현 1 - 인접 행렬로 그래프 구현하기 모든 자료구조가 그래왔듯이 그래프를 구현하는 방식에는 순차 자료구조를 이용하는 방식과 연결 자료구조를 이용하는 방식 두가지가 있습니다. 그래프에서도 마찬가지이지만 이름을 조금 다르게 부릅니다. 순차 자료구조를 이용해서 구현하는 것을 인접 행렬 기반 그래프, 연결 자료구조를 이용해서 구현하는 것을 인접 리스트 기반 그래프 라고합니다. 오늘은 첫 번째 순차 자료구조를 이용한 방식인 인접 행렬을 이용한 그래프를 구현해보겠습니다. 1. 인접 행렬 Adjacent Matrix 인접 행렬은 그래프에서 정점이 어떤 간선으로 연결되었는지를 나타내는 행렬입니다. 정점 n개의 그래프에 대해서 nXn행렬을 이용합니다. 이때 정점끼리 연결되어 있다면 행렬의 값을 1로, 연결되어있지 않다면 행렬의 값을 0으로 이용합니다. 예시.. 2021. 10. 4.
300x250

티스토리툴바