포시코딩

퀵 정렬(Quick Sort) 정렬 알고리즘의 꽃 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 함수를 작성 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해 다시 동일 함수를 호출하여 위 작업을 반복 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right)을 리턴한다. 배우기 앞서 기대한 알고리즘 중 하나 파이썬에서 구현 시 아름다울 정도라는데 얼마나 감동할 수 있을지 기대를 잔뜩 하고 들어갔던 것 같다. 크게는 아래 순서를 따라간다. pivot은 보통 제일 앞에걸로 지정 pivot을 기준으로 분류 분리된 left, right를 재귀 함수를 통해 1~2 반복 그렇게 데이터 수가 1개가 될 때 까지 반복한다. 구현 def qsort(l..

동적 계획법(Dynamic Programming, DP) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결 최종적으로 전체 문제를 해결하는 알고리즘 상향식 접근법으로, 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식 Memoization 기법 사용 Memoization(메모이제이션)이란? 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술 문제를 잘게 쪼갤 때 부분 문제는 중복되어 재활용됨 ex) 피보나치 수열 분할 정복(Divide and Conquer) 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 ..

재귀를 활용한 문제들 팰린드롬(Palindrome) 앞뒤 구성이 같은 문자열 ex) 기러기, 토마토, 우영우 재귀 함수를 통해 간단히 구현할 수 있다. 코드 def palindrome(str): if len(str)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/42626 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 풀이 풀긴 풀었는데 heapq를 import 하지 않고선 방법이 없는건가..? 일단 아래는 heap 복습 겸 직접 구현해서 푼 풀이.. 근데 heap 구현이 잘못됐는지 계속 틀린다. def solution(scoville, K): # 출력: 섞어야 하는 최소 횟수 # 2 self.heap_arr[right_child_idx]: if self.heap_arr[popped_idx] > self...

힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) * 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 이에 반해, 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 우선순위 큐 import queue data_queue = queue.PriorityQueue() data_queue.put((10, "korea")) data_queue.put((5, 1)) data_queue.put((15, "china")) print(d..

트리 노드와 브랜치로 구성된 사이클을 이루지 않도록 구성한 데이터 구조 * 트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용 Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함) Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이 Parent Node: 어떤 노드의 다음 레벨에 연결된 노드 Child Node: 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node (Terminal Node): Child Node가 하나도 없는 노드 Sibling (Brother Node): 동일한 Parent Node를 가..

Chaining 데이터 추가 함수 hash_table = list[0 for i in range(8)] def get_hash(data): return hash(data) def get_address(hash): return hash % 8 def save_data(data, value): hash_key = get_hash(data) hash_address = get_address(hash_key) if hash_table[hash_address] != 0: for i in range(len(hash_table[hash_address])): if hash_table[hash_address][i][0] == hash_key: # 같은 hash의 키로 데이터가 있을 경우 hash_table[hash_add..

문제 https://school.programmers.co.kr/learn/courses/30/lessons/120884 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 def solution(chicken): return test(0, chicken) def test(chicken, prev_coupon): if prev_coupon < 10: return chicken service, coupon = divmod(prev_coupon, 10) coupon += service return test(chicken+service, coupon)

문제 https://school.programmers.co.kr/learn/courses/30/lessons/120882 내 풀이 def solution(score): score = [(x+y)/2 for [x, y] in score] spair = [*score] result = [0] * len(score) x = 1 while len(spair) > 0: m = max(spair) temp = 0 for i, e in enumerate(score): if e == m: result[i] = x temp += 1 while spair.count(m) > 0: spair.remove(m) x += temp return result 다른 풀이

문제 https://school.programmers.co.kr/learn/courses/30/lessons/120863 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 내 풀이 def solution(polynomial): answer = '' x_arr = [] i_arr = [] for e in polynomial.split(' '): if e == '+': continue elif e.find('x') > -1: x_arr.append(int(1 if e == 'x' else e[:-1])) else: i_arr.append(int(e)) if su..