Algorithm
[1028 알고리즘 22] 유클리드호제법 : 최댓값 구하기
# GCD # GCD : Greatest common divisor : 최대공약수 # 유클리드 호제법 # : a,b에 대해 a를 로 나눈 나머지를 r이라 하면 # a,b의 최대 공약수는 b와 r의 최대 공약수와 같다. # a b # 192 162 # 162 30 # 30 12 # 12 6 >> 최대 공약수 6 def gcd(a, b): print("---" + str(a) + ", " + str(b)) if a % b == 0: return b else: return gcd(b, a % b) print(gcd(192, 162)) 출처 https://youtu.be/7C9RgOcvkvo
[1028알고리즘 FROM 동빈나 21]그래프 탐색 : DFS vs BFS
DFS Depth-first search : 깊이 우선탐색 - 스택(선입후출, 바구니, append, pop), 재귀함수로 구현 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2. 스택의 최상단 노드에 방문하지 않는 인접한 노드가 하나라도 있으면 >>>>>>>>파이썬 : https://youtu.be/7C9RgOcvkvo graph = [ [], [2,3,8], [1,7], [1,4,5], [3,5], [3,4], [7], [2,6,8], [1,7] ] visited = [False] *9 dfs(graph, 1, visited) bfs(graph, 1, visited) GFS BFS 1>2>3 넣었다 꺼냄 > 1>2 1>4>5 넣었따 꺼냄 1>4>6 ... from __future__ imp..
[1028알고리즘 20]Dynamic Programming
피보나치 수열. _ 재귀함수. 1,1,2,3,4,8 1 + 1 = 2 fibo(1)=1 fibo(2)= 1 fibo(3) =fibo(1)+fibo(2) fibo(n) = fibo(n-2) + fibo(n-1) 같은 계산을 N^n 반복. 결과를 기록해서 이용. = 메모이제이션 Memoization 문제를 쪼갤수 있는 구조= 겹치는 부분문제 = Overlapping subproblem. input = 100 # memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다! memo = { 1: 1, 2: 1 } # Top Down 방식. 반대는 바텀업 def fibo_dynamic_programming(n, fibo_memo): if n in fibo_memo: return fibo_memo[n]..
[1028알고리즘 19]해쉬
해쉬 테이블 : "키", "데이터"를 저장함으로써 즉각적으로 데이터를 받아오고 업데이트 하고 싶을 때 사용하는 자료구조 해쉬함수 : 임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 해쉬값을 출력하는함수입니다. 해쉬 테이블의 내부 구현은 키를 해쉬 함수를 통해 임의의 값으로 변경한 뒤 배열의 인덱스로 변환하여 해당하는 값에 데이터를 저장합니다. 만약, 해쉬 값 혹은 인덱스가 중복되어 충돌이 일어난다면? 체이닝과 개방주소법으로 해결. items = [None]*8 hash("가") %86 hash("나")%8 5 items[hash("가") %8]="가위" items[hash("나") %8]="나비" 결과 :: items[None, None, None, None, None, '나비', '가위', None..
[1028알고리즘 18]정렬
정렬 데이터를 순서대로 나열하는 방법을 의미합니다. 버블정렬 앞뒤 숫자 비교해서 정렬: 1st 와 2nd, 2nd와 3nd, 3nd와4th 와 비교 input = [10, 4,2] def bubble_sort(input): n = len(input) for loop1 in range(n - 1): for loop2 in range(n - 1 - loop1): print(loop2, loop2 + 1, input) if input[loop2] > input[loop2 + 1]: input[loop2], input[loop2 + 1] = input[loop2 + 1], input[loop2] return input print(bubble_sort(input)) 선택정렬 선택해서 정렬. : 가장 작은 숫자를 ..
[1028알고리즘 17]재귀함수(Recursive function)
팩토리얼 def factorial(n): if n == 1: return 1 ##print(">>", n) return factorial(n - 1) * n print(factorial(5)) 회문(palindrome) 은 순서를 거꾸로 읽어도 제대로 읽은 것과 같은 단어와 문장을 말합니다. 한 글자도 회문 ex) 토마토, 오디오 def is_palindrome(string): string_len = len(string) if string_len
[1028알고리즘 16]이진탐색 vs 순차탐색
이진 탐색 알고리즘의 장점 선형 탐색과 비교하여 탐색 시간이 빠르다. (선형 탐색의 경우 시간 복잡도는 T(n) = θ(n)이다. ) 이진 탐색 알고리즘의 단점 정렬된 리스트에서만 사용될 수 있다. 순차탐색의 시간복잡도는 O(n) 이진탐색의 시간복잡도는 O(logN) 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_Sequential(target, array): find_count = 0 for idx in range(len(finding_numbers)): find_count += 1 if finding_numbers[idx] ==..
[1028알고리즘 15]트리, 힙
트리 계층형 비선형 자료구조.(큐, 스택 : 선형구조) Node : 트리에서 데이터를 저장하는 기본요소 Root Node : 트리 맨 위에 있는 노드 Level: 최상위 노드를 Level 0으로 하였을때 하위 B 브렌치로 연결된 노드의 깊이 Parent Node: 어떤 노드의 하위 레벨에 연결된노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node(Terminal Node) Child Node가 하나도 없는 노드 Sibling : 동일한 Parent Node를 가진노드 *자매 형제 시빌링 Depth: 트리에서 Node가 가질 수 있는 최대 Level 이진트리, 이진 탐색트리, 균형트리(AVL, red-black), 이진힙(최대힙, 최소힙) 이진트리 노드가 최대 두 개의 자식을..
[1028알고리즘 14]그래프
그래프 연결되어 있는 정점과 정점간의 관계를 표현할수 있는 자료구조. 선형구조는 자료저장, 꺼내는것, 비선현구조는 표현에 초점. 그래프는 연결관계에 초점. 그래프는 유방향(Directed Grape)과 무방향(undirected Grape) 그래프 두가지가 있음. 1) 인접행렬(Adjacency Matrix) 2차원 배열로 그래프의 연결 관계를 표현 0 1 2 3 0xOxx 1OxOx 2xOxO 3xxOx graph = [ [false, true , false, false] [true, false, true, false] [false, true, false, true] [false, false, true, false] ] 2) 인접리스트(Adjacency List) 링크드 리스트로 그래프의 연결관계를 표..
[1028알고리즘 13]탑송신
#[6, 9, 5, 7, 4] →[0, 0, 2, 2, 4] # 4 는 4번째에서 수신 # 7은 2번째에서 수신 # 5는 두번째에서 수신 # 9는 수신안됨 # 6은 수신안됨 top_heights = [6, 9, 5, 7, 4] def get_resive_top_order(heights): result = [0]* len(heights) while heights: height = heights.pop() for idx in range(len(heights)-1,0,-1): print(idx) if heights[idx] > height: result[len(heights)] = idx +1 break return result print(get_resive_top_order(top_heights))
[1028알고리즘]Queue - JAVA
import java.util.HashMap; import java.util.Map; Map wants_dic = new HashMap(); wants_dic.put(1, 1); System.out.println(wants_dic.get(1)+1); import java.util.LinkedList; import java.util.Queue; Queue queue = new LinkedList(); System.out.println(queue.add(1)); System.out.println(queue.peek()); System.out.println(queue.poll()); System.out.println(queue.add(1)); System.out.println(queue.add(2)); Sys..
[1028알고리즘 12] 큐 구현
노드구현 큐 의 초기화 구현 * head, tail 큐의 enqueue data 마지막에넣음 큐의 dequeue 처음에서뺌 큐의 peek 큐의 isEmpty() class Node: def __init__(self, data): self.data = data self.next = None class Queue: def __init__(self): self.head = None self.tail = None def isEmpty(self): return self.head is None def enqueue(self,data): new_node = Node(data) if self.isEmpty(): self.head = new_node self.tail = new_node return self.tail.n..
[1028알고리즘 11] 스택구현
노드생성 스택의 push _입력 스택의 pop _ 빼내기._head 스택의 peek_맨앞데이터 보기 스택의 isEmpty() 스택이 비어있는지 여부. class Node: def __init__(self, data): self.data = data self.next = None class Stack: def __init__(self): self.head = None def push(self, value): next_node = self.head self.head = Node(value) self.head.next = next_node def pop(self): return_node = self.head if self.is_empty(): print("비었음") return self.head = retur..
[1028알고리즘 10]스택 vs 큐
스택 : Last in First out : 한쪽 끝으로만 자료를 넣고 뺼 수 있는 자료구조. 했떤 행동 순서기억할때 유리. push : 맨 위에 데이터 넣기 pop 맨위의 데이터 뽑기 peek 맨위의 데이터 보기. isEmpty 스택이 비어있는지 여부 반환. stack = [] # 빈 스택 초기화 stack.append(4) # 스택 push(4) stack.append(3) # 스택 push(3) top = stack.pop() # 스택 pop print(top) # 3! 스택구현 큐 First in First out enqueue(data) 맨 뒤에 데이터 추가. : tail 에 추가. dequeue() 맨앞에 데이터 뽑기 : head 에 서 뺌 peek() 맨앞의 데이터 보기 isEmpty()큐가..
[1028알고리즘 09]링크드리스트 구현
node 구현 _ data, next 링크드리스트 init _head 링크드리스트 append 링크드리스트 프린트 all 링크드리스트 get Node_index 링크드리스트 add Node index value 링크드리스트 delete Node index class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self, value): self.head = Node(value) def __len__(self): cur = self.head list_len = 1 while cur.next is not None: list_len += 1 cur = cur.next return li..
[1028알고리즘 08]배열 vs 링크드리스트
배열 링크드리스트특징 배열 링크드리스트 정의 같은 종류의 데이터들이 순차적으로 저장되는 자료구조 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다 특정원소 조회 원소에 즉시 접근 0부터 시작하는 인덱스 존재O(1) 리스트 특정원소 접근시 연결고리를 따라 탐색 O(N) 원소를 삽입/삭제 O(n) O(1)의 시간복잡도 앞뒤 포인터만 변경 원소 새로 추가 모든 공간 다 차면 새로운 공간 할당 모든 공간 다 차도 맨 뒤에 노드만 동적추가 특징 크기가 정해진 데이터 공간, 변경 불가,데이터 접근하는 경우가 빈번하면 Array 리스트는 크기가 정해지지 않은 데이터 공간삽입 삭제 빈번하면 LinkedList python 배열은 list 라고 부름 append 를 함 ..
[1028알고리즘 07]최소변경횟수
#Q. 0과 1로만 이루어진 문자열이 주어졌을 때, 이 문자열에 있는 모든 숫자를 전부 같게 만들려고 한다. 할 수 있는 행동은 문자열에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다. # 예를 들어 S=0001100 일 때,전체를 뒤집으면 1110011이 된다. # 4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다. # 하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다. # 주어진 문자열을 모두 0 혹은 모두 1로 같게 만드는 최소 횟수를 반환하시오. input="01110" def fin..
[1028알고리즘 06] 정수입력 시 그 이하 소수 출력
제곱근 이하만 계산하면된다 : 18의 약수 3*6, 6*3 도 됨.. 제곱근 이하만 확인하면 OK 설명 참고 >> www.it-note.kr/308 # 005 정수입력시 그이하 소수 출력 number = 20 # 소수 : 약수가 1과 자기자신밖에 없는것. # N이 N의 제곱근보다 크지 않은 어떤소수로도 나눠지지 않는다. def find_prime_list_under_number(number): prime_list = [] count = 0 for n in range(2, number + 1): for i in prime_list: count += 1 if n % i == 0 and i * i
[1028알고리즘 05] 반복되지 않은 첫번째 문자출력
# Q. 다음과 같이 영어로 되어 있는 문자열이 있을 때, 이 문자열에서 반복되지 않는 첫번째 문자를 반환하시오. 만약 그런 문자가 없다면 _ 를 반환하시오. # "abadabac" # 반복되지 않는 문자는 d, c 가 있지만 "첫번째" 문자니까 d를 반환해주면 됩니다! import re #input = "abadabac" input = "abab" def find_not_repeating_first_character(input): ascii_a = ord("a") ascii_z = ord("z") occured_alphabet = [0] * (ascii_z - ascii_a + 1) # print(ord("z")-ord("a")+1) input_param = input.lower() input_para..
[1028알고리즘 04] 곱하기 or 더하기 선택 가장큰수는?
#Q. 다음과 같이 0 혹은 양의 정수로만 이루어진 배열이 있을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 '✕' 혹은 '+' 연산자를 넣어 결과적으로 가장 큰 수를 구하는 프로그램을 작성하시오. #단, '+' 보다 '✕' 를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서 순서대로 이루어진다. input = [0, 3, 5, 6, 1, 2, 4] # 1이하는 더하고 크면 곱한다. def find_max_plus_or_multiply(input): result = input[0] for idx in range(1,len(input)): if input[idx] >= 1 : result += input[idx] else: result *= input[idx] return..
[1028알고리즘 03] 최빈값(가장많은빈도) 찾기
# 002 최빈값 찾기, 최빈값==가장많은 빈도 import re input = "I'm Going To Live Every Minute Of It." # 정규 표현식(正規表現式, 영어: regular expression, 간단히 regexp[1] 또는 regex, rational expression) def find_max_occured_alphabet(input): ascii_a = ord("a") ascii_z = ord("z") occured_alphabet = [0] * (ascii_z - ascii_a + 1) # print(ord("z")-ord("a")+1) input_param = input.lower() input_param = re.sub("[^a-z]", "", input_param..
[1028알고리즘 02] 최댓값 찾기
# 001 최대값을 찾아라 input = [1, 2, 4, 6, 7, 8, 9] def find_max_num(input): max_num = input[0] for idx in range(1,len(input)): if max_num < input[idx]: max_num = input[idx] return max_num print(find_max_num(input))
[1028알고리즘 01] 기본용어
알고리즘 어떤 문제의 해결을 위하여 입력된 자료를 토대로 하여 원하는 출력을 유도해내는 규칙의 집합 시간복잡도 입력한 값과 해결한 시간과 상관관계 공간복잡도 입력한 값과 해결한 공간과 상관관계 cf) 알고리즘의 성능은 시간보다 공간 희생이 더 좋은방법 점근표기법 asymptotic notation 어떤 함수의 증가양산을 다른 함수와 비교로 표현하는 추론과 해석의 방법 빅오 Big-O O(n) 최악의 성능 빅오메가 Big-Ω Ω(n) 최선의 성능