한다 공부

이 문제는 sort STL을 이용해서 풀었다 알고리즘을 include하고 sort(시작, 끝, 정렬방식(선택)); 하면 된다. 정렬방식의 경우 기본 값은 오름차순이라 한다. #include #include #include using namespace std; //각 자리 숫자 합 함수 //아스키 코드 이용해서 문자열 중 숫자만 추출 int sum(string s) { int i, sum = 0; for (i = 0; i = 48 && s[i] > n; temp = n; while (temp != 0) { cin >> num; guitar.push_back(num); temp--; } sort(guitar.begin(),guitar.end(),cmp)..

문제 : 같은 알파벳이 나온다면 무조건 연속해야한다. 그러한 문자열의 갯수 출력 예시 : 11 happy new year aba abab abcabc a limi abbbbbba cbalsl bb 를 입력한다면 출력이 5가 되어야 한다. 왜냐하면 그룹단어는 happy new year a bb 이기 때문 다들 알파벳 배열 만들어서 하던데 나는 다른 방법을 이용해보고 싶어서 마음대로 풀다가 더 고생한 느낌이다,, 아이디어 : 주석참고 1. 문자열 총 갯수 = total 2. 그룹 단어가 아닌게 발견되면 total-- 3. i번째 문자열의 j번째 알파벳을 j++해나가며 같은 알파벳 있는지 체크 4. 연속하면서 같은 알파벳은 pass, 연속하지 않은데 같은 알파벳이면 total-- 하기 5. 한 문자열 체크 했..

우선순위 큐란, 우선순위의 개념을 큐에 도입한 자료구조이다. 선입선출 FIFO(First In First Out)인 큐와 달리 우선순위 큐는 우선순위가 높은 데이터가 먼저 나온다. 우선순위 큐는 배열, 연결리스트를 이용할 수도 있지만 히프라는 자료구조로 구현하려고 한다. Heap heap heap 히프는 우선순위 큐를 위해 만들어진 자료구조이다 배열로 구현한 히프는 삭제시 O(n)의 복잡도를 가지고 연결리스트 히프는 삭제시 O(n)의 복잡도를 가진다 하지만 히프의 경우 어느정도 정렬이 된 상태기 때문에 O(log n)의 복잡도를 가진다 데이터가 많아질수록 n과 log n의 경우 차이가 크기 때문에 히프를 사용하는 것이 효율성이 높다 히프는 부모 노드의 키 값이, 자식 노드의 키 값보다 항상 큰 이진트리이..

binary search tree 이진 탐색 트리 : 이진 트리 기반의 탐색을 위한 자료구조이다. 이진 탐색 트리의 정의는 다음과 같다. 모든 원소의 키는 유일한 키를 가진다. 왼쪽 서브 트리 키들은 루트 키보다 작다. 오른쪽 서브 트리의 키들은 루트의 키보다 크다. 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다. 쉽게 말하자면 루트를 기준으로 작은 수는 왼쪽 노드에, 큰 수는 오른쪽 노드에 붙이면 된다. 18 26 7 12 3 31 27 이 랜덤하게 주어졌다고 하자. 그럼 우선 첫 번째 주어진 18을 루트로 잡는다. 그리고 두 번째 주어진 26은 18보다 크므로 오른쪽 자식노드로, 세 번째 주어진 7은 18보다 작으므로 왼쪽 자식노드로 넘긴다 그리고 네 번째 주어진 12는 18보다 작으므로 왼쪽 자식노..

앞에서 본 이진트리는 순회하는 것 말고도 다양한 연산들이 있다. 이번 포스팅에서는 트리의 전체 노드 개수 세기 단말 노드의 개수 구하기 트리의 높이 구하기 를 알아보고자 한다. 앞에서 사용한 이 트리를 이용해보자 트리를 보면 알 수 있듯이 전체 노드는 7개이다. 단말 노드는 3개이다. (22 35 95) 트리의 높이는 4이다. #include #include typedef struct TreeNode { struct TreeNode* left; int data; struct TreeNode* right; }TreeNode; TreeNode n7 = { NULL,22,NULL }; TreeNode n6 = { NULL,95,NULL }; TreeNode n5 = { &n7,35,NULL }; TreeNod..

