Machineboy空

バブルソートの定義データ列の隣り合う（となりあう）要素を比較し交換することを繰り返すことによりデータ列をソートバブルとは「泡（あわ）」の意味で、ソートの過程でデータが移動する様子が、水中で泡が浮かんでいくように見えることからこの名前がついています。左の要素と比較し、左の方が大きければ交換するバブルソートのPseudo Codebubble_sort(A : 配列, n : Aの要素数) for i = 0 to n-2 for j = n-1 down to i+1 if a[j-1] > a[j] then swap(a[j-1], a[j]) バブルソートの時間複雑度 O(n^2) using System;using System.Linq;class Program{ static void Mai..

選択ソートの定義「未整列な配列」の最小値を取り出し、「整列済み配列」の末尾に付け加える 選択ソートのPseudo Codeselection_sort(A : 配列, n : Aの要素数) for i = 0 to n-2 // A[i] ~ A[n-1] の最小値を見つけ、A[i]と交換する // つまり、整列済みとなっている A[0] ~ A[i-1] の末尾に、A[i] ~ A[n-1] の最小値を付け加える // A[i] ~ A[n-1] の最小値の位置を保存する変数 min_index を用意 // 暫定的に A[i] を最小値とする min_index 選択ソートの時間複雑度O(n^2) using System;using System.Linq;class Program{ ..

ソートの定義順序付け可能なデータの列を、昇順または降順に並び替える操作順序付け（じゅんじょつけ）순서 붙이기昇順（しょうじゅん）오름 차순降順（こうじゅん）내림 차순ソートの事例得点表を元にしてランキングを作成するデータの集まりから、上位k個を取ってくる貪欲アルゴリズムの前処理挿入ソートの定義「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入する手持ちのトランプを並び替える際挿入ソートのPseudo Codeinsertion_sort(A : 配列, n : Aの要素数) for i = 1 to n-1 // A[i] を、整列済みの A[0] ~ A[i-1] の適切な位置に挿入する // 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく ..

https://school.programmers.co.kr/learn/courses/30/lessons/49191?language=csharp

원리배열 A가 정렬되어 있다고 할 때, A の真ん中の要素が k 未満であれば、A の前半分の要素もすべて k 未満であることがわかります。つまり、A の前半分について探索する必要が無くなります。A의 중앙값보다 비교할 요소가 작다면, 나머지 오른쪽 절반의 요소들 보다 작다.逆に、A の真ん中の要素が k より大きければ、A の後ろ半分の要素もすべて k より大きいので、A の後ろ半分について探索する必要が無くなります。A의 중앙값보다 비교할 요소가 크다면, 나머지 왼쪽 절반의 요소들 보다 크다.つまり、「対象とする探索範囲の中央の値」と「探索したい値」を比較することで、探索範囲を半分にすることができます。즉, 탐색 범위의 중앙 값과 탐색하고 싶은 값을 비교하며 탐색 범위를 절반으로 줄일 수 있다!Tipソート済みであること정렬되어 있어야 한다.二分探索..

분할정복(Divide and Conquer)Divide : 큰 문제를 작은 문제로 분할한다.기저사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야한다.Conquer: 작은 문제의 답을 모아 큰 문제의 답을 구한다.일반적으로 재귀로 구현한다.  백트래킹(backtracking)답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘가지치기(pruning)를 통해 연산량의 유의미하게 줄여줌가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야함.정확한 시간 복잡도를 구하기 어려움 분할 정복백트래킹주로 재귀적인 방식으로 해결하위 문제를 해결하고 결과를 결합하여 문제를 해결문제 해결을 위해 모든 가능한 선택을 시도한 후,..

1. 회문(Palindrome)ex) "소주만병만주소", "수박이박수", "Madam, I'm Adam", "1234321" 회문을 판단하는 방법? 2. 올바른 괄호 문자열(VPS = Valid Parenthesis String)ex) (()), (())()보통은 스택(Stack)을 사용해서 해결')'가 입력될 때마다, 스택에 있는 '('를 하나씩 지운다. 이때 스택(top)이 비어있거나 '('이 없으면 올바른 괄호 문자열이 아님모든 문자열을 순회한 뒤, 스택이 비어있으면 올바른 괄호 문자열이고 비어있지 않으면 올바르지 않은 괄호 문자열임