Back to the Basics

그래프를 순회하는 방법 중 가장 일반적인 너비 우선 검색과 깊이 우선 검색에 대해 공부한다 1. 너비 우선 방법 (BFS , Breadth-First Search) 그림출처 위의 그림과 같이 그래프에서 연결된 노드와 해당 노드들 간의 간선을 순서대로 검색하는 알고리즘을 말한다. 한 단계씩 내려가면서 해당 노드와 같은 레벨에 있는 노드들을 먼저 순회한다. 이진트리검색의 차수 우선 순회와 비슷한 개념이다. 구현을 위해서는 Queue를 필요로 한다. 시간 복잡도 O(V+E) : V는 정점의 개수이고 E는 간선의 개수이다. 전체 그래프를 순회하기 위해 모든 정점과 간선을 방문해야 하기 때문 아래의 무지향성 그래프의 예와 함께 코드를 분석해보자 탐색 순서는 a → b → d→ c →e 이다. 아래 코드에서 ver..

이전에 파이썬 공부를 하면서 [빅오,자료형] 에 대해 정리를 한적이 있다. 빅오가 무엇이고 빅오 표기법의 종류, 상한과 최악에 대한 글을 작성하였다. 이번 포스팅 에서는 빅오 표기 규칙과 시간 복잡도를 구하는 방법에 대해 공부해 정리해보겠다. 빅오를 표기하기 위해서는 알고리즘의 처리해야 할 데이터의 수 n에 대한 연산횟수 f(n)을 구하여 빅오를 구한다. 각 알고리즘의 연산 획수 함수끼리 비교하지 않고 빅오를 계산 하는 이유는 데이터의 수가 많아짐에 따른 연산횟수의 증가 정도가 더 중요하기 때문이다. 빅오 표기법 규칙 계수 법칙 : "상수를 제거하라" 상수 k >0 , f(n)이 O(g(n)) 이면 kf(n)은 O(g(n))이다. n이 충분히 크기 때문에 상수항을 무시해도 되기 때문. 다음의 경우를 비교..

자료구조 Graph에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다. 코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다. 1. Graph Graph 란 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있다 간접적인 관계가 있는 경우 몇 개의 점과 전에 걸쳐 이어진다. 하나의 점 : 정점 vertex라고 표현 하나의 선 : 간선 edge라고 표현 Graph의 종류 무방향 그래프(Undirected Graph) 연결 완계에서 방향성이 없는 그래프를 말한다. 방향 그래프(Directed Graph) 간선에 방향 정보가 포함되어있는 그래프. digraph라고도 부른다. 완전 그래프(Comp..

자료구조 Tree에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다. 코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다. 1. Tree Tree란 데이터를 순차적으로 나열시킨 선형구조가 아닌, 하나의 데이터 뒤에 여러 개의 데이터가 있는 비선형 구조이다. 단방향 그래프이며 계층적 구조를 갖고 사이클이 없다. 용어 정리 깊이 (depth) : 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현한다. root node는 깊이가 0이고 밑으로 갈수록 Level 1, Level 2로 커진다. 레벨 (Level) : 같은 깊이를 갖고있는 노드를 묶어서 레벨로 표현한다. 높이 (Height) 리프 노드를 기준으로 루트까지의 높이 (height) 트리의 최고 레벨을..

자료구조 Queue에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다. 코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다. Achievement Goals Queue 자료구조에 대해 이해한다 Queue 자료구조가 가진 특징을 학습한다. Queue 자료구조를 사용하기 적합한 상황을 이해한다 다른 자료구조 와의 차이점을 이해하기 위해 자료 구조 내부를 직접 구현한다. Queue 자료구조를 배열로 대체해볼 수 있다. 1. Queue Queue 란 Queue도 Stack과 비슷하게 데이터를 순서대로 쌓는 자료구조이다. Stack과는 다르게, 먼저 들어온 건이 먼저 나오는 구조이다. 선입선출 , Firts-In-First-Out (FIFO) OR Last-In-Last-Ou..

자료구조 Stack과 Queue에 대해서 알아아보고, 이를 어떤 방식으로 사용하는지 알아본다. 코드스테이트 Lesson 내용의 일부와 윤성우의 열혈 자료구조 책을 참고하였다. Achievement Goals 자료구조에 대해 이해한다. Stack , Queue 자료구조에 대해 이해한다 각 자료구조가 가진 특징을 학습한다. 각 자료구조를 사용하기 적합한 상황을 이해한다 다른 자료구조와의 차이점을 이해하기 위해 자료 구조 내부를 직접 구현한다. 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체해볼 수 있다. 0. 추상 자료형 (ADT : Abstract Data Type ) 자료구조를 공부하기에 앞서 추상 자료형 ADT를 먼저 이해하고 시작해야 한다. 추상 자료형은 Computer Science..

꼬리 재귀(Tail recursion in JavsScript) 너무 많은 재귀 호출은 메모리 초과 (Stack overflow) 오류를 발생시킬 수 있다. Tail recursion(꼬리 물기 재귀)은 call stack에 새로운 stack을 생성하지 않고 함수를 참조할 수 있게 한다. 다음 연산에 필요한 값을 다음 루틴에 넘기면 호출당했던 곳으로 돌아와 연산을 거칠 필요가 없어 메모리에 쌓이지 않고 한 번씩만 호출되도록 만드는 형태이다. 많이 사용하는 예제인 factorial 함수를 예로 들어보자. [일반적인 재귀 코드] function factorial(n){ if(!) return 1; return n*factorial(n-1); } 위의 코드는 다시 호출 당했던 곳으로 돌아가게 되는 일반적인 재..

재귀 함수와 메모리 사용량 간의 관계 문제를 풀다 보면, 재귀 함수가 참 편리할 때가 있다. 반복문보다는 재귀를 쓸 때가 더 편할 때도 있지만, 아무래도 함수를 한번 더 콜 하기 때문에 부담스러운 부분이 있는 것 같다. 프로그래머라면 사용하는 함수 또는 메서드, 알고리즘의 시간 복잡도나 메모리 사용량에 대해서 알아야 한다. 앞으로도 많이 사용할 재귀의 메모리 사용량에 대해서 알아보자! 1. 재귀란? 간단하게, 재귀에 대해서 먼저 알아보자! 재귀는 간단한 동작 하나를 반복적으로 처리해야 할 때 , 간단한 동작을 재귀를 사용하여 반복함으로써 작업을 단순화 시킬 수 있는 자료구조이다. 재귀는 1. 주어진 문제를 비슷한 구조의 더 작은 문제로 나룰 수 있는 경우 2. 중첩된 반복문이 많거나 반복문의 중첩 횟수(..