이누의 개발성장기

트리 경로의 합 루트 노드와 임의의 수 'targetSum'을 주어, 루트 노드부터 리프 노드까지 가는 경로의 합 중 targetSum과 일치하는 값이 있는지 확인한다. 하나라도 일치하면 True를 리턴하고, 일치하는 수가 없으면 False를 리턴한다. 풀이 class Node(): def __init__(self, val): self.val = val self.left = None self.right = None def path_sum(node, targetSum): def path_sum(now_node, now_sum): if (now_node.left == None) and (now_node.right == None): now_sum += now_node.val return [now_sum] el..

이진트리 깊이별로 나누기 이진트리의 root노드를 파라미터로 주었을 때 그를 기반으로 깊이별 요소들을 각각 리스트로 저장해 가지는 이차원 리스트를 리턴해라 import queue class Node(): def __init__(self, val): self.val = val self.left = None self.right = None def printTree(node): all_lines = [] line = [] q = queue.Queue() q.put(node) q.put(Node(-1)) while q.qsize() > 0: node = q.get() if not node: continue else: if node.val == -1: # 새 리스트 생성 if q.qsize() > 0: all_l..

스트리밍 데이터 평균값 구하기 정수 데이터가 한번에 하나씩 주어진다고 하자. 데이터는 최대 size개까지만 받을 수 있다. size를 초과해 값이 들어오면 오래된 값부터 삭제된다. size 범위로 MovingAvg 클래스를 초기화하고 nextVal함수로 새로운 값을 받고 현재까지의 평균을 리턴한다. 풀이 import queue class MovingAvg(): def __init__(self, size): self.size = size self.myQue = queue.Queue() self.sum = 0 def nextVal(self, num): self.myQue.put(num) self.sum += num if (self.myQue.qsize() == (self.size+1)): self.sum -..

배열의 회전 배열의 회전은 Rotation을 떠올리면 이해가 편하다. '한번의 회전'은 '한번의 Rotation'으로, [1,2,3,4,5]가 [2,3,4,5,1]이 된다. 배열과 회전 횟수를 파라미터로 활용해 배열을 회전하는 알고리즘을 짜보자. 풀이 def rotateArray(nums, k): partialReverse(nums, 0, len(nums) - 1) partialReverse(nums, 0, k - 1) partialReverse(nums, k, len(nums) - 1) return nums # 다음 함수는 추가적인 공간 사용 없이 배열의 일부를 뒤집어 주는 함수입니다. def partialReverse(nums, start, end): for i in ra..

0 이동시키기 0과 양수가 섞여있는 배열이 존재한다. 해당 배열의 0들을 전부 뒷쪽으로 옮겨 [양의정수들, 0들] 형태로 나타나야 한다. 풀이 def moveZerosToEnd(nums): currentPosition = 0 for i in range(len(nums)): if nums[i] != 0: temp = nums[currentPosition] nums[currentPosition] = nums[i] nums[i] = temp currentPosition += 1 return nums 단순히 생각해보면 리스트 2개를 만들고, 각각 양수와 0을 담아 마지막에 합칠 수 있다. 하지만 그런 방법은 공간복잡도 측면에서 비효율적이다. 따라서 해당 배열 자체를 수정하는 방법을 생각해보았다. 현재 i 인덱스..

주어진 숫자를 1로 만들기 위한 최소 횟수 구하기 int형의 숫자 num이 주어졌을 때 해당 num을 한정된 연산을 이용해 최대한 적은 연산 횟수로 1을 만들어야 한다. 가장 적은 케이스의 횟수를 구하라. 할 수 있는 연산은 3으로 나누기, 2로 나누기, 1 빼기 총 세가지이다. 풀이 def convertTo1(num): now = 1 tries = 0 check = [0 for _ in range(1,num + 1)] for i in range(0,num): tries = check[i] now_num = i + 1 plus_one_index = now_num + 1 - 1 mul_two_index = now_num * 2 - 1 mul_three_index = now_num * 3 - 1 if (pl..

배열에서 타겟과 일치하는 수 2개 찾기 int형 배열과 int형 타겟수이 주어진다. 배열에는 중복되는 수가 없다. 두 수를 합쳐서 타겟수이 되는 두 수가 반드시 배열에 존재한다. 풀이 def twoSum(nums, target): nums.sort() i = 0 j = len(nums) - 1 while i target: j -= 1 elif sum < target: i += 1 return a,b sort를 진행해 배열을 순서대로 만든다. (시간복잡도 O(N logN)) 그리고 양끝에 인덱스를 하나씩 두고 두 수의 합이 너무 크면 끝 인덱스를 줄이고, 두 수..

약수 효율적으로 구하기 1 이상의 자연수 n을 받았을 때 해당 수의 약수들을 구하라. 약수들은 리스트 형태로 숫자 크기 순서대로 출력하라. 단순 풀이 def get_divisor(n): n = int(n) divisors = [] for i in range(1, n + 1): if (n % i == 0): divisors.append(i) return divisors 가장 단순한 방법은 for문을 돌면서 하나씩 약수인지 체크(n % i == 0)하여 해당 값을 약수 리스트에 넣어주는 것이다. O(N)의 시간복잡도를 가진다. 효율화 풀이 def get_divisor(n): n = int(n) divisors = [] divisors_back = [] for i in range(1, int(n**(1/2))..

시청방해자 영화관에 사람이 일렬로 앉아있다고 가정하고, 앉은 키가 뒷 사람 모두보다 더 커서 뒷사람 모두에게 피해를 주는 사람의 수를 세자. 사람의 수 N을 입력받고, N명의 사람의 앉은 키를 입력받는다. 예를 들어, 10을 입력받고 56 46 55 76 65 53 52 53 55 50을 입력받으면, 뒷 사람 모두의 키보다 큰 인원은 3이므로 3을 출력한다. 풀이 (단순 접근) #include int main() { //freopen("input.txt", "rt", stdin); int n,i,j,tmp,res = 0, flag = 1; int h[101]; scanf("%d", &n); for(i=0; i

아나그램 두 문자열이 알파벳의 나열 순서를 다르지만 그 구성이 일치하면 두 단어는 아나그램이라고 한다. 예를 들어, AbaAeCe 와 baeeACA는 아나그램이다. 두 문자열을 받고, 두 문자열이 아나그램이면 'YES'를, 아나그램이 아니면 'NO'를 출력한다. 풀이1 #include int main() { freopen("input.txt", "rt", stdin); char a[101],b[101]; int i,j,flag=1; scanf("%s", &a); scanf("%s", &b); for (i = 0; a[i] != '\0'; i++) { for (j = 0; b[j] != '\0'; j++) { if (a[i] == b[j]) { b[j] = '0'; break; } } } for(i=0; ..