chamkkae
2022.03.28
@chamkkae님이 새 포스트를 작성했습니다.
15일차 - 코딩테스트 Level 1 3월 과정
N, M = 7, 7 # matrix 배열 matrix = [     [1, 1, 0, 0, 0, 0, 0],     [0, 1, 1, 0, 1, 1, 1],     [0, 1, 1, 1, 1, 1, 1],     [0, 1, 0, 1, 0, 0, 1],     [0, 0, 0, 1, 0, 0, 1],     [1, 0, 0, 1, 1, 1, 1],     [1, 1, 1, 1, 0, 1, 0], ] # 방문경로 배열 visited = [[0] * M for _ in range(N)] # 좌/우/위/아래 방향 이동 dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1] # BFS 경로 탐색 # queue 방식 사용 queue = [(0, 0)] visited[0][0] = 1 while queue:     x, y = queue.pop(0)     if x == N - 1 and y == M - 1:         # 최종 경로 도착         print(visited[x][y])         break     for i in range(4):         nx = x + dx[i]         ny = y + dy[i]         if 0 <= nx < N and 0 <= ny < M:             if visited[nx][ny] == 0 and matrix[nx][ny] == '1':                 visited[nx][ny] = visited[x][y] + 1                 queue.append((nx,ny))
chamkkae
2022.03.24
@chamkkae님이 새 포스트를 작성했습니다.
13일차 - 코딩테스트 Level 1 3월 과정
class Heap:     def __init__(self, heap_size):         self.arr = [None] * heap_size         self.heap_count = 0     def compare_with_parent(self, index):         if index <= 1:             return False         parent_index = index // 2         if self.arr[index] < self.arr[parent_index]:             return True         else:             return False     def insert(self, data):         self.heap_count += 1         if self.heap_count == 1:             self.arr[self.heap_count] = data             return         self.arr[self.heap_count] = data         insert_index = self.heap_count         while self.compare_with_parent(insert_index):             parent = insert_index // 2             self.arr[insert_index], self.arr[parent] = (                 self.arr[parent],                 self.arr[insert_index],             )             insert_index = parent         return True     def compare_with_child(self, index):         left = 2 * index         right = 2 * index + 1         if self.arr[left] == None and self.arr[right] == None:             return False         if self.arr[right] == None:             if self.arr[left] < self.arr[index]:                 return left             else:                 return False         if self.arr[left] < self.arr[right]:             return left         else:             return right     def pop(self):         index = 1         root = self.arr[1]         terminal_data = self.arr[self.heap_count]         self.arr[self.heap_count] = None         self.arr[index] = terminal_data         self.heap_count -= 1         while True:             child_index = self.compare_with_child(index)             if not child_index:                 break             self.arr[child_index], self.arr[index] = (                 self.arr[index],                 self.arr[child_index],             )             index = child_index         return root # Heap의 최대 크기 입력 heap_size = int(input("Enter Max Heap Size: ")) # Heap 생성 schedules = Heap(heap_size) # 처리할 작업 수 입력 schedule_num = int(input("Enter the number of work: ")) # 입력된 우선순위와 작업 내용 저장 schedule_works = {} for i in range(schedule_num):     priority, work_name, _ = input("Enter priority and work name: ").split('"')     schedules.insert(int(priority.strip()))     schedule_works[priority.strip()] = work_name.strip() for idx in range(1, schedule_num+1):     print(f'{idx}번째 진행할 작업: {schedule_works[str(schedules.pop())]}') 다른 코메님이 하신 코드 클론코딩했습니다.
paulben0410
2022.03.22
@paulben0410님이
11일차 - 코딩테스트 Level 1 3월 과정
포스트를 좋아합니다.
chamkkae
2022.03.22
@chamkkae님이 새 포스트를 작성했습니다.
11일차 - 코딩테스트 Level 1 3월 과정
class Node:     def __init__(self, data):         self.data = data         self.left = None         self.right = None def get_tree(idx):     if idx == 0:         root = Node(7)         node_3 = Node(3)         node_10 = Node(10)         root.left = node_3         root.right = node_10         node_1 = Node(1)         node_5 = Node(5)         node_3.left = node_1         node_3.right = node_5         node_8 = Node(8)         node_10.left = node_8         node_4 = Node(4)         node_5.left = node_4         node_12 = Node(12)         node_4.left = node_12     elif idx == 1:         root = Node(100)         node_10 = Node(10)         node_11 = Node(11)         root.left = node_10         root.right = node_11         node_7 = Node(7)         node_5 = Node(5)         node_10.left = node_7         node_10.right = node_5         node_9 = Node(9)         node_1 = Node(1)         node_11.left = node_9         node_11.right = node_1         node_25 = Node(25)         node_14 = Node(14)         node_7.left = node_25         node_5.right = node_14         node_36 = Node(36)         node_19 = Node(19)         node_9.right = node_36         node_1.left = node_19         node_23 = Node(23)         node_36.left = node_23     elif idx == 2:         root = Node(8)         node_10 = Node(10)         node_11 = Node(11)         root.left = node_10         root.right = node_11         node_5 = Node(5)         node_9 = Node(9)         node_10.right = node_5         node_11.left = node_9     return root def get_tree_height(node, cur_height):     global max_height, d_node     if node == None:         return         if max_height < cur_height:         max_height = cur_height         d_node = node         get_tree_height(node.left, cur_height+1)     get_tree_height(node.right, cur_height+1) def answer(idx):     global max_height, d_node     max_height = 0     root = get_tree(idx)     get_tree_height(root, 0)     print(f'가장 깊은 레벨에 존재하는 노드: {d_node.data}')     print(f'Tree의 높이: {max_height}') for idx in range(3):     answer(idx)
HJTN
2022.03.21
@HJTN님이
10일차 - 코딩테스트 Level 1 3월 과정
포스트를 좋아합니다.
chamkkae
2022.03.21
@chamkkae님이 새 포스트를 작성했습니다.
10일차 - 코딩테스트 Level 1 3월 과정
# 노드 클래스. # 생성자로 데이터와 포인터를 받는다. # 포인터가 입력이 안된 경우, 해당 노드가 종단점이라는 의미. class Node:     def __init__(self, data, pointer=None):         self.data = data         self.pointer = pointer # 링크드리스트 클래스. # 클래스 객체 생성시 데이터가 존재하지 않는 노드를 생성한다. # 해당 노드의 포인터가 바로 Head. class LinkedList(object):     def __init__(self):         self.head = Node(None)         # 링크드리스트의 노드 개수를 저장하는 변수 size.         self.size = 0     # idx 위치에 존재하는 노드를 받아온다.     def get(self, idx):         # 입력된 인덱스가 링크드리스트 사이즈보다 클 경우, 오류가 발생.         if idx >= self.size:             print("Index Error")             return None         # 인덱스가 0인 경우, 헤드를 받아오라는 의미         if idx == 0:             return self.head         else:             node = self.head             for _ in range(idx):                 node = node.pointer             return node     # 데이터를 링크드리스트 종단점으로 추가한다.     def append(self, data):         if self.size == 0:             self.head = Node(data)             self.size += 1         else:             node = self.head             # 종단점의 포인터는 None값을 가짐.             while node.pointer != None:                 node = node.pointer             new_node = Node(data)             node.pointer = new_node             self.size += 1     # 데이터를 idx 위치에 추가한다.     def insert(self, value, idx):         if self.size == 0:             self.head = Node(value)             self.size += 1         # idx가 0이라는건, Head 자리에 새로운 데이터를 넣는다는 의미.         elif idx == 0:             self.head = Node(value, self.head)             self.size += 1         else:             node = self.get(idx - 1)             if node == None:                 return             new_node = Node(value)             next_node = node.pointer             # 삽입하려는 idx 이전의 노드의 포인터를 새로운 노드로 설정             node.pointer = new_node             # 현재 노드의 포인터를 삽입하려는 idx 이후의 노드로 설정             new_node.pointer = next_node             self.size += 1     # idx 위치의 노드를 삭제한다.     def delete(self, idx):         if self.size == 0:             print("Empty Linked List")             return         elif idx >= self.size:             print("Index Error")             return         elif idx == 0:             self.head = self.head.pointer             self.size -= 1         else:             node = self.get(idx - 1)             node.pointer = node.pointer.pointer             self.size -= 1     def print_linked_list(self):         node = self.head         while node:             if node.pointer != None:                 print(node.data, "-> ", end="")                 node = node.pointer             else:                 print(node.data)                 node = node.pointer LL = LinkedList() LL.append("Data1") LL.print_linked_list() LL.append("Data2") LL.print_linked_list() LL.append("Data3") LL.print_linked_list() LL.insert("Data4", 1) LL.print_linked_list() LL.delete(0) LL.print_linked_list() LL.delete(2) LL.print_linked_list() LL.delete(0) LL.print_linked_list()
chamkkae
2022.03.18
@chamkkae님이 새 포스트를 작성했습니다.
9일차 - 코딩테스트 Level 1 3월 과정
import queue task_num = int(input()) task = queue.Queue() for i in range(task_num):     cust_id, task_time = input().split()     task.put([int(cust_id), int(task_time)]) def answer(task):     print('-- 처리한 고객의 아이디 --')     total_time = 0     work_time = 50     cust_list = []     while(task.qsize() > 0):         cust_id, task_time = task.get()         if task_time > work_time:             print(cust_list)             cust_list.clear()             total_time += 10             work_time = 50         cust_list.append(cust_id)         total_time += task_time         work_time -= task_time     print(cust_list)     print(f'\n총 소요시간: {total_time}분') answer(task) 다른 분 코드 참고해서 작성했습니다!
chamkkae
2022.03.16
@chamkkae님이 새 포스트를 작성했습니다.
7일차 - 코딩테스트 Level 1 3월 과정
[문제 풀이] (1) 소스코드 def print_prime_by_range(n: int):     prime_range = n + 1     prime_list = [True] * prime_range     for i in range(2, int(n ** 0.5) + 1):         if prime_list[i]:             for j in range(i + i, prime_range, i):                 prime_list[j] = False     return prime_list def answer(N: int):     prime = []     prime_list = print_prime_by_range(N)     num, start = 2, 2     while num <= N:         if prime_list[num]:             prime.append(num)             if sum(prime) == N:                 print(f'연속된 소수 {prime}의 합은 {N}입니다.')                 break             elif sum(prime) > N:                 start += 1                 num = start         num += 1 answer(41) answer(20) (2) 실행 결과
chamkkae
2022.03.15
@chamkkae님이 새 포스트를 작성했습니다.
6일차 - 코딩테스트 Level 1 3월 과정
[문제 풀이] (1) 소스코드 - 스택 활용 버전 def validate_brace_pair(brace: str):     stack, result = [], '유효한'     for b in brace:         if b == '{':             stack.append('{')         elif stack:             stack.pop()         else:             result = '유효하지 않은'             break     if stack:         result = '유효하지 않은'     print(f'{result} 중괄호 쌍입니다.') validate_brace_pair("{{}}{}") validate_brace_pair("{{}") validate_brace_pair("{{{}}}") validate_brace_pair("}{{{}}}{") (2) 소스코드 - 스택 미활용 버전 def validate_brace_pair(brace: str):     result = '유효하지 않은'     if len(brace) % 2 == 0:         x, y = 0, 0         for b in brace:             if b == '{':                 x += 1             else:                 y += 1             if x < y:                 break         if x == y:             result = '유효한'     print(f'{result} 중괄호 쌍입니다.') validate_brace_pair("{{}}{}") validate_brace_pair("{{}") validate_brace_pair("{{{}}}") validate_brace_pair("}{{{}}}{") (3) 실행 결과
yuuulya
2022.03.14
@yuuulya님이
5일차 - 코딩테스트 Level 1 3월 과정
포스트를 좋아합니다.
chamkkae
2022.03.09
@chamkkae님이 새 포스트를 작성했습니다.
3일차 - 코딩테스트 Level 1 3월 과정
[개념 정리] (1) 선형 탐색 알고리즘 → O(n) 배열의 첫 요소에 접근해 목표값과 동일한지 확인한다. 동일하지 않을 경우, 다음 요소에 접근해 목표값과 동일한지 확인한다. 목표값이 나올 때까지 위의 과정을 반복한다. 목표값을 찾았을 경우, 값을 반환하고 탐색을 종료한다. (2) 이진 탐색 알고리즘 → O(log n) 정렬된 배열의 중간값을 확인해, 목표값보다 큰지 작은지 확인한다. 중앙값이 목표값보다 작다면 중앙값 우측 배열을, 크다면 중앙값 좌측 배열을 탐색 대상으로 지정한다. 변경된 탐색 대상에서 목표값을 찾거나, 배열의 크기가 1 또는 2가 될 때까지 위의 과정을 반복한다. 목표값을 찾았을 경우, 값을 반환한다. [문제 풀이] (1) 소스코드 print('< 입력 >') LAN = [int(input()) for _ in range(4)] left = 1 right = max(LAN) while left <= right:     count = 0     middle = (left + right) // 2     for L in LAN:         count += (L // middle)     if count >= 10:         left = middle + 1     else:         right = middle - 1 print(f'\n< 결과 >\n{right}') (2) 실행 결과 이분 탐색 알고리즘을 활용해 코드를 작성했습니다.
chamkkae
2022.03.08
@chamkkae님이 새 포스트를 작성했습니다.
2일차 - 코딩테스트 Level 1 3월 과정
[개념 정리] (1) Big-O 표기법 문제 해결 알고리즘의 성능을 표기하는 방법 중 하나 최악의 경우를 대비하는 표기법 (2) Big-O 표기법 계산 다중의 원시작업: 여러 개의 원시작업을 하나로 계산 연속문: 각 작업의 실행시간을 합산 반복문: 반복문의 최대 반복 횟수 중첩 반복문: 각 반복문의 최대 반복 횟수를 곱하여 계산 (3) Big-O 표기법 계산 요령 낮은 차수의 항들을 탈락시킨다. 최소한의 함수 계열을 사용한다. 함수 계열 중 가장 단순한 표현을 사용한다. [문제 풀이] 1️⃣ 시간 복잡도: O(N+M) 첫 번째와 두 번째 작업은 실행시간이 각각 N, M인 반복문이므로, 각 작업의 시간 복잡도는 O(N), O(M)입니다. 두 반복문이 연속하여 나타난 형태이므로, 최종 시간 복잡도는 두 실행시간을 합친 O(N+M)입니다. 2️⃣ 시간 복잡도: O(N²) 첫 번째 작업은 최대 반복 횟수가 N인 반복문 안에 최대 반복 횟수가 N인 반복문이 들어있는 중첩 반복문이므로, 첫 번째 작업의 시간 복잡도는 두 반복문의 최대 반복 횟수를 곱한 O(N²)입니다. 두 번째 작업은 최대 반복 횟수가 N인 반복문이므로, 두 번째 작업의 시간 복잡도는 O(N)입니다. 두 작업이 연속하여 나타난 형태이므로, 시간 복잡도는 두 실행시간을 합친 O(N² + N)입니다. Big-O 표기법에 따라 낮은 차수의 항을 탈락시키면, 최종 시간 복잡도는 O(N²)입니다.