ekgns119
2022.03.28
@ekgns119님이 새 포스트를 작성했습니다.
미로 문제
삼주간의 길다면 길도 짧다면 짧은 코딩테스트 1이 끝났네요. 처음부터 끝까지 완벽하게 이해하진 못했지만, 잘안된 것들을 복습하여 발판 삼아 더 성장하도록 노력하겠습니다. 감사합니다. def solution(answers):   answer = []   point = [0, 0, 0]   one = [1,2,3,4,5,1,2,3,4,5]   two = [2,1,2,3,2,4,2,5]   three = [3,3,1,1,2,2,4,4,5,5]   for i in range(len(answers)):     if answers[i] == one[i%len(one)]:      point[0] += 1     if answers[i] == two[i%len(two)]:      point[1] += 1     if answers[i] == three[i%len(three)]:      point[2] += 1    for i in range(len(point)):       if point[i] == max(point):      answer.append(i+1)    return answer
ekgns119
2022.03.25
@ekgns119님이 새 포스트를 작성했습니다.
데이터 삽입 구현하기
마지막으로 갈수록 흐지부지되는 느낌은 있지만, 금요일 오늘이 지나고 주말이니 종합적으로 복습을 하여, 조금 단단하게 만들 필요가 있겠다. 오늘 배열을 사용한 그래프 표현을 보고 데이터를 삽입하는 insert 함수를 구현해보았다. n = int(input("노드 :” )) arr=[[0]*4 for _ in range(4)] #4x4 행렬 생성 def insert(start_node, get_node, weight, not_direction):     if not_direction: # 무방향 그래프인 경우         arr[start_node][get_node] += weight         arr[get_node][start_node] += weight     else: # 방향 그래프인 경우         arr[start_node][get_node] += weight # insert(주는 노드, 받는 노드, 가중치, 무방향그래프 여부) insert(0, 1, 1, 1) insert(0, 3, 1, 1) insert(1, 2, 1, 1) insert(1, 3, 1, 1) insert(2, 3, 1, 1) for i in range(4):     print(*arr[I])
ekgns119
2022.03.23
@ekgns119님이 새 포스트를 작성했습니다.
전위 순회 트리
거의 다 오긴 했는데 중반 부 부터는 저 스스로의 힘으로 과제를 하기 힘드네요 from typing import List class Node():   def __init__(self,data=0):     self.data=data     self.left=None     self.right=None class Solution:   def buildTree(self,preorder:List,inorder:List):     if inorder:       index = inorder.index(preorder.pop(0))        node = Node(inorder[index])       node.left= self.buildTree(preorder,inorder[0:index])        node.right = self.buildTree(preorder,inorder[index+1:])       return node def post_order(node):   if node==None:     return   post_order(node.left)   post_order(node.right)   print(f'{node.data}',end=' ') preorder_arr=list(map(int,input('전위 순회 결과: ').split())) inorder_arr=list(map(int,input('중위 순회 결과: ').split())) tree=Solution() post_order(tree.buildTree(preorder_arr,inorder_arr))
ekgns119
2022.03.22
@ekgns119님이 새 포스트를 작성했습니다.
트리의 높이 구하기
알고리즘 관련 공부는 처음이라 그런지 매우 복잡해지;네요... 마무리 잘할 수있겠죠..? class Node:   def __init__(self, data):     self.data = data     self.left = None     self.right = None def get_tree(): #트리 구현   root = Node(7)   node3 = Node(3)   node10 = Node(10)   root.left = node3   root.right = node10   node1 = Node(1)   node5 = Node(5)   node3.left = node1   node3.right = node5   node8 = Node(8)   node10.left = node8   node4 = Node(4)   node5.left = node4   node12 = Node(12)   node4.left = node12   return root def pre_order(node, k): #전위 순회    global height, maxnode   depth = k       if node == None:     return   depth += 1   if depth > height:     height = depth     maxnode = node   pre_order(node.left, depth)   pre_order(node.right, depth) root = get_tree() height = 0 pre_order(root, 0) print(f"트리의 높이: {height-1} \n해당 레벨의 노드: {maxnode.data}")
ekgns119
2022.03.21
@ekgns119님이 새 포스트를 작성했습니다.
이중 링크드 리스트
이게 가면 갈수록 복잡해지네요...오늘 공부한 부분은 근 시일 내에 복습 후 다시 돌아와서 공부해보도록 하겠습니다. class Node(object):     def __init__(self, data, prev=None, next=None):         self.data = data         self.prev = prev         self.next = next          class DoubleLinkedList(object):     def __init__(self):         self.head = Node(None)         self.tail = Node(None, self.head)         self.head.next = self.tail         self.size = 0              def size(self):         return self.size          def is_empty(self):         if self.size == 0:             print("Double Linked List is empty!")         else:             return False              def get(self, idx):         if idx >= self.size:             print("Index Error!")             return                  if idx + 1 < self.size - index:             node = self.head             for _ in range(index+1):                 node = node.next                          else:             node = self.tail             for _ in range(self.size - index+1):                 node = node.prev                          return node          def add_head(self, value):         pred, succ = self.head, self.head.next         new_node = Node(value)         new_node.prev = pred         new_node.next = succ         pred.next = new_node         succ.prev = new_node                  self.size += 1              def add_tail(self, value):         succ, pred = self.tail, self.tail.prev                  new_node = Node(value)         new_node.prev = pred         new_node.next = succ         pred.next = new_node         succ.prev = new_node                  self.size += 1              def insert(self, value, idx):         if idx > self.size:             return                  if idx < self.size - idx:             pred = self.head             for _ in range(idx):                 pred = pred.next         else:             succ = self.tail             for _ in range(self.size - idx):                 succ = succ.prev             pred = succ.prev                  self.size += 1         new_node = Node(value)         new_node.prev = pred         new_node.next= succ         pred.next = new_node         succ.prev= new_node              def delete(self, idx):         if idx < 0 or idx >= self.size:             print("Index Error!")             return                      if idx < self.size - idx:             pred = self.head             for _ in range(idx):                 pred = pred.next             succ = pred.next.next         else:             succ = self.tail             for _ in range(self.size - idx - 1):                 succ = succ.prev             pred = succ.prev.prev                  self.size -= 1         succ.prev = pred         pred.next = succ              def print_linked_list(self):         node = self.head         while node:             if node.next != None:                 print(node.data, "->", end="")                 node = node.next             else:                 print(node.data)                 node = node.next dl = DoubleLinkedList() dl.add_head("data1") dl.print_linked_list() dl.add_head("data2") dl.print_linked_list() dl.add_tail("data3") dl.print_linked_list() dl.insert("data4", 2) dl.print_linked_list() dl.delete(0) dl.print_linked_list() dl.delete(2) dl.print_linked_list() dl.delete(0) dl.print_linked_list()
ekgns119
2022.03.18
@ekgns119님이 새 포스트를 작성했습니다.
가면 갈수록 조금씩 복잡해지네요! 오늘도 조금 힘든 것 같습니다. 주말을 이용하여, 코딩테스트 과정 전체를 가볍게 둘러본 후 다시 돌아와 복습해보도록 하겠습니다. 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)
HJTN
2022.03.15
@HJTN님이
괄호 판정
포스트를 좋아합니다.
ekgns119
2022.03.14
@ekgns119님이 새 포스트를 작성했습니다.
선택 정렬
선택 정렬은 제자리 정렬 알고리즘 중 하나이다. 전체 배열에서 최솟 값을 탐색합니다. -찾아낸 최솟값을 첫 번째 위치의 데이터와 교환합니다. 맨 처음 원소를 제외한 전체 배열에서 최솟값을 탐색합니다. -찾아낸 최솟값을 배열의 두 번째 위치의 데이터와 교환합니다. 첫 번째, 두 번째 원소를 제외한 전체 배열에서 최솟값을 탐색합니다. -찾아낸 최솟값을 배열의 세 번째 위치의 데이터와 교환합니다. 모든 데이터가 정렬될 때까지 위 과정을 반복합니다. a = [9, 6, 7, 3, 5] for i in range(len(a) - 1): for j in range(i, len(a))): num = min(a[i:]) if num == arr[j]" arr[i], arr[j] = arr[j], arr[i] print(f'위치 교환이 일어남 : ", a)
ekgns119
2022.03.14
@ekgns119님이 새 포스트를 작성했습니다.
버블 정렬
버블 정렬은 기본적으로 오름차순으로 정렬하는 알고리즘이다. 인접한 두 값을 비교하여, 큰 수가 오른쪽에 있도록 값을 세팅하는 작업을 배열의 0번 인덱스부터 마지막 인덱스까지 진행한다. 이러한 과정을 한번 수행하면 배열에서 가장 큰 값이 마지막 인덱스 위치로 이동하고, 이 일련의 과정을 '스캔'이라고 부른다. 이 스캔 작업을 '모든 숫자가 정렬될 때 까지' 반복 수행하는 알고리즘이 버블 정렬이다. ex) 5 2 9 1 6 *스캔 1회 0번 인덱스와 1번 인덱스의 값을 비교한다. 0번 인덱스의 값이 1번 인덱스의 값보다 크므로, 두 수의 자리를 교체해 줍니다. 2 5 9 1 6 1번 인덱스와 2번 인덱스를 비교해, 위와 같이 큰 수가 뒤로가도록 해준다. 2 5 9 1 6 2번 인덱스와 3번 인덱스를 비교해, 큰 수가 뒤로가도록 해준다. 2 5 1 9 6 3번 인덱스와 마지막 4번 인덱스를 비교해, 큰 수가 뒤로가도록 해준다. 2 5 1 6 9 *스캔 2회 스캔 1회의 결과 배열을 그대로 사용한다. 2 5 1 6 9 0 ~ 3번 인덱스에서, 스캔 작업을 수행한다.(인접한 두 값을 비교해, 큰값이 뒤로) 2 1 5 6 9 *스캔 3회 스캔 2회의 결과 배열을 그대로 사용한다. 2 1 5 6 9 0 ~ 2번 인덱스에서, 스캔 작업을 수행한다. 1 2 5 6 9 *버블 정렬의 구현 arr = [5, 2, 9, 1, 6] length = len(arr) print(f"정렬 전 : {arr}") #배열의 크기만큼 반복 for i in range(length):   #배열의 총 크기에서, i값과 1을 뺀 만큼 반복한다.   for j in range(0, length - i -1):   #현재 j 인덱스 위치의 값이 j + 1 인덱스 위치의 값이 더 크다면     if arr[j] > arr[j+1]:       #두 값의 위치를 변경한다.       arr[j], arr[j+1] = arr[j + 1], arr[j] print(f"정렬 후 : {arr}") *버블 정렬 특징 버블 정렬은 인접한 값만 계속해서 비교하는 방식이기 때문에 구현이 쉽다는 장점이 있다. 코드가 굉장히 직관적이라, 기본 문법만 알아도 구현하는데 큰 문제가 없다. 버블 정렬은 최선과 최악 모두 O(n^2)의 복잡도를 가진다. 즉, 등차 수열의 합에 의해, 아래와 같은 연산량이 계산된다. => 배열의 개수 N = 연산량 N(N-1)/2 빅오 표기법은 상수항이 제거되므로, 'O(n^2)'의 시간 복잡도를 가지는걸 확인.
obh3705
2022.03.11
@obh3705님이
반복과 재귀
포스트에 댓글을 남겼습니다.
obh3705
2022.03.11
@obh3705님이
반복과 재귀
포스트를 좋아합니다.
ekgns119
2022.03.10
@ekgns119님이 새 포스트를 작성했습니다.
반복과 재귀
*반복과 재귀의 차이 1. 반복(Iteration) 반복은 for, while등의 반복 구문을 사용해 원하는 동작을 반복해서 수행하는 방법을 의미한다. ex) def factorial(n): fact = 1 for i in range(1, n+1) fact *= i return fact => n의 값이 변하더라도 fact 변수 하나만 사용하므로, 공간 복잡도는 O(1)이라고 할 수 있다. 2. 재귀(recursion) 재귀는 함수 내부에서 자기 자신을 다시 호출하는 방식을 의미한다. 함수 내부에서 자기 자신을 호출하기 때문에, 함수에 '종료 조건이 존재'해야 한다. while문을 사용한 무한 반복문을 생각해보면 된다. ex) def factorial(n): if n > 1: return n*factorial(n-1) else: return 1 1) factorial(4) => n이 4 이므로, 1보다 크다. return 4*factorial(3) 2) 4*factorial(3) => n이 3이므로, 1보다 크다. return 4*3*factorial(2) 3) 4*3*factorial(2) => n이 2이므로, 1보다 크다. return 4*3*2*factorial(1) 4) 4*3*2*factorial(1) => n이 1이므로, 종료조건에 해당한다. return 4*3*2*1 ** 1) , 2) , 3) 과정에선 factorial 함수를 리턴하고 있기 때문에, 즉 재귀적으로 자기 자신을 호출하고 있기 때문에 추가적인 연산이 필요했지만, 4) 과정에선 n의 값이 1이므로, 종료 조건을 만나 1을 리턴했다. if 위와 같이 종료 조건이 존재하지 않는다면...?? => RecursionError *반복 vs 재귀 1) 재귀의 장점 직관적이다. 재귀의 첫 번째 장점은 직관성이다. num이 1보다 작으면 num을 리턴하고, num이 1보다 크면 재귀 함수를 호출한다. but, 반복문은 fib배열에 초기 값을 주고, num이 1보다 크면 fib 배열에 추가적인 초기 값을 주고 반복문을 실행하는 둥.. 재귀에 비해 조금 안 읽힌다. 불필요한 변수를 줄일 수 있다. 두 번째 장점은 '변수의 개수가 줄어든다.' 라는 점이다. 반복에서 사용해야 하는 fib, i 변수는 재귀에선 사용하지 않는다. so, 재귀는 반복에 비해 읽기 쉽다. 2) 재귀의 단점 반복이 재귀보다 빠르다. 함수는 호출되고 종료되는데 들어가는 간접적인 처리 시간, 메모리 사용량이 반복문보다 크다. 따라서 for while 등을 사용하는 반복보단 재귀의 속도가 느리다. 재귀는 오류 발생의 여지가 존재한다. 재귀에서 종료조건이 존재하지 않을 때 Stack Overflow라는 오류가 발생했다.(C언어) 해당 오류가 종료 조건이 없을 때만 발생하는 것이 아니라, 재귀 함수의 깊이가 과다하면 발생하는 오류이다. 함수를 호출하게 되면 함수의 매개변수, 지역변수, 리턴값 등이 stack memory라는 공간에 저장된다. 즉, 재귀 함수를 사용하면 함수를 반복 호출하므로, stack memory에 할당된 공간 허용량을 초과하여 Stack Overflow 오류가 발생하는 것이다. *정리 속도 : 반복 > 재귀 가독성 : 반복 < 재귀 따라서, 알고리즘 설명같이 가독성이 중요한 상황이나 속도에 큰 차이가 없는 경우엔 재귀를, 재귀로 구현하면 시간복잡도가 변경되는 경우에는 반복을 사용하자
ekgns119
2022.03.09
@ekgns119님이 새 포스트를 작성했습니다.
탐색
start = 0 end = length - 1 mid = (start + end)/2; //중앙값 설정 //목표값을 찾았을 때 if(arr[mid] == target) //key 값을 찾았을 때   return 1;  //1을 리턴 //중앙값이 목표값보다 클 때 else if(arr[mid] > target) //중앙값이 목표값보다 큰 경우   end = mid - 1  // 끝 인덱스를 감소 //중앙값이 목표 값보다 작을 경우 else   //중앙값이 목표값보다 작은 경우    start = mid + 1; // 목표값이 배열 내부에 없을 경우 while(end >= start){   //...생략... } return 0; => 목표 값이 배열 내부에 없으면 시작 인덱스가 끝 인덱스보다 커지는 모순이 발생한다. 따라서 목표 값이 배열에 존재하지 않는다고 판단하고, 반복문 종료. *이진탐색 시간 복잡도 전체 데이터의 수 = N 1)첫 번째 탐색 후, 절반의 데이터가 살아남는다.  남은 데이터 : N/2 2)두 번째 탐색 후, 절반의 데이터만 살아남는다.  남은 데이터 : N/(2*2) 3)k 번째 탐색 후, 절반의 데이터만 살아남는다.  남은 데이터 : N/(2*k) 시간 복잡도를 계산할 때, 우리는 최악의 경우까지 생각해야 한다. 이진 탐색은 탐색할 배열의 데이터가 1개 남을 때까지 반복하는 게 최악의 경우이다. N/(2*k) = 1 => 2*k = N => k = log2(N) 따라서, 이진 탐색의 연산 횟수는 데이터 크기에 로그 2를 취한 것과 비례한다. 이런 경우, 시간복잡도는 O(log n)로 나타낼 수 있다. 빅오 표기법은 상수 부분을 무시하기 때문.