우기의 알 블로그 저자 한승욱이라고 합니다.
스스로 알을 깨고 나오는 새처럼
언젠가 알을 깨고 온전한 나 자신이 되었을 때, 그때를 기다리며 제 속에서 솟아 나오는 것을 글로써 표현하고자 합니다.
'개발 기술블로그'를 위주로 저 한승욱의 다양한 관심사, 생각, 철학 등을 포스팅합니다.
힙 힙이란? 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 항상 최대, 최소값들이 요구되는 연산이 있을 때 쓰기 매우 좋다 💡 그렇다면 힙을 구현하려면 어떻게 해야할까? 힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨(또는 반대로) 있게 하는 자료구조. 즉 부모 노드의 값이 자식 노드의 값보다 항상 커야 함(또는 반대로) 이를 통해 최대의 값을 빠르게 구할 수 있음 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 이 나와야..
큐 한쪽 끝으로 자료를 넣고, 반대쪽에서는 자료를 뺄 수 있는 선형구조 놀이기구가 한 줄로 서서 한줄로 나오는 것을 비유 가능 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..
스택 한쪽 끝으로만 자료를 놓고 뺄 수 있는 자료구조 Last in First out, First in Last out(빨래통 구조) 넣은 순서를 쌓아두고 있기에 예를 들면 컴퓨터의 되돌리기 기능에 활용되는 구조 💡 스택이 제공하는 기능 push(data): 맨 위에 데이터 넣기 pop(): 맨 위의 데이터 뽑기 peek(): 맨 위의 데이터 보기 isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기 데이터의 삭제와 삽입이 잦은 자료 구조기에 링크드 리스트와 유사하게 구현 class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.head = None def..
병합 정렬 실제 면접에서 자주 출제됨(직접 구현 형식) 배열의 앞 부분과 뒷 부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업의 반복 [1, 2, 3, 5] # 정렬된 배열 A [4, 6, 7, 8] # 정렬된 배열 B [] # 두 집합을 합칠 빈 배열 C ↓ 1단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 1과 4를 비교합니다! 1
3주차에 배울 것 정렬 스택, 큐의 개념과 활용법 해쉬의 개념과 활용법 정렬 정렬이란 데이터를 순서대로 나열하는 것이다. 정렬하기 위해서는 다양한 방법이 있다. 대표적으로 스택/큐, 해쉬 등을 배워보고자 한다. 스택/큐 스택과 큐는 들어가고 나오는 곳이 정해져있는 자료구조 스택: Last in, first out 큐: First in, first out 해쉬 해쉬 알고리즘을 통해 문자열을 고정된 길이의 데이터로 만들 수 있음 블록체인 기술에서도 쓰이고 딕셔너리를 만들 때도 활용됨 예전에 수업시간에 해시 테이블, 체이닝기법, 개방주소 기법을 배웠던 것이 어렴풋이 기억난다.... 정렬 정렬이란? 데이터를 순서대로 나열하는 방법 이는 이진 탐색을 가능하게 하기도, 데이터를 효율적으로 탐색할 수 있게 만든다 컴..
Q1. 링크드리스트 끝에서 k번 째 값 출력하기 ❓ Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오. [6] -> [7] -> [8] # 이런 링크드 리스트가 입력되었을 때, # 끝에서 2번째 값은 7을 반환해야 합니다! # 코드 스니펫 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self, value): self.head = Node(value) def append(self, value): cur = self.head while cur.next is not None: cur = cur.next cur.next = Node(value) def get_kth_nod..
이진탐색과 재귀함수 이진탐색은 반을 쪼개고 탐색하는 방식 순차탐색은 하나하나 탐색하는 방식 이진탐색을 항상 사용할 수 있는 것은 아니므로 어떨 때 사용 가능한지 배워야함 이진탐색 vs 순차탐색 이진탐색: 1~100 숫자 맞추기 놀이를 한다고 했을 때 "범위의 절반인 50"을 시도하는 방식. 50을 말한다. 대답이 up이라면 1~49는 후보에서 없어진다. 대답이 down이라면 51~100은 후보에서 없어진다. ............ # 예제 코드. 14를 찾는 코드 finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_binary(targe..
기술개발/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. 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..
기술개발/Algorithm 2021. 1. 27. 17:55
스택 한쪽 끝으로만 자료를 놓고 뺄 수 있는 자료구조 Last in First out, First in Last out(빨래통 구조) 넣은 순서를 쌓아두고 있기에 예를 들면 컴퓨터의 되돌리기 기능에 활용되는 구조 💡 스택이 제공하는 기능 push(data): 맨 위에 데이터 넣기 pop(): 맨 위의 데이터 뽑기 peek(): 맨 위의 데이터 보기 isEmpty(): 스택이 비었는지 안 비었는지 여부 반환해주기 데이터의 삭제와 삽입이 잦은 자료 구조기에 링크드 리스트와 유사하게 구현 class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.head = None def..
기술개발/Algorithm 2021. 1. 26. 18:29
병합 정렬 실제 면접에서 자주 출제됨(직접 구현 형식) 배열의 앞 부분과 뒷 부분의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업의 반복 [1, 2, 3, 5] # 정렬된 배열 A [4, 6, 7, 8] # 정렬된 배열 B [] # 두 집합을 합칠 빈 배열 C ↓ 1단계 : [1, 2, 3, 5] ↓ [4, 6, 7, 8] 1과 4를 비교합니다! 1
기술개발/Algorithm 2021. 1. 25. 20:08
3주차에 배울 것 정렬 스택, 큐의 개념과 활용법 해쉬의 개념과 활용법 정렬 정렬이란 데이터를 순서대로 나열하는 것이다. 정렬하기 위해서는 다양한 방법이 있다. 대표적으로 스택/큐, 해쉬 등을 배워보고자 한다. 스택/큐 스택과 큐는 들어가고 나오는 곳이 정해져있는 자료구조 스택: Last in, first out 큐: First in, first out 해쉬 해쉬 알고리즘을 통해 문자열을 고정된 길이의 데이터로 만들 수 있음 블록체인 기술에서도 쓰이고 딕셔너리를 만들 때도 활용됨 예전에 수업시간에 해시 테이블, 체이닝기법, 개방주소 기법을 배웠던 것이 어렴풋이 기억난다.... 정렬 정렬이란? 데이터를 순서대로 나열하는 방법 이는 이진 탐색을 가능하게 하기도, 데이터를 효율적으로 탐색할 수 있게 만든다 컴..
기술개발/Algorithm 2021. 1. 19. 20:30
Q1. 링크드리스트 끝에서 k번 째 값 출력하기 ❓ Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오. [6] -> [7] -> [8] # 이런 링크드 리스트가 입력되었을 때, # 끝에서 2번째 값은 7을 반환해야 합니다! # 코드 스니펫 class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self, value): self.head = Node(value) def append(self, value): cur = self.head while cur.next is not None: cur = cur.next cur.next = Node(value) def get_kth_nod..
기술개발/Algorithm 2021. 1. 16. 19:10
이진탐색과 재귀함수 이진탐색은 반을 쪼개고 탐색하는 방식 순차탐색은 하나하나 탐색하는 방식 이진탐색을 항상 사용할 수 있는 것은 아니므로 어떨 때 사용 가능한지 배워야함 이진탐색 vs 순차탐색 이진탐색: 1~100 숫자 맞추기 놀이를 한다고 했을 때 "범위의 절반인 50"을 시도하는 방식. 50을 말한다. 대답이 up이라면 1~49는 후보에서 없어진다. 대답이 down이라면 51~100은 후보에서 없어진다. ............ # 예제 코드. 14를 찾는 코드 finding_target = 14 finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] def is_existing_target_number_binary(targe..