FE BE 개발 메모장/알고리즘과 자료구조(JS)
깊이 우선 탐색, 너비 우선 탐색
깊이우선 탐색(DFS, Depth-First Search) 루트 노드에서 시작해서 연결된 노드의 가지 하나의 최하단 노드까지 탐색 하고, 그다음 노드의 최하단까지 탐색한다. 전체적으로 깊게 탐색 한다고 해서 깊이 우선 탐색이라불린다. 특징 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다. 전위 순회(Pre-Order)를 보함한 다른 형태의 트리순회는 모두 DFS의 한 종류이다. 그래프 탐색의 경우 반드시 어떤 노드를 방문했었는지 여부를 반드시 검사해야한다. 그렇지 않을경우 무한루프에 빠질 위험이 있다. 너비우선탐색(BFS, Breadth-First Search) 루트 노드에서 시작해 탐색한 노드의 가장 인접한 노드들부터(좌우로) 먼저 탐색 한다음, 그 다음 자식 노드들을 넓게 탐색한다. 특징 직..
알고리즘의 기초 Big-O Notation과 복잡도(Complexity)
Big-O Notation Big-O는 알고리즘의 효율성을 나타내는 지표로서 알고리즘의 시간 복잡도와 공간 복잡도에 사용하며, 불필요한 연산들을 제거하고 알고리즘 분석을 쉽게 할 목적으로 사용된다. 시간복잡도와 공간복잡도 시간 복잡도(Time Complexity): 입력된 N의 크기에 따라 실행되는 조작의 수를 나타낸다. 공간 복잡도(Space Complexity): 알고리즘이 실행될 때 사용하는 메모리의 양을 나타낸다. 각 Big-O 표기법에 대한 시간복잡도(Time Complexity) Big-O는 다양한 실행시간이 존재하여, 다양하게 표현되지만, 가장 대표적인 표기법을 나열했다. O(1) 시간 복잡도 Constant time 입력 데이터의 크기에 상관없이 일정한 시간이 걸리는 알고리즘의 시간복잡도를..
자료구조 Graph
그래프(Graph) 단순히 노드(N, Node)와 그 노드를 연결하는 간선(E, edge)을 하나로 모아놓은 자료 구조이다. 연결 되어있는 객체 간의 관계를 표현할 수 있고, 여러개의 고립된 부분 그래프로 구성될 수 있다. 그래프의 특징 그래프는 네트워크 모델이다 2개 이상의 경로가 가능하다.(노드들 사이에 무방향/방향 또는 양방향 경로를 가질 수 있다) 루트 노드라는 개념이 없다 부모-자식 관계개념이 없다. 간선의 유무는 그래프에 따라 다르다. 그래프와 트리의 차이 그래프(Graph 트리(Tree) 정의 노드와 그 노드를 잇는 간선을 하나로 모아 놓은 자료구조 그래프의 한 종류 DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한종류 방향성 방향 그래프(Directed)..
자료구조 Tree, BST
Tree 트리로 부르는 이유는 거꾸로 뒤집어 놓은 나무처럼 생겼다고 해서 불려진 이름이다. 트리의 특징. 그래프의 한 종류이다. 트리는 계층 모델이다. 트리의 순회는 Pre-oreder, In-order, Post-order로 이루어진다. 트리의 종류는 이진 트리, 이진 탐색 트리, 균형 트리, 이진 힙 등이 있다. 트리(Tree)의 구조 루트노드(Root Node) : 트리의 맨 위에 있는 노드로, 트리 당 단 하나의 루트만 있다. 부모노드(Parent Node) : 루트 노드를 제외하고, 간선으로 연결된 자식 노드 위의 노드를 부모노드라고 부른다. 자식노드(Child Node) : 특정 노드 아래로 연결된 노드를 자식 노드라 부른다. 단말노드(Leaf Node) : 자식이 없는 노드로, 말단 혹은 잎..
연결리스트와 이중연결리스트(LinkedList Family)
연결 리스트(Linked List) 이름 그대로 연결 리스트이다. 각 데이터들을 줄로 매듭을 지어 묶어놓은 것처럼 데이터들 끼리 이어져 있다는 추상적인 이유로 연결 리스트라고 부른다. 이 데이터들은 동적이며, 이어주는 줄을 링크라고 부른다. 맨 앞의 노드를 의미하는 head와 맨 마지막노드는 tail이라는 구조로 이어져있다. 노드의 구조 연결리스트의 각 노드(node)는 두개의 필드가 존재한다. 값을 저장해줄 데이터 필드 : data 나 value등으로 불린다. 다음 노드의 주소를 담고있는 포인터 : next나 next link, pointer라고 불린다. 이런 연결리스트 구조는 쭉 나열되어 있는 배열의 구조와 다르게 다양한 공간에 흩어져있는 데이터들을 포인터로 이어주기만 하 면 된다. 처음 노드는 he..
자료구조 스택(Stack)과 큐(Queue)
스택(Stack) 스택(Stack)을 번역하면 쌓다, 쌓아올리다 라는 의미를 가지고있다. 스택 자료구조는 물건을 쌓아 두는것처럼 차곡차곡 쌓아 올린 형태의 자료구조를 말한다. 스택의 특징 LIFO (Last In First Out) 구조로, 맨 위에서 자료를 넣고 뺄 수 있는 구조이다. 스택에 데이터를 push하면 항상 최상단에 들어가고, pop 으로 최근에 push를 한 데이터가 나온다. 자료가 없을 경우 pop을 하게되면 stack underflow, 스택의 크기 이상의 자료를 push할 경우 stack overflow 스택의 구조 push('item') : 새로운 데이터를 Storage안에 있는 통 안에 쌓아 올리는 작업을 한다. pop() : 받아놓은 데이터의 맨 위에 있는 물건을 내보낸다. TO..
OOP(Object-Oriented Programming)
객체(Object) 객체는 실제로 존재하는 어떠한 대상(실체한 사물)의 데이터와 그 데이터의 관련된 동작을 포함하는 개념이다. 객체 지향 프로그래밍(Object-Oriented Programming) 객체 지향 프로그래밍은 컴퓨터 프로그래밍 패러다임 중 하나로, 어떠한 문제의 데이터를 추상화 시켜 상태와 행위를 가진 독립된 여러 객체를 만들고, 그 객체들 간의 상호작용으로 결과를 반환하는 프로그래밍 기법이다. 예를 들자면 필요한 컴퓨터 청사진이 있다. 그 청사진을 Class라고 부른다. 컴퓨터를 실행시키기 위해서는 다양한 부품들이 존재하는데, 대표적으로 CPU, 메인보드, 램 메모리, 그래픽카드, SSD 또는 하드, 파워 서플라이, 쿨러, 화면을 출력할 모니터까지 이 각각의 독립된 객체(부품)들이 모여서..