Computer Science & Engnieering/Algorithm18 해시(Hash), 해시맵(HashMap), 해시셋(HashSet) 자료구조 키-값 쌍으로 저장되는 MAP과 데이터의 중복을 허용하지 않는 SET을 학습하려고 합니다.두 자료구조 모두 Hash 알고리즘을 사용하기 때문에 HashMap과 HashSet으로 설명하고자 합니다.해시 (Hash)해시(Hash)는 데이터의 키(Key)를 해시 함수(Hash Function)에 넣어 고정된 크기의 해시 값(Hash Value) 또는 해시 코드(Hash Code)를 생성하는 과정입니다.. 즉 해시(Hash)는 입력된 데이터를 고정된 길이의 데이터로 변환된 값을 말합니다.위 그림에서 해시는 4가 됩니다. 해시의 구성 요소는 다음과 같습니다.Key : 데이터를 찾는데 사용하는 고유한 식별자로, 해시 함수에 입력되는 값입니다.Value : 해당 키에 연결된 실제 데이터로, 해시 테이블에 저.. 2024. 11. 13. 너비 우선 탐색 (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. 동적계획(Dynamic Programming, DP) 동적계획(Dynamic Programming, DP)동적 계획법(DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결한 결과를 저장(메모이제이션)하거나 점진적으로 계산(Top-Down 혹은 Bottom-Up)하여 전체 문제를 해결하는 알고리즘 설계 기법입니다. 동적 계획법의 특징부분 문제의 중복성 : 동일한 하위 문제가 여러 번 재계산되는 문제를 해결하는데 적합합니다. 최적 부분 구조 : 문제의 최적해가 하위 문제의 최적해로 구성될 수 있어야 합니다. 동적 계획법의 접근 방법하향식 접근방법 재귀와 메모이제이션을 이용해 해결큰 문제를 작은 문제로 분할하면서 해결이미 계산된 하위 문제의 결과를 저장하여 중복 계산을 방지상향식 접근방법작은 문제부터 차례대로 해결하여 큰 문제를 해결보통 배열을 이용해 결과를 저.. 2024. 10. 25. 이전 1 2 다음
