Language/JAVA (5) 썸네일형 리스트형 [JAVA] 이진트리에서 BFS 구현하기 BFS란? Bredath First Serach 한국말로 번역하면 너비 우선 탐색이다. 너비 우선 탐색은 저번 포스팅 했던 DFS와 마찬가지로 트리나 그래프를 방문 또는 탐색하는 방법이다. 탐색 방법은 다음과 같다. 1. 루트에서 시작하여 자식 노드들을 [1]에 저장한다. 2.[1]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [2]에 저장한다. 3.[2]에 저장된 노드들을 차례로 방문한다. 또한 각각의 자식들을 [3]에 저장한다. 4.위의 과정을 반복하여 모든 노드를 방문하면 탐색을 마친다. DFS와 BFS의 탐색 순서의 차이를 확연하게 알 수 있다. DFS와의 차이점 중 가장 큰 것은, 여러 갈래 중 경로의 길이가 무한하고 탐색 목표가 다른 경로에 존재하는 경우 DFS로 탐색할 시에는 무.. [JAVA] 이진트리에서 DFS 구현하기 이진트리란? 이진트리에서 DFS를 구현하는 포스트를 작성하기 앞서서 이진트리를 짚고 넘어가야 할 것 같다. 이진트리는 아주 중요한 트리구조이다. 이진트리는 모든 노드가 정확하게 두개의 서브트리를 가지고 있는 트리이다. 왼쪽서브트리와, 오른쪽 서브트리가 자식노드로 존재할 수 있다. 물론, 공백이 될 수도 있다. 자식 노드 좌측은 부모노드보다 작은값, 우측은 큰 값으로 구성한다. class Node{ int data; Node lt,rt; public Node(int val){ data = val; lt=rt=null; } } Node를 구현한 클래스이다. 데이터를 정수라고 두었다. lt,rt는 각각 좌측,우측 자식노드를 구현한 것으로, 생성시에 자동으로 null값이 들어가도록 하였다. DFS란? DFS란,.. [JAVA]Set 의 개념,종류 및 사용법 Set 이란? Set을 먼저 한글로 해석 하면, 집합이다. Set 인터페이스를 구현한 컬렉션 클래스는 여러가지가 있는데 공통된 특징이 있다. 1. 요소의 저장 순서를 유지하지 않는다. 2. 같은 요소의 중복 저장이 되지 않는다. 중요한 것은 그냥 순서가 아니고 저장 순서라는 점이다. 대표적인 Set 컬렉션 클래스는 HashSet,TreeSet이 있다. HashSet HashSet 클래스는 Set 컬렉션 클래스 중 가장 많이 쓰인다. 앞서 설명했던 HashMap과 마찬가지로, 이름에서 알 수 있다시피, 해싱기법을 사용하여 검색 속도가 아주 우수하다. HashSet 클래스는 내부적으로 HashMap 인스턴스를 이용하여 요소들을 저장한다. TreeSet TreeSet 클래스는 HashSet과 더불어 많이 쓰이.. [JAVA] HashMap의 개념 및 사용법 HashMap 이란? HashMap은 Map 인터페이스를 상속하고 있는 대표적인 컬렉션이다. 이름에 Hash가 들어가있는 것을 보면 알겠지만 Hashing 을 사용하고 있다. Map 인터페이스를 상속하고 있기 때문에 key와 value 로 구성된 Entry 객체를 저장한다. HashMap 특징 삽입되는 순서와 들어 있는 위치가 관계가 없다. 중복된 value값은 가질 수 있지만, 중복된 key 값은 가질 수 없다. Hashing을 사용하기 때문에 많은 양의 데이터를 검색하는데 있어서 성능이 뛰어나다. HashMap 선언 및 메소드 HashMap 선언 HashMap map = new HashMap(); //new에서 타입 파라미터를 생략한 HashMap 생성 HashMap map = new HashMap(.. [Java] StringBuilder 정리 String str1 = "ab"; str1 += "c"; 위 예제코드에서 str1에는 무슨 문자열이 들어 가있을까? 간단하다. str1과 "c"가 합쳐진 "abc"가 들어가 있을거다. 위처럼 간단한 방법을 이용하여서 문자열끼리 더하거나 빼서 새로운 문자열을 생성할 수 있다. 허나, 위 방법은 단점을 지니고 있다. String은 위같은 방법으로 연산을 진행하면 새로운 String 객체가 리턴될것이다. 다시금 말해, 메모리의 재할당이 이루어질 것이다. 이러한 문제는 위 예제처럼 크기가 작은 프로그램에서는 문제가 되지 않는다. 허나, 프로그램이 커질 수록 메모리의 낭비가 심해질 것이다. 위 문제를 해결하기 위해 JAVA에는 StringBuilder 클래스가 있다. StringBuilder 클래스는 새로운 객.. 이전 1 다음
