본문 바로가기

장원익 기술블로그

💻 Computer Science/- Data Structure, Algorithm147

[자료 구조] - 트리 자료 구조 (4)-이진 탐색 트리 자바로 구현하기 :: Binary Search Tree implementation by java 이진 탐색 트리를 이해하기 위해서는 트리에 대한 기본 개념 및 용어 와 이진 트리의 종류와 기본에 대한 지식이 있어야 원활한 이해가 가능하니 아직 이해가 부족한 사람들은 꼭 한 번 가볍게 읽고 오는 것을 추천한다. 이진 탐색 트리 Binary Search Tree 이진 탐색 트리는 다음과 같은 조건을 만족하는 이진 트리를 Binary Search Tree라고 한다. 기본 전제 : 트리의 키에는 값이 반드시 존재하며 값들은 비교할 수 있는 집단이 존재하는 전순서 여야 한다. 조건 1 : 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값 보다 작아야 한다. 조건 2 : 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다. 조건 3 : 같은 키의 값을 갖는 노드는 .. 2020. 6. 18.

[자료 구조] - 트리 자료 구조 (3)-이진 트리와 종류(완전, 포화, 완벽, 균형) :: Binary Tree (Full, Complete, Perfect, Balanced) 이진 트리는 우리가 앞으로 마주하게될 트리(Red-Black Tree, AVL Tree, Segment Tree)들중 가장 쉽고 자주 쓰이는 트리이다. 이진 트리 Binary Tree 이진 트리는 노드가 왼쪽 자식과 오른쪽 자식을 갖는 트리이다. 이 때 중요한 점이 왼쪽 자식과 오른쪽 자식을 하나씩만 가져야 이진 트리가 된다. 이러한 이진 트리는 왼쪽 자식과 오른쪽 자식을 구분한다는 특징이 있는데, 우리가 트리의 개념과 용어 에서 배웠듯이 오른쪽 자식은 오른쪽 서브트리를 갖고 왼쪽은 왼쪽 서브트리를 가질 수 있다. 이제 이진 트리에 대해서 알았으니 그 종류에 대해 알아보자. 이진 트리의 종류 이진 트리의 종류는 크게 5가지가 있다. 한글로 번역하는 과정에서 여러 참고 서적들이 잘 못 번역하여 잘 못 알게.. 2020. 6. 18.

[자료 구조] - 트리 자료 구조(2)-트리의 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) :: Tree-Search (Breadth-First Search, Depth-First Search) 지난 시간에 우리는 트리에 대한 기본 개념과 용어에 대해서 알아보았으니 이제 트리를 파고들 준비가 되었다. 원래 BFS와 DFS는 그래프 자료구조쯤 가서야 구현도 할만하고 재밌지만 막상 가서 하려면 어려울 수 있으니 이번 시간에는 가볍게 읽어보고 이런게 있구나 하고 넘어가는 시간이 되었으면 좋겠다. 트리의 탐색 트리의 탐색에는 두 가지 방법이 있다. 너비 우선 탐색 깊이 우선 탐색 BFS::너비 우선 탐색 너비 우선 탐색은 가장 낮은 레벨에서 시작히서 왼쪽에서 오른쪽 방향을 검색하고 한 레벨에서 검색이 끝나면 다음 레벨로 내려가는 방식으 검색 구조이다. 너비 우선 탐색은 가까운 정점을 먼저 방문 하고 멀리 있는 정점을 나중에 방문한다는 점에서 특정 정점과의 관계가 중요한 탐색 방법이다. 예를 들어 전 세.. 2020. 6. 18.

[자료 구조] - 트리 자료 구조(1)-기본 트리 용어 및 개념 정리 :: Tree Data Structure. 트리 자료구조 트리 자료구조는 우리가 일상을 살면서 모르지만 자주 마주하고 사용하는 개념이다. 이를테면 우리 부모와 자식의 관계 또한 트리 구조이다. 트리 하면 가장 대표적으로 표현하는 것이 바로 컴퓨터의 File System이다. 파일을 찾기 위해서 우리는 디렉토리 안에 또 디렉토리를 파고 들어가서 파일을 찾곤 하는데, 이것이 바로 트리의 사용이다. 더 다양한 트리의 사용을 보고 트리를 유추해보자! File System HTML Tag 구조 도-시군구-읍면동-의 주소 체계 DBMS 라우터 통신 알고리즘 검색 엔진 위에서 나온 사용들이 갖는 가장 두드러지는 공통점이 있는데, 바로 계층 구조라는 것이다. 계층 구조 트리는 계층 구조의 대표적 자료구조이다. 계층 구조라고 함은 부모-자식 관계를 갖는 데이터의.. 2020. 6. 18.

[알고리즘-PS(재귀)] Java로 하노이 탑 알고리즘 재귀적으로 구현하기 :: Hanoi Tower Algorithm Java Code by recursion 하노이 탑은 정말 유명한 퍼즐이다. 하노이 탑에 대해서 자세히 알고싶다면 하노이탑 위키 에서 자세히 읽어보는 것도 재밌을 것 같다. 하노이 탑을 간단하게 설명하자면 세 개의 기둥과 이 기둥에 꽂을 수 있는 크기가 다양한 원판들이 있고, 퍼즐을 시작하기 전에는 한 기둥에 원판들이 작은 것이 위에 있도록 순서대로 쌓여 있다. 게임의 목적은 다음 두 가지 조건을 만족시키면서, 한 기둥에 꽂힌 원판들을 그 순서 그대로 다른 기둥으로 옮겨서 다시 쌓는 것이다. 조건 한 번에 하나의 원판만 옮길 수 있다. 큰 원판이 작은 원판 위에 있어서는 안 된다. -> 항상 작은 원반이 위에 있어야 한다. 하노이 탑의 원판을 모두 옮기려면 (2^n - 1)의 경우가 필요하다. 하지만 우리는 재귀 호출에 대해서 능하기 때문에 빠.. 2020. 6. 13.

[자료구조-PS] Java 에서 단순 연결 리스트 구현하기 :: (Simple Linked List sample code) 단순 연결 리스트 단순 연결 리스트는 가장 단순한 형태의 연결 리스트로 노드가 다음 노드를 가리키는 하나의 참조만 갖고 있으며, 단방향으로 참조할 수 있는 특징 덕분에 구현하기 간단하다. 연결 리스트와 노드 생성 연결 리스트를 만들었으니 삽입과 삭제 연산을 구현해보자. 삽입 연산 삽입 연산은 총 세 가지로 크게 구분할 수 있다. Head에 삽입하기. Tail에 삽입하기. 특정 위치에 삽입하기. 1. Head에 삽입하기 Head에 삽입하기 전에 다음과 같은 과정을 거친다. 새로운 노드 생성 새로운 노드의 다음 노드(link 필드)를 기존에 있던 head노드로 설정 헤드 노드와 새로운 노드의 교환. 테일 노드를 기존의 헤드노드로 설정. 2. Tail에 삽입하기 3. 특정 위치에 삽입하기 특정 위치에 노드를 .. 2020. 6. 12.

이전 1 ··· 17 18 19 20 21 22 23 ··· 25 다음

티스토리툴바