Keep calm and carry on

병합 정렬(Merge Sort)은 배열을 재귀적으로 반으로 나누고, 각 부분을 정렬한 다음 다시 병합하여 전체 배열을 정렬하는 알고리즘이다.아래 내용은 배열을 나누고 병합하는 과정을 단계별로 설명한다. 주어진 배열[6, 4, 7, 3, 9, 1, 8] 배열을 반으로 나누기 (Divide)첫 번째 나누기 [6, 4, 7, 3, 9, 1, 8] / \[6, 4, 7, 3] [9, 1, 8]두 번째 나누기 [6, 4, 7, 3] [9, 1, 8] / \ / \ [6, 4] [7, 3] [9, 1] [8] / \ / \ / \[6] [4] [7] [3] [9] [1] [8]  배열을 병합..

그래프란,객체의 일부 쌍(Pair)들이 '연관되어' 있는 객체 집합 구조를 말한다.그래프 이론에서 ‘그래프’는 수학적 구조를 의미하며, 이는 객체 간의 관계를 나타내는 도구다. 그래프는 두 가지 주요 구성 요소로 이루어져 있다.정점 (Vertices): 그래프의 기본 단위. 각 정점은 그래프에서 고유한 객체나 노드를 나타낸다.간선 (Edges): 정점 간의 연결을 나타낸다. 간선은 두 정점을 연결하여 그들 간의 관계를 나타낸다.그래프는 여러 종류로 나뉘며, 각각의 종류는 특정한 특성과 용도를 가진다무방향 그래프 (Undirected Graph): 간선에 방향이 없는 그래프다. 예를 들어, 두 정점 A와 B를 연결하는 간선이 있다면, A에서 B로 또는 B에서 A로 이동할 수 있다.방향 그래프 (Direct..

해시 테이블(Hash Table) 또는 해시맵(Hash Map)은 키를 값에 매핑할 수 있는 구조이다.해시 테이블은 대부분의 연산이 분할 상환 분석에 따라 시간 복잡도가 O(1)이라는 점이다. 즉, 데이터의 양과 상관 없이 빠른 성능을 기대할 수 있다. 해싱은 정보를 가능한 한 빠르게 저장하고 검색하기 위해 사용하는 중요 기법 중 하나다.  해시 테이블의 핵심은 해시 함수다. 해시 함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다.해시 함수는 다음과 같은 특징이 있다. 고정된 출력 크기: 입력 데이터의 크기와 상관없이 항상 고정된 크기의 해시 값을 출력한다.신속한 계산: 해시 값 계산이 빠르게 이루어진다.결정론적: 동일한 입력에 대해 항상 동일한 해시 값을 반환한다.충..

quick sort: 정렬 속도가 아주 빠르다는 데서 착안해 붙여진 직관적인 이름이다.퀵정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하여 모든 그룹이 1개의 요소가 될때까지 반복한다.그룹을 나누는 기준을 피벗(pivot) 이라고 한다. 배열을 두 그룹으로 나누기 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의 요소를 배열 오른쪽으로 옮겨야 한다. 아래 배열을 통해 과정을 살펴보자.int[] arr = [5, 7, 1, 4, 6, 2, 3, 9, 8]// pl x pr가운데 인덱스를 피벗 x, 왼쪽 끝 요소를 pl, 오른쪽 끝 요소를 pr 이라 했을 때1. arr[pl] >= x 가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔한다. (pl+..

자료구조는 크게 메모리 공간 기반의 연속(Contiguous)방식과 포인터 기반의 연결(Link)방식으로 나뉜다.배열은 이 중 연속방식의 가장 기본이 되는 자료형이다. 연결 방식의 가장 기본이 되는 자료형은 연결 리스트이다.배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할방받는 작업을 수행하는 자료형이다. 배열의 예시를 그림으로 살펴보자.  C언어를 기준으로 int arr[4] = {4, 7, 29, 0}; 라는 예시를 들면, 위 그림과 같다. 32비트 이상의 시스템에서는 int를 4바이트로 사용한다. 배열은 어느 위치나 O(1)에 조회가 가능하다는 장점이 있다. 동적배열 배열이란 고정된 크기만큼의 연속된 메모리 할당한다. 그러나 실제 크기를 가늠하기 어려운 상황에 따라 동적으로 메모리를 ..

'재귀 알고리즘의 예시와 분석'의 내용을 살펴봤다. 다음으로 재귀 알고리즘의 비재귀적 표현 방식과 메모화를 확인해본다.재귀 알고리즘의 비재귀적 표현 recur 메서드를 비재귀적으로 구현하는 방법을 살펴본다. 우선 '꼬리' 재귀를 제거 하는 방법이 있다. recur(n - 2)는 인수로 n - 2를 전달하여 recur 메서드를 호출한다.이 호출을 바꾼다. n값을 n - 2로 업데이트하고 메서드의 시작 지점으로 돌아간다. // 수정 이전의 코드if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); // 꼬리를 제거, n - 2로 업데이트하고 메서드의 시작 지점으로 돌아가야 한다} // 수정 후의 코드, if 문을 while 문으로 수..

재귀 알고리즘 분석하기 재귀 호출을 여러 번 실행하는 순수(genuinely) 재귀의 예시.package org.study.bohyohshibata;public class Recur { static void recur(int n) { if (n > 0) { recur(n - 1); System.out.println(n); recur(n - 2); } } public static void main(String[] args) { recur(4); }} 출력 결과는 아래와 같다.1231412하향식 분석과 상향식 분석recur(4) 는 아래와 같은 순서대로 실행된다.recur(3)을 실행.4를 ..

빅오 (Big-O) 컴퓨터과학에서 빅오는 입력값이 커질 때 알고리즘의 실행 시간(시간 복잡도)과 함께 공간 요구 사항(공간 복잡도)이 어떻게 증가하는지를 분류하는 데 사용되며, 알고리즘의 효율성을 분석하는 데도 매우 유용하게 활용된다.빅오 표기법이란 입력 크기가 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법으로, 특히 점근적 실행 시간이란 입력값 n이 커질 때, 즉 입력값이 무한대를 향할 때 함수의 실행시간 추이를 의미한다. 알고리즘은 궁극적으로는 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다.빅오로 시간 복잡도를 표현할 때는 최고차 항만을 표기하며, 계..

자바 알고리즘 인터뷰 책을 보며 학습한 내용 // 예시List a = new ArrayList();// 삽입 시 add() 사용a.add(1);a.add(2);a.add(3);Set b = new HashSet();// 삽입, add() 로 동일b.add(1);b.add(2);b.add(3);Map c = new HashMap();// 삽입 시 put() 사용, 키/값 형태로 데이터 추가c.put("a", 1);c.put("b", 2); 초기 자료형의 성능 문제 자바는 1.0 정식 버전을 출시하던 초기 시절부터 목록형 자료형에 대한 고민이 있었다. 자바 컬렉션 프레임워크가 등장한 것은 그로부터 2년이나 더 지난 후였고, 그 전에는 C++의 영향을 받아 벡터 형태의 자료형과 해시 테이블 형태의 자료형을 별..

자료구조와 함께 배우는 알고리즘 입문 책을 보며 학습한 내용 이진 검색 이 알고리즘은 데이터가 키값으로 이미 정렬(sort)되어있다 전제 조건이 필요하다.이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다. 이진 검색 알아보기아래와 같이 오름차순으로 정렬된 데이터에서 39를 검색하는 예시다.int[] a = {5, 7, 15, 28, 29, 31, 39, 58, 68, 70, 95};먼저 배열의 중앙(10 / 2 == 5)에 위치한 요소인 a[5](값: 31)부터 검색을 시작.검색할 값인 39는 중앙 요소(a[5])보다 큼. 따라서 검색 대상을 뒤쪽의 5개(a[6] ~ a[10])로 좁힘. 그리고 다음 검색 범위의 중앙에 위치한 요소인 a[8](값: 68) 선택한다.검색할 값인 39는 중앙요소 a[..