이누의 개발성장기

회의실배정 https://www.acmicpc.net/problem/1931 n = int(input()) meet_list = [] for _ in range(n): meet_list.append(list(map(int, input().split()))) meet_list.sort(key=lambda x: [x[1],x[0]]) result = 1 last_book_end_time = meet_list[0][1] for idx in range(1, len(meet_list)): if last_book_end_time

괄호의 점수 (,)의 두개의 문자로만 구성된 올바른 괄호문자열이 입력으로 주어진다. (짝이 안맞는 경우는 없음) “()” 은 1점 '('과 ')' 사이에 n점짜리 문자열이 있다면 (2*n)점으로 계산 둘 이상의 괄호가 나란히 있다면 두 괄호의 점수를 합침 ex. "(()(()()))" 는 10점 풀이 def getParenthesisScore(st): Fragments = [] # ')'과 '('이 만나는 지점을 기준으로 나눠 각각을 'Fragment'라 부름 # Fragments는 이들 Fragment들이 담기는 공간 # 예를 들어 ()()(())는 () / () / (())로 나누어져 Fragments에 저장된다. Fragment = "" # Fragment가 저장될 공간. () or (()) or ..

하노이의 탑 def hanoi(height) : result = [] def move(begin, end, height): if (height == 1): result.append((begin, end)) else: mid = (6 - begin - end) move(begin,mid,height-1) result.append((begin,end)) move(mid,end,height-1) move(1,3,height) return result def main(): print(hanoi(3)) 유명한 하노이의 탑 문제이다. 처음 프로그래밍을 접했을 때, 이 문제로 하루종일 끙끙댔엇는데 이번엔 3분정도 고민 후 해결했다. (새삼 뿌듯했다.) 최대한 단순하게 접근하는 것이 포인트였다. 10개의 링을 마지막으..

중복되지 않은 하나의 숫자 찾아내기 숫자들의 배열이 주어진다. 배열은 2n - 1의 크기를 가지며 1부터 n까지의 숫자로 이루어져 있다. 모든 숫자가 2번씩 나타나지만 하나의 숫자만 한번 나타난다. 해당 수를 찾아라. 풀이 def findSolo(nums): nums.sort() for i in range(0, len(nums), 2): if (nums[i] != nums[i + 1]): return nums[i] return 0 def main(): print(findSolo([1, 5, 3, 1, 2, 6, 4, 5, 2, 6, 3])) 배열을 정렬후 (NlogN) 반복문으로 2개씩 넘어가면서 체크한다. 다음 인덱스의 값과 다른 경우 해당 값을 리턴한다.

최대 수익 구하기 인덱스별로 주식의 가격이 적혀있는 리스트가 있다. 해당 리스트에서 주식을 사고 팔았을 때 얻을 수 있는 최대 수익은 얼마인지 구해라 풀이 def maximizeProfit(nums): max_profit = 0 min_price = nums[0] for now in nums: profit = now - min_price if profit > max_profit: max_profit = profit if min_price > now: min_price = now return max_profit def main(): print(maximizeProfit([1,2,3,4,5,6,7])) # 6 print(maximizeProfit([7,6,5,4,3,2,1])) # 0 print(maximi..

마지막으로 남는 카드 1~n순서로 쌓여있는 카드뭉치가 존재한다. (맨 앞이 1) 앞부터 제일 앞카드는 버리고, 그 다음카드는 제일 뒤로 옮긴다. 해당 과정을 반복한다. 제일 마지막에 남는 카드 1장의 숫자를 리턴해라. 풀이 from collections import deque def deque_process(n): my_deque = deque([i for i in range(1, n + 1)]) while(len(my_deque) != 1): my_deque.popleft() my_deque.rotate(-1) return my_deque[0] 가장 기본에 충실한 방법이다. 카드뭉치를 deque로 만들고, 이를 pop하고 rotate하기를 카드뭉치 사이즈가 1이 될 때까지 반복한다. 그리고 마지막에 남..

트리 경로의 합 루트 노드와 임의의 수 '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..