바위타는 두루미

문제 두 개의 32비트 수 N과 M이 주어지고, 비트 위치 i와 j가 주어졌을 때, M을 N에 삽입하는 메서들을 구현하라. M은 N의 j번째 비트에서 시작하여 i번째 비트에서 끝난다. j번째 비트에서 i번째 비트까지에는 M을 담기에 충분한 공간이 있다고 가정한다. 다시말해 M = 10011라면, j와 i사이에 적어도 다섯 비트가 있다고 가정해도 된다는 것이다. j = 3이고 i = 2인 경우처럼 M을 삽입할 수 없는 상황은 발생하지 않는다. 접근법 3가지 단계를 거쳐서 문제를 해결할 수 있을 것이다. 1. N의 i에서 j까지의 비트를 0으로 만든다. 2. M을 쉬프트해서 j부터 i번 비트자리에 오도록 만든다. 3. M 과 N을 합한다. def updateBits(int n , int m , int j ,..

- 몇가지 비트 트릭 1. 0110+ 0110 은 0110을 왼쪽으로 한번 쉬프트 한 것과 같다. - 0110 *2 와 같기 때문에 2. 0100 * 0011은 0011을 왼쪽으로 두번 쉬프트 한 것과 같다. - 0100은 4이기 때문에 0011*4와 동일 3. 1101 ^ (~1101) 은 모든 비트가 1이 된다. - XOR연산은 두 비트가 다를때 1을 가지는데 NOT연산으로 모든 비트를 반전 시켰으므로 각 비트들은 서로 다르다. 4. 1011 & (~0

문제 각 노드의 값이 정수(음수 및 양수) 인 이진 트리가 있다. 이때 정수의 합이 특정 값이 되도록 하는 경로의 개수를 세려고한다. 경로가 꼭 루트에서 시작해서 말단 노드에서 끝날 필요는 없지만 반드시 아래로 내려가야한다. 즉, 부모노드에서 자식노드로만 움직일 수 있다. 알고리즘을 어떻게 설계할 것인가. 접근법 해법 1 : 가능한 모든 경로를 다 살펴보면서 각 노드에서 재귀적으로 아래로 내려가면서 경로의 합을 구해나간다. 하지만 TimeComplexity = O(NlogN)번 호출된다. 해법2 : Running Sum을 이용한다 ! 각 위치에서 러닝합을 알고있다면 runningSum(x) = runningSum (y) - targetNumber 일 것이다. 우리는 경로의 갯수만 알면 되므로 runnin..

문제 이진 트리 클래스를 바닥부터 구현하려고 한다. 노드의 삽입, 검색, 삭제 뿐만 아니라 임의의 노드를 반환하는 getRandomNode() 매서드도 구현한다. 모든 노드를 같은 확률로 선택해주는 getRandomNode메서드를 설계하고 구현하라. 또한 나머지 메서드는 어떻게 구현할지 설명하라. 접근방법 우선 문제를 보면 "이진트리에서 임의의 노드를 반환하는 알고리즘을 설계해라"와 동시에 "클래스를 바닥부터 구현하려고한다."라는 문구가 있다. 그 말은 아마도 문제 해결을 위해서는 자료구조의 내부를 접근해야한다는 것을 의미 할 것 같다. 이 문제의 해결법은 매우 다양하다. 느린해결법부터 빠르지만 해결되지 않는 해결법 최적의 해결법까지 차례로 생각해보자. 1. [느리지만 동작하는] 모든 노드를 배열에 복사..

문제 두 개의 커다란 이진 트리 T1과 T2가 있다고 하자. T1이 T2보다 훨씬 크다고 했을때, T2가 T1의 하위 트리인지 판별하는 알고리즘을 작성하라. T1안에 있는 노드 n의 하위트리가 T2와 동일하다면 T2는 T1의 하위 트리다. 다시말해, T1에서 노트n의 아래쪽을 끊어냈을때 그 결과가 T2와 동일해야한다. 접근법 1. 순회를 통해 노드 안의 데이터들로 문자열을 만들고, T2의 문자열은 T1의 문자열의 부분 문자열이 된다. - 어떤 순회를 해야할까에 대한 문제가 있다. 중위 순회를 한다고 했을때에는 이진탐색트리를 중위 순회 한다고 했을때 정렬된 값이 나온다고 했다. 그 말은 값은 같지만 구조가 다른 이진탐색트리에서는 같은 값이 나올 것이다. 전위 순회를 한다고 해보자. 전위 순회를 한다고 해도..

문제 배열의 원소를 왼쪽에서부터 차례로 트리에 삽입함으로써 이진탐색트리를 생성할 수 있다. 이진 탐색 트리안에서 원소가 중복되지 않는다고 할때 해당 트리를 만들어 낼 수 있는 가능한 배열을 모두 출력하여라 예제 입력 : 출력 : { 2, 1, 3 } {2, 3, 1} 접근법 배열의 원소를 왼쪽부터 차례로 트리에 삽입함으로써 주어진 이진 탐색 트리를 만들기 위해서는 1. 리스트의 첫번째 노드는 무조건 root 노드여야 한다! 2. 왼쪽 부분트리의 노드가 먼저나오든, 오른쪽 부분 트리의 노드가 먼저 나오는 것은 중요하지 않다. ( 어쩌피 2 다음에는 순서에 상관없이 3은 오른쪽으로 1은 왼쪽으로 생성될 것이기 때문에 ) 3. 그렇기 때문에 현재 노드의 왼쪽 부분트리와 오른쪽 부분트리에서 만들어질 수 있는 가..

문제 이진트리에서 노드 두 개가 주어졌을때 이 두 노드의 첫 번째 공통조상을 찾는 알고리즘을 설계하고 그 코드를 작성하라. 자료구조내에 추가로 노드를 저장해 두면 안된다. 반드시 이진탐색트리일 필요는 없다. 해법 1. 부모노드에 대한 링크가 있는 경우 - p와 q에서 시작해서 둘이 만날 때까지 위로 올라가면 된다. (교집합문제와 비슷한 방식) - p의 경로를 따라 올라가면서 q를 덮을 수 있는 노드인지 확인한다. p의 부모의 본인이 아닌 다른쪽의 하위노드들을 검사하여 q가 있다면 그것이 첫번째 조상, 아니라면 그 위의 부모를 탐색하는 방식 2. 부모노드에 대한 링크가 없는 경우 - p와 q가 어떤 노드로부터 둘다 오른쪽에 있다면 오른쪽으로 내려가서 공통 조상의 여부를 찾아야 한다. 더이상 같은 쪽에 있지..

문제 프로젝트의 리스트와 프로젝트들 간의 종속관계 ( 즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻 ) 가 주어졌을때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다. 접근법 위상정렬을 이용해서 해결할 수 있다. 1. 유입간선 수를 확인하며 순서를 정한다. def Solution(projects): indegree = {} adj_list = {} for p in projects : indegree[p[1]] = indegree.get(p[1],0)+1 if indegree.get(p[0],-1) == -1 : indegree[p[0]] = 0 cur_adj_list = adj_list.get(p..

문제 이진 탐색 트리에서 주어진 노드의 '다음' 노드( 중위 후속자 ) 를 찾는 알고리즘을 작성하라. 각 노드에는 부모 노드를 가리키는 링크가 존재한다고 가정하자. 해결법 이진 트리에서 중위 후속자를 찾는방법 1. 오른쪽 노드가 있다면 오른쪽 노드의 가장 왼쪽 노드 2. 오른족 노드가 없다면 현재 노드가 왼쪽 노드일때까지 부모를 타고 올라가기 def get_left(node): while node.left is not None : node = node.left return node def Solution(node): if node is None : return None if node.right is not None : return get_left(node.right) else : cur = node p ..

문제 주어진 이진트리가 이진 탐색 트리인지 확인하는 함수를 작성하라. 접근법 1. 중위순회를 이용하여 배열의 원소를 저장해두고 이것이 정렬된 결과인지 확인한다. -> 중복된 값이 있을때 재대로 동작하지 않을 수 있다. 사실, 배열에 저장한다고 해도 바로 전의 원소와 그다음 원소만 사용하기 때문에 굳이 배열이 필요없음을 알 수 있다. 2. 마지막으로 검사했던 원소만 저장해두고 순회하며 그 다음 원소와 비교한다. last = float("Inf") def chkBST(root): if root is None: return True if not chkBST(root.left) : return False if last != float("Int") and last >= root.data : return False..