개발 블로그

🐢 트리    - 계층적인 구조를 나타내는 자료구조    - 부모-자식 관계의 노드들로 이루어짐    - 정의: 1개 이상의 노드로 이루어진 유한 집합        - 하나의 루트 노드 존재        - acyclic graph ** 가계도는 트리가 아니다.** 동등한 위치에 있는 노드끼리는 간선이 존재하지 않는다. (트리는 acyclic graph) 🐢 트리의 용어    - 노드: 트리의 구성요소    - 루트: 부모가 없는 노드    - 서브트리: 하나의 노드와 자손들로 이루어짐    - 단말노드 (terminal, leaf): 자식이 없는 노드    - 비단말노드: 자식을 가지는 노드 ** 노드 하나만 존재 --> 트리인가요?? : YES** empty, 즉 트리에 아무 노드도 없는 경우도 ..

🐢 재귀함수 (recursion): 직접 또는 간접적으로 자기 자신을 호출하는 함수이다.    - recursive definition (재귀적 정의) 가능한 문제들을 recursion으로 풀 수 있다. 🐢 recursion vs. iteration    대부분의 재귀는 반복으로 바꿔서 작성할 수 있다.    - recursion        1. 성능이 좋지 않다.        2. 많은 내부 함수 호출로 인해 overhead (함수호출은 context switch overhead 발생)    - iteration        1. 수행속도가 빠르다. (성능이 좋다.)        2. 재귀적인 문제에서는 프로그램 작성이 아주 어려울 수 있다. 🐢 factorial programming (by r..

Concept | List🐢 Collection (여러 개의 원소들을 저장할 수 있는 자료구조): List, Set, MapList, 선형 리스트: 순서 (Order)를 가진 항목들의 모임Set (집합): 항목 간의 순서의 개념이 없음    1. 순서 없음    ex) (1,2,3)==(2,3,1)    2. 중복을 허락하지 않음    ex) (1,1,2,3,3)==(1,2,3)Map: key와 value가 대응되는 원소를 나타낸다.흔히 원소 표현은 인덱스로 한다.cf) 대표적인 class in JAVA    1. Hash table    2. Hash map ! 우리가 일상에서 말하는 '버킷리스트'라던지 '위시리스트'는 자료구조에서의 list가 아니다?--> 버킷리스트와 위시리스트 모두 순서가 중요하..

Concept | Linked list* 노드(Node): 의 쌍- 노드는 데이터 필드와 링크 필드로 구성된다.    - 데이터 필드: 리스트의 원소, 즉 데이터 값을 저장한다.    - 링크 필드: 다른 노드의 주소값을 저장하는 장소로, 포인터의 역할을 한다고 보면 된다.cf) 배열은 데이터 필드로만 구성된다.- 메모리 안에서의 노드의 물리적 순서가 리스트의 논리적 순서와 일치할 필요는 없다.cf) 배열은 서로 연속되는 공간에 데이터가 저장되기 때문에 일치한다. 🐢 linked list 장점    - 삽입과 삭제가 용이하다. (배열의 단점을 해결한 부분)    - 연속된 메모리 공간이 필요 없다.    - 크기의 제한이 없다. (Dynamic Memory Allocation)🐢 linked list..