선택 정렬 (selection sort) 선택정렬은 대상 데이터에서 최대나 최소 데이터를 찾아서, 정렬 방법에따라 알맞은 위치로 이동시키는 방법이다. 선택정렬은 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)로 비효율적이기 때문에 잘 사용하지는 않지만, 응용해서 일부 사용할때도 있기 때문에, 방법은 알아두는것이 좋다. 핵심 이론 이 방법을 처음 접했을때 드는 생각은 굉장히 단순하고 비효율적이라는 생각이 들었다. [ 5, 3, 1, 6, 4, 2] int[] arr = { 5, 3, 1, 6, 4, 2 } 위와 같은 정렬되지 않은 배열이 있을 때, 선택정렬을 이용하여 내림차순으로 정렬해보자. 첫번째 사이클 arr[0]에는 가장 큰수가 와야한다. arr[1]부터 arr[5]까지 모든 값들 중 가장 큰 수 ..
버블정렬 (bubble sort) 버블정렬은 인접한 두 데이터의 크기를 비교해 두 데이터를 서로 바꿔가며 정렬하는 방법이다. 간단히 구현할 순 있지만, 시간복잡도는 O(n^2)로 다른 정렬 알고리즘보다 속도가 느린 편이다. 핵심 이론 정렬되지 않은 정렬의 첫번째 인덱스부터 그 다음 인덱스와 비교하며, 정렬 조건에 따라 자리를 바꿔준다. 루프 범위 설정 인접한 데이터 값을 비교한다. swap조건에 부합하면 swap연산을 수행하고, 부합하지 않으면 그냥 넘어간다. 2번~3번을 반복한다. 전 범위를 반복하면 정렬된다. ( 만약 전 범위를 반복하지 않았지만, 만약 하나의 루프에서 swap연산이 한번도 일어나지 않는다면 끝내도된다.) Code 정렬되지 않은 배열 arr이 주어질 때 public static voi..
BFS(Breadth-First Search) : 너비 우선 탐색 그래프 완전 탐색 시작 노드에서 출발해 시작 노드를 기준으로 가장 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다. FIFO 탐색 -> Queue 자료구조를 이용한다. 목표 노드에 도착하는 경로가 여러개일 때 최단경로를 보장한다. 1. 시간복잡도 인접 리스트 노드의 개수가 많고, 간선 수가 적을 때 유리하다. 인접 행렬 노드의 개수가 적고, 간선 수가 많을 때 유리하다. 인접 리스트 인접 행렬 특정 간선 검색 O(degree(N) : 해당 노드의 차수 O(1) 정점의 차수 계산 O(degree(N)) O(N) 전체 노드 탐색 O(E) O(N^2) 메모리 N+E N^2 2. BFS 핵심 이론 1) 방문여부 확인용 배열 BFS도 DFS와 ..
DFS(Depth-First Search) : 깊이 우선 탐색 그래프 완전 탐색 : 모든 노드를 방문하고자 할때, 이 방법을 선택한다. 그래프의 시작 노드에서 출발하여 탐색할 한 쪽 분기를 정해서 최대깊이까지 탐색을 마친 후, 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘이다. 재귀함수 또는 Stack 자료구조를 이용한다. 재귀함수를 이용하므로 stack overflow에 유의해야 한다. 스택 오버플로우(stack overflow)는 지정한 스택 메모리 사이즈보다 더 많은 스택 메모리를 사용하게 되어 에러가 발생하는 상황을 일컫는다. 1. 시간복잡도 (노드 수: N, 에지 수 E) 인접 리스트 노드의 개수가 많고, 간선 수가 적을 때 유리하다. 인접 행렬 노드의 개수가 적고, 간선 수가 많을 때 ..
1. 배열이란? 동일한 자료형(Type)의 데이터를 하나의 연속된 공간에 저장하는 자료구조이다. 각 데이터의 저장 위치는 index(0부터 시작)를 부여해 접근한다. 정해진 크기의 메모리를 먼저 할당받아 사용한다. 즉, 선언할 때 크기를 미리 지정해야한다. 한번 선언하면 이후에 크기를 변경할 수 없다. 비어있는 인덱스가 존재해서는 안된다. 만약 특정한 값으로 초기화하지 않은 배열 안의 데이터를 참조하면 예외가 발생한다. 인덱스(index) 인덱스는 배열의 각 저장 위치를 가리키는 0부터 1씩 증가하는 값이다. 배열 이름 옆에 대괄호[ ]에 기입한다. int[] arr = new int[5]; arr이라는 이름의 배열이 있고, 5개의 저장공간을 갖는다. 첫번째 저장공간의 값을 가져올때는 arr[0], 두번..
컬렉션 프레임워크 JDK에서 자료구조를 구현해놓은 라이브러리 java.util 패키지에 구현되어 있음 개발 시간을 절약하기 위해 list, set, map 등 여러가지 알고리즘을 사용할 수 있음 java doc 링크 : https://docs.oracle.com/javase/8/docs/api/ 1. List 인터페이스 객체를 순서에 따라 저장, 관리 중복 허용 ArrayList, LinkedList, Vector, Queue 등 https://docs.oracle.com/javase/8/docs/api/ 2023.02.06 - [JAVA공부/자료구조] - [JAVA/자료구조] List 2. Set 인터페이스 객체를 순서와 관계없이 저장, 관리 아이디, 사번, 주민번호 등 유일한 값을 관리하는데 유용 중..
