알고리즘 공부

인덱스를 사용하여 값에 바로 접근할 수 있다.새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다. 값을 삽입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.배열의 크기는 선언할 때 지정할 수 있으며, 한 번 선언하면 크기를 늘리거

1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값을 구한다.완전탐색 O(n^2) 솔루션을 → O(n)으로 성능 향상 가능연속된 구간의 원소들을 처리하기를 원하거나, 정렬된 배열에서 무언가를 구할 때 투 포인터를 시도할 수 있다.포인터 2개가 같

스택과 큐는 리스트에서 조금 더 발전한 형태의 자료구조.둘의 구조는 비슷하지만 처리 방식은 다르다.삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out)의 구조로 이루어지는 자료구조.Untitled위치top : 삽입과 삭제가 일어나는 위치연산push

정렬 정렬 알고리즘의 정의 | 정렬 알고리즘 | 정의 | | --- | --- | | 버블(bubble) | 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 | | 선택(selection) | 대상에서 가장 크거나 작은 데이터를 찾아가 선택

DFS(깊이 우선 탐색) 깊이 우선 탐색은 그래프 완전 탐색 기법 중 하나이다. 깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 노드 개수를 V

너비 우선 탐색(BFS, Breadth-First Search)는 그래프를 완전 탐색하는 방법 중 하나도, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.너비 우선 탐색은 선입선출 방식으로 탐색하므로 큐를 이용해 구현한다

이진 탐색 이진 탐색은 데이터가 정렬되어 있는 상태에서 원하는 값을 찾아내는 알고리즘이다. 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 이진 탐색은 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인

그리디 알고리즘은 현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.최적의 해를 보장하지는 않음그리디 알고리즘은 다음과 같은 3단계를 반복하면서 문제를 해결한다.해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를

소수는 자신보다 작은 2개의 자연수를 곱해 만들 수 없는 1보다 큰 자연수를 말한다.이와 같은 의미로 1과 자기 자신 외의 약수가 존재하지 않는 수를 말하기도 한다.코딩 테스트에서는 이러한 소수를 판별하는 방식을 묻는 소수 구하기 문제가 종종 출제된다.소수를 구하는 대

그래프는 노드와 엣지로 구성된 집합이다.노드는 데이터를 표현하는 단위이고, 에지는 노드를 연결한다.트리도 그래프의 일종이며, 그래프는 여러 알고리즘에 많이 사용되는 자료구조이므로 코딩 테스트에 자주 등장한다.그래프의 사이클이 생성되는지 판별하는 알고리즘알고리즘 조건 :

그래프를 구현하는 방법 3가지에지 리스트인접 행렬인접 리스트엣지를 중심으로 그래프를 표현엣지 리스트는 배열에 출발 노드, 도착 노드를 저장하여 엣지를 표현또는 출발 노드, 도착 노드, 가중치를 저장하여 가중치가 있는 엣지를 표현하기도 함엣지 리스트는 벨만 포드나 크루스

유니온 파인드는 일반적으로 여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 union 연산과 두 노드가 같은 집합에 속해 있는지를 확인하는 find 연산으로 구성되어 있는 알고리즘이다.find 연산은 자신의 대표노드를 찾아주는 연산유니온 파인드는

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘이다.위상 정렬에서는 항상 유일한 값으로 정렬되지 않는다.사이클이 존재하면 노드 간의 순서를 명확하게 정의할 수 없으므로 위상 정렬을 적용할 수 없다.진입 차수를 이해해 보자. 진입 차수는 자기 자신을

다익스트라 다익스트라 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다. 엣지는 항상 양수여야 한다는 제약 조건이 있다. 특정 노드에서 다른 노드들의 최단 거리를 구하는 문제가 주어졌을 때 다익스트라 알고리즘을 사용하면 문제를 해결할 수 있다. 다익스트라 알고

벨만-포드 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.음수 가중치 엣지가 있어도 수행할 수 있다는 특징이 있다.전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있다.벨만-포드 알고리즘은 다음 3가지 단계의 원리로 동작한다.벨만-포드 알고리즘은 엣지를 중

플로이드-워셜 알고리즘은 그래프에서 최단 거리를 구하는 알고리즘이다.모든 노드 간에 최단 거리를 탐색음수 가중치 엣지가 있어도 수행 가능 단, 음수 사이클이 있으면 안된다.동적 계획법의 원리를 이용해 알고리즘에 접근한다.대부분 플로이드-워셜 알고리즘을 사용하는 노드의

최소 신장 트리(minimum spanning tree)란 그래프에서 모든 노드를 연결할 때 사용된 엣지들의 가중치의 합을 최소로하는 트리이다.크루스칼, 프림 알고리즘 2개로 나뉜다.여기서는 크루스칼 알고리즘을 다룬다.사이클이 포함되면 가중치의 합이 최소가 될 수 없으

트리는 노드와 엣지로 연결된 그래프의 특수한 형태이다.그래프의 표현으로도 트리를 표현할 수 있다.순환 구조를 지니고 있지 않고, 1개의 루트 노드가 존재한다.루트 노드를 제외한 노드는 단 1개의 부모 노드를 갖는다.트리의 부분 트리 역시 트리의 모든 특징을 따른다.트리

이진 트리는 각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리를 말한다.트리 영역에서 가장 많이 사용되는 형태트리가 코딩테스트에서 나오는 유형 2가지그래프의 표현 → 인접 리스트로 트리를 구성한 후 → BFS,DFS로 문제풀기1차원 배열 표현 → 인덱스 트리

주어진 데이터의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해낸 자료구조의 형태세그먼트 트리의 종류는 구간 합, 최대/최소 구하기로 나눌 수 있고, 구현 단계는 트리 초기화하기, 질의값 구하기(구간 합 또는 최대/최소), 데이터 업데이트하기로 나눌 수 있다.

트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 최소 공통 조상(LCA : lowest common ancastor)이라고 한다.구하는 방식으로는 일반적인 방

조합은 그 자체로 코딩 테스트에 자주 출제되는 주제동적 계획법을 이해하는데 기초가 되므로 매우 중요하다.조합은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다.조합과 비교되는 순열은 nPr로 표현되고, n개의 숫자 중 r개를 뽑아 순서를 고려해

동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최종적으로 복잡한 문제의 답을 구하는 방법큰 문제를 작은 문제로 나눌 수 있어야 한다.작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.모든 작