java

보이어-무어(Boyer-Moore) 알고리즘

1. 개념 📸 보이어-무어(Boyer-Moore) 알고리즘은 skip이라는 것을 활용한 문자열 매칭 알고리즘이다. 여기서 skip이란 문자열을 비교할 때 불필요한 비교가 있다면 건너뛸 수 있도록 도와주는 것이다. (정확한 명칭은 아니지만 아래의 동작방식을 본다면 왜 skip이라고 불리는지 알 수 있을 것이다.) 보이어-무어 알고리즘은 문자열을 비교할 때 일반적으로 앞부분보다는 뒷부분에서 불일치가 일어날 확률이 높다는 성질을 활용한다. 그래서 비교할 문자열과 패턴을 앞부분부터 확인하는 것이 아닌 뒷부분부터 확인하게 된다. 2. 동작방식 🎬 기본적인 동작방식은 일치하지 않은 문자를 만난 경우 패턴에서 일치하는 문자를 찾아서 이동한 후 비교를 다시 시작한다는 것이다. 본문은 'abphone' 패턴은 'phon..

라빈-카프(Rabin-Karp) 알고리즘

1. 개념 ⚽ 라빈-카프(Rabin-Karp) 알고리즘이란 해싱(Hashing)을 이용한 문자열 매칭 알고리즘이다. 비교하고자 하는 문자들과 패턴의 문자들을 일일이 비교하는 대신에 문자열의 해시값을 비교하는 방식으로 진행된다. 2. 동작방식(연습용) 🏀 동작 방식은 아래와 같다. 해시 함수를 설정한다. 해시 함수를 이용하여 패턴의 해시값을 구한다. 비교하고자 하는 문자열의 해시값을 구한다. 일치하면 패턴과 찾은 문자열을 1:1 비교한다. 일치하지 않으면 비교하고자 하는 문자열을 한 칸 뒤로 옮겨서 3번부터 다시 시작한다. 해시값이 같더라도 1:1 매칭을 통해서 최종적으로 패턴과 비교하고자 하는 문자열이 일치하는지 확인하는 절차가 필요하다. 그 이유는 해시값이 같다고 해서 무조건 같은 문자열이라고 보장할 ..

플로이드-와샬(Floyd-Warshall) 알고리즘

1. 개념 🐕‍🦺  플로이드-와샬(Floyd-Warshall) 알고리즘이란 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이다. 다익스트라(Dijkstra) 알고리즘과 다르게 음의 가중치를 허용한다는 게 특징이라고 할 수 있다.  다익스트라 알고리즘을 간단하게 설명하자면 출발 정점으로부터 모든 정점까지의 최단경로를 구하는 알고리즘이다. 다익스트라를 이용하여 플로이드-와샬 알고리즘을 구현한다고 하면 출발 정점을 모든 정점의 개수만큼 설정해 주면 된다.  순차 탐색 방법으로 다익스트라를 구현하면 O(V^2)이고, 모든 정점을 출발 정점으로 한다고 하면 O(V * V^2) = O(V^3)이 되게 된다. 플로이드-와샬 알고리즘의 시간복잡도 또한 O(V^3)으로 같다. 하지만 플로이드-와샬 알..

최장공통부분수열(Longest Common Subsequence - LCS)

1. 개념 🐢 최장공통부분수열(Longest Common Subsequence)이란 주어진 수열의 부분 수열에서 가장 긴 것을 의미한다. 위의 그림에서 알 수 있는 것처럼 부분 수열이 연속적일 필요는 없다. 2. 동작방식 🦎 동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자. 문자열 A와 문자열 B를 한 글자씩 비교한다. 비교하는 문자가 같다면 DP[i][j] = DP[i - 1][j - 1] + 1이 된다. 비교하는 문자가 다르다면 DP[i][j]는 DP[i-1][j]와 DP[i][j-1] 중에 큰 값으로 설정한다. 1번과 2번 과정을 반복한다. 여기서 말하는 DP[i][j]는 문자열 A는 i번째까지 문자열 B는 j번째까지 고려하였을 경우에 얻을 수 있는 최장공통부분수열의 길이이다..

