우기의 알 블로그 저자 한승욱이라고 합니다.
스스로 알을 깨고 나오는 새처럼
언젠가 알을 깨고 온전한 나 자신이 되었을 때, 그때를 기다리며 제 속에서 솟아 나오는 것을 글로써 표현하고자 합니다.
'개발 기술블로그'를 위주로 저 한승욱의 다양한 관심사, 생각, 철학 등을 포스팅합니다.
문자열 압축 ❓ Q. 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압..
나 잡아 봐라 ❓ Q. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오. 조건은 다음과 같다. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다. 코니와 브라운의 위치 p는 조건 0 visited[2] = { 0 : True } # 위치 2 1 -> visited[1] = { 1: True} # 3 -> visited[..
농심 라면 공장 ❓ 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 이 나와야..
기술개발/Algorithm 2021. 2. 16. 16:25
문자열 압축 ❓ Q. 데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다. 간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압..
기술개발/Algorithm 2021. 2. 15. 17:27
나 잡아 봐라 ❓ Q. 연인 코니와 브라운은 광활한 들판에서 ‘나 잡아 봐라’ 게임을 한다. 이 게임은 브라운이 코니를 잡거나, 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나는데 걸리는 최소 시간을 구하시오. 조건은 다음과 같다. 코니는 처음 위치 C에서 1초 후 1만큼 움직이고, 이후에는 가속이 붙어 매 초마다 이전 이동 거리 + 1만큼 움직인다. 즉 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, …이다. 브라운은 현재 위치 B에서 다음 순간 B – 1, B + 1, 2 * B 중 하나로 움직일 수 있다. 코니와 브라운의 위치 p는 조건 0 visited[2] = { 0 : True } # 위치 2 1 -> visited[1] = { 1: True} # 3 -> visited[..
기술개발/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 이 나와야..