이야기박스

Problem Given a number, find the next smallest palindrome larger than this number. For example, if the input number is “2 3 5 4 5”, the output should be “2 3 6 3 2”. And if the input number is “9 9 9”, the output should be “1 0 0 1”. The input is assumed to be an array. Every entry in array represents a digit in input number. Let the array be ‘num[]’ and size of array be ‘n’ Example There can be..

Problem Given a number n, print all primes smaller than or equal to n. It is also given that n is a small number. 정수 N이 주어집니다. 이 정수 N보다 작은 모든 소수를 찾으면 됩니다. Example Input : n =10 Output : 2 3 5 7 Input : n = 20 Output: 2 3 5 7 11 13 17 19 Approach 우선 소수에 대하여 다시 짚고 넘어가 보려 합니다. 소수란 자기 자신과 1 이외에는 다른 약수가 없는 수를 의미합니다. 그러면 우리는 어떤 수가 소수인지 아닌지 어떻게 알 수 있을까요? 모든 수에 대해서 한 번씩 나눠보면 될까요? 너무 비효율적인 방법입니다. 우리는 에라토..

Problem Given a string str representing a number having N digits, the task is to calculate the number of ways to make the given number divisible by 3 by changing at most one digit of the number. 특정 정수 N이 주어집니다. 그리고 우리는 이 정수 N에서 하나의 자릿수의 숫자를 변경할 수 있습니다. 이때 변경할 수 있는 숫자 중, 3으로 나누어질 수 있는 숫자는 몇 개인지 확인해보는 문제입니다. Example 예시는 다음과 같습니다. Input: str[] = “23” Output: 7 Explanation: Below are the numbers tha..

Problem Given a function random01Generator() that gives you randomly either 0 or 1, implement a function that utilizes this function and generate numbers between 0 and 6(both inclusive). All numbers should have same probabilities of occurrence. 먼저 0과 1을 생성하는 랜덤 함수가 주어집니다. 이제 우리는 위에 주어진 함수를 통하여 주어진 값 이하의 랜덤 숫자를 반환하는 함수를 만들어보면 됩니다. 주어진 문제에서는 6이라는 값이 Input으로 주어졌습니다. 하지만 우리는 6을 넘어서 INT_MAX 값까지 동작하는 ..

스플레이 트리트리의 노드가 탐색 또는 갱신을 위해 접근된 후, 스플레이되는 이진 탐색 트리를 말합니다. * 노드가 스플레이 된다 = 노드를 루트로 이동시킨다 - 사용되는 환경에 따라 재조정되는 방식==> 트렌드를 반영하는 이진트리라 할 수 있습니다. 스플레이 트리의 장점1. 구현이 단순합니다. ( AVL 트리 같은 경우는, 균형을 유지하기 위해 복잡했는데 스플레이 트리는 이것이 필요 없습니다. ) 2. 탐색, 삽입, 삭제에 O(log n)의 실행시간을 제공합니다. 3. 각 항목에 대한 접근빈도가 불균등한 사전에 사용하면 유리합니다.( locality의 개념을 생각하시면 되겠습니다. ) 스플레이 하는 시점1. 탐색 - 키가 발견되면, 그 노드를 스플레이- 발견되지 않으면, 실패한 외부노드의 부모노드를 스플..

AVL Tree이진 탐색 트리의 경우, 운이 나빠 편향트리가 형성이 되면 O(n)의 시간복잡도를 가지게 됩니다.그렇기에 좌우 높이차가 1이 넘지 않는 트리를 만드는데, 이것이 AVL 트리입니다. 주의할 점삽입, 삭제가 이루어지는 경우, AVL 트리의 균형속성이 파괴될 수 있습니다. 이런 경우, 불균형을 찾아서 해소해주어야 합니다. 때문에 두가지 필요한 매서드가 있습니다.1. 균형검사 (balance check)2. 개조 (restructure) 회전 : 회전 요령은 자동차 핸들을 생각하시면 됩니다.L - 반시계 방향으로 회전R - 시계 방향으로 회전 단일회전 이중회전 모든 회전 후 ** 개인적 견해 : LL, RR, LR, RL 이렇게 정의를 하는데, 개인적으로는 그냥 이해하고 하는 것이 더 쉽다.이 용..

얼핏보면 분할통치법을 쓸것 같지만 아닙니다!분할 통치법은 양쪽으로 나눈 후, 모두 다루고 다시 합치지만이진 탐색 트리는 양쪽으로 나눈 후 한쪽은 안씁니다!! ㅎㅎ합치지도 않구요 !! ㅎㅎ 이진 탐색 트리의 핵심key (left child) O(n)최선의 경우 - 좌우 대칭인 경우 --> O(log n) 코드는 코드 게시판에 올릴게요~

§ n log n 은 어떻게 나오는 것일까 정렬은 하는 과정은 완전 이진트리 형태의 결정트리(Decision Tree) 형태로 표현할 수 있습니다.--> 비교를 수행 후, 결과에 따라 좌우 부트리 중 한쪽 부트리로만 순회하는 형태 n개의 잎이 존재하는 포화이진트리의 높이는 최소 log (n+1) 인 것은 다들 아시겠죠그렇다면 n! 개의 잎이라면? log n! ==> 어떠한 비교 알고리즘도 최소 log(n!) 시간을 소요 한다는 것을 알 수 있습니다.이를 수학적으로 유도하면 log(n!) = log( n * (n-1) * (n-2) *....* 3 * 2 * 1 )>= log(n * (n-1) * .... * (n/2) )>= log( (n/2) * (n/2) * (n/2) *...* (n/2) ) = l..