본문 바로가기

기초83

C++ 기초 : tree (4) Red - Black tree라는 자가 균형 기능이 들어간,이진 탐색 트리 기반의 자료 구조로는 'set'이 있습니다. 아래 코드가 set의 사용 예시인데요, 우선 include 지시문을 통해 set을 포함시킵니다. set이라는 클래스 템플릿 또한 std라는 namespace에구현이 되어 있기 때문에 바로 사용하기 위해 using std::set; 코드를 쓰겠습니다.  그리고 main 함수에서 int형 데이터를 관리하는 set을 생성해 줬습니다.   이후 insert 함수를 통해 100과 50, 75를 삽입해 줬습니다.  set의 구조는 아래 그림과 같을 겁니다. 처음 들어온 데이터인 100이 루트 노드가 되고이후 들어온 50은 100보다 작으므로 왼쪽,150은 100보다 크므로 오른쪽 자식 노드가 되죠.. 2024. 4. 26.
C++ 기초 : tree (3) 아래와 같은 이진 탐색 트리가 있습니다. 이때 150이라는 데이터를 넣으려고 합니다.  그럼 일단 루트 노드부터 비교를 하겠죠? 150은 100보다 크니까 오른쪽으로 갑니다.그곳에는 300이 있네요. 150은 300보다 작으므로 왼쪽에 자식 노드로 배치될 겁니다.  보면 처음 루트 노드를 비교할 때부터 자리를 잡을 때까지노드를 비교한 후, 한 쪽을 선택하기 때문에나머지 절반을 배제하고 있습니다. 이진 탐색 트리는 데이터를 탐색할 때뿐만 아니라,데이터를 입력하는 과정도 O( log N )이네요.  반면에 vector와 list는 비교할 것 없이 바로 데이터를 입력하죠. 빅오 표기법으로 나타내면O ( 1 )입니다. 대신 탐색할 때는 O( N )이죠. 이진 탐색 트리는 입력과 탐색 모두O ( logN )으로 .. 2024. 4. 26.
C++ 기초 : tree (2) 이진 트리도 종류가 있습니다. '완전 이진 트리'라는 것인데요.자식 노드를 반드시 2개씩 모두 채워 나가는 트리입니다.  완전 이진 트리는 배열로 구현을 합니다. 아래 그림을 통해 완전 이진 트리를어떻게 배열로 구현하는지 살펴 봅시다. 위와 같은 완전 이진 트리가 있습니다. 1번 노드는 해당 트리에서 루트 노드이며2번과 3번 노드를 자식 노드를 데리고 있습니다. 2번 노드는 4와 5번을 자식 노드로,3번 노드는 6과 7번을 자식 노드로 데리고 있습니다.  1번 노드를 배열의 0번 인덱스에 넣습니다. 이 상태에서 자식 노드인 2번 노드를 넣으려고 합니다. 첫 번째 자식 노드의 자리는 2k + 1입니다.여기서 k는 부모 노드가 있는 인덱스 번호이죠. 두 번째 자식 노드의 자리는 2k + 2입니다. 즉 1번 .. 2024. 4. 26.
C++ 기초 : tree (1) list는 노드를 관리합니다. 노드를 vertex(정점)라고 부르기도 합니다. 이러한 노드 간의 연결 관계를 표현할 수 있으면이것은 그래프입니다. 예를 들어 지하철 노선 같은 경우도그래프라고 볼 수 있죠.    아래 그림을 보시죠. 그래프의 연결 관계를 봤을 때처음 노드에서 한 바퀴를 돌아다시 처음 노드로 돌아올 수 있다면이를 순환(Circuit, Cycle) 가능하다고 표현합니다.  그러나 트리는 아래 그림처럼 이러한 순회가 불가능한 그래프입니다. 연결 관계를 보면 맨 아래 노드에서처음 노드로 갈 방법이 없죠?    그래프(Graph)와 트리(Tree)는 모두 자료 구조이며,트리는 그래프의 일종입니다. 포함 관계를 그림으로 표현하자면 위 그림과 같죠.  트리는 부모 노드와 자식 노드를 연결한 구조로가족.. 2024. 4. 26.
C++ 기초 : inline 함수를 선언하고 정의를 하기 위해Ctrl + . 을 통해 정의 부분을 만들면'inline'이라는 키워드가 붙습니다. 이게 무슨 의미일까요? 함수 A(){  ...  함수 B();  ...} 자, 위와 같은 함수가 있습니다. 함수 A를 호출하면 쭉 코드가 실행되다가함수 B 호출 구문을 만나 Stack 영역에 함수 B를 호출하고여기서 함수 B를 실행한 뒤 반환하고다시 함수 A로 돌아와 남은 코드를 실행하고 함수 A가 종료될 것입니다. 근데 만약 함수 B 앞에 inline 키워드를 붙이면함수 B를 호출했을 때 함수 B로 점프하여 실행하지 않고함수 A 코드에 함수 B 코드를 붙여넣고 함수 A를 실행하면서 그대로 실행합니다.즉 실제로 함수 B를 호출하는 구문이 없다고 봐도 되는 거죠.  이러한 경우 함수 B 호출.. 2024. 4. 26.
C++ 기초 : list iterator 직접 구현한 list 클래스에도iterator를 구현하겠습니다. 일단 list 역할은 하는 cList 클래스에inner 클래스인 iterator를 만듭니다. list에서 iterator가 갖고 있어야 하는 정보는어떤 list가 관리하는 노드인가,즉 list의 주솟값을 알아야 하고어떤 노드를 가리킬 것인가즉 node의 주솟값을 알아야 합니다. 해당 iterator가 사용할 수 있는지,사용할 수 없는지 확인할 수 있는멤버 bValid도 만들었습니다.  이후 iterator의 생성자와 소멸자를 만듭니다. 기본 생성자는 list를 가리키는 m_pList와 노드를 가리키는 m_pNode의 값을 이니셜라이저를 통해nullptr로 초기화합니다. 이렇게 만들어진 iterator는 사용할 수 없는 iterator이므로 .. 2024. 4. 25.

티스토리툴바