[자료구조] 트리? + 이진 트리 (Binary Tree)

1. 트리 1.1 트리란? 트리(Tree)란 계층적인 구조를 나타내는 자료구조이다. 이전에 다룬 스택(Stack)과 큐(Queue)와 같은 선형 구조와 달리 트리는 비선형 구조이며, 나무를 거꾸로 그린 형태이다. 1.2 트리 용어 노드(node): 트리를 구성하는 기본 원소 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들 리프 노드(leaf (node))/단말 노드(terminal node): 자식이 없는 노드 간선(edge): 노드간의 연결 레벨..

→2021.01.03

IT/Data Structure

[자료구조] 순환 (Recursion) - 팩토리얼, 거듭제곱 계산, 피보나치 수열, 하노이의 탑, 영역 채색

1. 순환 1.1 순환이란? 순환(Recursion)은 컴퓨터 과학에서 재귀라고도 하며 자신을 정의할 때 자기 자신을 재참조하는 방법을 뜻한다. 순환은 알고리즘을 해결하는데 사용되는 일종의 프로그래밍 기법이며, 트리 자료구조를 공부하기에 앞서 간단하게 알아보자. 1.2 반복 vs 순환 프로그래밍 언어에서 같은 일을 반복하기 위한 방법에는 반복(iteration)과 순환(recursion)이 있다. 반복이란 for나 while 등의 반복문을 사용하여 조건이 만족할 때까지 계속하여 반복시키는 방식이다. 순환은 위에서 말한대로 method가 자기 자신을 다시 호출하는 방식을 의미한다. 일반적으로 순환은 method 호출을 하게 되므로 반복에 비해 수행 속도가 떨어진다. 하지만, 필요한 경우 순환을 사용하면 반..

→2021.01.02

IT/Data Structure

[자료구조] 리스트 (ArrayList vs LinkedList)

1. 리스트 1.1 리스트란? 리스트(List)란 앞에서 공부한 배열, 스택, 큐 등과 같은 선형 자료구조이다. 그렇다면 이들과 리스트의 차이점은 무엇일까? 스택과 큐의 경우 자료의 접근이 전단(front) 혹은 후단(rear)에 제한되어 있다. 하지만 리스트는 이러한 제한이 없다. 즉, 임의의 위치에 있는 항목에 접근이나 연산이 가능하다는 것이다. 1.2 배열 vs 리스트 배열(array) 또한 임의의 위치에 접근이 가능하다. 그렇다면 배열과 리스트의 차이는 무엇일까? 배열은 각각의 원소에 순서대로 index가 할당되어 있다. 위 배열에서 c 원소를 삭제하는 경우 아래와 같은 형태가 된다. 삭제한 c의 메모리 공간은 빈 공간으로 남아있으며, d와 e의 index는 변함이 없다. 만약 위의 행위가 리스트..

→2021.01.02

IT/Programming

[C++] 메모리 정적 할당 vs 동적 할당 (Stack vs Heap)

📃 이전 글 : [C++] 포인터 한방에 이해하기 (Call by Value vs Call by Reference) Memory 영역 (Stack vs Heap) 컴퓨터에서 메모리 영역은 아래와 같이 나뉘어있다. Code : 실행한 프로그램의 코드가 저장됨 Data : 전역변수와 static변수가 저장되며 프로그램 종료 시까지 사라지지 않고 남아있음 Heap : 동적으로 할당된 메모리영역이며 프로그래머에 의해 할당( C++ : new, C : malloc ) 및 해제( C++ : delete, C : free )됨 Stack : 지역변수와 매개변수가 할당되고 함수를 빠져나가면 자동 소멸됨 정적 메모리 할당 vs 동적 메모리 할당 프로그래밍 관점에서 메모리 영역에는 크게 stack과 heap 메모리 공간이..

→2021.01.01

IT/Programming

[C++] 포인터 한방에 이해하기 (Call by Value vs Call by Reference)

포인터 (Pointer) 포인터 변수 포인터란 "어떤 것을 가리키는 것"을 의미한다. C나 C++ 등의 프로그래밍 언어에서 포인터는 "주소를 가리키는 것"을 뜻하며, 이러한 것을 저장하는 변수를 포인터 변수라고 한다. 프로그래밍에서 포인터가 악명이 높기로 유명하지만, 의외로 단순하니 겁먹을 필요가 없다. 아래 코드를 보자. int a = 10; int* p = &a; a라는 int형 변수를 선언하고 10으로 초기화하였다. p라는 int형 포인터 변수를 선언하고 a의 주소값으로 초기화하였다. 여기서 한가지 짚고 넘어가야 할 것이 있다. & (주소 연산자) 주소 연산자 &를 사용하면 변수에 할당된 메모리 주소를 확인할 수 있다. 참고로 비트 연산자 AND(&)와 모양은 같지만, 주소 연산자는 단항 연산자이고..