CS공부: 데이터 스트럭처
1.자료형: 숫자형, 문자형
자료형 데이터 스트럭처를 공부하기 전에 간단한 자료형을 알아보자. 컴퓨터는 2진법으로 이루어져 있다. 0000 0000은 0을 의미하고 0000 0001은 1을 의미하고 0000 0010은 2의 1승, 즉 2를 의미한다. 0000 0011은 2의 1승+1을 의미한다.
2.자료구조: 연결 리스트(Linked List)
\[Javascript] 연결 리스트 구현하기 - 클래스 신택스 대신 프로토타입을 사용하려거든 참조\[자료구조] 연결리스트 with JavaScript - 꼼꼼한 개념설명 및 클래스로 구현을 하려거든 참조.본 글에서는 jangws님의 \[JS 자료구조] 단일 연결 리스
3.자료구조: 스택과 큐
\[JS 자료구조] 스택(Stack)과 큐(Queue) 를 참조했다.가장 마지막에 요소를 추가할 수 있고,가장 마지막 요소를 제거할 수 있는 자료구조를 의미한다.지난번 글 연결리스트에서 언급한 것 처럼, 스택은 직접 구현하는 것보다 Array를 이용하는 것이 빠르다.
4.자료구조: 트리, 힙, 우선순위 큐
트리 자료구조란 '하나의 부모'와 '하나 이상의 자식'으로 구성된 그래프를 의미한다. 데이터의 계층을 나타내는데에 사용된다.트리는 다음의 특징을 갖는다.1\. 정점들이 연결되어 있다.2\. 연결된 그래프들 간에 cycle이 없다.3\. cycle이 없다는 것은 n개의
5.자료구조: 서로소 집합(Union-Find 알고리즘)
'합집합-찾기' 알고리즘은 집합에 관한 알고리즘이다.Find : 어떠한 요소가 어떤 집합에 속해있는지를 찾는 과정이다.Union : 요소들을 하나의 집합에 합하는 과정이다.Union-find 알고리즘이 시행되고 나면, 모든 요소들은 특정한 집합에 속하게 된다. 이를 바
6.자료구조: 그래프, BFS, DFS
그래프란 노드와 간선으로 이루어진 자료구조를 의미한다.다른 자료구조와 비교하면링크드 리스트 : NextNode (혹은 PrevNode와 NextNode)라는 포인터를 가지고 있다. 트리 : 하나의 부모 노드가 여러개의 자식 노드를 가진다.그래프 : 여러개의 노드가 여러
7.알고리즘: 크루스칼 알고리즘 (최소 신장 트리)
크루스칼 알고리즘은 가중 그래프 내에서 최소 비용으로 모든 노드를 연결하는 알고리즘이다. 이 알고리즘을 통해 만들어진 그래프는 '하나의 루트 노드'로, '최소 비용'으로, '모든 노드를 연결'하는 최소 비용 신장 트리(minimum spanning tree, MST)이
8.알고리즘 : 다익스트라 알고리즘, 프림 알고리즘
에르허츠 데이크스트라가 여친이랑 데이트하다가 10분만에 고안한 최단경로 알고리즘으로 알려져 있다.O(n^2)의 시간 복잡도를 가지지만, 우선순위 큐를 적용할 시에 O((V+E) log V)의 시간 복잡도로 소폭 개선할 수 있다. (우선순위 큐로 최단거리의 노드를 찾는
9.알고리즘: 플로이드-워셜 알고리즘
다익스트라 알고리즘은 특정 s에서 e까지의 최단 거리를 구하는 데에 사용된다.그렇다면 임의의 i에서 j까지의 최단거리를 구할 때에는?그래프의 지점에 대해서 서로의 최단 거리를 구하면 된다.참고 - 안경잡이 개발자참고 - 이코테 강의(프리라이프님 정리)다익스트라 알고리즘
10.알고리즘 : 벨만-포드 알고리즘
플로이드 워셜 알고리즘에 아래와 같은 부분이 있었다.graph\[a]\[b] = Math.min(graph\[a]\[b], graph\[a]\[k] + graph\[k]\[b]);해당 부분을 '어떤 노드'가 업데이트 될 때 '다른 노드'에서 '또 다른 노드'로 가는 모
11.알고리즘 : 위상 정렬
위상 정렬은 노드들의 선후 관계에 따라 노드들을 나열하는 알고리즘이다.가령, 메인 퀘스트 2를 수행하기 위해서는 서브 퀘스트 1, 2, 3을 수행해야 하고, 서브 퀘스트를 받기 위해서는 메인 퀘스트 1을 수행해야 하는 게임이 있다고 해보자.위상 정렬의 결과는 \[메인
12.자료형. 비트연산자 / 문자열조작
몇몇 코딩테스트에서 비트연산자, 문자열조작 등 기본적인 언어 사용법이 나와서 정리할 필요가 있어 정리한다.@nulbo \[TIL / JavaScript] 비트 연산자에 잘 정리되어 있다.num.toString(2)을 이용하면 2진법의 비트로 이루어진 문자열을 반환한다.
13.알고리즘 치트시트 1. 핵심편 - 프레임형 사고
데이터 구조를 다룰 때에는 '순회'와 '접근'의 측면을 핵심으로 볼 필요가 있다. 그리고 이를 '추가, 삭제, 검색, 수정'으로 구체화할 수 있다. 연결 리스트와 배열배열은 확장하는 경우 배열의 복사를 진행하므로 O(N)의 시간 복잡도를 가진다. 연결 리스트는 O(1)
14.알고리즘 치트시트 2. 동적 계획법
동적 계획법의 프레임은1\. '상태'와 '선택' 찾기2\. 'DP 배열'과 'DP 함수'의 정의를 명확히 하기3' 상태 간의 관계 찾기로 요약할 수 있다.동적 계획법의 두 가지 속성을 가진다. 참조1\. Overlapping Subproblems - 하위 문제의 존재