데이터의 추상적 형태와 그 데이터를 다루는 방법만을 정해놓은 것을 가지고 ADT(Abstract Data Type) 혹은 추상 자료형이라고 한다. ADT중 널리 쓰이는 큐, 스택,트리에 대해 알아보자 큐(Queue) - 데이터를 집어넣을 수 있는 선형(linear) 자료형이다. - 먼저 집어넣은 데이터가 먼저 나온다. (FIFO, First In First Out) - 데이터를 집어넣는 enqueue, 데이터를 추출하는 dequeue - 큐는 순서대로 처리해야 하는 작업을 임시적으로 저장해주는 버퍼(buffer)로 많이 사용 쓰임 - 대기열 예) 프린터에서 인쇄 작업을 처리하는데 사용되는 대기열 - 네트워크 통신 예) 인터넷 라우터는 패킷을 수신하면 해당 패킷을 대기열에 추가하여 다음 목적지로 전송 스택..
DFS란 깊이 우선 탐색이라는 의미로 트리나 그래프에서 한 루트로 탐색하다 특정 상황에서 최대한 깊숙이 들어가서 확인한 뒤 돌아가 다른 루트로 탐색하는 방식이다. 일반적으로 재귀호출을 사용하여 구현하지만 단순한 스택 배열로 구현하기도 한다. 갈림길이 나타날 때마다 다른길이 있다는 정보만 기록하면서 자신이 지나간 길을 지워나간다. 그러다 막다른 곳에 도달하면 갈림길까지 돌아가면서 이 길은 아님이라는 표식을 남긴다. 그렇게 갈림길을 순차적으로 탐색해 나가다 목적지를 발견하면 그대로 해답을 내고 종료된다. 👍장점 - 현 경로상의 노드들만 기억하면 되므로 저장 공간의 수요가 비교적 적다. - 목표 노드가 깊은 단계에 있을 경우 결과물을 빨리 구할 수 있다. 👎단점 - 결과물이 없는 경로에 깊이 빠질 가능성이 있..
정렬알고리즘이 뭔가요? 📚특정원소들을 사전처럼 일정한 순서대로 열거하는 알고리즘입니다. 왜중요하나요? 🔎탐색에 용이합니다. 정렬이 되지 않은 숫자에서 특정 숫자값을 찾으려면 결국 하나씩 탐색을 해야합니다. 하지만 정렬이된 숫자라면 훨씬 빨리 원하는 숫자를 찾을 수 있습니다. 종류에는 무엇이 있나요? 1. 버블정렬 더보기 인접한 두개의 요소를 비교해서 조건에 따라 위치를 교환해줍니다. 배열길이보다 1번 적게 비교가 일어나며 한번 정렬이 일어나면 마지막요소는 고정되므로 그 때마다 하나 더 적게 비교가 일어나게 됩니다. 두 요소를 비교하고 교환만 이루어지므로 가장 간단하고 쉬운 정렬방법이지만 최악의 경우 모든 요소를 교환해서 시간복잡도O(n^2)가 좋지 않습니다. 저는 왼쪽에서 오른쪽으로 정렬되는 상황만 있는..
메모이제이션은 변수로 미리 배열의 값을 저장해두고 다음 인덱스의 배열을 만들때 사용할 수 있는 방법이다. 동일한 계산을 반복할때 이전에 계산한 값을 메모리에 저장해두어 불필요한 계산을 없애고 실행속도를 빠르게 한다. 메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다. 출처 - 위키피디아 가장 흔히 사용되는 피보나치 수열을 구하는 함수를 살펴보자. let memo = [0,1] function fibonacci(n) { if(memo[n] === undefined){ memo[n] = fibonacci(n-2)+f..
