알고리즘

참고 링크코딩테스트에서 자주 출제되는 유형브루트 포스DFSBFS시뮬레이션/구현 // 가장 많이 출제됨DP그리디이분탐색투포인터이 외에도우선순위 큐해시 맵trie 알고리즘유니온 파인드크루스칼 알고리즘트리의 지름 구하기브루트 포스(완전 탐색)모든 경우를 다 탐색하는 경우.

빅-오메가 : 최선일때빅-세타 : 보통일때 (2/N)빅-오 : 최악일때 (N) => 최악일 경우를 염두에 둬야 한다시간 복잡도 따질 때는 데이터의 개수를 확인연산횟수 = 알고리즘 시간 복잡도 X 데이터의 크기어떤 정렬을 사용할 것인지 생각해야함상수는 시간 복잡도 계산에

배열은 메모리의 연속 공간에 값이 체워져 있는 형태의 자료구조인덱스를 통해 참조할 수 있다인덱스를 사용하여 값에 바로 접근할 수 있따새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다값을 산입하거나 삭제하려면 해당 인덱스 주변에 있는 값을 이동시키는 과정이

합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘코딩테스트에서 사용 빈도가 높다구간 합의 핵심 이론구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다합 배열 S 정의Si = A0 + A1 + A2 + ... + Ai-1 + Ai /

스택은 삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out) = FILO삽입과 삭제가 한 쪽에서만 일어나는 특징스택에서 값을 빼낼 때 pop은 top이 가리키는 값을 스택에서 빼게 되어 있다위치top : 삽입과 삭제가 일어나는 위치연산push :

버블정렬 : 데이터의 인접 요소 끼리 비교하고, swap 연산을 수행하여 정렬하는 방식선택정렬 : 대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식삽입정렬 : 대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는

대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법.구현 방법이 복잡하고 시간 복잡도도 O(n²)으로 효율적이지 않아 코딩 테스트에선 많이 사용하지 않는다..최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap

그래프 완전 탐색 기법 중 하나깊이 우선 탐색은 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른 쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘그래프 완전 탐색재귀 함수로 구현 => DFS스택 자료 구조로 이용시간 복잡

너비 우선 탐색도 그래프를 완전 탐색하는 방법 중 하나로, 시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘그래프 완전 탐색FIFO 탐색Queue 자료구조 이용시간 복잡도 ( 노드 수 : V, 에지 수 : E ) : O(V+E)

데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다타깃 데이터 검색중앙값 비교를 통한 대상 축소 방식시간 복잡도 : O(logN)이진 탐색은 정렬 데이터에서 원하는 데

현재 상테에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘 => 최적의 해 보장 X해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다

소수는 1과 자기 자신 외에 약수가 존재하지 않는 수를 말한다에라토스테네스의 체 원래1\. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다2\. 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지

그래프는 노드와 에지로 구성된 집합이다.노드는 데이터를 표현하는 단위이고 에지는 노드를 연결하는 선이다트리도 그래프의 일종이다유니온 파인드 : 그래프의 사이클이 생성되는지 판별하는 알고리즘. 사이클 유무 판단위상 정렬 : 조건 : 사이클이 없어야한다. 방향이 있는 그래

여러 노드가 있을 때 특정 2개의 노드를 연결해 1개의 집합으로 묶는 유니온 연산과두 노드가 같은 집합에 속해 있는지를 확인하는 파인드 연산으로 구성되어 있는 알고리즘자신의 대표 노드를 찾아줌각 노드가 모두 대표 노드이므로 배열은 자신의 인덱스값으로 초기화한다find

위상 정렬은 사이클이 없는 방향 그래프에서 노드 순서를 찾는 알고리즘 이다노드 간의 순서를 결정사이클이 없어야 함시간 복잡도 : O(V+E)항상 유일한 값으로 정렬되지 않는다.진입 차수 : 자기 자신을 가리키는 에지의 개수진입차수 배열을 이용한 정렬

다익스트라 알고리즘

그래프 DP => 조합과 연관이 있다 인덱스 트리 >> 코테에 자주나옴 점화식 : n개에 대한 답을 도출하고 싶을 때 재귀적으로 답을 도출 ex) 피보나치 수열 조합 : n개의 숫자에서 r개를 뽑는 경우의 수 순열 : n개의 숫자 중 r개를 뽑아 순서를 고려해 나열

모든 알고리즘 문제들은 완전 탐색을 이용해 정답을 도출할 수 있다단지 비효율적인 연산과 시간을 없애고 답을 효율적으로 도출하기 위해 여러 알고리즘 기법을 사용하는것동적 계획법은 여러 유형의 문제들을 논리적인 사고를 이용해 효율적으로 풀 수 있는 사고방식동적 계획법의 원

시간 복잡도 O(big-O) : big-O는 시간의 상한을 나타낸다. 배열의 모든 값을 출력하는 알고리즘은 O(N)으로 표현할 수 있을 뿐만 아니라 O(N³), 이 외에 N보다 큰 big-O 시간으로 표현할 수도 있다. 상한 수행 시간 Ω(big-Omega) : Ω는

자료구조/알고리즘/개념연결 리스트 / 너비 우선 탐색 / 비트 조작트리, 트라이, 그래프 / 깊이 우선 탐색 / 메모리(스택vs힙)스택 & 큐 / 이진 탐색 / 재귀힙 / 병합 정렬 / 동적 프로그래밍Vector/ArrayList / 퀵 정렬 / big-O 시간&공간⭐

모든 경우의 수를 시도해 보는 방법상대적으로 구현이 간단하고, 해가 존재한다면 항상 찾게 된다경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우에 유용하다순열선택 순서가 결과에 영향을 미치는 경우조합선택 순서가 결과에 영향을 주지 않는 경우

삽입정렬이란 2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식을 사용하는 정렬 방식이다.어떤 대상을 '오름차순'으로 정렬할 때 삽입정렬은 2번째 원소부터 앞의 원소와 비교하는 과정을 통해 적절한 위치에 삽입하고 n번째 원소까지 이

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 부분리스트로 나누어 하나는 피벗보다 작은 값들의 부분리스트, 다른 하나는 피벗보다 큰 값들의 부분리스트로 정렬한 다음, 각 부분리스트에 대해 다시 위 처럼 재귀적으로 수행하여 정렬하는 방법퀵 정렬은 기본적으로 '분할