배열의 반전은 다음을 나타냅니다. 배열을 정렬된 형식으로 변환하는 데 필요한 변경 수. 배열이 이미 정렬되어 있으면 반전이 0개 필요하고 다른 경우 배열이 반전되면 반전 수가 최대가 됩니다. 이 문제를 해결하기 위해 병합 정렬 방식을 따라 시간 복잡도를 줄이고 분할 정복 알고리즘으로 만들 것입니다. 입력 및 출력 Input: A sequence of numbers. (1, 5, 6, 4, 20). Output: The number of inversions required to arrange the numbers into ascen

중앙값은 중간 숫자입니다. 즉, 중앙값은 정렬된 목록의 중간 관측값입니다. 50%의 누적 백분율에 해당합니다. 두 배열의 크기는 같아야 합니다. 처음에는 두 개의 개별 배열의 중앙값을 찾은 다음 개별 중앙값을 비교하여 두 목록의 실제 중앙값을 구합니다. 입력 및 출력 Input: Two sorted array are given. Array 1: {1, 2, 3, 6, 7} Array 2: {4, 6, 8, 10, 11} Output: The median from two array. Here the median value is 6.

무방향 그래프는 두 정점 사이에 두 개의 정점 분리 경로가 있는 경우 이중 연결 그래프라고 합니다. 즉, 두 정점 사이에 순환이 있다고 말할 수 있습니다. 그래프 G가 연결되어 있고 그래프에 관절점이 없거나 절단 정점이 있는 경우 그래프 G는 양방향 그래프라고 말할 수 있습니다. 이 문제를 해결하기 위해 우리는 DFS 순회를 사용할 것입니다. DFS를 사용하여 관절 지점이 있는지 여부를 찾으려고 합니다. 또한 DFS가 모든 정점을 방문하는지 여부를 확인합니다. 그렇지 않으면 그래프가 연결되지 않았다고 말할 수 있습니다. 입력

BFS(Breadth First Search) 탐색은 주어진 그래프의 모든 노드를 방문하는 데 사용되는 알고리즘입니다. 이 탐색 알고리즘에서는 하나의 노드를 선택한 다음 모든 인접 노드를 하나씩 방문합니다. 인접 정점을 모두 완료한 후, 다른 정점을 확인하기 위해 더 이동하고, 인접 정점을 다시 확인합니다. 이 알고리즘을 구현하려면 Queue 데이터 구조를 사용해야 합니다. 모든 인접 정점이 완료되면 모든 인접 정점이 대기열에 추가되고, 대기열에서 한 항목이 제거되고 해당 정점을 다시 통과하기 시작합니다. 그래프에서는 때때로

무방향 그래프의 간선을 제거하거나 그래프 연결을 끊거나 그래프의 다른 구성 요소를 만드는 경우에만 연결이라고 합니다. 실용적인 접근 방식에서는 브리지 연결이 끊어질 때 네트워크에 일부 브리지가 존재하면 전체 네트워크가 끊어질 수 있습니다. 입력 및 출력 알고리즘 bridgeFind(시작, 방문, 디스크, 낮음, 상위) 입력 - 시작 정점, 노드 방문 시 표시할 방문 배열, 디스크는 정점의 발견 시간을 보유하고, low는 하위 트리에 대한 정보를 보유합니다. 부모는 현재 정점의 부모를 유지합니다. 출력 - 다리가 발견되

이 문제에서는 하나의 무방향 그래프가 제공되며 그래프가 트리인지 확인해야 합니다. 트리의 기준을 확인하면 간단히 찾을 수 있습니다. 트리에는 주기가 포함되지 않으므로 그래프에 주기가 있으면 트리가 아닙니다. 다른 접근 방식을 사용하여 확인할 수 있습니다. 그래프가 연결되어 있고 V-1 모서리가 있으면 트리일 수 있습니다. 여기서 V는 그래프의 정점 수입니다. 입력 및 출력 Input: The adjacency matrix. 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 Output:

그래프의 연결성을 확인하기 위해 순회 알고리즘을 사용하여 모든 노드를 순회하려고 합니다. 순회 완료 후 방문하지 않은 노드가 있으면 그래프가 연결되지 않습니다. 방향 그래프의 경우 연결을 확인하기 위해 모든 노드에서 순회를 시작합니다. 때때로 한 가장자리는 바깥쪽 가장자리만 가질 수 있지만 안쪽 가장자리는 없을 수 있으므로 해당 노드는 다른 시작 노드에서 방문하지 않습니다. 이 경우 순회 알고리즘은 재귀 DFS 순회입니다. 입력 및 출력 Input: Adjacency matrix of a graph    0

