Computer Science59 그래프 탐색(2) - BFS(너비우선탐색) 알고리즘 너비 우선 탐색(Breadth First Search : DFS)은 그래프의 특정 노드에서 시작하여 전체 노드를 탐색하는 알고리즘이다. 탐색을 할 때 시작 정점에서 인접한 노드를 먼저 탐색하여, 가까운 정점을 먼저 방문하고 멀리 떨어진 정점을 나중에 방문하는 방식을 가진다. level을 높여가면서 각각의 정점을 탐색해나가는 알고리즘이다. 알고리즘 구현 방식에는 큐를 사용한다. 정점의 수가 n이고, 간선의 수가 e인 그래프의 경우 시간복잡도 - 인접 행렬로 표현된 경우, 시간복잡도는 O(n^2) - 인접 리스트로 표현된 경우, 시간복잡도는 O(n+e) ** 그래프의 크기가 작을 경우, BFS가 더 유리함 (알고리즘 구현) 재귀 함수 - 인접 행렬(이차원 배열)로 구현했을 때. 아래와 같은 그래프(트리)가 .. 2021. 1. 20. 그래프 탐색(1) - DFS(깊이 우선 탐색) 알고리즘 깊이 우선 탐색(Depth First Search : DFS)은 그래프의 특정 노드에서 시작하여 전체 노드를 탐색하는 알고리즘이다. 탐색을 할 때 시작 정점에서 한 방향으로 계속 가다가 더 이상 갈 수 없게 되면, 다시 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색을 진행하는 방식을 가진다. 알고리즘 구현 방식에는 재귀 함수로 코드를 작성하거나 스택을 사용하는 두 가지가 있다. 정점의 수가 n이고, 간선의 수가 e인 그래프의 경우 시간복잡도 - 인접 행렬로 표현된 경우, 시간복잡도는 O(n^2) - 인접 리스트로 표현된 경우, 시간복잡도는 O(n+e) (알고리즘 구현) 재귀 함수 - 인접 행렬(이차원 배열)로 구현했을 때. 아래와 같은 그래프(트리)가 존재할 때, 행렬에서 간선이 존재하는 부분은.. 2021. 1. 19. 자카드 유사도란? 자카드 유사도란? : Jaccard Similarity 혹은 자카드 지수라고 불리며, 두 문장을 각각 단어의 집합으로 만든 뒤 두 집합을 통해 유사도를 측정하는 방식 중 하나다. (정의) 교집합의 크기 / 합집합의 크기 - 0과 1 사이의 값을 가진다. - 만약 두 집합이 동일하다면 1의 값을 가진다. - 만약 두 집합의 교집합이 없다면 0의 값을 가진다. 자바로 만든 자카드 유사도 >> jihyeong-ji99hy99.tistory.com/148 2020. 12. 27. [JAVA] 제너릭과 List 제너릭 알고리즘 : 컬렉션에 적용할 수 있는 메서드이다. - static으로 선언된 함수 집합 - 요소 타입에 관계 없이 사용 가능 - 컬렉션 중에서 조건을 만족하는 경우에 사용 가능 리스트 알고리즘 : 리스트에 적용할 수 있는 메소드이다. - 리스트 상속 모든 클래스에 적용 가능 - sort(), shuffle(), reverse(), rotate(), swap(), replaceAll(), fill(), binarySearch() 메소드 등 위의 두가지를 동시에 적용할 수 있는 예시 ① Collections.sort 함수 : 리스트를 상속한 모든 컬렉션 객체를 사용 가능 - sorting한 결과를 정렬 - 전제 조건은 list의 요소 타입이 Comparable Interface를 상속해야 한다. (비.. 2020. 11. 20. [JAVA] 기본 클래스, Object 기본 클래스, Object 클래스 : 최상위 슈퍼 클래스이며 모든 메소드가 Object 메소드를 상속하고, Object의 일반 메소드를 오버라이드하여 사용할 수 있다. (메소드 종류) - protected Object clone() throws CloneNotSupportedException : 객체의 복사를 생성하여 리턴한다. - public boolean equals(Object obj) : 주어진 다른 Object obj가 동일 여부를 리턴해준다. - public final Class getClass() : 객체의 런타임 클래스를 돌려준다. - public int hashCode() : 객체의 해시 코드 값을 반환한다. - public toString() : 객체를 문자열로 반환한다. ① Clone.. 2020. 11. 20. [JAVA] 컬렉션이란? 제너릭을 이용하는 대표적인 사례 >> Collection Framework 컬렉션이란? : 여러 개의 요소를 묶어 하나의 단위로 만드는 객체이다. (=자료구조) - 인터페이스 : 추상 클래스 - 구현 : 구체클래스 - 알고리즘 : 함수의 집합 컬렉션 프레임워크가 필요한 이유 : 모든 SW는 데이터를 여러 개 모아서 관리하는 기능을 포함한다. (CRUD, Create/Read/Update/Delete) 리스트, 큐, 집합, 맵과 같은 형태로 제공할 수 있는데, 재사용 가능성이 크므로 라이브러리로 제공한다. -> 다양한 자료구조의 코드 간에 중복 제거(재사용의 최대화) // 우리가 여태 사용해 왔던 ArrayList 또한 컬렉션 프레임워크에 해당한다. 자바의 컬렉션 프레임워크 장점 1) 계층적 인터페이스 사.. 2020. 11. 3. 이전 1 ··· 5 6 7 8 9 10 다음
