기타

양방향 연결 리스트란? 데이터를 가지고 있는 노드가 이전 노드와 다음 노드의 주소를 가지고 있는 리스트이다. 양방향 연결리스트의 특징 단방향 연결리스트는 이전 노드로 돌아가려면 저장을 해둬야했던 반면에, 양방향은 자유롭게 노드 이동이 가능하다. 그 대신에 이전 노드를 저장하는 변수가 하나 더 추가된다. 상황에 따라 사용하면 된다. 탐색이 빠르다고 하는 게시글도 몇몇 있는데, 정렬된 리스트가 아니면 의미 없기에 특징으로 적지 않겠다. 양방향 연결리스트 구현 (그림 설명) 2021/01/15 - [프로그래밍/자료구조 & 알고리즘] - 연결 리스트 (Linked List) 연결 리스트 (Linked List) 연결 리스트(Linked List)란? 데이터를 가지고 있는 노드가 다음 노드의 주소를 가지고 있는 ..

연결 리스트(Linked List)란? 데이터를 가지고 있는 노드가 다음 노드의 주소를 가지고 있는 리스트이다. 연결 리스트의 특징 메모리만 여유있다면, 크기 제한이 없다. 자료의 추가, 삭제가 O(1)에 가능하다. 자료의 탐색이 O(n)으로 느리다. But, 자료를 (추가, 삭제)하기 전에도 탐색을 한번 거쳐야 하기 때문에, (추가, 삭제)가 빠른 것을 장점이라고 말하기 어렵다. 연결 리스트 구현 (그림 설명) 자료를 쉽게 다루기 위해, Node 클래스 하나를 더미로 만들어 리스트의 시작 노드로 설정한다. 1. 데이터 추가 (맨 뒤에 삽입할 때) 받은 데이터로 노드를 하나 생성하고, 노드를 연결해준다. (리스트의 중앙에 삽입할 때) 마찬가지로 노드를 하나 생성하고, 위치를 찾아서 연결해준다. 순서 주의..

퀵 정렬(Quick Sort)란? 한 데이터를 골라 Pivot으로 설정하고, Pivot보다 작은 값은 왼쪽으로 넘기고 큰 값은 오른쪽으로 넘기면서 정렬하는 방식이다. 퀵 정렬의 특징 시간복잡도 최악 O(n^2), 평균 O(n log n) 분할정복 알고리즘이다. 평균적으로 매우 빠른 속도로 수행된다. 퀵 정렬 원리 1. 전체 배열을 대상으로 함수를 호출한다. 2. 가장 오른쪽 값을 Pivot으로 잡는다. (Pivot을 랜덤으로 잡으면 랜덤 퀵소트다.) 3. Pivot보다 작은 값들을 다 왼쪽으로 넘긴다. 3. Pivot이 들어갈 위치에 있는 값과 가장 오른쪽 값을 swap한다. 4. Pivot을 제외하고, 왼쪽과 오른쪽 배열을 계속 재귀함수 부른다. 퀵 소트 구현 (C++) #include #include..

합병 정렬(Merge Sort)란? 데이터들을 최소 단위로 쪼개고, 합치면서 정렬하는 방식이다. 합병 정렬의 특징 시간복잡도 O(nlog₂n) 분할정복 알고리즘이다. 배열을 분리한 뒤, 합칠 때 새로운 배열이 필요하다. 합병 정렬 원리 원래의 배열을 하나의 데이터를 가지는 배열로 쪼갠 뒤, 합치면서 정렬한다. 아래 그림은 합치면서 정렬하는 과정이다. 1. 정렬할 데이터를 담을 배열을 만든다. (변수명은 mergeArr로 했음) 1. 왼쪽 배열과 오른쪽 배열을 비교하면서 mergeArr에 추가한다. 2. 하나의 배열이 끝이나면, 다른 배열에 남은 값들을 mergeArr에 추가한다. 3. 정렬된 배열(mergeArr)을 원래의 배열에 복사한다. 합병 정렬 구현 (C++) #include #include vo..

버블 정렬(Bubble Sort)란? 인접한 2개의 데이터를 비교하며 정렬하는 방식이다. 데이터를 비교하는 방식이 버블과 비슷하다고 해서 지어진 이름이라고 한다. 버블 정렬의 특징 시간복잡도 O(n^2) 구현이 간단해서 테스트용으로 정렬할 때 주로 사용한다. 버블 정렬 원리 임의의 숫자 배열을 만들고, 오름차순으로 정렬하는 과정을 PPT로 만들어보았다. 위 과정을 한번 반복하게 되면, 맨 끝에 확정된 숫자가 생긴다. 그 다음은 확정된 숫자를 제외한 나머지 숫자들로 위 과정을 반복한다. 위 그림에 나타나 있는 과정을 반복해서 인덱스로 나타내보면, (0,1) (1,2) (2,3) (3,4) (4,5) (5,6) (6,7) (7,8)> 8번 인덱스 값 확정 (0,1) (1,2) (2,3) (3,4) (4,5)..

조립 구현 2가지 다른 클래스의 기능을 사용하고 싶을 때, 2가지 방법이 있다. 상속 관계, 포함 관계가 있는데 각각의 사용법과 차이점을 정리해보았다. 1. 상속 관계로 구현 구체화를 시킬 때, 구체화된 클래스도 같이 추가된다. class C_CHILD : public C_PARENT { }; 예시) 기존에 (A 몬스터)가 있다. (B 몬스터), (C 몬스터)가 기획적으로 추가된다. -> (몬스터를 상속받는 B 클래스), (몬스터를 상속받는 C 클래스)를 추가해야 한다. // 기존 class AAA : public C_MONSTER // 몬스터 클래스에는 기본적인 정보들이 들어있다고 가정. { }; // 추가된다면... class BBB : public C_MONSTER // BBB 클래스 생성 { };..

복사 생성자 클래스의 call by value를 지원하기 위해 기본으로 제공되는 생성자이다. class C_TEST { public: C_TEST(); // 기본 생성자 C_TEST(const C_TEST &other); // 복사 생성자 }; 복사생성자가 불리는 타이밍은 1. 대입 연산을 할 때 (직접 복사를 할 때) 2. 매개 변수로 사용될 때 (call by value) 3. 리턴 타입일 때 (call by value) 3개로 외우지 말고, 대입 연산 또는 call by value일 때 2개로 생각하면 편하다. 흔히 하는 복사 생성자 실수 1. 매개 변수의 자료형을 클래스(or 구조체) 자료형으로 받는 실수. 클래스나 구조체들은 변수에 비해 메모리의 크기가 크기 때문에, 복사 생성자로 넘기면 끔찍한..

메모리 관리하는 법 3가지 1. 메모리 풀 한번에 많이 잡아놓고, 필요한만큼 쓰다가 한번에 삭제하는 방식. 2. 매니저 매니저가 메모리를 잡아주고, 빌려가는 형식으로 만드는 방식. 이 방식이 젤 많이 쓰이는 것 같다. 3. 스마트포인터 알아서 해주는 방식. 일반 포인터보다 조금 느리기 때문에, 연산 속도가 필요하다면 일반 포인터를 쓰는 게 낫다. c++ 장점은 메모리 관리니까 일반 포인터를 쓰는 게 좋을 듯 하다. 메모리 누수잡기 https://docs.microsoft.com/ko-kr/visualstudio/debugger/finding-memory-leaks-using-the-crt-library?view=vs-2019 CRT 라이브러리로 메모리 누수 찾기 - Visual Studio C/C++ 디..