본문 바로가기

프로그래밍/자료구조6

간단한 이진-tree 만들기(들어온 순서대로 만들기) 1. 목표 C++ 사용해 간단한 tree구조를 만들어보겠습니다. 입력한 순서대로 만들어지는 2진-tree를 만들것입니다. 예를들어 1, 2, 3, 4, 5, 6, 7, 8 이 들어온다면 다음과 같이 만드는 것이 목적입니다. queue를 이용한 bfs 방법으로 만들었습니다. 2. 만들기1) 우선 간단한 Tree와 요소를 담을 vector, 자료를 처리할 queue를 선언합니다.#include #include #include using namespace std; class tree {private: int num; tree* right; tree* left;public: tree() { right = NULL; left = NULL; num = 0; } ~tree() { delete(right); delet.. 2020. 9. 28.

C/C++] 트라이(Trie) 알고리즘을 만들어보자!! 문자열을 (m log n)의 형태로 빠르게 찾는 알고리즘입니다. 구성은 Tree 형태로 만들어지며 입력은 다음과 같이됩니다. "like, bike, bool, book"을 입력받는다고 가정한다면, 이런식으로 들어가게 됩니다. 여기서 root 노드에서 자식노드로 갈 수 있는 경우의 수는 26가지 입니다. 왜냐???!!! 영어 알파벳은 26개 이기 떄문입니다.(대문자 제외) 그래도 모르시겠다고요??!! 영어 알파벳은 a ~ z 까지 있습니다. 이것의 갯수는 26개 입니다. 그럼 영어 단어들의 첫번째 문자로 올 수 있는 경우의 수는 26가지가 되는 것입니다. 예를들어 apple, banana, like, etc..... apple은 a로 시작하고 banana는 b로, like는 l로 시작합니다. 즉, 시작단어.. 2019. 12. 22.

C++ 이진탐색 구현하기(재귀) 이진탐색이란? 정렬되어 있는 배열의 수를 효율으로 빠르게 찾는 방법입니다. 실생활에서 쓰일 수 있는 예로는...... 술게임의 업다운이 있습니다. 물론 해당 숫자를 찾을 때, 50, 25, 17.... 이런식으로 진행하면 안되지만..... 떠오르는 예제가 이것밖에 없내요..ㅎㅎ..... 시간 복잡도는 O(longN) 이며 4,294,967,296개(약 43억개)를 32번만에 찾아낼 수 있는 빠른 알고리즘 입니다. 기초적이지만 재귀함수를 사용해 찾는 방법이라 재귀를 처음 접하거나 익숙하지 않다면 구현이 다소 어렵고 이해하기도 어렵습니다. 이런 좋은 알고리즘이지만 한가지 제약조건이 필요한데, 그것은 숫자가 정렬되어 있어야 한다는 점입니다. 우선 코드를 보겠습니다. #include using namespace.. 2019. 12. 4.

Kadane's algorithm 이란? (설명) 코딩 문제를 풀다보면 이런 문제가 나옵니다. "배열 A의 요소들 중 연속된 합이 가장 큰 수를 구하시오" "배열 A의 요소들 중 연속된 합이 가장 큰 배열 요소의 범위를 구하시오" 배열 요소중 양수만 있을 경우 모두 다 더해주면 되지만 음수가 들어가면 머리가 복잡해 집니다. 직관적으로 풀어버리면 이중 for문을 사용해 각 범위마다 값을 구한 후 구한 값들 중 가장 큰 값을 구해야 합니다. 하지만 이는 O(n^2)이 되버리며 코딩 문제에서도 이러한 답은 원하지 않습니다. 그리고 이러한 문제는 흔히 볼 수 있으며, 코딩 테스트를 준비하고 있는 분들이라면 기본적으로 손쉽게 풀 수 있어야 한다고 생각합니다. 위 문제들은 O(n)으로 풀 수 있는데 Kadane's algorithm을 사용하면 됩니다. 위 식이 K.. 2019. 11. 19.

C++] 위상정렬 구현 및 설명 위상정렬은 각 노드들의 간선 개수를 구한 후 간선개수가 가장 적은 요소부터 순회하는 알고리즘입니다. 여기서 간선 개수란 각 노드마다 연결된 개수를 의미합니다. 간선 개수가 적은 요소들을 순회하기 때문에 한번에 원하는 지점까지 못가게 되는 특징이 있습니다. 위상정렬을 이용한 예제들은 주로 '게임 스킬트리, 우선순위에 대한 시간 문제 등...' 다양하게 사용되고 있습니다. 아래 그림을 통해 코드를 구현해 보겠습니다. 여기서 만약 A에서 E로 간다고 가정한다면 A는 B나 C를 거치고 D를 거처서 E로 가거나 혹은 D에서 F를 거처 E로 가게 됩니다. 즉, 노드 간선을 기점으로 모든 노드를 순서대로 거처가는걸 알 수 있습니다. 이 간선을 거처가는것이 하나의 조건이 될 수 있습니다. 아래는 구현 코드 입니다. #.. 2019. 9. 26.

C++] 인접 리스트 구현 인접리스트는 그래프의 한 종류입니다. 인접리스트를 쓰는 가장 큰 이유는 바로 탐색 때문인데, 우리는 인접리스트를 통해 연결된 모든 노드들을 확인할 수 있습니다. 우선 아래의 그림의 그래프를 만들어 보겠습니다. #include #include #include #include using namespace std; enum { A, B, C, D ,E}; void AddGraph(vector * v, int x, int y) { v[x].push_back(y); v[y].push_back(x); } int main(void) { vector g[5]; AddGraph(g, A, B); //A B 연결 AddGraph(g, A, D); //A D 연결 AddGraph(g, B, C); //B C 연결 AddGr.. 2019. 9. 23.

이전 1 다음

티스토리툴바

스킨편집 -> html 편집에서