최장공통문자열(Longest Common Substring - LCS)

들어가기에 앞서 LCS를 구별하도록 하자. 일반적으로 LCS라고 하면 최장공통부분수열(Longest Common Subsequence)을 뜻하지만, 최장공통 문자열(Longest Common Sustring)도 LCS라고 부르기도 한다. 둘의 차이점은 구하고자 하는 부분 문자열의 연속성이라고 할 수 있다. 이번 글에서는 최장공통 문자열(Longest Common Substring)에 대해서 먼저 알아보자 1. 개념 🦆 최장공통부분문자열(LCS)은 연속된 부분 문자열 중 가장 길이가 긴 문자열을 말한다. 2. 동작 방식 🐓 동작 방식은 DP를 이용한다. 문자열 A와 문자열 B가 주어졌다고 하자. 문자열 A와 문자열 B를 한 글자씩 비교한다. 비교하는 문자가 같다면 DP[i][j]는 DP[i-1][j-1] ..

JVM 메모리 구조

1. JVM 개념 👨‍🔧 JVM(Java Virtual Machine)이란 '자바를 실행하기 위한 가상의 컴퓨터'라고 할 수 있다. 여기서 말하는 가상의 컴퓨터란 실제 컴퓨터(하드웨어)가 아닌 소프트웨어로 구현된 컴퓨터 속의 컴퓨터이다. 자바로 작성된 애플리케이션은 모두 JVM에서만 실행되기 때문에 자바 애플리케이션을 실행하기 위해서는 JVM이 반드시 필요하다. JVM은 OS에 종속적이기 때문에 해당 OS에서 실행 가능한 JVM이 필요하다. 이러한 특성으로 인해 자바의 장점 중 하나로 'Write Once, Run AnyWhere.(한 번 작성하면 어디서든 실행된다.)'라는 것이 있다. 2. 3가지 주요 영역 👩‍🔬 JVM은 메모리를 용도에 따라 여러 영역으로 나누어 관리한다. 그 중 3가지 주요 영역인..

퀵 정렬 (Quick Sort)

1. 정의 👨‍🚀 퀵 정렬(Quick Sort)은 분할 정복 방법을 이용하는 정렬 알고리즘이다. 퀵 정렬은 피벗(Pivot)을 기준으로 분할과 정복이 이루어지게 된다. 퀵 정렬은 '피벗을 선택하는 방식'과 '재귀 또는 비재귀 방식'의 선택에 따라 다양한 구현 방법이 존재한다. 이번 글에서는 '왼쪽 피벗을 선택하는 방식'과 '재귀 방식'을 통한 퀵 정렬을 알아보도록 하자. 2. 동작 방식 🦸‍♂️ 기본적인 동작 방식은 아래와 같다. 배열에서 임의의 원소인 pivot을 선택한다. (해당 글에서는 배열에서 제일 왼쪽 원소를 pivot으로 선택한다.) pivot을 기준으로 pivot보다 작은 원소는 왼쪽으로, pivot보다 큰 원소는 오른쪽에 오도록 배열을 배치한다. pivot을 기준으로 나누어진 왼쪽 배열과 ..

힙 정렬 (Heap Sort)

