개발자되기 프로젝트

루트부터 시작하여 인접한 노드를 먼저 탐색하고 그 다음으로 깊이 방향으로 진행. 즉, 깊에 탐색하기 보다는 넓게 탐색 하는 방법 * 깊게 탐색하는 방법 : DFS(Depth First Search) 인접한 노드를 모두 탐색하고 깊게 나아가기 때문에 queue를 활용하여 구현이 가능한다. - 루트부터 시작하여, 방문할 때 마다 해당 노드를 enqueue하고 인접한 노드를 모두 enqueue한다. - 더이상 방문할 인접 노드가 없으면, queue에서 head를 dequeue한다. - 해당 노드와 인접한 노드를 방문 및 enqueue한다. - 모두 방문할 때 까지 계속 반복. - 즉 enqueue, dequeue를 계속 반복한다. 아래 순서를 따가 구체적인 사례를 보자. 1. 탐색 순서 1) 루트부터 시작. ..

앞서 DFS에 대한 개념 및 예시를 알아보았다. 코드로 작성해보자! 1. UndirectedGraph를 matrix로 구현하기 DFS를 코드로 구현하기 앞서, 그래프를 matrix로 등록하는 코드를 작성하자. 그래프는 이전에 사용한 그래프와 동일한 그래프를 사용할 예정. public class UndirectedGraph { //현재 노드가 몇개? int nubmer; int from; int to; //matrix private int[][] nodeMatrix; //가중치 private int weight; public UndirectedGraph(int nubmer){ this.nubmer = nubmer; nodeMatrix = new int[nubmer][nubmer]; //UndirectedG..

0. 그래프란? node와 node를 edge로 연결한 비선형 자료구조,. 즉 객체관의 관계?를 나타내는 방법 1. 그래프 탐색 그래프 안에 어떤 노드가 있는지 알아보는 방법. 어느 한 노드부터 시작하여 모든 노드를 한 번씩 방문! 2. 그래프를 maxtirx로 나타내기 예를들어 "2"와 인접한 노드를 확인해보자. "2"와 인접한 노드는"0", "5", "6"이다. 즉 (2, 0), (2, 5), (2, 6)에 1을 입력한다. 만약 가중치가 부여된다면 해당 값 입력하면 됨. 위의 그래프는 양방향으로 이동이 가능하다. 즉, (0, 2), (5, 2), (6, 2)에 "1"이 똑같이 입력된다. 따라서 해당 matrix는 symmetric하다. 단, 그래프가 방향성이 있을 경우 , symmetric하지 않다...

1. Element 삭제하기 루트에 있는 값(별)은, min heap일 때 제일 작고, max heap일 경우 가장 크다. 즉 heap에서 꺼낼 경우 루트에 있는 요소만 꺼낸다. 2. 10을 꺼냈다. 빈칸으로 남는다. 3. 빈칸에는 가장 마지막에 있는 요소가 들어온다고 가정하자. 4. 이 때, 80이 저 위치에 있는게 맞냐?! min heap인 경우 child 중 가장 작은 수와 비교하고. max heap인 경우 child중 가장 큰 수와 비교한다. 지금은 min heap이니 80과 20을 비교한다. 5. 80은 20보다 크다. 80이 기존 20의 자리에 있다고 가정하자! 6. child 중 가장 작은 수인 40과 비교하자. 7. 80은 40보다 크다. 80이 기존 40의 위치에 있다고 가정하자! 8. ..

평균 수행시간이 O(logN)인 경우 : 한 번 수행할 때 마다 정렬해야 하는 수가 1/2개로 줄어드는 경우 - Quick 정렬(퀵 정렬) : worst인 경우 O(n^2) 까지 가능.. - Merge 정렬(병합 정렬) : 메모리를 가지고 있다. element를 분배한다. 얘네를 다시 병합하면서 sorting - Heap 정렬(힙 정렬) : Heap 이라는 tree구조. 실제 구현은 배열로 만듦. 단, Merge 정렬과 Heap 정렬은 추가적인 메모리가 필요하다. 0. Heap 정렬 Heap 이란? complite binary tree(BT)를 의미한다. Complite Binary Tree란? 이진 트리로, 1) 무조건 element가 왼쪽부터 채워져야 하고 2) height가 h라 할 때, h-1까지..

일반적으로 정렬 알고리즘은 O(n^2)의 수행시간을 가짐. 1. Selection Sort 50 10 60 80 90 100 20 위와같이 숫자 배열이 있을 때, 오름차순으로 정렬해보자 앞에서부터 쭉 스캔해서 제일 작은 값 찾고, 가장 앞에 위치시킴. 다름 위치에는 누굴 데려올까, 쭉 스캔하다가 가장 작은 값 선택(selection) 즉, n개의 값을 n번 씩 봐야 하기 때문에 O(n^2)이다. 2. Bubble Sort 아래와 같이 숫자 배열이 있다고 하자. 50 10 60 90 80 20 100 1) 50 & 10 비교한다. 10이 더 작다. -->50 ↔ 10 위치 바꾼다. 10 50 60 90 80 20 100 3) 50 & 60 비교 --> 그대로 10 50 60 90 80 20 100 5) 6..

여러 개의 수가 정렬 되었을 경우 특정 수를 찾는 방법 단순 반복문을 사용하면 앞에서 부터 차례로 찾아가기 때문에, 입력된 값에 따라 비교 횟수가 증가한다. 즉 O(n)의 수행이 이루어진다. 정렬된 상태에서 수행 횟수를 줄이기 위해서는 binary Search가 효율적이다. 왜냐? 아래와 같은 상황이라고 가정하자. 10개의 수의 배열이 주어진다. [12, 25, 31, 43, 53, 64, 78, 82, 95, 103] 95의 위치를 찾아보자. 1) 단순 반복문을 사용해서 하나씩 비교하면, 12부터 차례대로 비교해서 95와 같은지 확인해야 한다. 2) binary search를 사용하면, 중간에 있는 값이 95보다 큰지 작은지 판단한다. 3) 중간에 있는 값은 53이다. 따라서 이제 53이전의 숫자는 고..

10개의 숫자를 입력받는다. 10개의 숫자 중 가장 큰 값과 가장 작은 값을 찾는다. 몇 번째 수인지 찾는다. 반복문을 한 번만 사용한다. 예 : 10, 65, 84, 22, 42, 100, 210, 85, 87, 32 가 주어진 경우 max : 210, 7번 째 min : 10, 1번 째 얼마나 효율적인 알고리즘을 만드느냐가 중요함. 하나의 변수를 지정해 주고, 해당 변수를 update를 진행. Time complexity? for문이 얼마나 중첩되어 있냐? for문이 도는데. 뭐에 dependent하냐? public class MinMaxProblem { public static void main(String[] args) { int n = 10; Scanner sc = new Scanner(Syst..