🥬 상추의 공간

단순 연결 리스트란? 연결리스트는 데이터를 저장하는 자료구조 중 하나이다. 연결리스트 종류도 여러개 있지만, 지금 살펴보려는 것은 단순 연결 리스트이다. 연결리스트는 여러 개의 노드(Node)로 이루어져 있다. 단순 연결 리스트는 2개의 필드를 가지고 있는데, 데이터 필드와 다음 노드 주소를 가지고 있는 링크 필드(포인터)로 구성되어 있다. create, search, insert, remove 등을 효율적으로 구현하기 위해 사용한다고 한다. 구현 코드 전체적인 구현 코드는 다음과 같다. class LinkedList { constructor() { let init = new Node("init"); this.head = init; this.tail = init; this.currentNode = und..

리스트의 중간 값을 찾아 원하는 값과 비교해서 진행하는 알고리즘이다. 이 알고리즘을 이용하려면 먼저 정렬이 되어있어야한다. 중간값 = (최솟값 + 최댓값) / 2 중간값 위치에 해당하는 값과 검색하고자 하는 값과 비교한다. 만약 찾고자 하는 값이 중간 값보다 크다면 중간 값 이하는 검색하지 않고, 작다면 중간 값 이상은 검색하지 않는다. 이렇게 원하는 값 찾을 때까지 검색 범위를 반씩 쪼개며 찾는다. 이분 검색의 시간 복잡도는O(logN)이다. 아래는 예시 문제 및 풀이코드다. [인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 10. 이분검색 문제 임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면 이분검색으로 M이..

선택 정렬 가장 작은 것을 선택해서 제일 앞으로 보내는 알고리즘이다. 제일 작은 원소를 찾아서 탐색 기준점으로부터 가장 앞 원소와 바꾸고 이를 끝까지 반복한다. 시간복잡도는 O(N^2)이다. 데이터 커질수록 엄청 커지므로 최대한 피해야할 시간복잡도다. 아래는 예시 문제 및 풀이방법이다. [인프런] Node.js / 섹션7-정렬과 그리디, 결정알고리즘 / 1. 선택정렬 문제 N개이 숫자가 입력되면 오름차순으로 정렬하여 출력 풀이 function solution(arr) { let answer = arr; let min, tmp, index; for (let i = 0; i < answer.length; i++) { min = Number.MAX_SAFE_INTEGER; for (let j = i; j < ..

스택 마지막에 들어간 데이터가 먼저 나가는 자료구조다. LIFO(Last Input First Out) 구조를 가진다. 실생활 예로는 페이지 뒤로가기, 되돌리기(Ctrl + Z), 책상에 쌓인 책이 있다. 큐 먼저 들어간 데이터가 먼저 나가는 자료구조다. FIFO(First Input First Out) 구조를 가진다. 실생활 예로는 줄을 서는 것이 있다.

슬라이딩 윈도우란? 슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 유사하게 부분 배열들을 활용하는 알고리즘이다. 투포인터와 다른 점은 부분 배열의 길이(크기)가 고정적이다. 그래서 포인터 변수가 2개일 필요가 없다. 이름 그대로 고정적인 너비를 가진 창문을 두고 옆으로 한칸씩 이동하며 값을 구하는 방법이다. 예를들어, N개의 원소를 갖는 배열이 있다. 이때 W의 너비를 갖는 창문이 있다. 너비가 3인 창문을 제일 왼쪽에 배치하고, 창문을 왼쪽에서 시작하여 한 칸씩 오른쪽으로 이동한다. 매 순간 창문 안에서의 정보를 활용해 유추해서 값을 구한다. 즉, 같은 너비의 연속 구간들을 연속적으로 처리할 때 주로 사용되는 테크닉이다. 인접한 구간들 사이에 겹치는 정보를 최대한 활용하는 것이 포인트다. 관련 문제 ..

투 포인터란? 배열에서 원래 이중 for문으로 O(N^2)에 처리되는 작업을 2개의 포인터의 움직임으로 O(N)에 해결하는 알고리즘이다. 여기서 포인터는 C언어의 포인터가 아니라 작업을 처리하기 위해 생성한 변수이다. 포인터라는 변수를 두개를 선언해서 투 포인터라고 부른다. 이분탐색 문제를 투 포인터로도 해결 할 수 있다. 완전 탐색 알고리즘으로 하면 O(N^2)의 수행시간이 나오는데, 투포인터로 시간복잡도를 O(N)으로 줄일 수 있다. 예시 문제: N개의 자연수로 구성된 수열이 있을 때, 합이 M인 부분 연속 수열의 개수 구하기. 수행 제한 시간은 O(N) 투 포인터로 문제 해결하는 방법 시작점(start)과 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다. 현재 부분 합이 M과 같다면,..

완전 탐색이란? 완전 탐색은 브루트 포스라고도 불리는데, brute force를 그대로 해석해보면 '난폭한 힘' 이다. 즉, 브루트 포스는 머리는 쓰지 않고 무식하게 모든 경우의 수를 다 해보는 방법이다. 실생활 예를 들어보면, 비밀번호를 맞춰야 하는데 범위가 0000~9999라면 0000부터 하나하나 다 시도해보는 것이다. '생일이지 않을까?'라고 유추하지 않고 말이다. 문제를 풀 때 기준점을 잡지 못할 때 주로 접근한다고 한다. 종류 순열, 백트래킹(재귀함수), BFS 가 있다. 보통 for, while, 재귀함수를 이용해 풀이한다.