딩동댕 코딩유치원

문제 해결방안 입력받은 배열에 있는 값들을 내림차순으로 정렬하면 가장 비싼 물건에 가장 할인율이 높은 쿠폰을 적용할 수 있으므로 내림차순 정렬한 후 인덱스를 하나씩 증가시키면서 각 가격에 쿠폰을 적용한 후 가격을 더해준다. shop_prices = [30000, 2000, 1500000] user_coupons = [20, 40] def get_max_discounted_price(prices, coupons): prices.sort(reverse=True) coupons.sort(reverse=True) price_index = 0 coupon_index = 0 max_discounted_price = 0 while coupon_index < len(coupons): max_discounted_pric..

문제 해결방법 파이썬의 딕셔너리를 이용하여 각 배열의 값들을 key값으로 두고 True를 value로 준 후 참석한 학생 목록을 다시 한 번 돌면서 중복되는 값들을 지운다. 그 후 남아있는 값의 key값만 추출해서 출력한다. all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"] present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"] def get_absent_student(all_array, present_array): student_dict = {} for key in all_array: student_dict[key] = True for key in present_..

hash함수를 이용하여 key값을 임의의 값으로 변경한 후 배열의 인덱스에 넣어 해당하는 값에 데이터를 저장 하는 것으로 데이터를 쉽게 찾고 출력할 수 있다. 충돌을 방지 하기 위해 chaning방식을 사용하여 구현하였다. class LinkedTuple: def __init__(self): self.items = list() def add(self,key,value): self.items.append(key,value) def get(self,key): for k,v in self.items: if key == k: return v class LinkedDict: def __init__(self): self.items = [] for i in range(8): self.items.append(Linke..

큐는 한 쪽으로 데이터를 넣고, 반대쪽에서 데이터가 빠져나가는 가장 먼저 들어온 값이 가장 먼저 나가는 FiFO(First In First Out)방식의 자료구조이다. 큐의 예시로는 놀이기구나, 티켓 발권기 등을 생각 해 볼 수 있다. class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.head = None self.tail = None def enqueue(self, value): new_node = Node(value) if self.is_empty(): self.head = new_node self.tail = new_node return self.tail..

문제 해결 방법 가장 먼저 결과를 담을 배열을 탑의 길이만큼 만든 후 배열의 값을 하나씩 뽑아 각 인덱스의 값들과 비교하여 pop한 값보다 인덱스의 값이 큰 경우 그 인덱스가 몇 번째인지 배열에 넣어준다. top_heights = [6, 9, 5, 7, 4] def get_receiver_top_orders(heights): # 제일 먼저 0으로 초기화 result = [0] * len(heights) # 원소를 뒤에서부터 하나씩 빼주기 while heights: height = heights.pop() # 원소를 뺀 후 뒤에서 부터 검사하기 for idx in range (len(heights)- 1,0,-1): if heights[idx] > height: # result의 맨 뒤에서 부터 값을 넣어..

스택은 데이터를 한 쪽으로만 넣고 뺄 수 있으며, 가장 마지막에 들어온 값이 가장 먼저 나가는 LIFO(Last In First Out) 이며, LinkedList방식으로 구현 해 보았다. class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.head = None def push(self, value): new_head = Node(value) new_head.next = self.head self.head = new_head # pop 기능 구현 def pop(self): if self.is_empty(): return "Stack is Empty" delete..

병합하기 병합은 array_a와 array_b의 값들을 1과4, 2와 4, 3과 4, 5와 4, 5와 6 이런 식으로 비교하여 작은 값들을 순서대로 새로운 배열에 넣어주어 정렬하는 과정으로 병합 정렬에서 이와 같은 방법이 사용된다. array_a = [1, 2, 3, 5] array_b = [4, 6, 7, 8] def merge(array1, array2): result = [] array1_index = 0 array2_index = 0 while array1_index < len(array1) and array2_index < len(array2): # 더 작은 값을 result에 붙여준다 if array1[array1_index] < array2[array2_index]: result.append..

삽입정렬은 정렬되어 있는 숫자들에 또 다른 숫자를 넣어 하나씩 탐색한 후 맞는 자리에 끼워 넣는 정렬방법이다. 이도 똑같이 for문을 두 번 사용하여 O(N^2)만큼의 시간 복잡도가 걸리지만, 비교하는 값이 정렬이 되어 있는 상태라면 break문을 사용하여 for문을 빠져나오므로 정렬이 어느 정도 되어 있는 상태에서는 선택정렬과 버블정렬보다 좀 더 효율적이다. input = [4, 6, 2, 9, 1] def insertion_sort(array): n = len(array) for i in range(1,n): for j in range(i): if array[i - j - 1] > array[i - j]: array[i - j - 1],array[i - j] = array[i - j],array[i ..

선택정렬은 각 값들을 하나씩 탐색 한 후 가장 작은 숫자를 찾아 맨 앞 인덱스에 넣고, 두 번째로 작은 값을 찾아 첫번 쨰 인덱스에 넣고 세 번째로 작은 값을 찾아 두 번째 인덱스에 넣는 식으로 정렬이 끝날 때 까지 위의 과정을 반복하는 방법이다. 버블 정렬이 가장 끝의 인덱스에 큰 숫자가 정렬되는 것과 달리 선택 정렬은 앞 인덱스에 작은 숫자 순서대로 정렬이된다. 이또한 두 개의 for문을 돌아야 하므로 O(N^2)만큼의 복잡도를 가진다. input = [4, 6, 2, 9, 1] def selection_sort(array): n = len(array) for i in range(n - 1): # 최솟값 저장(인덱스에) min_idx = i for j in range(n - i): if array[i..

버블 정렬은 앞의 값과 뒤의 값을 비교해서 만약 앞의 값이 더 크고 뒤의 값이 더 작다면 두 값을 교환해가면서 정렬하는 방법으로 한 번 정렬이 끝날 때 마다 배열의 가장 뒤의 값이 제일 큰 값으로 정렬된다. 간단하지만, for문을 두 번 돌기 때문에 시간 복잡도가 O(N^2)만큼 걸리기 때문에 배열이 거의 정렬되어 있는 형태가 아니라면 효율적이지 않은 방법이다. input = [4, 6, 2, 9, 1] def bubble_sort(array): n = len(array) for i in range(n - 1): for j in range(n - 1 -i): if array[j] > array[j + 1]: array[j],array[j+1] = array[j+1],array[j] return bubbl..