Algorithm + DS

피보나치 수열의 n번째 수를 구하는 문제. 재귀(Recursion)를 이용해 아래로 내려가는 Top-Down 방법과 0번째 부터 n 번째 까지 더해가며 구하는 Bottop-Up 방법을 사용했다. 재귀를 사용하여 풀었을 때 답은 구해졌지만, 실행 시간이 오래 걸려서 테스트를 하나 통과하지 못했다. 요구 시간은 0.1 이었고, 재귀를 이용한 풀이는 0.368초...

Bubble Sort 는 배열의 가장 왼쪽 혹은 오른쪽에서 시작하여 다음숫자와 크기를 비교하여 큰 것을 가장 끝으로 보내는 정렬 방법이다. 두가지 방법으로 풀어봤는데, 첫번째 풀이는 while 문에서 숫자 교환이 일어났을 때 바뀌는 changed라는 변수를 사용하여, 숫자 교환이 일어나지 않을 때 까지(정렬이 완료 됐을 때 까지) 배열의 처음부터 끝까지 ...

Stack 기본 개념 stack(스택)은 LIFO(Last In First Out)를 따르는 자료구조이다. 바닥에 책을 쌓은 다음, 다시 한권 씩 들어올릴 때 가장 위의 책부터 들어올리게된다. 주로 사용하게 되는 메소드는 pop()과 push() 가 있고, 각각 스택에 자료를 빼고 넣는 역할을 한다. 그림을 통해 스택의 동작 과정을 보자. 123123....

Linked List 정의 링크드 리스트(Linked List)는 노드(자료)들이 한 줄로 연결되어있는 방식으로 데이터를 저장하는 자료구조이다. 각 노드는 데이터와 포인터를 가지고 있다. 포인터는 다음 혹은 이전의 노드와의 연결을 담당한다. 자동적으로 길이가 늘어나는 배열이라고 생각할 수 있겠는데, 사실 지금 공부하고 있는 자바스크립트에서는 큰 의미가 없지...

정의 그래프 그래프(Graph)는 연결되어 있는 데이터들의 관계를 표현하는 자료구조이다. 다양한 형태를 가질 수 있는 여러개의 노드(Node)와 노드 사이를 잇는 엣지(Edge)로 이루어져 있다. 그래프를 분류하는 방법에는 여러가지가 있다. 엣지의 상태에 따른 분류로는단방향 그래프(Undirected), 양방향 그래프(Directed), 가중치 그래프(W...

개념 해시테이블(Hash Table)은 키(Key)를 값(Value)에 매핑하여 저장하는 자료구조이다. 두가지 데이터를 연결하여 저장하는 자료구조라고도 할 수 있다. 배열에서는 인덱스를 가지고 값을 찾지만(array[index]), 해시테이블을 이용하면 인덱스가 아닌 키로 매칭되는 값을 찾을 수 있다. 전화번호부에서 이름-전화번호 를 키-값이라고 생각하면 ...

개념 시간복잡도(Time Complexity)는 어떤 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 의미한다. 어떤 알고리즘을 수행하는데 필요한 기본 연산이 얼마만큼의 시간이 걸린다고 할 때, 기본연산의 최대 개수를 나타낸다. 시간복잡도는 입력의 크기에 따라 다양해질 수 있기 때문에 측정방법도 다양하다. 주로 사용되는 방법은 모든 입력에 대해 걸리는 ...

N-Queens N-Queens Problem은 NxN의 체스판에 N개의 퀸을 서로 충돌하지 않게 놓는 방법 혹은 그 수를 구하는 문제다. 예를 들어 4-Queens의 정답은 두 가지가 가능하다. 4queens1.png4queens2.png N-Queens의 정답을 찾기 위해서 필요한 키워드는 DFS(깊이우선탐색, Depth First Search), 재귀...