바위타는 두루미

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

도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다. 각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 제한사항 이 마을에 있는 집은 3개 이상 1,000,000개 이하입니다. money 배열의 각 원소는 0 이상 1,000 이하인 정수입니다. 입출력 예 money return [1, 2, 3, 1] 4 def getMax(money): isget = False first = 0 second = 0 cur_num = 0 for m in money:..

두 개의 단어 begin, target과 단어의 집합 words가 있습니다. 아래와 같은 규칙을 이용하여 begin에서 target으로 변환하는 가장 짧은 변환 과정을 찾으려고 합니다. 1. 한 번에 한 개의 알파벳만 바꿀 수 있습니다. 2. words에 있는 단어로만 변환할 수 있습니다. 예를 들어 begin이 hit, target가 cog, words가 [hot,dot,dog,lot,log,cog]라면 hit -> hot -> dot -> dog -> cog와 같이 4단계를 거쳐 변환할 수 있습니다. 두 개의 단어 begin, target과 단어의 집합 words가 매개변수로 주어질 때, 최소 몇 단계의 과정을 거쳐 begin을 target으로 변환할 수 있는지 return 하도록 solution 함..

문제 각 노드의 값이 정수(음수 및 양수) 인 이진 트리가 있다. 이때 정수의 합이 특정 값이 되도록 하는 경로의 개수를 세려고한다. 경로가 꼭 루트에서 시작해서 말단 노드에서 끝날 필요는 없지만 반드시 아래로 내려가야한다. 즉, 부모노드에서 자식노드로만 움직일 수 있다. 알고리즘을 어떻게 설계할 것인가. 접근법 해법 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가 어떤 노드로부터 둘다 오른쪽에 있다면 오른쪽으로 내려가서 공통 조상의 여부를 찾아야 한다. 더이상 같은 쪽에 있지..

A message containing letters from A-Z is being encoded to numbers using the following mapping:'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given a non-empty string containing only digits, determine the total number of ways to decode it. Example 1: Input: "12" Output: 2 Explanation: It could be decoded as "AB" (1 2) or "L" (12). Example 2: Input: "226" Output: 3 Explanation: It could be decoded as "BZ" (2 26)..

문제 프로젝트의 리스트와 프로젝트들 간의 종속관계 ( 즉, 프로젝트 쌍이 리스트로 주어지면 각 프로젝트 쌍에서 두번째 프로젝트가 첫 번째 프로젝트에 종속되어 있다는 뜻 ) 가 주어졌을때, 프로젝트를 수행해 나가는 순서를 찾으라. 유효한 순서가 존재하지 않으면 에러를 반환한다. 접근법 위상정렬을 이용해서 해결할 수 있다. 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..