DFS(깊이 우선 탐색)는 그래프 탐색 알고리즘입니다. 이 알고리즘은 하나의 시작 정점이 주어지고 인접 정점이 발견되면 그 인접 정점으로 먼저 이동하고 같은 방식으로 순회를 시도한다. 가능한 한 전체 깊이를 이동한 다음 역추적하여 새 경로를 찾기 위해 이전 정점에 도달합니다. 반복적인 방식으로 DFS를 구현하려면 스택 데이터 구조를 사용해야 합니다. 재귀적으로 수행하려면 외부 스택이 필요하지 않으며 재귀 호출에 대해 내부 스택을 수행할 수 있습니다. 입력 및 출력 Input: The Adjacency matrix of a g

이 문제에서는 무방향 그래프가 제공됩니다. m 색상도 제공됩니다. 문제는 그래프의 인접한 두 정점이 동일한 색상을 가지지 않도록 m개의 다른 색상을 가진 노드를 할당하는 것이 가능한지 찾는 것입니다. 솔루션이 존재하는 경우 어떤 정점에 어떤 색상이 할당되었는지 표시합니다. 정점 0부터 시작하여 다른 노드에 하나씩 색상을 할당하려고 합니다. 하지만 할당하기 전에 색상이 안전한지 확인해야 합니다. 인접한 정점에 같은 색상이 포함되어 있으면 색상은 안전하지 않습니다. 입력 및 출력 Input: The adjacency matrix of

이 문제는 체스 판에서 N개의 여왕이 배열되어 있어 어떤 여왕도 판의 다른 여왕을 공격할 수 없도록 하는 문제입니다. 체스 퀸은 가로, 세로, 가로, 대각선 어느 방향으로든 공격할 수 있습니다. 이진 행렬은 다른 퀸을 공격할 수 있는 퀸이 없는 N 퀸의 위치를 ​​표시하는 데 사용됩니다. 입력 및 출력 Input: The size of a chess board. Generally, it is 8. as (8 x 8 is the size of a normal chess board.) Output: The matrix that re

이 문제에는 N x N 크기의 주어진 미로가 있습니다. 소스와 대상 위치는 각각 왼쪽 상단 셀과 오른쪽 하단 셀입니다. 일부 셀은 이동이 가능하고 일부 셀은 차단됩니다. 한 쥐가 시작 정점에서 대상 정점으로 이동하기 시작하면 경로를 완료할 수 있는 방법이 있는지 찾아야 합니다. 가능하면 쥐의 올바른 경로를 표시합니다. 미로는 이진 행렬을 사용하여 제공되며 1로 표시되고 유효한 경로이며 그렇지 않으면 차단된 셀에 대해 0으로 표시됩니다. 참고: 쥐는 오른쪽 또는 아래쪽의 두 방향으로만 이동할 수 있습니다. 입력 및 출력 입력:이

암호 산술 문제에서 일부 문자는 숫자를 할당하는 데 사용됩니다. 10개의 다른 문자가 산술 연산을 올바르게 수행하기 위해 0에서 9까지의 숫자 값을 보유하는 것과 같습니다. 두 단어가 주어지고 다른 단어는 그 두 단어에 대한 덧셈의 답이 주어집니다. 예를 들어 BASE와 BALL이라는 두 단어가 있고 결과는 GAMES라고 말할 수 있습니다. 이제 기호 숫자로 BASE와 BALL을 추가하려고 하면 GAMES라는 답이 나옵니다. 참고 &minuns; 최대 10자여야 하며, 그렇지 않으면 풀 수 없습니다. 입력 및 출력 입력:이 알

