요리사가 요리를 할때 적절한 재료, 도구, 레시피가 필요하듯개발자는 적절한 데이터, 자료구조, 알고리즘을 이용해야합니다.자료구조란, 메모리를 효율적으로 사용하여 빠르고 안정적으로 데이터를 처리하는 것이 목표로상황에 따라 유용하게 사용될 수 있도록 특정 구조를 이루고 있
코딩테스트 연습을 하다보면 가끔 효율성테스트가 존재합니다.이는 알고리즘의 로직을 코드로 구현할때 입력값(N)의 변화에따라 연산 회수에 비해어느정도의 시간이 소요되는지 나타냅니다.프로그램의 성능을 파악하기 위해서는 고려할 것들이 있습니다.입력의 크기, 하드웨어 성능, 운
배열은 연관된 테이터를 연속적인 형태로 구성된 구조를 가집니다.배열에 포함된 원소는 순서대로 번호(index)가 붙습니다.고정된 크기를 가지며 일반적으로 동적으로 크기를 늘릴 수 없습니다.(JavaScript처럼 대부분의 스크립트 언어는 동적으로 크기가 증감가능합니다.
배열이 추가와 제거가 반복되는 로직에서 불리하다면 무엇을 사용해야 할까요?연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조입니다.각 요소는 노드(node)라고 부르며 데이터 영역과 포인터 영역으로 구성됩니다.메모리가 허용하는한 요소를 제한없이 추가할 수
Last In First Out(선입후출)이라는 개념을 가진 선형 자료구조 입니다.바닥이 막힌 상자를 생각하면 쉽게 이해하실 수 있습니다.스택 메모리는 함수가 실행되면 지역변수, 매개변수가 저장되는 메모리 영역입니다.다음 코드가 실행되면 어떤일이 발생할까요?안쪽에 위치
First In Fist Out(선입선출) 개념을 가진 선형 자료구조 입니다.영화 예매를 위해 줄을 설때 먼저 선사람이 먼저 예매를 할 수 있다고 생각하면 쉽습니다.Linear Queue와 Circular Queue가 존재합니다.선형 큐는 배열과연결 리스트로 구현이 가
해시 테이블은 한정된 배열 공간에 Key를 index로 반환하여 값들을 넣습니다.그렇다면 index를 어떻게 구할까요?키와 값을 받아 키를 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료구조입니다.값을 삽입시 O(1)의 시간 복잡도를 가지고 키를 알
그래프는 정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조 입니다.정점 집합과 간선 집합으로 표현 가능합니다.정점은 여러 개의 간선을 가질 수 있습니다.크게 방향 그래프와 무방향 그래프로 나눌 수 있습니다.간선은 가중치를 가질 수 있습니다.사이클이 발생할
방향 그래프의 일종으로 정점을 가리키는 간선이 하나존재한다.가장 상위의 정점을 Root, 각 정점을 Node, 더 이상 자식이 없는 정점을 Leaf Node라고 합니다.이밖에도 Root로부터 몇번째 깊이인지를 표현하는 Level 한 정점에서 뻗어나가는 간선의 수를 De
이진 트리를 이용한 자료구조로 우선순위가 높은 요소가 먼저 나가기 위해요소가 삽입, 삭제 될때 즉시 정렬되는 특징이 있습니다.여러 개의 값들 중 최대값과 최소값을 빠르게 찾아낼 수 있습니다.주의!우선순위 큐를 힙이라고 부르기도 하지만 정확히는 아닙니다.배열을 우선순위에
트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조입니다.각 간선은 새롭게 추가되는 정보를 가지고 있고 정점은 이전 정점으로부터 더해진 문자열 정보를 갖습니다.검색어 자동완성, 사전 찾기 등에 응용된다.L이 문자열의 길이일 때 탐색, 삽입은 O(L
선형탐색은 순서대로 하나씩 찾는 탐색 알고리즘입니다.따라서 O(n)의 시간복잡도를 갖습니다.정렬 되어있는 요소들을 반씩 제외하며 찾는 알고리즘입니다.O(logn)의 시간복잡도를 갖습니다.반드시 정렬이 되어있어야 한다. 정렬이 되어있지 않으면 정렬을 진행해야하기 때문에그
너비 우선 탐색(BFS) 너비 우선 탐색은 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 입니다. 특징 큐를 이용하여 구현할 수 있다. 시작 지점에서 가까운 정점부터 탐색한다. 정점수 V, 간선수 E일때 BFS의 시간복잡도는 O(V + E
그리디는 매 선택에서 현재 상황에서 가장 최적인 선택지를 선택하는 알고리즘으로최적해를 보장해주지 않습니다. 다음과 같은 상황에서 A에서 F로 가는 경우의수는A - B - C - FA - D - E - F2가지가 있습니다.그리디 알고리즘을 사용하면 시작지점 A에서 가장
백트래킹 백트래킹은 모든 경우의 수를 탐색하는 알고리즘 입니다. DFS나 BFS를 이용할 수 있고 탐색에서 사이클이 발생할 수 있다면 BFS를 이용하는 것이 편합니다. 모든 경우의 수를 탐색하기 때문에 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 가지치기(Pr
동적 계획법(Dynamic Programming) 동적 계획법은 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식입니다. 메모리를 많이 사용하는 대신 빠른 성능을 자랑하고 두 가지 방법론이 있습니다. 메모이제이션(Memoization) 타뷸레이션(Tabulatio