Manta Ray's

너비 우선 탐색 시작점에서 도달 가능한 모든 간선을 탐색하여 찾는 과정 탐색을 하면서 시작점으로부터 거리를 계산한다. 탐색을 하면서 직전 정점의 위치를 저장한다. (거쳐온 정점을 기록한다.) 탐색을 하면서 정점의 상태를 변환한다. 초기화 : not discovered = white 발견한 정점 : discovered = gray 완료된(방문한) 정점 : finished = black 슈도코드 1. 주어진 모든 Graph를 초기화 * 정점의 상태 : 초기화(white) * 시작점으로부터의 거리 : ∞ * 바로 직전의 정점 : 초기화(NULL) 2. 시작 위치 저장 * 시작 정점의 상태 : 발견(gray) * 시작점으로부터의 거리 : 0 * 바로 직전의 정점 : NULL * Queue에 방문한 경로에 현재위..

삽입 정렬 Key 값과 정렬된 리스트가 주어졌을때, Key값을 정렬된 리스트의 알맞은 위치에 삽입 Key 값을 하나씩 추가하면서 정렬. ① i 위치의 값을 0~(i-1) 위치까지의 값과 비교하여 i위치의 값이 들어갈 위치를 찾음. ② i 위치의 값을 찾은 자리에 삽입 시간복잡도 최선의 경우 : 0 ~ i-1 배열이 이미 정렬된 경우 > 비교를 1번만 하면 됨 => n-1 최악의 경우 : 0 ~ i-1 배열이 반대로 정렬된 경우 > 모든 배열 값과 다 비교해야 함. => n(n-1)/2 O(n²) 구현 (JAVA) public int[] sort(int[] arr) { //배열을 리스트로 변경 List list = Arrays.stream(arr).boxed().collect(Collectors.toLis..

선택정렬의 종류 ① 최소값 선택 정렬 (오름차순) ② 최대값 선택 정렬 (내림차순) 최소값 선택 정렬 (오름차순) 정렬되지 않은 숫자 중에 가장 작은 숫자를 선택한다. 선택한 가장 작은 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다. 모든 숫자를 옮길 때까지 반복한다. 최대값 선택 정렬 (내림차순) 정렬되지 않은 숫자 중에 가장 큰 숫자를 선택한다. 선택한 가장 작은 숫자를 정렬되지 않은 숫자들 중 첫번째 숫자와 위치를 바꾼다. 모든 숫자를 옮길 때까지 반복한다. 시간복잡도 n개가 있을 때 가장 큰/작은 수를 구하기 위해서 n-1 번의 비교가 일어남. => n(n-1) / 2 O(n²) 구현 (JAVA) public int[] solution(int n, int[] arr) { for(in..

알고리즘이란 ? 주어진 문제를 효율적으로 풀기위한 방법을 단계별로 기술해놓은 것. 알고리즘 설명 4단계 ① Problem definition (문제 정의) ② Algorithm description (알고리즘 설명) ③ Correctness proof (정확성 증명) ④ Performance Analysis (성능분석) - Running Time (수행시간) - Space Consumption (사용공간) 재귀와 반복 [재귀] 실행 도중 자기 자신을 호출하는 함수로 특정 조건을 만족하면 멈춘다. 재귀 함수가 자신을 호출하는 횟수가 최대 재귀 깊이를 초과하면 스택 오버플로 에러가 발생한다. [반복] 특정 조건이 만족될 때까지 실행이 되풀이 되는 함수. 종료 조건이나, 반복 횟수를 지정하지 않으면 스택 오퍼..