전체 글

변수

1. 변수 🏃‍♂️ 자바에서 자료형은 크게 '기본형'과 '참조형' 두 가지로 나눌 수 있다. 기본형 변수는 실제 값(data)을 저장하고, 참조형 변수는 어떤 값이 저장되어 있는 주소(memory address)를 값으로 갖는다. 기본형에는 8가지의 타입이 있고, 8개의 기본형을 제외한 나머지는 모두 참조형이다. 2. 기본형 🏌️‍♂️ 1. 구분 기본형은 크게 '논리형, 문자형, 정수형, 실수형'으로 구분한다. 논리형 boolean 문자형 char 정수형 byte short int long 실수형 float double 2. 크기 기본형의 크기는 다음과 같다. 1 byte 2 byte 4 byte 8 byte 논리형 boolean 문자형 char 정수형 byte short int long 실수형 floa..

퀵 정렬 (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)에만 적용이 가능하다. 즉, 사이클이 발생하지 않는 방향 그래프여야 한..

병합 정렬(Merge Sort)

합병정렬이라고도 불리는 병합정렬에 대해서 알아보자. 1. 정의 🎃 병합정렬이란 정렬해야 하는 배열을 가장 작을 때까지 나누고, 그 시점부터 인접한 부분배열끼리 비교하며 정렬하는 알고리즘이다. 해당 알고리즘은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한다. (분할 정복(Divide and Conquer)이란 문제를 분할하고, 분할한 문제를 정복하여 합치는 것이다.) 2. 동작 방식 🎪 주어진 배열을 절반으로 분할하여 부분배열로 나눈다. - 분할(Divide) 해당 부분배열의 길이가 1이 될 때까지 계속해서 1번 과정을 반복한다. 인접한 부분 배열끼리 합친다. - 정복(Conquer) 위의 그림을 통해 알 수 있듯이 크기가 1이 될 때까지 분할이 진행된다. 그리고 인접한 배열끼리 합..

삽입 정렬(Insertion Sort)

1. 정의 🧵 삽입 정렬은 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 카드 예시를 살펴보면 쉽게 이해할 수 있을 것이다. '4, 2, 3, 1, 5'라는 숫자 적힌 5장의 카드가 순서대로 있다고 하자. 앞에서부터 순서대로 카드를 뽑으면서 손에 쥔다고 생각하자. 뽑힌 카드는 이미 손에 쥐어진 카드들 사이에 위치를 찾아들어간다. 이미 손에 쥐어져 있는 카드들 뽑은 카드 자신의 위치를 찾아들어간 모습 4 4 4 2 2 4 2 4 3 2 3 4 2 3 4 1 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1번 숫자가 적힌 카드가 자신의 위치를 찾아가는 것을 다시 한번 살펴보자. 1번 카드는 4번과 비교하고, 3번과 비교하고, 2번과 ..

선택 정렬(Selection Sort)

선택 정렬은 여러 가지 면에서 앞에서 살펴본 버블 정렬과 상당히 비슷하다. 두 가지 정렬 방법을 구분하는 게 어렵지는 않으니, 선택 정렬을 공부하는 김에 버블 정렬도 같이 공부하는 것을 추천한다. 1. 정의 🎿 선택 정렬은 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 2. 동작 방식 🧦 N개의 원소가 있다고 하자. 우선, 배열에서 최솟값을 찾는다. 그리고 첫 번째 원소와 배열에서 찾은 최솟값의 원소를 바꿔준다. 이것이 1회전 수행한 것이다. 이렇게 되면 배열의 첫 번째에 위치한 원소가 가장 작은 값을 가지게 된다. 2회전을 수행할 때는 첫 번째 원소를 제외한 나머지 배열들 중에서 최솟값을 찾는다. 그리고 해당 원소와 배열의 두 번째 원소를 바꿔준다. 이와 같은 방식으..

버블 정렬(Bubble Sort)

거품 정렬이라고도 불리는 버블 정렬에 대해서 알아보자. 1. 정의 👟 버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 2. 동작 방식 👞 N개의 원소가 있다고 하자. 첫 번째 원소와 두 번째 원소를 비교하여 만약 첫 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 그리고 두 번째 원소와 세 번째 원소를 비교하여 만약 두 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 이러한 동작을 (마지막 - 1) 번째의 원소와 마지막 원소를 비교할 때까지 수행한다. 이것이 1회전 수행한 것이다. 이렇게 되면 마지막에 위치한 원소가 가장 큰 원소가 된다. 2회전을 수행할 때 마지막 원소를 제외한 나머지들을 정렬해 준다. (N - 1) 회전까지 수행하면 정렬이 마무리된다. 위의 방식은 오름차순으로 정렬을 ..

다익스트라(Dijkstra) 알고리즘

1. 기본 개념 🍄 1. 최단 경로 가중치 그래프에서 두 정점 사이의 경로들 중에서 가중치의 합이 최소가 되는 경로 2. 대표적인 최단 경로 알고리즘 다익스트라(Dijkstra) 벨만포드(Bellman-Ford) 플로이드 와샬(Floyd-Warshall) 정의 출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘 출발 정점로부터 모든 정점까지의 최단 경로를 구하는 알고리즘 모든 정점에서 다른 모든 정점까지의 최단 경로를 구하는 알고리즘 특징 음의 가중치를 허용 X 음의 가중치를 허용 O 음의 가중치를 허용 O 사용하는 알고리즘 그리디 알고리즘 그리디 알고리즘 DP 알고리즘 시간복잡도 O(V ^ 2) 또는 O(E log V) O(V ^ 2) 또는 O(E log V) O(V ^ 3) 2. 다익스트라(..