컴공생의 개인공부일지

정의 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법 비트 연산자 A B ~A ~B A & B A | B A ^ B 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 1 1 0 0 1 1 0 NOT(~) : 비트 값을 반전하여 변환 AND(&) : 대응하는 두 비트가 모두 1일 때, 1 반환 OR(|) : 대응하는 두 비트 중 모두 1이거나 하나라도 1일 때, 1 반환 XOR(^) : 대응하는 두 비트가 서로 다를 때, 1 반환 SHIFT(>>, 0100 -> 1000 : 1 -> 2 -> 4 -> 8 오른쪽 시프트 : 1000 -> 0100 -> 0010 -> 0001 : 8 -> 4 -> 2 -> 1 비트 마스크의 집합의 활용 다..

정의 완전이진트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬 방식 동작 과정 1. 정렬할 N개의 원소로 최대 힙 구성 2. 최대 힙의 루트 노드와 마지막 원소 위치 교환 3. 새 루트 노드에 대해 최대 힙 구성 4. 원소 개수만큼 2와 3을 반복 수행 시간복잡도 최선일 경우 O(nlogn), 평균일 때 O(nlogn), 최악일 경우에도 O(nlogn)이다. 과정 1로 build heap 과정으로 O(nlogn)의 시간 복잡도를 가진다. 과정 2와 3은 최대 힙에서 원소를 하나 삭제한 다음 heapify를 진행하는 것과 같으므로 O(logn)이 걸리고 원소 개수만큼 반복되므로 O(nlogn)이 된다. 따라서 O(nlogn) + O(nlogn) = O(nlogn)의 시간복잡도를 가진다. 공간복잡도 추가적..

정의 정렬되어 있는(이분 탐색의 주요 조건) 배열에서 데이터를 찾으려 시도할 때, 순차탐색처럼 처음부터 끝까지 하나씩 모든 데이터를 체크하여 값을 찾는 것이 아니라 탐색 범위를 절반씩 줄여가며 찾아가는 탐색 방법이다. 시간 복잡도 전체 탐색 : O(N) 이분 탐색 : O(logN) 동작 과정 우선 정렬을 한다. left와 right로 mid 값을 설정한다. mid와 내가 구하고자 하는 값과 비교한다. 구할 값이 mid보다 :left = mid + 1 구할 값이 mid보다 낮으면 :right = mid - 1 left > right가 될 때까지 계속 반복하기 소스 코드 Java public static int solution(int[] arr, int M) { // arr 배열에서 M을 찾자 Arrays...

정의 하나의 배열을 두개로 균등한 배열로 분할하고 분할된 배열을 각각 정렬한 다음, 이를 다시 합하여 정렬을 완성하는 알고리즘이다. 분할 정복의 일종으로, 하나의 큰 문제를 두 개의 작은 문제로 분할하여 해결한 다음, 결과를 모아서 문제를 완전히 해결하는 전략이다. 동작과정 리스트의 길이가 1 이하이면 이미 정렬된 것으로 보고 그대로 데이터 리턴. 그렇지 않은 경우에는 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다. 시간복잡도 최선의 경우 O(nlogn), 평균의 경우 O(nlogn), ..

그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘 가중치가 음수를 가지면 안되고 인접한 정점으로 가는 간선중 가장 적은 비용을 가지는 간선을 택한다. 알고리즘 수행중 새로운 경로가 생기면 그 경로를 기록하고 이후에 생기는 또 다른 경로와 비교하면서 최단 경로를 탐색한다. 다익스트라 알고리즘 순서 1. 최단 거리 값은 무한대 값으로 초기화한다. for(int i = 1; i

정의 분할 정복 방법을 통해 주어진 배열을 정렬한다 💡분할 정복 방법이란? : 문제를 작은 2개의 문제로 분리하고 각각을 해결한 뒤 결과를 모아서 문제를 해결하는 방법 동작 과정 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다. 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 한다. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다. 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다. 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지므로, 이 알고리즘은..

정의 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하는 정렬 알고리즘 동작 과정 정렬은 2번째 위치(index)의 값을 temp에 저장한다. temp와 이전에 있는 원소들과 비교해 삽입해나간다. 1번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복한다. Python 코드 def insert_sort(x): for i in range(1, len(x)): j = i - 1 key = x[i] while x[j] > key and j >= 0: x[j+1] = x[j] j = j - 1 x[j+1] = key return x Java 코드 void insertionSort(int[] arr) { for(..

정의 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 동작 과정 주어진 배열 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다. 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체한다. Python 코드 def selectionSort(x): length = len(x) for i in range(length-1): indexMin = i for j in range(i+1, length): if x[indexMin] > x[j]: indexMin = j x[i], x[indexMin] = x[indexMin], x[i] return x Java 코드 void selectionSort(int[] list) { int indexMin, temp; for..

정의 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 동작 과정 1회전에 첫 번째 원소와 두 번째 원소, 두 번째 원소와 세 번째 원소.. n-1번째 원소와 n번째 원소를 비교하여 조건에 맞지 않으면 서로 교환한다. 1회전 수행시 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘어난다. Python 코드 def bubble_sort(arr): for i in range(len(arr) - 1, 0, -1): for j in range(i): if arr[j] > arr[j + 1..