자료구조 및 알고리즘

많은 수의 데이터를 다룰 때 사용하는 자료구조각 데이터를 인덱스와 1:1 대응하도록 구성데이터가 메모리 상에 연속적으로 저장됨인덱스를 이용하여 데이터에 빠르게 접근 가능데이터의 추가/삭제가 번거로운 편미리 최대 길이를 정해서 생성해야 함가변 길이 배열은 배열의 크기를

ADT란 추상적 자료구조로, 실제로 프로그래밍 언어들에서 존재하지 않는 자료구조이다. 자료구조의 방법이 코드로 정해진 것이 아닌, 구조의 행동 양식만 정의된 것이다. 스택과 큐가 ADT의 종류이다. 스택은 Last In, First Out (LIFO) 원칙을 따르는 자

버블 정렬은 배열을 정렬하는 간단한 알고리즘 중 하나이다. 인접한 두 요소를 비교하여 교환하는 방식으로 동작하며, 이 과정을 반복하면서 가장 큰 또는 작은 값이 배열의 끝으로 이동하는 정렬 알고리즘이다.배열의 첫 번째 요소부터 인접한 두 개의 요소를 비교한다.앞의 요소

깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다.미로를 생각하면, 한 방향으로만 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 뒤로 돌아

node와 edge로 구성된 집합node : 데이터를 표현하는 단위edge : 노드를 연결그래프는 여러 알고리즘에 많이 사용되는 자료구조유니온 파인드, 위상 정렬, 다익스트라, 최소 신장 트리 등등에 사용엣지를 중심으로 표현출발 노드, 도착 노드, 가중치를 저장가중치가

인접한 데이터를 비교하며 자리를 바꾸는 방식시간 복잡도 O(n^2)sudo code앞의 데이터를 정렬 해가면서 삽입 위치를 찾아 정렬하는 방식시간 복잡도 O(n^2)sudo code최소 또는 최대 값을 찾아서 가장 앞 또는 뒤부터 정렬하는 방식시간 복잡도 O(n^2)s

최소 신장 트리(minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로 하는 트리 -> 크루스칼, 프림 알고리즘이 있음다음과 같은 도시와 길이 있다고 생각해보자도시: A, B, C, D길(가중치)A-B: 1A-

노드와 링크로 구성된 자료구조(그래프의 일종, Cycle 없음)계층적 구조를 나타낼 때 사용폴더 구조, 조직도 등등..트리의 구조특징하나의 노드에서 다른 노드로 이동하는 경로는 유일노드가 N개인 트리의 Edge의 수는 N-1개cycle X모든 노드는 서로 연결되어 있음

매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법빠르게 근사치를 구할 수 있다.결과적으로는 최적해가 아닐 수도 있다.예시N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때, 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기종료 시간 기준으로 정렬먼저 종료되

큰 문제를 작은 부분 문제로 나누어 해결하는 방법(ex.합병정렬, 퀵정렬, 이진검색)분할 정복 과정문제를 하나 이상의 작은 부분들로 분할부분들을 각각 정복부분들의 해답을 통합하여 원래 문제의 답을 구함분할 정복 장점문제를 나누어 처리하며 어려운 문제 해결 가능병렬처리에

촐발점에서 목표점까지의 최단 경로를 구하는 알고리즘한 노드에서 다른 모든 노드로의 최단 경로를 구할 수 이씀간선에 음의 가중치가 없어야 함그리디 + DP형태알고리즘복잡도 : O(ElogV)인접 리스트로 그래프를 나타낸다.최단 거리 배열을 초기화한다출발 노드는 거리가 없

음수 간선이 포함되어 있어도 최단 경로 구할 수 있음음수 사이클이 있으면 정상적으로 동작하지 않음매번 모든 간선을 확인하기 때문에 다익스트라에 비해 느림알고리즘 복잡도: O(VE)

모든 노드 간의 최단 경로를 구하는 알고리즘음의 간선이 포함되어 있어도 사용 가능음수 사이클이 있으면 정상 동작하지 않음알고리즘 복잡도(V^3)

사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘시간 복잡도 : O(V+E)가장 먼저 진입 차수 값을 계산하고 진입 차수 배열을 만든다.진입 차수 배열에서 진입 차수가 0인 노드를 선택하고 선택한 노드를 정렬 배열에 추가한다.그 후 인접 리스트에서 선택된 노드가

문제를 풀기 위해 가능한 모든 경우를 탐색하지만, 불필요한 경우는 미리 제외(가지치기)하여 효율성을 높인다.재귀적 탐색: 현재 단계에서 해를 구성하고, 다음 단계로 넘어가며 재귀적으로 해를 확장한다.조건 검사(가지치기, Pruning): 현재 경로가 문제의 조건을 만족