1. 정의 🏄‍♂️ 힙정렬이란 자료구조 힙(Heap)을 기반으로 하는 정렬 방식이다. 오름차순 정렬일 경우 최대힙을 이용하고 내림차순 정렬일 경우 최소힙을 이용한다. 간단하게 설명하자면 힙 정렬은 루트노드를 제거하고 제거된 루트 노드를 배열의 뒷부분부터 채워 넣으면서 정렬이 이루어지는 것이다. 2. 동작 방식 🚣‍♂️ 최대힙을 이용하여 오름차순으로 정렬하는 경우를 생각해 보자. 가장 쉽게 생각할 수 있는 동작방식은 아래와 같다. 정렬해야 하는 원소들을 하나씩 힙에 넣어준다. 삭제를 하면서 루트 노드를 가져오고 그것을 배열의 뒷부분부터 채운다. 이렇게 한다면 기존 배열로부터 힙을 구성하는 배열 하나를 추가적으로 만들고(1번 과정), 뒷부분부터 정렬된 원소들을 넣을 배열을 하나 더 만들어야 한다.(2번 과정..

[자료구조] 힙(Heap)

1. 정의 🐳 힙(Heap)이란 여러 값들 중 최댓값 혹은 최솟값을 빠르게 찾아내기 위한 자료구조이다. 힙의 특징 완전 이진트리의 일종이다. 반정렬 상태이다. 최대힙(Max Heap) 또는 최소힙(Min Heap)에 따라서 루트 노드가 항상 가장 큰 값이거나 가장 작은 값을 유지하기 때문이다. 중복된 값을 허용한다. 힙의 종류 최대 힙 (Max Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진트리 형식 최소 힙 (Min Heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진트리 형식 2. 동작 방식 🐟 인덱스 0 1 2 3 4 5 6 7 8 값 - 9 7 6 4 5 1 3 8 Heap은 배열을 통해 쉽게 구현이 가능하다. 그 이유는 힙이 완전 이진트리이..

공변 반환타입 (Convariant Return Type)

1. 정의 🌻 공변 반환타입이란 재정의한 메서드의 반환 타입은 상위 클래스의 메서드가 반환하는 타입의 하위 타입이 될 수 있다는 것이다. 기존의 오버라이딩은 '메서드의 이름', '매개 변수의 개수, 타입, 순서', '리턴 타입'이 같아야 했다. 하지만 JDK1.5부터 공변 반환타입이 추가되면서 오버라이딩을 할 때 다른 리턴 타입을 가질 수 있게 되었다. 여기서 다른 타입이란 부모클래스에 정의된 메서드의 리턴 타입의 서브타입을 말한다. 2. 구현(JAVA) 🌼 오버라이딩에서의 리턴타입은 부모클래스 리턴 타입의 서브타입이면 된다. 이 점을 유의해서 코드를 보자. class Parent { Parent testMethod() { return this; } } class ChildA extends Parent ..

마커 인터페이스 (Marker Interface)

1. 정의 🏒 interface XXX { } 마커 인터페이스(Marker Interface)란 아무 메서드도 선언하지 않은 인터페이스다. 해당 인터페이스는 객체의 타입과 관련된 정보만을 제공해 주는 역할을 한다. 그래서 컴파일러와 JVM은 마커 인터페이스를 통해 객체에 대한 추가적인 정보를 얻을 수 있다. 조금 더 간단하게 말하자면, 마커 인터페이스는 자신을 구현하는 클래스가 특정 속성을 가진다는 것을 표현해 주는 것이다. 2. 예시를 통한 이해 🥍 마커 인터페이스를 구현하는 클래스가 특정 속성을 가진다는 것을 표시해 주는 이유는 무엇일까? 아래의 동물 예시를 통해 알아보자. 기본 설정은 아래와 같다. 상위클래스인 Animal이라는 클래스가 있다. Dog, Lion, Snake, Fish... 등 여러..

위상 정렬(Topology Sort)

1. 정의 🧊 위상 정렬(Topology Sort)이란 순서가 정해져 있는 작업을 차례대로 수행할 때 그 순서를 결정해 주는 알고리즘이다. 교육과정의 선수과목이 위상 정렬을 설명하는 가장 적절한 예시이다. 컴퓨터 공학을 전공하고 있는 학생은 다음 전공과목(ex. 알고리즘)을 듣기 위해서는 선수 과목(ex. 자료구조)을 필수적으로 들어야 한다. 기초컴퓨터프로그래밍 → 자료구조 → 알고리즘 자료구조 → 논리회로및설계 → 논리회로실험 알고리즘 → 논리회로및설계 → 논리회로실험 또한, 위상정렬은 위와 같이 여러 개의 경로가 존재할 수 있다. 마지막 특징으로는 위상 정렬은 비순환 유향 그래프(DAG - Directed Acyclic Graph)에만 적용이 가능하다. 즉, 사이클이 발생하지 않는 방향 그래프여야 한..