자료구조

배열은 여러 개의 값을 순차적으로 나열한 자료구조이다. 프로그래밍에서 배열은 사용 빈도가 매우 높은 기본적인 자료구조이다. 특징위에서 기술한 것처럼 배열은 여러 개의 값을 저장하는 자료구조이다. 배열은 여러개의 동일한 타입의 값을 동일한 크기의 연속된 메모리 공간에 순차적으로 값을 저장하는 데이터 모음이다. 배열을 구성하는 요소 값을 배열에 저장하는데, 이때 요소를 저장하는 위치 번호를 나타내는 숫자를 인덱스라 한다.인덱스는 0부터 배열 전체 요소의 수 - 1 까지 존재한다.  위의 사진에서 int로 타입을 선언했다면 int를 제외한 다른 타입의 값은 해당 배열에 저장할 수 없다. 배열의 표현C언어의 배열을 살펴보자int array [10] = { 35, 33, 11, 12, 52, 63, 13, 64,..

문제https://www.acmicpc.net/problem/1972 풀이이 문제는 주어진 각 문자열을 순회하며 현위치의 문자와 정해진 거리만큼 떨어져있는 문자를 합친 문자열의 중복 확인한 문제이다. 중복 확인은 Set 객체를 이용했으며, Set 객체 사용 연습을 위해 사용했다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number))const [n] = input.shift();let map = input.slice();let an..

문제 설명https://www.acmicpc.net/problem/13414문제 풀이 방법이번 문제는 중복 처리 알고리즘 문제이다. 원래는 객체 리터럴을 이용해 인덱스를 저장해 풀이를 진행했지만, 케이스가 길어지면 시간 초과 에러가 발생할 수 있다 생각했다. 그래서 Set 객체를 이용해 다시 풀어봤다. Set은 먼저 나온 요소만 저장하기 때문에 원본 요소의 뒤에 나온 중복 요소를 순서대로 처리할 수 있다.정답 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n')const [N, L] = in..

힙 Heap 정의 힙은 완전 이진 트리 자료구조 이다. 힙에서는 항상 루트 노드를 제거한다. 종류 최소힙 (min heap) 루트 노드가 가장 작은 값을 가진다. 가장 작은 데이터가 우선적으로 제거된다. 최대힙 (max heap) 루트 노드가 가장 큰 값을 갖는다. 값이 가장 큰 데이터가 우선적으로 제거된다. 완전 이진 트리란? 루트 노드 부터 시작하며 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 데이터가 차례대로 삽입되는 트리를 의미한다. 힙에 새로운 원소가 삽입될 때 새로운 원소가 삽입되었을 때 O(log N)의 시간 복잡도로 힙 성질을 유지할 수 있다. 삽입시에 부모 노드와 크기를 비교하여 자리를 바꾼다. (최소힙은 부모노드 보다 작으면 up, 최대힙은 크면 up) 비교결과가 false 혹은 노드 도..

큐 (Queue) 선입선출 FIFO(First In First Out)의 자료구조이다. 데이터가 들어오는 위치는 가장 뒤에 있고, 나가는 위치는 가장 앞에 있어서, 선입선출의 구조를 갖게된다. 즉, 먼저 들어온 데이터가 먼저 제거된다. 큐의 동작 1️⃣ Enqueue : 큐에 데이터를 추가한다. 큐가 꽉 차있을 때 Overfolw condition이 된다. 2️⃣ Dequeue : 큐에서 데이터를 제거한다. 데이터는 들어온 순서대로 빠져나온다. 큐가 비어져 있을 때는 Underflow condition이 된다. 3️⃣ Front : 큐의 앞부분의 데이터를 가진다. 4️⃣ Rear : 큐의 뒷부분의 데이터를 가진다. 큐의 종류 큐를 구현하기에 front(머리)와 rear(꼬리) 두가지 지표를 추적해야 한다..

스택(Stack)이란? 1️⃣ 스택은 뒤로 넣고 뒤만 뺄 수 있는 연결리스트이다. 2️⃣ 스택은 실행이 되는 특정한 순서를 따르는 선형적 데이터 구조이다. 두가지 순서로 동작한다. 1️⃣ LIFO(Last In First Out) : 후입선출 2️⃣ FILO(First In Last Out) : 선입 후출 JS에서는 pop()과 push() 메서드를 이용하면 된다. 중요한 포인트!!! 스택은 크기를 고정해서 사용하기 때문에, 고정된 크기의 스택에 데이터를 계속 넣게 되면 다른 메모리 영역을 침범한다. 이를 StackOverFlow라고 한다. 스택 메모리 영역은 프로그램이 자동으로 사용되는 임시 메모리 영역이다. (지역변수, 매개변수, 리턴 값 같이 잠시 사용되고 사라지는 데이터를 저장하는 영역) 프로세스..