💡 선택 정렬 (Selection Sort) 대상 데이터의 최소값과 최대값을 찾아서 데이터가 나열된 순으로 찾아가며 선택하는 방법이다. 구현 방법이 복잡하고 시간복잡도도 버블 정렬과 같이 O(n2)으로 비효율적이다. 선택 정렬의 원리만 간단히 알아보자. 과정 남은 정렬부분에서 최대값 & 최소값을 찾는다. 남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap 한다. 가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다. 전체 데이터 크기만큼 index가 커질 때 까지 즉, 남은 정렬 부분이 없을 때까지 반복한다. 구현 선택 정렬을 이용해 내림차순 정렬을 구현한다. public class SelectionSort { static String testA = ..

💡 버블 정렬 (Bubble Sort) 데이터의 인접 요소의 크기를 비교하고, swap 연산을 수행하며 정렬하는 방식 시간복잡도는 O(n2)으로 굉장히 느린편이다. 보통 loop를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다. 과정 비교 연산이 필요한 경우 loop 범위를 설정한다. 인접한 데이터 값을 비교한다. swap 조건에 부합하면 swap 연산을 수행한다. loop가 끝날때까지 2~3을 반복한다 정렬 영역을 설정한다, 다음 loop를 실행할 때는 이 영역을 제외한다. 비교 대상이 없을 때까지 1~5를 반복한다. 만약 특정 loop의 전체 영역에서 swap이 발생하지 않으면, 정렬이 됬다는 의미이므로 프로세스를 종료해도 된다. 버블정렬을 이용한 N개의 수 오름차순 정렬 sort()를 이용하..

💡 DFS Depth-First Search의 약자이며 깊이 우선 탐색을 하는 알고리즘이다. 동작방식 스택을 이용하므로 재귀를 이용했을때 간결한 구현이 가능하며 시간복잡도는 O(N)이다. 탐색 시작 노드에 스택일 삽입하고 방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣어 방문 처리하고, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 위의 과정을 더 이상 수행할 수 없을 때까지 반복한다. 방문처리란? 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 이를 통해 각 노드를 한 번씩만 처리할 수 있다. 재귀 함수를 이용한 DFS 구현 노드들은 호출을 받으면 하위의 노드를 재귀 호출 하기 전, 자기 자신을 출력한..

💡 ArrayList로 스택 구현 public class Implementation_Stack { private ArrayList listStack = new ArrayList(); public void push(Integer data) { listStack.add(data); } public Integer pop() { if (listStack.size() == 0) { return null; } else { return listStack.remove(listStack.size()-1); } } public int size() { return listStack.size(); } public Integer peek() { if (listStack.size() == 0) { return null; } el..

💡 선형조사법 (Linear Probing) 채우려는 공간이 이미 차 있다면, 비어있는 칸을 찾을 때까지 다음 칸을 확인하는 방법이다. 비어있는 칸을 찾아 그 곳에 채운 후 위치가 바뀌었다는 사실을 알려야 한다. 예시 객체 x 객체 x의 hashCode 값인 h를 구한다. h를 양수로 변환 -> h & 0x7FFFFFFF; 테이블의 크기와 % 연산 -> h % table.size(); h를 가지고 x를 적절한 위치로 저장, 이 때 위치는 hashCode의 값에 따라 다름 객체 y 위와 동일한 방법으로 h를 구한다. x의 위치와 동일한 값이 나오면 x의 위치에 y를 저장해야 한다. 이런 상황을 충돌이라고 한다. 해결 x의 다음 칸에 y를 저장 y의 위치가 바뀌었다는 사실을 알려야 한다.\ 삭제의 경우 데이..