welcome!

문제보러가기https://www.acmicpc.net/problem/1620 이진검색 AVL 트리를 이용하여 해결했다.정답소스보러가기https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/1620.cc

/*The source of this article is from1 Geeks For Geeks (https://www.geeksforgeeks.org/avl-tree-set-1-insertion/) 2 Wikipedia (https://en.wikipedia.org/wiki/AVL_tree)*/AVL tree의 생성과 삽입, 순회에 대해 이번 시간에는 AVL Tree에 대한 개론과 생성과 삽입, 순회에 대한 구현을 말하려고 한다. 개요AVL Tree는 BST의 일종이다. BST는 Binary Search Tree이며 원어 뜻 그대로 Search 하는데에 특화된 Tree이며, 거기에 더해 삽입, 삭제 등을 하는데에 효율적으로 설계 되어있다. naive 한 이진검색트리에 대해서 이전 포스트에서 이미 다루었..

/*This article is from 1 youtube ( https://www.youtube.com/watch?v=aZjYr87r1b8 )2 wikipedia3 geeks for geeks4 introduction to algorihtm5 bunch of website, blog6 Rosetta code*/ B+ trees B+ trees 는 balanced n - ary search Tree 의 일종이다. n - ary Tree는 말 그대로 한 노드가 자신의 자식노드를 최대 n 개 까지 가질 수 있는 트리이다. 이 때, Search Tree 이므로 각 노드들의 자식 - 부모 관계는 그 노드의 키에 의해 결정된다. Binary Search Tree 가 최대 2개의 자식을 가지는 Bin - ary 이..

문제보기https://www.acmicpc.net/problem/5639 이진 검색 트리를 전위 순회한 결과를 이용해 트리 모양을 유추하고 후위 순회를 출력하는 문제이다.전위 순회는 (루트 - 왼쪽 - 오른쪽) 이므로 입력값이 이전 입력값보다 작으면 반드시 왼쪽으로 다리를 뻗어 있는 것다. 만약 크다면 이전 입력 노드에 대한 successor 노드(해당 노드보다 큰 key를 가진 노드들 중 가장 작은 노드) 보다 큰지 작은지 판단하여, 만약 successor 보다 작다면 이전 입력 노드의 우측 child로 들어가면된다. 만약 successor 보다 크다면 successor의 우측 subtree 로 가거나 아니면 successor에 대한 successor의 우측 subtree로 가는지 반복적으로 체크해줘야..

/* The source of this article is from 1 Wikipedia (https://en.wikipedia.org/wiki/Binary_search_tree) 2 Geeks for Geeks (https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/) 3 Introduction to algorithm 3rd edition 4 Handbook of discrete and combinatorial mathematics. I just write down this post for my learning in CS. I don't have any authority for comercial uses with this..

백준 15991 1, 2, 3 더하기 - 6문제 보러가기 https://www.acmicpc.net/problem/15991 문제정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 합은 대칭을 이루어야 한다.1+1+1+11+2+12+2정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 경우의 수 문제이다. 이 문제를 푸는데 무려 2달 이나 걸렸다. 2달 전 처음 접했을 때 엄청 푸려고 노력했다. 한 4일 정도 노력을 했는데 안풀렸다. 특수한 스킬이 필요한 것이 아니라 이해력 문제였는데 못 풀었기 때문에, 그리고 또 이 문제 시리즈를 1, 2, 3, 4, 5, ... 순서대로 풀려..

Codeforces 1041D glider문제보러가기 이 문제는 비행기 내에서 주어지는 높이와 임의의 시작점에서 종이 비행기를 던지는데 해당 종이비행기가 비행할 수 있는 최대인 거리를 찾는 문제이다.비행기가 임의의 점을 비행할 때 종이비행기를 던지면, 항상 하강하며 앞으로 나아가는데 이 때, 특정 구간에서는 하강을 하지 않고 앞으로 갈 수 있다는 것이다. 특정 구간에는 상승기류가 있다고 하자.즉, 종이 비행기가 날라갈 수 있는 최대인 거리를 찾기위해서는 상승 기류 구간을 잘 고려한다음 x좌표 (1 ~ 1e9) 사이의 점을 골라 던져야 한다는 것이다. 나는 그렇게 똑똑한 사람이 아니기 때문에 먼저 브루트포스하게 찾아보려고 했다. 아마 브루트 포스하게 접근하다보면 솔루션이 보이겠지. 라고 생각했다. 이 문제..

최대유량 기초문제백준 6086 최대유량최대유량 기초문제이다. USACO Silver 문제이긴한데, 유량 알고리즘이 하나도 응용되지 않은 문제이다. 따라서 배열과 dfs 탐색만 있으면 가능하다. 소스보기 (dfs) : https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/6086.cc 소스보기 (bfs):https://github.com/ingyeoking13/algorithm/blob/master/bj/p1000/6086bfs.cc

백준 12784인하니카 공화국 문제는 흥미로운 문제였다. 인하니카는 섬으로 이루어진 나라인데, 각 섬은 다리들이 연결하고 있다. (그래프 ,,, ?)다리는 모든 섬을 연결할 수 있는 최소한의 개수로 사용되고 있다. (트리 .. !)다리가 한 개인 마을에 살인마가 존재하기 때문에 내가 사는 곳(1번 노드) 과 끊어야한다.이때 각 각의 다리를 끊는 비용은 주어질 때, 살인마가 존재 할 가능성이 있는 모든 마을에 대해 다리를 끊을 때 최소비용 을 구하라. 라는 문제이다. 이 문제는 난해할 수 있는데, 생각대로 깊이 우선탐색을 구현하면 쉽게 해결 할 수 있다.그러나 나는, 이 문제를 통해 좀 더 확장할 수 있는 재귀탐색 기법을 보여주고 싶었는데이 문제는 조금만 뉘앙스를 바꾸면, 트리에서 루트노드에서부터 모든 리..

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV_6pTXqsXUDFAWS 홍준이의 사전놀이 난이도 : D5 (하지만 기본적인 Trie data structure implemetation이었다) 트라이 자료구조를 통해 수행했다. 만약 트라이가 뭔지 모른다면 제가 정리한 포스팅이 있습니다 클릭 클릭 온라인 커뮤니티에서 들었는데, 가장 현명했던 방법은 단어를 insert 하면서 각 노드를 cnt++ 해주는것이 나중에 임의의 문자열 S에 해당하는 단어가 몇개있는지 체크해주는 것이였다. 나는 재귀를 통해 word 를 체크하였고, 그 방법은 최악의 경우의 연산수는 26^10 ( S