munjji 님의 블로그

이분 탐색 (binary search)정렬된 배열 안에서 특정 원소를 찾을 때,인덱스 i부터 j의 중간값을 비교해서 중간값이 찾는 원소가 아니라면 인덱스의 i와 j를 재정의 하는 방법으로 탐색한다.인덱스 i와 j를 정할 때 마다 탐색 범위는 반으로 줄어든다. 이분 탐색 방법처음 범위는 0부터 마지막 인덱스까지다.이때 중간 인덱스를 mid라고 한다.mid와 찾는 원소를 비교한다.찾는 원소와 mid 인덱스의 값이 같다면 탐색을 종료한다.mid 인덱스의 값 mid 인덱스의 값 > 찾는 원소일 때는 right = mid - 1로 하여 2를 반복한다.만약 left > right이 된다면 해당 배열에 찾는 원소가 없는 것이다.이분 탐색 구현 (java)1. 반복문 public static boolean BSearc..

비트와 바이트컴퓨터는 10진법이 아닌 2진법을 사용해 정보를 저장하기 떄문에 0과 1만을 저장한다.전기 신호의 전압이 일정 기준보다 높으면 1, 그렇지 않으면 0으로 변환하여 사용한다.비트(bit)비트는 0과 1을 표현할 수 있는 최소 단위여러 개의 비트를 조합하여 데이터를 표현한다.ex) 000, 001, 010, ...바이트(byte)8비트를 한 묶음으로 표현한 단위즉 1바이트 당 256(2^8)가지의 데이터 표현이 가능하다.바이트를 더 큰 단위로 묶어 1KB, 1MB, 1GB, 1TB로 표현한다.컴퓨터의 숫자 표현 - 정수음수의 표현부호 비트컴퓨터는 n비트에서 가장 왼쪽의 비트(최상위 비트)를 부호 비트로 사용하여 음수를 표현한다.부호 비트가 1이면 음수, 0이면 양수 또는 0이다.예를 들어 4비트..

플로이드-워셜(Floyd–Warshall)모든 정점 쌍 사이의 최단 거리를 구하는 알고리즘== 모든 정점을 하나씩 중간 경유지로 허용해보며, 최단 경로를 갱신하는 알고리즘 언제 사용하는가?정점의 수가 크지 않을 때 (보통 모든 정점 쌍 최단 거리가 필요할 때음수 간선이 있을 때 (단, 음수 사이클은 안 됨)핵심 아이디어중간 정점을 하나씩 추가해가면서i -> k -> j로 가는 게 i -> j로 직접 가는 것보다 짧은가?를 확인한다. 핵심 반복 구조 수식 (3중 for문)// k -> 거쳐갈 수 있는 중간 정점 집합을 하나씩 늘려가는 것for (int k = 0; k dist[i][k] + dist[k][j]) { dist[i][j] = dist[i][k] + dist[k][j..

최소 신장 트리 (MST: Minimum Spanning Tree)그래프에서 모든 정점을 포함하고 사이클이 없으며, 총 간선 비용이 최소인 트리MST의 핵심 특징간선은 정확히 n - 1개사이클이 없음모든 노드 연결총 비용 최소 MST를 구하는 대표 알고리즘 2개알고리즘의 공동목표모든 정점을 최소 비용으로 사이클 없이 연결하자즉, 최소 신장 트리 만들기1️⃣ Kruskal 알고리즘"간선을 비용 기준으로 정렬해서 가장 싼 것부터 고르자"간선 비용(cost) 기준 오름차순 정렬작은 것부터 선택사이클 생기면 건너뜀Union - Find 사용시간복잡도는 O(E log E)과정모든 간선을 비용 기준 오름차순 정렬가장 작은 간선부터 하나씩 선택사이클이 생기면 버림간선이 V-1개가 되면 종료2️⃣ Prim 알고리즘"현..