Algorithm22 그래프 구현 그래프 자세히 알아보기 그래프 구현 방식 인접 행렬 (adjacency matrix) 인접 리스트 (adjacency list) 차이점 인접 행렬 인접 리스트 정점 간의 간선 여부 graph[x][y] 의 값으로 한번에 확인 graph 의 원소에서 y가 나올때까지 탐색 공간 복잡도 V개의 노드 표현 위해V^2 만큼의 공간 필요 인접 노드를 찾기 위해 모든 노드를 순회 공간복잡도 : O(V^2) V개의 리스트에 간선(E) 만큼 원소가 들어있음 인접 노드를 쉽게 찾을 수 있음 공간복잡도 : O(V+E) 주사용 간선이 많이 있는 밀집 그래프 간선의 연결 여부 확인에 유리 간선이 적게 있는 희소 그래프 인접 노드 확인에 유리 인접 행렬 그래프를 2차원 배열에 저장하는 방법으로 노드 수보다 간선 수가 많은 den.. 2022. 6. 14. 이진 트리 순회 트리 순회 방식 전위 순회 부모 -> 왼쪽 -> 오른쪽 순으로 순회한다. 1-2-4-5-3-6-7 중위 순회 왼쪽 -> 부모 -> 오른쪽 순으로 순회한다. 4-2-5-1-6-3-7 후위 순회 왼쪽 -> 오른쪽 -> 부모 순으로 순회한다. 4-5-2-6-7-3-1 코드 구현 DFS_전위 순회 public class Solution { Node root; public void DFS(Node root){ if(root==null) return; else { System.out.print(root.data+ " -> "); //전위 순회 출력 DFS(root.lt); //트리 왼쪽으로 값 전달 | (root.lt).lt (root.lt.lt).lt // System.out.print(root.data+ " -.. 2022. 6. 13. 알고리즘 구성 및 간단 비교 알고리즘 트리 종류에 따른 알고리즘 구분 ex. BFS : 너비 우선 탐색을 진행하며, Queue를 사용하는 경우 DFS : 깊이 우선 탐색을 진행하며, Stack을 사용하는 경우 백트래킹 : 재귀함수를 사용하여 완전 탐색을 하는 경우 2022. 6. 9. 재귀 함수 개요 재귀 함수란 자기 자신을 호출하는 함수, 반복문의 형태로 아래 코드와 같은 형식으로 작성된다. public void DFS(int n){ if(n==0) return; else { DFS(n-1); // 자기자신 호출 } } public static void main(String[] args) { Main T = new Main(); T.DFS(3); } 위 코드에서 T.DFS(3)을 호출하면 호출 순서대로 스택 메모리에 프레임 형태로 담기며 스택 메모리에는 호출된 함수의 매개변수, 지역변수, 함수가 끝나고 돌아갈 반환 주소값 등이 저장된다. 이처럼 재귀 함수는 메모리를 많이 차지하기에 반복문에 비해 성능이 좋지 않다. 예제 재귀 함수를 이용한 팩토리얼 public int DFS(int n){ if.. 2022. 6. 8. Insertion Sort https://sskl660.tistory.com/81 [Java]삽입 정렬(Insertion Sort) *삽입 정렬(Insertion Sort) ->삽입 정렬이란 2번째 원소부터 n번째 원소까지 차례로 해당 원소가 위치할 인덱스에 원소를 삽입하는 방식을 사용하는 정렬 방식이다. ->2번째 원소부터 n번째 원소부터 sskl660.tistory.com 2022. 6. 3. Bubble Sort 개요 거품 정렬은 데이터를 '비교'하면서 찾기 때문에 '비교 정렬'이며 정렬의 대상이 되는 데이터 외에 추가적인 공간을 필요로 하지 않기 때문에 '제자리 정렬(in-place sort)'이기도 하다. 정확히는 데이터를 서로 교환하는 과정(swap)에서 임시 변수를 필요로 하나, 이는 충분히 무시할 만큼 적은 양이기 때문에 제자리 정렬로 보는 것이다. 이는 선택정렬과도 같은 부분이다. 그리고 이전에 다뤘던 선택 정렬과는 달리 거품 정렬은 앞에서부터 차례대로 비교하기 때문에 '안정 정렬'이기도 하다. 정렬 동작 First Pass 첫 요소들을 시작으로 서로 인접한 두 요소를 순차적으로 비교한다. ( 5 1 4 2 8 ) –> ( 1 5 4 2 8 ) ( 1 5 4 2 8 ) –> ( 1 4 5 2 8 ) (.. 2022. 6. 1. 이전 1 2 3 4 다음
