힙

오늘은 C++의 개체지향 프로그래밍 부분을 공부하고 정리한 내용을 포스팅 해 보려고 한다. 양이 많아서 두 번의 포스팅에 나누어서 적어보려고 한다. 개체지향 프로그래밍 개념은 C++에만 있는 건 아니다. Java에도 있고 다른 많은 언어에도 있다. Java로 예를 들면, 다음과 같은 개념들은 자바와 C++ 모두 있는 것들이다. 클래스 개체 생성자 함수 오버로딩 힙에 개체 생성하기 등 하지만 자바에는 없고 C++에만 있는 개념들도 있다. 예를 들면 스택에 개체 생성하기 복사 생성자 소멸자 연산자 오버로딩 등 C++은 OOP와 OOP가 아닌 것들을 섞어서 쓸 수 있다는 장점도 가지고 있다. 자바는 OOP에 관해서 엄격한 편이지만, C++은 C의 후방호환성을 가지고 있어서 유연하다는 장점이 있다. OOP의 핵..

오늘 살펴볼 문제는 백준 1655번 문제이다. https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다. www.acmicpc.net 나는 처음에 이 문제를 정말 단순하게 직관적으로 접근했었다. N개의 입력값을 받아서 하나씩 ArrayList에 받고 그 때마다 정렬을 한 뒤 i/2 번째 원소를 찾아서 출력하면 되지 않나? 라고 접근해서 풀었고 시간초과가 나왔다. 이는 당연한게 시간 복잡도가 O(N*N*logN)..

오늘은 트리와 힙 자료구조에 대해서 알아보려고 한다. 트리 트리(Tree)는 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료구조이다. 계층적(Hierarchical) 자료구조라고 표현하기도 한다. 유닉스/윈도우의 디렉터리(폴더) 구조가 대표적인 트리 구조의 예시이다. 트리와 관련된 용어들은 다음과 같다. 노드(Node) : 트리를 구성하는 기본 원소 간선(Edge) : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미 루트 노드(Root Node) : 트리 구조에서 최상위에 있는 노드 부모 노드(Parent Node) : 루트 노드 방향으로 직접 연결된 노드 자식 노드(Child Node) : 루트 노드 반대방향으로 직접 연결된 노드 형제 노드(Siblings Node) : 같은 부모 노드를 갖는..