우기의 알 블로그 저자 한승욱이라고 합니다.
스스로 알을 깨고 나오는 새처럼
언젠가 알을 깨고 온전한 나 자신이 되었을 때, 그때를 기다리며 제 속에서 솟아 나오는 것을 글로써 표현하고자 합니다.
'개발 기술블로그'를 위주로 저 한승욱의 다양한 관심사, 생각, 철학 등을 포스팅합니다.
농심 라면 공장 ❓ Q. 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환 하시오. dates[i]에는 i번째 ..
Dynamic Programming(동적 계획법) 피보나치 수열 - DP를 공부하기 전 몸풀기 📖 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. [위키백과] Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3 Fibo(5) = Fibo(4) + Fibo(3) = 3 + 2 = 5 Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8 ..... Fibo(n) = Fibo(n - 1) + Fibo(n-2) 비슷한 구조가 반복되니 재귀 로 문제를 풀 수 있을 것이다. # 코드 스니펫 input = 20 def fibo..
BFS, DFS란? BFS: 자료의 검색, 트리나 그래프를 탐색하는 방법으로써 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS: 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더이상 방문하지 않은 정점이 없을때가지 방문하지 않은 모든 정점들에 대해서도 적용 이 두개가 필요한 이유: 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 탐색이 있는 반면 전부 탐색 해야하는 경우가 있다. 위 두 방법은 이때 모든 경우의 수를 탐색할 때 필요한 알고리즘이다. 💡 DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구합니다. 따라서 공간을 적게 씁니다. 그러나 최단 경로를 탐색하기 쉽지 않습니다. B..
그래프 DFS, BFS에 대해 활용하기 전에 배우는 사전 개념 그래프란? 연결되어 있는 정점과 정점간의 관계를 표시한 자료 구조 💡 비선형 구조는 표현에 초점이 맞춰져 있다고 말씀 드렸는데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다. # 출처: 스파르타코딩클럽 예를 들면 SNS의 관계 같은 경우가 그래프 구조일 것 💡 노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) # 출처: 스파르타코딩클럽 그래프는 원..
힙 힙이란? 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 항상 최대, 최소값들이 요구되는 연산이 있을 때 쓰기 매우 좋다 💡 그렇다면 힙을 구현하려면 어떻게 해야할까? 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨(또는 반대로) 있게 하는 자료구조. 즉 부모 노드의 값이 자식 노드의 값보다 항상 커야 함(또는 반대로) 이를 통해 최대의 값을 빠르게 구할 수 있음 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다! 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이 4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다! 8 L..
트리 뿌리와 가지로 구성되어 거꾸로 세워 놓은 나무처럼 보이는 계층형 비선형 자료 구조 선형구조와 다르게 계층적 혹은 망으로 구성 자료를 표현하는데 초점이 맞춰져 있음 컴퓨터 폴더 구조와 같이 하나의 밑에 밑에 있는 계층적 구조가 중요하다면 트리를 쓰는 것이 맞음 큐, 스택 같은 경우는 선형구조인데 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태이다. 자료를 저장하고 꺼내는 것 에 초점이 맞춰져 있음 💡 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하..
4주차에 배우는 것 트리, 힙의 개념과 활용법 그래프, BFS, DFS Dynamic Programming의 개념과 필요성 트리 & 힙 트리를 이용하면 계층 구조의 데이터를 쉽게 표현 가능 힙을 이용하면 최댓값, 최솟값을 쉽게 뽑을 수 있음 BFS & DFS BFS(Breadth First Search): 너비 우선 탐색, 모든 것들을 하나씩 방문해야지만 다음 것을 봄 DFS(Depth First Search): 깊이 우선 탐색, 깊이로 내려가며 방문 각 탐색의 장단점 알기 Dynamic Programming 동적 계획법 부분 문제의 해를 통해 전체 문제를 해결하는 방법 DP라고도 하며 알고리즘 문제를 해결하는데 매우 많이 사용되는 편
Q1. 쓱 최대로 할인 적용하기 ❓ Q. 다음과 같이 숫자로 이루어진 배열이 두 개가 있다. 하나는 상품의 가격을 담은 배열이고, 하나는 쿠폰을 담은 배열이다. 쿠폰의 할인율에 따라 상품의 가격을 할인 받을 수 있다. 이 때, 최대한 할인을 많이 받는다면 얼마를 내야 하는가? 단, 할인쿠폰은 한 제품에 한 번씩만 적용 가능하다. # 코드 스니펫 shop_prices = [30000, 2000, 1500000] user_coupons = [20, 40] def get_max_discounted_price(prices, coupons): # 이 곳을 채워보세요! return 0 print(get_max_discounted_price(shop_prices, user_coupons)) # 926000 이 나와야..
해쉬 해쉬 테이블이란? 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인 연관 배열 추가에 사용되는 자료 구조 해시 함수를 사용하여 색인(index)을 버킷(bucket), 슬롯(slot)의 배열로 계산 데이터의 저장과 검색이 아주 빠르게 진행된다. 파이썬에서는 딕셔너리 = 해쉬 테이블 딕셔너리 키를 통해 바로 데이터를 받아올 수 있으므로 속도가 매우 빠름 찾는 데이터에 대해 배열을 전부 다 둘러보지 않고도 바로 값을 조회할 수 있는 자료구조 딕셔너리는 내부적으로 배열을 사용 class Dict: def __init__(self): self.items = [None] * 8 이와 같은 구조에서 해쉬 함수를 이용하여 저장과 검색을 진행 해쉬 함수 class Dict: def __init__(self): self..
큐 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조 놀이기구가 한 줄로 서서 한줄로 나오는 것을 비유 가능 First In First Out 💡 큐가 제공하는 기능 enque(data): 맨 뒤에 데이터 추가 dequeue(): 맨 위의 데이터 뽑기 peek(): 맨 위의 데이터 보기 isEmpty(): 큐가 비었는지 안 비었는지 여부 반환 스택과 마찬가지로 데이터 넣고 뽑는 걸 자주하는 자료 구조이므로 링크드 리스트와 유사하게 구현 가능 스택과 다르게 끝과 시작의 노드를 전부 가지고 있어야 함 self.head, self.tail class Node: def __init__(self, data): self.data = data self.next = None class Queue: d..
기술개발/Algorithm 2021. 2. 11. 18:24
농심 라면 공장 ❓ Q. 라면 공장에서는 하루에 밀가루를 1톤씩 사용합니다. 원래 밀가루를 공급받던 공장의 고장으로 앞으로 k일 이후에야 밀가루를 공급받을 수 있기 때문에 해외 공장에서 밀가루를 수입해야 합니다. 해외 공장에서는 향후 밀가루를 공급할 수 있는 날짜와 수량을 알려주었고, 라면 공장에서는 운송비를 줄이기 위해 최소한의 횟수로 밀가루를 공급받고 싶습니다. 현재 공장에 남아있는 밀가루 수량 stock, 밀가루 공급 일정(dates)과 해당 시점에 공급 가능한 밀가루 수량(supplies), 원래 공장으로부터 공급받을 수 있는 시점 k가 주어질 때, 밀가루가 떨어지지 않고 공장을 운영하기 위해서 최소한 몇 번 해외 공장으로부터 밀가루를 공급받아야 하는지를 반환 하시오. dates[i]에는 i번째 ..
기술개발/Algorithm 2021. 2. 10. 16:26
Dynamic Programming(동적 계획법) 피보나치 수열 - DP를 공부하기 전 몸풀기 📖 수학에서, 피보나치 수(영어: Fibonacci numbers)는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. [위키백과] Fibo(4) = Fibo(3) + Fibo(2) = 2 + 1 = 3 Fibo(5) = Fibo(4) + Fibo(3) = 3 + 2 = 5 Fibo(6) = Fibo(5) + Fibo(4) = 5 + 3 = 8 ..... Fibo(n) = Fibo(n - 1) + Fibo(n-2) 비슷한 구조가 반복되니 재귀 로 문제를 풀 수 있을 것이다. # 코드 스니펫 input = 20 def fibo..
기술개발/Algorithm 2021. 2. 8. 16:52
BFS, DFS란? BFS: 자료의 검색, 트리나 그래프를 탐색하는 방법으로써 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색해가고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다. DFS: 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법. 더이상 방문하지 않은 정점이 없을때가지 방문하지 않은 모든 정점들에 대해서도 적용 이 두개가 필요한 이유: 정렬된 데이터를 이분 탐색하는 것처럼 아주 효율적인 탐색이 있는 반면 전부 탐색 해야하는 경우가 있다. 위 두 방법은 이때 모든 경우의 수를 탐색할 때 필요한 알고리즘이다. 💡 DFS 는 끝까지 파고드는 것이라, 그래프의 최대 깊이 만큼의 공간을 요구합니다. 따라서 공간을 적게 씁니다. 그러나 최단 경로를 탐색하기 쉽지 않습니다. B..
기술개발/Algorithm 2021. 2. 5. 17:58
그래프 DFS, BFS에 대해 활용하기 전에 배우는 사전 개념 그래프란? 연결되어 있는 정점과 정점간의 관계를 표시한 자료 구조 💡 비선형 구조는 표현에 초점이 맞춰져 있다고 말씀 드렸는데, 선형구조는 자료를 저장하고 꺼내는 것에 초점이 맞춰져 있고, 비선형구조는 표현에 초점이 맞춰져 있습니다. 이번 자료구조인 그래프는 바로 연결 관계에 초점이 맞춰져 있습니다. # 출처: 스파르타코딩클럽 예를 들면 SNS의 관계 같은 경우가 그래프 구조일 것 💡 노드(Node): 연결 관계를 가진 각 데이터를 의미합니다. 정점(Vertex)이라고도 합니다. 간선(Edge): 노드 간의 관계를 표시한 선. 인접 노드(Adjacent Node): 간선으로 직접 연결된 노드(또는 정점) # 출처: 스파르타코딩클럽 그래프는 원..
기술개발/Algorithm 2021. 2. 4. 14:29
힙 힙이란? 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 항상 최대, 최소값들이 요구되는 연산이 있을 때 쓰기 매우 좋다 💡 그렇다면 힙을 구현하려면 어떻게 해야할까? 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨(또는 반대로) 있게 하는 자료구조. 즉 부모 노드의 값이 자식 노드의 값보다 항상 커야 함(또는 반대로) 이를 통해 최대의 값을 빠르게 구할 수 있음 8 Level 0 6 3 Level 1 2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다! 8 Level 0 6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이 4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다! 8 L..
기술개발/Algorithm 2021. 2. 3. 19:57
트리 뿌리와 가지로 구성되어 거꾸로 세워 놓은 나무처럼 보이는 계층형 비선형 자료 구조 선형구조와 다르게 계층적 혹은 망으로 구성 자료를 표현하는데 초점이 맞춰져 있음 컴퓨터 폴더 구조와 같이 하나의 밑에 밑에 있는 계층적 구조가 중요하다면 트리를 쓰는 것이 맞음 큐, 스택 같은 경우는 선형구조인데 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태이다. 자료를 저장하고 꺼내는 것 에 초점이 맞춰져 있음 💡 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하..
기술개발/Algorithm 2021. 2. 2. 23:05
4주차에 배우는 것 트리, 힙의 개념과 활용법 그래프, BFS, DFS Dynamic Programming의 개념과 필요성 트리 & 힙 트리를 이용하면 계층 구조의 데이터를 쉽게 표현 가능 힙을 이용하면 최댓값, 최솟값을 쉽게 뽑을 수 있음 BFS & DFS BFS(Breadth First Search): 너비 우선 탐색, 모든 것들을 하나씩 방문해야지만 다음 것을 봄 DFS(Depth First Search): 깊이 우선 탐색, 깊이로 내려가며 방문 각 탐색의 장단점 알기 Dynamic Programming 동적 계획법 부분 문제의 해를 통해 전체 문제를 해결하는 방법 DP라고도 하며 알고리즘 문제를 해결하는데 매우 많이 사용되는 편
기술개발/Algorithm 2021. 2. 1. 16:45
Q1. 쓱 최대로 할인 적용하기 ❓ Q. 다음과 같이 숫자로 이루어진 배열이 두 개가 있다. 하나는 상품의 가격을 담은 배열이고, 하나는 쿠폰을 담은 배열이다. 쿠폰의 할인율에 따라 상품의 가격을 할인 받을 수 있다. 이 때, 최대한 할인을 많이 받는다면 얼마를 내야 하는가? 단, 할인쿠폰은 한 제품에 한 번씩만 적용 가능하다. # 코드 스니펫 shop_prices = [30000, 2000, 1500000] user_coupons = [20, 40] def get_max_discounted_price(prices, coupons): # 이 곳을 채워보세요! return 0 print(get_max_discounted_price(shop_prices, user_coupons)) # 926000 이 나와야..
기술개발/Algorithm 2021. 1. 29. 21:11
해쉬 해쉬 테이블이란? 컴퓨팅에서 키를 값에 매핑할 수 있는 구조인 연관 배열 추가에 사용되는 자료 구조 해시 함수를 사용하여 색인(index)을 버킷(bucket), 슬롯(slot)의 배열로 계산 데이터의 저장과 검색이 아주 빠르게 진행된다. 파이썬에서는 딕셔너리 = 해쉬 테이블 딕셔너리 키를 통해 바로 데이터를 받아올 수 있으므로 속도가 매우 빠름 찾는 데이터에 대해 배열을 전부 다 둘러보지 않고도 바로 값을 조회할 수 있는 자료구조 딕셔너리는 내부적으로 배열을 사용 class Dict: def __init__(self): self.items = [None] * 8 이와 같은 구조에서 해쉬 함수를 이용하여 저장과 검색을 진행 해쉬 함수 class Dict: def __init__(self): self..
기술개발/Algorithm 2021. 1. 28. 20:52
큐 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조 놀이기구가 한 줄로 서서 한줄로 나오는 것을 비유 가능 First In First Out 💡 큐가 제공하는 기능 enque(data): 맨 뒤에 데이터 추가 dequeue(): 맨 위의 데이터 뽑기 peek(): 맨 위의 데이터 보기 isEmpty(): 큐가 비었는지 안 비었는지 여부 반환 스택과 마찬가지로 데이터 넣고 뽑는 걸 자주하는 자료 구조이므로 링크드 리스트와 유사하게 구현 가능 스택과 다르게 끝과 시작의 노드를 전부 가지고 있어야 함 self.head, self.tail class Node: def __init__(self, data): self.data = data self.next = None class Queue: d..