개발자되기 프로젝트

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

1.Queue란? Queue를 사전에서 찾으면 순서를 기다리는 열을 의미한다. 즉 순서를 기다린다는 것은 롯데월드가서 아틀란티스 타려고 줄서는 것을 의미한다. 이것을 data와 연결하면 data가 순서대로 입력되고 가장 먼저 입력된 data부터 처리되는 것을 의미. 순서대로 접수? 입력을 받고 그 순서대로 처리가 필요한 곳에 사용이 가능할 듯 하다. 2. Enqueue관련 method 1) add(element) queue 가장 뒤에 element를 insert한다. 성공하면 true를 반환한다. 만약 queue에 공간이 없어 입력에 실패하면 IllegalStateException을 반환한다. 2) offer(element) 성공하면 true, 실패하면 false를 반환한다.(add와 가장 큰 차이) 일..

- 동일한 데이터 타입을 순서에 따라 관리하는 자료 구조 - 노드에는 자료와 다음 요소를 가리키는 링크가 있다! 노드 = 자료 + 다음 링크 - 자료가 추가될 때 노드 만큼의 메모리를 할당 받고 이전 노드의 링크로 열결함. - i 번 째 요소를 찾는 데 걸리는 시간은 요소의 수(n)에 비례 : O(n) - jdk class: LinkedList 1. Node - 각 노드에는 이전, 이후 노드에 대한 정보가 있다. private static class Node { E item; Node next; Node prev; Node(Node prev, E element, Node next) { this.item = element; this.next = next; this.prev = prev; } } 2. LIn..

앞서 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. 맨 마지막(top) 위치에서만 자료를 추가, 삭제, 꺼내올 수 있다. 중간에 있는 자료를 꺼낼 수 없음! data를 블럭 쌓는 것 과 같이 하나씩 쌓아 올린다고 보면 된다. 2. Last In First out 3. 가장 최근의 자료를 찾아오는데 사용할 수 있음. 게임으로 예를 들면 가장 최근의 세이브를 불러오는 것과 유사. 4. 함수의 메모리는 호출 순서에 따른 stack 구조. 5. jdk Class : Stack으로 사용하면 된다. 6. Stack 이 제공하는 method - push() : item을 stack의 top에 추가 - pop() : top에 있는 item을 꺼내온다. - peek() : top에 있는 item을 보여준다. - search() : 특정 item이 stack 어디에 ..

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까지..