Computer Science & Engnieering40 해시(Hash), 해시맵(HashMap), 해시셋(HashSet) 자료구조 키-값 쌍으로 저장되는 MAP과 데이터의 중복을 허용하지 않는 SET을 학습하려고 합니다.두 자료구조 모두 Hash 알고리즘을 사용하기 때문에 HashMap과 HashSet으로 설명하고자 합니다.해시 (Hash)해시(Hash)는 데이터의 키(Key)를 해시 함수(Hash Function)에 넣어 고정된 크기의 해시 값(Hash Value) 또는 해시 코드(Hash Code)를 생성하는 과정입니다.. 즉 해시(Hash)는 입력된 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다.위 그림에서 해시는 4가 됩니다. 해시의 구성 요소는 다음과 같습니다.Key : 데이터를 찾는데 사용하는 고유한 식별자로, 해시 함수에 입력되는 값입니다.Value : 해당 키에 연결된 실제 데이터로, 해시 테이블에 저.. 2024. 11. 13. [자료구조] 연결 리스트(Linked List) 연결 리스트(Linked List)란?연결 리스트(Linked List)는 데이터를 저장하는 노드(Node)들이 포인터를 통해 연결된 자료구조입니다. 순차 자료구조인 배열(array)은 탐색 속도는 빠르지만, 삽입이나 삭제 연산 시 기존 원소를 옮겨야 하므로 시간이 더 소요됩니다. 이러한 단점을 보완하기 위해, 데이터를 저장하는 노드(Node)들이 포인터로 연결된 자료구조인 연결 리스트(Linked List)가 사용됩니다. 예를 들어연결 리스트는 기차에 비유할 수 있습니다. A, B, C라는 칸이 있고 다음칸을 나타내는 번호표가 있다면 A칸 다음 번호표가 B칸이라면 A칸과 B칸은 연결됩니다. 그리고 B칸은 C칸을 C칸은 X라는 번호표라면 B칸은 C칸과 연결되고 C칸은 마지막 칸이 됩니다. 기차의 칸을 연.. 2024. 11. 12. 너비 우선 탐색 (BFS) 너비 우선 탐색 (Breadth First Search)너비 우선 탐색(Breadth First Search)은 그래프(Graph)나 트리(Tree)를 탐색하는 알고리즘입니다. BFS 동작 원리시작 노드를 방문하고 큐(Queue)에 추가합니다.큐에서 노드를 하나 꺼냅니다.방문하지 않은 인접 노드를 모두 방문하고 큐에 추가합니다. 큐가 빌 때까지 2~3 과정을 반복합니다.BFS 구현그래프를 예시로 코드를 작성하도록 하겠습니다. import java.util.*;public class BFS { // 그래프를 인접 리스트로 표현 static class Graph { private int V; // 노드 수 private LinkedList[] adj; // 인접 리스트 .. 2024. 11. 10. 깊이 우선 탐색(DFS) 깊이 우선 탐색(DFS)DFS(Depth First Search)는 그래프(Graph)나 트리(Tree)에서 사용되는 탐색 알고리즘입니다. DFS의 동작 원리시작 노드를 방문합니다. (시작 노드 방문)방문하지 않은 노드가 있으면 해당 노드로 이동합니다. (인접 노드 탐색)더 이상 방문할 노드가 없을 때까지 탐색을 반복합니다. (반복)더 이상 방문할 노드가 없으면 이전 노드로 돌아갑니다. (백트래킹)모든 노드를 탐색할 때까지 반복합니다 (모든 노드 탐색) DFS 구현 방법 위와 같이 노드가 있다 가정하겠습니다. import java.util.*;public class DFS { // 그래프를 인접 리스트로 표현 static class Graph { private int V; // 노.. 2024. 11. 9. 힙 정렬(Heap Sort) 힙 정렬(Heap Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 네 번째로 정리할 정렬 알고리즘은 힙 정렬입니다. 힙 정렬이란?힙 정렬은 완전 이진 트리 구조를 기반으로 한 선택 정렬의 변형입니다. 힙 정렬은 힙 자료구조를 사용하여 정렬을 수행합니다. 동작 원리힙 생성(Build Heap)배열을 최대 힙 또는 최소 힙의 형태로 변환합니다.최대 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음최소 힙 : 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음정렬 과정힙의 루트 노드(최대 힙의 경우 가장 큰 값)를 배열의 끝으로 이동시킵니다.힙의 크기를 줄이고 다시 힙 소것ㅇ을 유지하도록 조정합니다.이 과정을 반복하여 정렬된 배열을 만듭니다.예시힙 만들기힙새로 추가된.. 2024. 11. 7. 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 세 번째로 정리할 정렬 알고리즘은 삽입 정렬입니다. 삽입 정렬이란?삽입 정렬은 배열을 순차적으로 탐색하면서 각 원소를 그 이전의 부분 배열에 적절한 위치에 삽입하여 정렬하는 알고리즘입니다. 동작 원리배열의 두 번째 원소부터 시작해서 첫 번째 원소와 비교한 후 적절한 위치에 삽입합니다.그 다음 원소를 비교하여 이미 정렬된 부분 배열의 적절한 위치에 삽입합니다.이 과정을 배열의 끝까지 반복합니다.예시[31, 25, 12, 22, 11] 이 처음 상태인 배열입니다. [31, 25, 12, 22, 11] 두 번째 원소를 부분 리스트에서 적절한 위치에 삽입합니다. [, 31, 12, 22, 11] 세 번째 원소.. 2024. 11. 6. 선택 정렬(Selection Sort) 선택 정렬(Selection Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 두 번째로 정리할 정렬 알고리즘은 선택 정렬입니다. 선택 정렬이란?선택 정렬은 배열을 순차적으로 탐색하면서 최소값 찾아 맨 앞에 위치한 값과 교체하는 방식입니다. 동작 원리배열의 첫 번째 원소부터 시작하여 나머지 원소들 중에 가장 작은 원소를 찾아 첫 번째 원소와 교환합니다.두 번째 원소부터는 이미 정렬된 부분을 제외한 나머지 배열을 탐색하여 가장 작은 값을 찾아 두 번째 원소와 교환합니다.이 과정을 배열 끝까지 반복하면서 정렬이 완료됩니다.예시패스테이블최솟값0[9, 1, 6, 8, 4, 3, 2, 0]01[0, 1, 6, 8, 4, 3, 2, 9]12[0, 1, 6, 8, 4, 3, 2, 9]23[0.. 2024. 11. 5. 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 알고리즘을 공부하면서 정렬 알고리즘을 정리하고자 합니다. 이에 첫 번째로 정리할 정렬 알고리즘은 버블 정렬입니다. 버블 정렬이란?버블 정렬은 인접한 두 원소를 비교하여 크기 순서대로 정렬하는 알고리즘입니다. 동작 원리배열을 처음부터 끝까지 순차적으로 비교합니다.두 원소를 비교하여 만약 순서가 잘못되었다면 두 원소를 교환합니다.이 과정은 배열 끝까지 진행되고 한 번의 패스가 끝나면 가장 큰 값이 맨 뒤로 이동합니다.반복적으로 비교하면서 각 패스를 통해 진행됩니다.예시[7, 2, 0, 1, 5, 6, 4] 와 같이 정렬되지 않은 배열이 있다고 가정합니다. 알고리즘은 배열의 첫 두 숫자 (7, 2)를 비교합니다. 여기서 7 > 2로 정렬되지 않았으므로 두 수의 자리를 바꿉.. 2024. 11. 4. 그리디 알고리즘(Greedy Algorithm) 서론 그리디란 무엇이고 어떻게 적용하는지 간단히 정리하고자 합니다. 출처 : 나무위키 그리디 그리디 알고리즘그리디 알고리즘 (욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인namu.wiki 코딩 테스트를 준비하면서 예전에 공부했던 그리디 알고리즘을 정리하면서 공부하고자 합니다. 1. 그리디 알고리즘이란?그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.출처 : 나무위키 그리디 알고리즘은 문제를 해결할 때 현재 단계에서 최선이라 생각되는 선택을 반복적으로 수행하여 최적의 해답에 도달하는 알고리즘입니다. 매 단계.. 2024. 11. 3. 이전 1 2 3 4 5 다음
