거누의 개발노트

파이만 알고리즘 1. 문제를 적는다. 2. 골똘히 생각한다. 3. 답을 적는다. 이 세상의 어떠한 어려운 문제도 해결할 수 있게 해 주는 우주 최강의 무적 알고리즘이라고 설명하고 있다. 일단 보면 너무 황당하다. 대부분의 사람들이 파인만같은 천재들만 사용할 수 있는 방법이라고 생각한다. 그런데, 사실 이 말은 같은 물리학자인 머리겔만? 이 말한 것으로 알려져있다. 결론부터 말하면 머리겔만이라는 사람이 파인만한태 열등감을 가지고 있어서 비꼬는식의 농담같은 거였다고 한다. 사실 이 이야기를 겔만이 했다는 뒷배경만 제외하고 나면 너무나 당연한 말이다. 모든 문제는 문제로서 인식하고, 깊이 생각하는 과정을 거쳐야 해결할 수 있다는 말이기 때문이다. 본론으로 들어가면 소프트웨어 소프트웨어를 설명할 때는 음식을 만..

Quicksort 분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘입니다. 배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눕니다(Divide). 그리고 그 사이에 기준을 위치시킵니다. 작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤(Conquer) 결과를 합치면 정렬된 배열을 얻을 수 있습니다. def quicksort(lst, start, end): def partition(part, ps, pe): pivot = part[pe] i = ps - 1 for j in range(ps, pe): if part[j]

정렬? 엑셀이나 문서작성 프로그램을 사용한 사람이라면 데이터를 오름차순 혹은 내림차순으로 정렬 해본적이 있을 것이다. 정렬이란 데이터의 집합을 어떠한 기준(핵심항목, key)으로 기준의 최소값이면 최대값까지 최대값이면 최소값까지 일정한 순서로 줄지어 세우는 것이다. [4, 6, 2, 9, 1] # 정렬되지 않은 배열 [1, 2, 4, 6, 9] # 오름차순으로 정렬된 배열! [9, 6, 4, 2, 1] # 내림차순으로 정렬된 배열! 버블정렬? 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 소스코드 def bubble(lst): for i in range(l..

문제 널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오. 배열에 자연수 x를 넣는다. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. 프로그램은 처음에 비어있는 배열에서 시작하게 된다. 입력 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다. 예제 입력 9 0 12345678 1 2 0 0 0 0 32 예..

문제 정수 배열 nums이 주어지면 배열에서 k번째로 가장 큰 요소를 반환 하는 프로그램을 작성하시오. 입력 Input: nums = [3,2,1,5,6,4], k = 2 출력 Output: 5 작성한 코드1 class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return heapq.nlargest(k,nums)[-1] https://leetcode.com/problems/kth-largest-element-in-an-array/ Kth Largest Element in an Array - LeetCode Level up your coding skills and quickly land a job. This is the be..

문제 m x n이진 행렬 mat이 제공 되는데, 1의 개수가 가장 적은 k 개의 인덱스를 반환하는 프로그램을 작성하시오. 입력 Input: mat = [[1,1,0,0,0], [1,1,1,1,0], [1,0,0,0,0], [1,1,0,0,0], [1,1,1,1,1]], k = 3 출력 Output: [2,0,3] 작성한 코드1 def kWeakestRows(mat: List[List[int]], k: int) -> List[int]: ans = [] s = collections.defaultdict(int) for i in range(len(mat)): # 1의 개수가 몇 개인지 c = collections.Counter(mat[i]) # 인덱스를 키로 1의 개수 만큼으로 하는 딕셔너리 s[i] = c[..

문제 정수 배열에서 (첫번째 최대값-1)*(두번째 최대값-1)을 해주는 프로그램을 작성. 입력 Input: nums = [3,4,5,2] 출력 Output: 12 # (5-1)*(4-1) 작성한 코드1 def maxProduct(nums: List[int]) -> int: n = sorted(nums, reverse=True) return (n[0]-1)*(n[1]-1) 작성한 코드2 def maxProduct2(nums: List[int]) -> int: h = heapq.nlargest(2, nums) return (h[0] - 1) * (h[1] - 1) list를 sort 할 때 는 시간 복잡도가 O(NlogN) 이고, heapq는 push, pop 할 때 O(logN) 이여서 힙이 빠르다는걸 알..

이진 탐색 트리란? 이진탐색과 연결리스트(linked list) 를 결합한 자료구조의 일종이다. 이진탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다. 부모 기준 왼쪽에는 작은 값, 오른쪽에는 큰 값을 가진다. 평균적으로 탐색의 시간복잡도는 O(logN), 치우친(skewed) 경우 O(n) 따라서 균형이 중요하다. 아래 그림에서 균형잡힌 경우와 치우친 경우를 확인할 수 있다. 이진 트리의 검색, 삽입, 삭제 검색 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다. 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다. 불일치하고 검색하고자 하는 ..