기술개발/Algorithm 2021. 2. 3. 19:57

트리 뿌리와 가지로 구성되어 거꾸로 세워 놓은 나무처럼 보이는 계층형 비선형 자료 구조 선형구조와 다르게 계층적 혹은 망으로 구성 자료를 표현하는데 초점이 맞춰져 있음 컴퓨터 폴더 구조와 같이 하나의 밑에 밑에 있는 계층적 구조가 중요하다면 트리를 쓰는 것이 맞음 큐, 스택 같은 경우는 선형구조인데 자료를 구성하고 있는 데이터들이 순차적으로 나열시킨 형태이다. 자료를 저장하고 꺼내는 것 에 초점이 맞춰져 있음 💡 Node: 트리에서 데이터를 저장하는 기본 요소 Root Node: 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node: 어떤 노드의 상위 레벨에 연결된 노드 Child Node: 어떤 노드의 하..

기술개발/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..

기술개발/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. 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..

기술개발/Algorithm 2021. 1. 13. 19:09

소수 나열하기 Q. 정수를 입력 했을 때, 그 정수 이하의 소수를 모두 반환하시오. 소수는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. input = 20 def find_prime_list_under_number(number): # 이 부분을 채워보세요! return [] result = find_prime_list_under_number(input) print(result) # 내 코드 input = 20 def find_prime_list_under_number(number): result = [] for i in range(1, number+1): count = 0 for j in range(1, i+1): if i % j == 0: count += 1 if count

기술개발/Algorithm 2021. 1. 12. 18:04

점근표기법 알고리즘의 성능을 수학적으로 표기하는 방법 즉 알고리즘의 '효율성'을 평가하는 방법. 어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법. 이전에서 공부했던 시간복잡도와 공간복잡도도 점근 표기법의 일종. 빅오(Big-O) 표기법 최악의 성능이 나올때 어느 정도의 연산량이 걸릴 것인지 표기 빅 오메가(Big-Ω) 표기법 최선의 성능이 나올때 어느 정도의 연산량이 걸릴 것인지 표기 배열에서 특정 요소 찾기 다음과 같은 숫자로 이루어진 배열이 있을 때, 이 배열 내에 특정한 숫자가 존재하면 True, 존재하지 않는다면 False를 반환하기 input = [3, 5, 6, 1, 2, 4] def is_number_exist(number, array): # 이 부분을 채워보세요..