아까 이진트리를 구현할 때 10 / \ 20 30 위와 같은 트리를 어떻게 순회해야 잘 순회했다고 소문이 날까? 여기엔 크게 3가지 순회가 있다. 전위 순회란 루트를 방문하고 왼쪽 서브트리, 오른쪽 서브트리를 방문하는 순회이다. 위의 트리를 예시로 들면 10 -> 20 -> 30 순으로 순회하는 것이다. 아래 코드에서 preorder이라는 함수를 통해 구현을 할 것이다. 중위 순회란 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문하는 순회이다. 위 트리를 예시로 들면 20 -> 10 -> 30 순으로 순회한다. 아래 코드에서 inorder이라는 함수를 통해 구현을 할 것이다. 후위 순회란 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순으로 방문하는 순회이다. 위 트리에서 20 -> 30 ->..

앞에서의 스택, 큐, 연결리스트는 선형 자료구조였다. 선형 자료구조란 자료들이 선형으로 나열되어있는 구조이다. 트리는 자료가 계층적인 구조로 이루어져있다. 예를 들면 가족의 가계도, 컴퓨터의 디렉토리 구조 등이 있다. 그래프와 트리의 차이점은, 사이클이 존재하면 그래프이고 사이클이 없고 상하관계가 존재하면 트리이다. -트리의 용어 루트 : 가장 높은 곳에 존재하는 노드 서브트리 : 루트가 아닌 나머지 노드들 간선 : 노드들을 연결하는 연결선 = edge 관계 : 부모, 자식, 형제, 조상, 자손 관계가 존재 (개념은 인간 관계랑 같음!) 단말노드 : 자식이 없는 노드 비단말노드 : 단말노드의 반대 차수 : 한 노드가 가지고 있는 자식 노드의 개수 레벨 : 트리의 각 층에 번호를 매긴 것 (루트는 레벨 1..

연결리스트로 큐와 스택을 구현해보자 [스택] 간단히 말하자면 연결리스트의 맨 앞에 삽입하고 맨 뒤만 삭제하면 된다. insert_first, delete_first !! 단순연결리스트에서도 구현했었다~ #include #include typedef int element; typedef struct StackNode { element data; struct StackNode* link; }StackNode; //top은 정수가 아니고 노드를 가리키는 포인터이다 typedef struct { StackNode* top; }LinkedStackType; void init(LinkedStackType* s) { s->top = NULL; } //insert_first! void push(LinkedStackTy..

[원형연결리스트] 단순연결리스트에 한계가 있음을 깨달았다 ... 원형연결리스트를 이용해 삽입 삭제를 더 편리하게 해보자! 단순연결리스트에서는 마지막 노드가 NULL을 가리켰지만 원형연결리스트에서는 마지막 노드가 첫 번째 노드를 가리킨다. 원형연결리스트를 이용하면 맨 뒤에 노드를 삽입하는 것이 용이해진다! 헤드 포인터가 마지막 노드를 가키리도록 구성하자. 헤드 포인터를 첫 번째 노드를 가키리도록 하면 마지막 노드를 접근하기 위해 모든 노드들을 다 거쳐가야하고, 비효율적으로 동작하기 때문에 헤드 포인터가 마지막 노드를 가리켜야한다 ㅠ ㅠ print_list(list) insert_first(list, data) insert_last(list, data) 를 이용해서 원형연결리스트를 구현해보자 #include..

연결리스트를 복습해보자 연결된 리스트 형태의 자료구조를 연결리스트라고 한다 (단순) 연결리스트는 자기 참조 구조체를 쓸 것이며, lisert 함수를 생성해 연결리스트에 데이터를 추가할 것이며 delete함수를 생성해 연결리스트의 데이터를 삭제할 것이다. print_list함수를 따로 생성해 연결리스트에 있는 데이터를 순서대로 출력하기도 할 것이다. . . 외에 여러 연산이 있지만 추후 필요하면 기술하기로 하겠다 배열과 연결리스트의 장/단점 으로는 무엇이 있을까? 배열은 구현이 간단하고 노드를 찾는 검색 속도가 빠르다. 인덱스를 이용해 해당 위치로 바로 이동할 수 있기 때문이다. 하지만 동적으로 크기를 변경하는게 힘들다. +배열의 경우 중간 데이터를 삭제할 때, 해당 데이터 뒤에 있는 데이터를 앞으로 한칸..