자료구조&알고리즘

요리에 비유할 수 있음요리를 하기 위해서는 재료와 조리도구, 요리 레시피가 있어야 가능하다.이 때 재료는 데이터, 조리도구는 자료구조, 요리 레시피는 알고리즘에 비유할 수 있다.이 세 가지를 잘 다루는 사람이 실력 있는 개발자가 될 수 있다.자료구조 + 알고리즘 = 프

고객이 영화관에서 영화를 예매하는 과정을 전산화해보자현실 세계고객이 어떤 영화를 볼지 선택영화 예매를 위해 대기 줄에 섬차례가 오면 영화 선택 및 좌석 선택최종적으로 영화 예매 비용 지불소프트웨어 세계영화 검색 : Trie대기 줄 : Queue좌석 선택 : HashTa

프로그램의 성능을 대략적으로 파악하기 위한 상대적인 표기법시간복잡도를 나타내기 위한 방법출처: 이선협 강사님 데브코스 강의 자료O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

연관된 데이터를 연속적인 형태로 구성한 구조이다.배열에 포함된 원소는 순서대로 번호(index)가 부여된다.고정된 크기를 가지며 일반적으론 동적으로 크기를 늘릴 수 없다.=> 하지만 JavaScript처럼 대부분 스크립트 언어는 동적으로 배열 크기를 조절할 수 있다.원

연결 리스트는 각 요소를 포인터로 연결하여 관리하는 선형 자료구조이다.각 요소는 노드라고 부르고 데이터 영역과 포인터 영역으로 나뉜다메모리가 허용되는 범위에서 제한없이 요소 추가가 가능하다.요소 탐색은 O(n)이 소요된다.요소 추가, 제거는 O(1)이 소요된다.Sing

Last In First Out(후입선출) 이라는 개념을 가진 선형 자료구조이다.바닥이 막힌 상자와 같은 유형요소를 넣는 행위를 PUSH, 빼는 것을 POP, 맨 위의 요소를 TOP이라고 부른다.기본적으로 스택 메모리에 스택 자료구조가 사용된다.함수 호출 및 실행을 단

큐(Queue)

해시 테이블 키와 값을 받아 해싱(Hashing)하여 나온 index에 값을 저장하는 선형 자료 구조이다. 삽입은 O(1), 키를 알고 있다면 삭제, 탐색도 O(1)의 시간 복잡도를 가진다. 각 테이블에 해당하는 index를 bucket이라고 부른다. 해시 함수 입력

정점과 정점 사이를 연결하는 간선으로 이루어진 비선형 자료구조이다.정점 집합과 간선 집합으로 표현 가능하다. 정점은 node, 간선은 edge라고도 부른다.실제 사례로 쓰이는 경우는 지하철 노선도 같은 지도나 페이지 랭크에서 쓰인다.정점은 여러 개의 간선을 가질 수 있

방향 그래프의 일종으로 정점을 가리키는 간선이 하나 밖에 없는 구조이다.Root(루트) : 가장 상위 노드Node(노드) : 각 정점을 노드라고 부른다.Leaf Node(리프 노드) : 자식이 없는 노드Level(레벨) : 루트로 부터 몇 번째 깊이인지 나타내는 지표D

FIFO인 큐와 달리 우선 순위가 높은 요소가 먼저 나가는 큐이다.우선순위 큐는 자료구조가 아닌 개념이다.이러한 우선순위 큐를 구현하기에 적합한 자료구조가 힙이다.이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제될 때 바로 정렬되는

문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조검색창의 문자 자동 완성 기능이 대표적인 사용 예이다.검색어 자동완성, 사전 찾기 등에 응용된다.문자열을 탐색할 때 단순하게 비교하는 것보다 효율적으로 찾을 수 있다.L이 문자열의 길이이면 삽입은 O(L)만

요소들을 일정한 순서대로 열거하는 알고리즘정렬 기준은 사용자가 정하기 나름이다.크게 비교식과 분산식 정렬로 구분한다.대부분의 언어가 빌트인으로 제공한다.삽입, 선택, 서블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다.비교 시뮬레이션 사이트 : https&#x

정리가 안된 책장에서 원하는 책을 찾는 방법에는 뭐가 있을까?순서대로 하나씩 찾는 탐색 알고리즘이다. O(n) 시간 복잡도가 걸린다.나이 맞추기 게임 : Up & Down으로 기준점을 정하여 찾는다.정렬되어 있는 요소들을 반씩 제외하면서 찾는 알고리즘이다. O(log

너비 우선 탐색 (BFS) 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 BFS의 특징 Queue를 이용하여 구현할 수 있다. 시작 지점에서 가까운 정점부터 탐색한다. V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V+E)

매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘이다. 항상 최적해를 보장해주지는 않는다.보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다.크루스칼, 다익스트라 알고리즘 등에 사용된다.직관적인 문제 풀이에 적합하다.거스름돈을 최대한 큰 단위로 거슬러 주려

내용😅 해당 내용은 공부하면서 정리한 글입니다. 틀린 부분이나 오해하고 있는 부분이 있다면 피드백 부탁드립니다.

문제를 해결할 때 작은 문제부터 해결하여서 큰 문제를 해결하는 문제 풀이 방식이다.백트래킹과 같이 특정 알고리즘이 아니고 문제 해결 방식이다.Dyanmic Programming(DP)라고도 부른다.메모리를 많이 사용하지만 빠른 성능을 보이므로 효율이 좋을 때가 있다.동

항상 여러가지 풀이 방법이 있을 수 있으니 다양한 풀이 방법을 찾아보자.같은 문제라도 다른 풀이 방법이 존재하므로 문제를 해결했다고 해서 끝날 것이 아니라 다른 사람의 풀이도 참고해보는 것이 좋다.항상 예외(엣지 케이스)가 있을 수 있다.문제에 주어진 테스트 케이스만