윤깡패 블로그

순열과 조합 핵심 이론 순열(Permutation) : 서로 다른 n개의 숫자에서 r개를 선택하여 순서를 고려해 나열할 경우의 수 (순서 고려 O) 조합(Combination) : 서로 다른 n개의 숫자에서 서로 다른 r개를 선택하는 경우의 수 (순서 고려 X) 조합 점화식 D[i][j] = D[i - 1][j] + D[i - 1][j - 1] * , 을 참고하였습니다.

구간 합 알고리즘 연속적으로 나열된 수가 있을 때, 맨 앞부터 특정 위치까지의 합을 미리 구해 놓고 사용하는 알고리즘 시간 복잡도 - O(1) 구간 합 핵심 이론 합 배열 S를 만드는 공식 S[i] = A[0] + A[1] + A[2] + ... + A[i - 1] + A[i] = S[i - 1] + A[i] - A[0]부터 A[i]까지의 합 구간 합을 구하는 공식 S[j] - S[i - 1] - i에서 j까지 구간 합 * , 을 참고하였습니다.

다익스트라(Dijkstra) 알고리즘 그래프에서 출발 노드와 그 외 모든 노드 간의 최단 거리를 탐색하는 알고리즘 특징 - 에지가 모두 양수일 때 정상적으로 동작한다. - 시간 복잡도 : O(ElogV) (노드 수 : V, 에지 수 : E) 다익스트라 알고리즘 핵심 이론 1. 인접 리스트로 그래프를 구현한다. - 인접 리스트에 연결한 배열의 자료형 : (노드, 가중치) 2. 최단 거리 배열을 초기화한다. - 출발 노드는 0, 이외의 노드는 무한(∞)으로 초기화한다. * 무한(∞) : 문제에서 주어진 모든 에지의 합보다 충분히 더 큰 수 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택하여 출발 노드로 설정한다. - 값이 0인 출발 노드에서 시작한다. 4. 선택한 노드를 거쳐 다른 노드로..

위상 정렬(Topology Sort) 알고리즘 사이클이 없는 방향 그래프에서 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 알고리즘 특징 - 항상 유일한 값으로 정렬되지 않는다. - 사이클이 없어야 한다. - 시간 복잡도 : O(V + E) (노드 수 : V, 에지 수 : E) 위상 정렬 수행 과정 1. 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트한다. * 진입 차수(In-Degree) : 자기 자신으로 들어오는 에지의 개수 2. 진입 차수가 0인 노드를 큐에 저장한다. [ 예시 ] 진입 차수가 0인 노드 1을 선택하여 위상 정렬 배열에 저장 3. 큐에서 데이터를 꺼내 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소한다. [ 예시 ]..

플로이드-워셜(Floyd-Warshall) 알고리즘 그래프에서 모든 노드 간에 최단 거리를 구하는 알고리즘 특징 - 음수 가중치 에지가 있어도 수행할 수 있다. - 동적 계획법의 원리를 이용해 알고리즘에 접근한다. - 시간복잡도 : O(V³) (노드 수 : V) 플로이드-워셜 핵심 이론 전체 경로의 최단 경로는 부분 경로의 최단 경로의 조합으로 이뤄진다. 플로이드-워셜 점화식 D[S][E] = min(D[S][E], D[S][K] + D[K][E]) 플로이드-워셜 알고리즘 구현 방법 1. 배열을 선언하고 초기화한다. D[S][E] : 노드 S에서 노드 E까지의 최단 거리를 저장하는 배열 초기화 - S == E ⇒ D[S][E] = 0 (자기 자신에게 가는 데 걸리는 최단 경로값) - S != E ⇒ D..

이진 탐색(Binary Search) 알고리즘 탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 알고리즘 이진 탐색 핵심 이론 특징 - 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있다. - 시간 복잡도 : O(logN) 과정 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는다. 1. 현재 데이터셋의 중앙값을 선택한다. 2. 중앙값 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터셋을 선택한다. 4. 과정 1 ~ 3번을 반복하다가 중앙값 == 타깃 데이터일 때 탐색을 종료한다. 구현 int start = 0; int end = A.size() - 1; while(start ta..

에라토스테네스의 체 알고리즘 소수를 구하는 대표적인 판별법 * 소수(Prime Number) : 1과 자기 자신 외에 약수가 존재하지 않는 수 ⇒ 1은 소수가 아니다. 시간 복잡도 : O(Nlog(logN)) + 매우 빠르게 동작한다. - 메모리가 많이 필요하다. ⇒ 알고리즘을 수행할 때 N의 크기만큼 배열을 할당해야 하기 때문 에라토스테네스의 체 핵심 이론 1. 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다. [ 예시 ] 1부터 30까지의 모든 자연수를 나열한다. 2. 2부터 시작하고, 남은 수 중에서 지워진 상태가 아닌 가장 작은 수를 찾는다. 3. 남은 수 중에서 현재 선택된 숫자의 배수를 배열에서 끝까지 탐색하면서 제거한다. 이때 처음으로 선택된 숫자는 제거하지 않는다. [ 예시 ] 2를 ..

정렬(Sort) 알고리즘 데이터를 정해진 기준에 따라 순서대로 나열해 의미 있는 구조로 재설정하는 것 버블(Bubble) 정렬 알고리즘 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식 특징 시간 복잡도 : O(n²) + 간단하게 구현할 수 있다. - 다른 정렬 알고리즘보다 속도가 느린 편이다. 과정 비교 연산이 필요한 루프 범위를 설정한다. 인접한 데이터 값을 비교한다. swap 조건에 부합하면 swap 연산을 수행한다. 루프 범위가 끝날 때까지 2~3번을 반복한다. 정렬된 영역을 설정한다. 다음 루프를 실행할 때는 이 영역을 제외한다. 비교 대상이 없을 때까지 1~5번을 반복한다. * 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데..

투 포인터 알고리즘 2개의 포인터로 알고리즘의 시간 복잡도를 최적화한다. 투 포인터 알고리즘을 활용하여 2개의 그룹을 병합하는 과정 - 시간 복잡도 : O(N + M) (N, M : 정렬된 배열 A와 B의 데이터 개수) 정렬된 배열 A와 B를 입력받는다. 배열 A에서 처리되지 않은 원소 중 가장 작은 원소를 data 1 index가 가리키도록 한다. 배열 B에서 처리되지 않은 원소 중 가장 작은 원소를 data 2 index가 가리키도록 한다. A[data 1 index]와 B[data 2 index] 중에서 더 작은 원소를 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다. 배열 A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4번의 과정을 반복한다. * , 을 참고하였습니다.

그리디(Greedy) 알고리즘 현재 상황에서 가장 좋아 보이는 것만을 선택하는 알고리즘 + 구현하기 쉽다. + 시간 복잡도가 우수하다. - 항상 최적의 해를 보장하지 못한다. 그리디 알고리즘 수행 과정 1. 해 선택 : 현재 상태에서 가장 최선이라고 생각되는 해를 선택한다. 2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다. 3. 해 검사 : 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전제 문제를 해결하지 못한다면 1번으로 돌아가 같은 과정을 반복한다. * , 을 참고하였습니다.