glenn

선택정렬이란? 처음 배열 탐색 시 최소값을 찾은 후 가장 첫번째 배열값과 자리를 바꾸는 방식. 시간복잡도 O(n^2)이며 큰 데이터셋에는 적합하지 않다. 따라서 큰 데이터셋에는 퀵, 힙, 병합정렬등을 고려. 선택정렬 흐름도 배열내 최솟값을 찾음 최솟값을 맨앞자리 값과 swap 이미 자리교체된 값의 다음값을 첫번째로 기준으로 삼고 1,2 번 과정 반복 round 9는 8번돌면 최종적으로 마지막 값은 정렬이 되있으므로 skip 자바 구현 public class Selection_Sort { public static void selection_sort(int[] a) { selection_sort(a, a.length); } private static void selection_sort(int[] a, int..

코딩테스트/[ 알고리즘 ] 2024. 4. 9. 16:04

이분탐색이란? 정렬된 배열 또는 리스트에서 특정 값을 찾는 고속 탐색 방법. 이진 탐색은 탐색범위를 1/2로 줄이며 탐색하기에, 선형탐색에 비해 빠르다. BUT 배열, 리스트는 정열되어 있어야 한다는 전제조건 배열의 '중간 값'을 선택 후 찾는값과 비교. 중간값이 찾는값보다 크면 '배열의 왼쪽 부분'에서 탐색 시작. 중간값이 찾는값보다 작으면 '배열의 오른쪽 부분'에서 탐색 시작. 위 과정 반복 시간복잡도 비교 순차적 탐색은 최악의 경우 배열의 끝까지 탐색하지만, 이분탐색은 1/2씩 범위를 줄여서 탐색하므로 빠르다. 방식 시간복잡도 순차적 탐색 O(n) 이분 탐 O(logn) 자바 구현 - 반복문으로 구현 public static boolean BSearch(int[] arr, int n) { int l..

코딩테스트/[ 알고리즘 ] 2024. 4. 8. 17:25

DFS vs BFS 너비 우선 탐색이란?( Breadth First Search) 루트 노드에서 탐색을 시작하여 같은 레벨에 있는 노드를 모두 탐색한 다음 하위 레벨로 내려가 또 모두 탐색을 진행하다가, 더이상 탐색할 노드가 없을 때 탐색을 멈추는 방식. BFS는 일반적으로 큐를 이용하여 구현한다. 자바 구현 class Graph { private int V; private LinkedList adj[]; // 링크드리스트의 배열 // constructor Graph (int v) { V = v; adj = new LinkedList[v]; // v개의 LinkedList 선언 및 생성 for (int i = 0; i < v; ++i) { adj[i] = new LinkedList(); } } void ..

코딩테스트/[ 알고리즘 ] 2024. 4. 8. 17:07

버블 정렬이란? 인접한 두 원소를 비교하며, 큰 수를 계속하여 뒤로 보내 정렬하는 방식. 간단히 구현할 순 있지만, 시간복잡도는 O(n^2)로 다른 정렬 알고리즘보다 속도가 느린 편이다. 자바 구현 public class bubbleSort { public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); int[] arr = new int[5]; for(int i=0; i

코딩테스트/[ 알고리즘 ] 2024. 3. 23. 15:59

DFS vs BFS   깊이 우선 탐색이란?(Depth First Search)"한거번에 덤비지말고 한명씩 덤벼" 그래프의 시작노드에서 출발하고 다음 구역으로 넘어가기 전에 해당 구역을 완벽하게 탐색일반적으로 BFS에 비해 널리 쓰인다. (코테에서 대부분의 탐색은 DFS로 구현) DFS는 주로 스택을 통한 반복이나 재귀를 통한 반복 구조(가장 일반적)로 구현.    대표 유형경로탐색 유형(최단거리, 시간)네트워크 유형(연결) : 여러개체들이 주어진 상태에서 연결되어있는 그룹의 갯수, 두 개체가 같은 네트워크안에서 연결되어있는지 확인조합 유형(모든 조합 만들기) : 여러가지의 조합을 만들고 비교해야하는 문제   자바 구현public class DFS_Recursion { // 오름차순 // 재귀 ..

코딩테스트/[ 알고리즘 ] 2024. 3. 20. 16:22

퀵 정렬이란?피벗(pivot)을 사용한 정렬 알고리즘이며 피벗에 따라 시간복잡도가 달라질 수 있다. 병합 정렬과 같은 분할 정복 알고리즘.많은 양의 데이터를 정렬하는데 유용.   시간복잡도평균O(nlogn)최악O(n^2)   동작방식 배열에서 하나의 요소를 기준으로 잡고 이를 피벗(Pivot) 이라고 한다.기준점은 아무기준이나 상관없으나, 보통 중앙값을 잡음.start는 pivot보다 크거나 같은 값을 찾을 때까지 움직이고, end는 pivot보다 작거나 같은 값을 찾을 때까지 움직인다.start와 end가 모두 충족 될 경우 swap해준다.2번의 과정을 반복한다.start와 end의 순서가 역전되면 반복문을 종료하고, start값을 기준으로 배열을 파티셔닝한다.나눠진 파티션 별로 다시 위의 과정을 재귀..

코딩테스트/[ 알고리즘 ] 2024. 3. 18. 22:11

Heap 이란? 우선순위큐를 위해 고안된 완전이진트리 형태의 자료구조, 여러값 중 최대/최소값을 빠르게 찾아내도록 만들어진 자료구조. ▶ 완전 이진트리 : 노드가 왼쪽부터 채워지는 형태 Heap의 종류 최소 힙 (min heap) : 부모노드 = 자식노드 데이터 삽입 최소 힙에 저장 - 삽입되는 값을 상위 부모노드와 비교하여 더 작을 경우 위로 swap 2. 최대힙에 저장 - 삽입되는 값을 상위 부모노드와 비교하여 더 클 경우 위로 swap 데이터 삭제 최소/최대힙의 가장 최상위 노드가 결국 최소값, 최대값이 되며, 힙 자료구조는 최소/최대값을 알아내는것이 목표임 따라서, 데이터를 삭제하면 최소/최대값이 삭제된다. 최대힙 삭제 예시 시간 복잡도 O(logN) 최악의 상황은 가장 root노드와 비교까지 할..

코딩테스트/[ 자료구조 ] 2024. 3. 16. 16:18

Hash 란? Hash 데이터를 key-value 형태로 저장하고 Key값이 배열의 인덱스로 저장되기에 검색과 저장이 빠른 자료구조 Hash Function & Hashing 해시함수란 key값을 고정된 길이의 hash로 변환하는 함수이며, 해싱은 key값을 hash로 변환하는 과정이다. (즉, 해시함수를 사용하여 해싱작업을 하는것, key값으로 > hash 생성) Hash Table 해시테이블은 연관배열구조를 이용하여 데이터를 key-value형태로 저장하는 자료구조. 해시테이블은 key-value가 1:1 매핑구조이므로 삽입, 삭제, 검색 과정에서 평균적으로 O(1)의 복잡도를 가짐 - 장점 : 중복제거, 데이터 캐시, 인덱스접근으로 빠른 연산속도 - 단점 : 공간복잡도 커짐, 충돌 발생 가능성, 순..

코딩테스트/[ 자료구조 ] 2024. 3. 16. 15:07