이 문제에는 일부 정수 요소가 포함된 집합이 있습니다. 그리고 또 다른 어떤 값도 제공되는데, 주어진 합 값과 합이 같은 주어진 집합의 부분집합을 찾아야 합니다. 여기서 역추적 접근 방식은 항목이 유효하지 않을 때 유효한 하위 집합을 선택하는 데 사용됩니다. 이전 하위 집합을 가져오기 위해 역추적하고 솔루션을 얻기 위해 다른 요소를 추가합니다. 입력 및 출력 Input: This algorithm takes a set of numbers, and a sum value. The Set: {10, 7, 5, 18, 12, 20, 15

이 섹션에서는 스도쿠라는 유명한 숫자 미로 문제를 해결하려고 합니다. 스도쿠는 9 x 9 숫자 그리드이며 전체 그리드도 3 x 3 상자로 나뉩니다. 스도쿠를 푸는 몇 가지 규칙이 있습니다. 이 문제를 해결하려면 1에서 9까지의 숫자를 사용해야 합니다. 하나의 행, 하나의 열 또는 하나의 3 x 3 상자에서 하나의 숫자를 반복할 수 없습니다. 역추적 알고리즘을 사용하여 스도쿠 문제를 해결하려고 합니다. 일부 셀이 숫자로 채워지면 유효한지 여부를 확인합니다. 유효하지 않은 경우 다른 번호를 확인합니다. 1-9 사이의 모든 숫자를

체스에서 우리는 기사가 특별한 방식으로 점프할 수 있다는 것을 알고 있습니다. 가로 2칸, 세로 1칸 또는 세로 2칸, 가로 1칸을 각 방향으로 움직일 수 있어 완전한 움직임은 영문 L과 같습니다. 이 문제에서는 빈 체스 판과 판의 어느 위치에서 시작하는 기사가 있습니다. 우리의 임무는 기사가 판의 모든 사각형을 방문할 수 있는지 여부를 확인하는 것입니다. 모든 사각형을 방문할 수 있을 때 시작 지점에서 해당 위치에 도달하는 데 필요한 점프 수를 배치합니다. 이 문제에는 여러 가지 해결책이 있을 수 있지만 가능한 한 가지 해결

이 문제에서는 정수 집합이 제공되므로 두 부분 집합의 합이 가능한 한 최소가 되도록 정수 집합을 두 부분으로 나누어야 합니다. 따라서 우리의 목표는 거의 같은 힘을 가진 두 그룹을 나누어 줄다리기 게임에 참여하는 것입니다. 부분집합 n의 크기가 짝수이면 n/2로 나누어야 하지만, n이 홀수인 경우 한 부분집합의 크기는 (n-1)/2, 다른 부분집합의 크기는 ( n+1)/2. 입력 및 출력 Input: A set of different weights. {23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4}

이 문제의 입력에서 한 문장은 공백 없이 제공되며 다른 사전에는 유효한 영어 단어도 제공됩니다. 개별 사전 단어에서 문장을 깰 수 있는 가능한 방법을 찾아야 합니다. 유효한 단어가 발견되면 유효한 단어를 찾기 위해 문자열 왼쪽부터 검색을 시도하고 해당 문자열의 다음 부분에서 단어를 검색합니다. 입력 및 출력 Input: A set of valid words as dictionary, and a string where different words are placed without spaces. Dictionary: {mobile,

이 문제에서 하나의 양의 정수 문자열이 주어졌을 때, 우리는 숫자를 k번 교환하여 다른 위치로 값이 최대인 순열을 찾아야 합니다. 우리는 숫자를 선택하고 최대 숫자를 찾기 위해 한 번에 하나씩 뒤따르는 숫자로 바꿔 이 문제를 해결할 것입니다. 이 과정을 k번 반복합니다. 역추적 전략이 여기에서 작동하는 이유는 이전 값보다 크지 않은 숫자를 찾으면 이전 값으로 역추적하고 다시 확인하기 때문입니다. 입력 및 출력 Input: A number of multiple digits. The input is: 129814999 Output:

Finite Automata를 구성하여 텍스트에서 패턴 검색을 간단히 수행할 수 있습니다. 먼저 유한 오토마타의 천이 테이블을 만들기 위해 2D 배열을 채워야 합니다. 테이블이 생성되면 검색 절차가 간단합니다. 오토마톤의 첫 번째 상태에서 시작하여 최종 상태에 도달하면 문자열에서 패턴을 찾았음을 의미합니다. 유한 오토마타 구성의 경우 시간 복잡도는 O(M*K), M은 패턴 길이, K는 다양한 문자입니다. 메인 패턴 검색의 복잡성은 O(n)입니다. 입력 및 출력 Input: Main String: “ABAAABCDBBAB

Kasai의 알고리즘은 접미사 배열에서 LCP(Longest Common Prefix) 배열을 가져오는 데 사용됩니다. 처음에는 접미사 배열이 발견됩니다. 그 후 Kasai의 알고리즘은 접미사 배열 목록을 사용하여 LCP를 찾습니다. LCP 배열의 경우 O(m log n)이 필요합니다. 여기서 m은 패턴 길이이고 n은 텍스트 길이입니다. Kasai의 알고리즘, 메인 문자열에서 패턴을 찾는 데 O(n)이 걸립니다. 입력 및 출력 Input: Main String: “banana” Output: Suffix Ar