본문 바로가기
728x90

AI월드/⚙️AI BOOTCAMP_Section 529

Greedy 탐욕 알고리즘 (다이나믹 알고리즘과의 비교) 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법 이렇게 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘 (결과적으로는 아닐수 있다) Greedy 와 Dynamic와의 비교 최적 부분 구조 문제를 푼다는 점에서 비교 DP 1) 문제를 작은 단위로 분할하여 해결한 후, 해결된 중복문제들의 결과를 기반으로 전체문제를 해결한다. Greedy 1) 각 단계마다 최적해를 찾는 문제로 접근한다. 2) 해결해야 할 전체문제의 갯수를 줄이기위해 개별적으로 문제를 해결해나가는 선택을 한다. 2021. 5. 26.
다이내믹 프로그래밍이란? (2) 상세 보편적 의미는 '문제의 일부분을 풀고 그 결과를 재활용하는 방법' 하나의 문제를 중복되는 서브문제로 나누어 푸는 방법 DP와 분할정복의 차이점 DP는 문제를 분할하는 경우 중복되는 서브문제가 있고, 분할정복은 분할된 서브문제가 독립적 DP는 서브문제가 같은 경우에 메모이제이션을 활용하여 같은 문제에 대해 해결할 수 있고, 분할정복은 서브문제가 다르기 때문에 메모이제이션을 활용하지 않는다. 다이나믹 프로그래밍 - (1) 중복된(반복되는) 서브문제 (Overlapping Subproblems) : 메인과 서브문제를 같은 방법(반복)으로 해결할 수 있어야 한다.(문제해결관점) - (2) 최적 부분 구조 (Optimal Substructure) : 메인문제 해결방법을 서브문제에서 구하여 재사용하는 구조여야 한다.. 2021. 5. 26.
다이나믹 프로그래밍이란? (핵심 간단정리) 재귀적으로 생각하기 + 불필요한 계산 줄이기 출처 : https://www.youtube.com/watch?v=2RwlzBDhGh4&feature=youtu.be 2021. 5. 26.
BFS, DFS 정의 _ 순회 탐색 알고리즘 BFS(breadth-first search) 너비우선탐색 BFS는 큐, 딕셔너리, 리스트, 내장함수 개념을 활용 bfs_graph = { # 그래프를 인접리스트로 표현 1: [2,3,4], 2: [1,5,6], 3: [1,6], 4: [1], 5: [6,7], 6: [5], 7: [6], } def bfs_queue(start_node): bfs_list = [start_node] queue = [start_node] while queue:#외부반복문 node = queue.pop(0) for i in bfs_graph[node]: #내부반복문 if i not in bfs_list: bfs_list.append(i) queue.append(i) return bfs_list bfs_queue(2) # 1.. 2021. 5. 25.
순회(traversal) (1) 개념 그래프 또는 트리처럼 연결된 구조에서 노드를 한 번씩 탐색, 방문하는 개념 순회의 목적은 모든 노드 또는 특정 노드를 방문하는 방법 (2) 방법 전위순회(preorder traverse) : 루트를 먼저 방문 중위순회(inorder traverse) : 왼쪽 서브트리를 방문 후 루트방문 후위순회(postorder traverse) : 순서대로 서브트리(왼쪽->오른쪽)를 모두 방문 후 루트를 방문 2021. 5. 24.
자료구조와 그래프 , data structure for design and graph (1) 그래프 : 자료구조 디자인의 한 방법 : 기본적으로 위 그림처럼 vert(노드 또는 정점)와 edge(간선)으로 연결 (2) 그래프와 트리와의 차이점 그래프는 "노드간의 관계"를 나타내며 , 트리는 "노드간의 계층"을 표현한다. (3) 그래프의 유형 - 방향성과 무방향성 (directed & undirected) - 순환과 비순환 (cyclic & Acyclic) (4) 가중그래프 : 경로의 총 가중치가 높을수록 경로이동시간(비용)이 길어진다 (5) 그래프 표현방법 - 인접리스트(adjacency lists)와 인접행렬(adjacency matrices) class Graph: def __init__(self): self.vertices = { "A": {"B"}, # 여기서 {"B"}가 set의.. 2021. 5. 24.
해시, 해시테이블, 해시충돌이란? 해시테이블이란? : 키를 활용하여 값에 직접 접근이 가능한 구조 : (파이썬의 딕셔너리는 내부적으로 해시테이블 구조) 해시(Hash)는 해시 함수를 통해 나온 값이다. 해시테이블은 키를 빠르게 저장 및 검색할 수 있는 테이블형태의 자료구조이다. 해시함수는 여러 키를 분할하기 위해 키를 해시값(정수값)으로 매칭시키는 역할을 한다. 해싱(Hashing)은 쉽게 말해서 다 흩뜨려놓고, 키와 매칭되는 값을 검색하는 과정이다 해싱의 장점 : 데이터 양에 영향을 덜 받으며 성능이 빠르다.(키를 통해 값을 검색한다.) 해시함수 해시충돌 해시충돌이 발생하는 이유는? 가능한 모든 데이터를 알고 있지 않으면 완벽한 해시 함수를 작성하는 것은 불가능 해시충돌은 키가 들어갈 자리(버킷)가 없는 경우에 발생 충돌이 적은 해시함.. 2021. 5. 21.
메모이제이션(Memoization) 분할된 서브문제를 해결하기 위해, 반복되는 해결법을 재사용하는 기법 미리 계산한 값을 재사용하므로 프로그램 실행속도를 빠르게 해준다 방법 : 반복되는 계산 결과를 특정 변수에 저장 ################################ memoization을 사용하지 않은 재귀의 경우 ################################ def recursive_factorial(n): # 최상위 호출 if n is 0: return 1 else: return n * recursive_factorial(n - 1) # 함수 내부 print(recursive_factorial(10)) print(recursive_factorial(4)) # 해석 n=5 를 호출, 수행한 뒤 n=4를 호출할때 fa.. 2021. 5. 18.
분할정복(Divide and conquer),퀵정렬,병합정렬과 재귀(Recursion) 분할정복과 재귀 분할정복 : 복잡하거나 큰 문제를 여러 개(병렬적으로)로 나눠서 푸는 방법 분할정복 방법 진행중에 재귀가 사용될 수 있다. 분할정복과 재귀 코드비교 # 재귀 : 1부터 10까지의 합 def func(num): if num < 1: return 0 else: return num + func(num-1) func(10) ########################## # 분할정복 : 1부터 10까지의 합 def func(num): if num == 1: return 1 if num % 2 == 1: return func(num - 1) + num else: return func(num / 2) * 2 + (num / 2) * (num / 2) func(10) 퀵정렬과 병합정렬의 비교 퀵정렬 .. 2021. 5. 18.
선택정렬, 삽입정렬, 버블정렬 선택정렬 왼쪽부터 가장 작은 노드와 비교하면서 교환 즉, 최소노드 선택 -> 왼쪽부터 비교 -> 교환 삽입정렬 아직 정렬되지 않은 특정 노드와 정렬된 노드들의 값을 비교하고 , 값이 더 큰 것의 인덱스보다 작은 인덱스에 삽입하며 정렬하는 알고리즘 선택정렬과 비슷하지만, 값이 가장 작은 원소를 선택하지는 않는다. 삽입정렬은 소량의 데이터를 정렬하기위한 효율적인 알고리즘 버블정렬 서로 이웃한 두 원소의 크기를 비교한 결과에 따라 교환을 반복하는 알고리즘 (단순 교환 정렬이라고도 함) 버블정렬은 옆에 있는 이웃노드만 교환하므로 안정적 # 버블정렬 소스코드 def bubble_sort(li): length = len(li) - 1 >> for i in range(length): # 외부 반복문(아래 그림에서 전.. 2021. 5. 17.
탐색 알고리즘(선형검색, 이진검색) 선형 검색 선형 검색은 기본적인 검색 알고리즘으로 한 번에 하나씩 모두 검색 처음부터 하나씩 체크하면서 검색하는 가장 기본적인 검색 def linear_search(linear_arr, search_number): for i in range(len(linear_arr)): if linear_arr[i] == search_number: return i linear_arr = [5,22,87,1,3] search_number = 1 print("search index : ",linear_search(linear_arr, search_number)) 이진 검색 숫자를 반으로 줄이면서 검색을 진행하기 때문에 선형보다 속도가 더 빠르다. 이진 검색 방법은 데이터가 이미 정렬된 경우에만 작동 def binary_s.. 2021. 5. 17.
정렬알고리즘의 필요성과 버블소트(거품정렬)의 이해 정렬이 필요한 이유 왜? 시각적으로 보기 좋은것 뿐만 아니라 탐색시간을 줄여줌 버블소트 (거품정렬)의 이해 두 숫자를 비교, 큰 숫자를 오른쪽으로 스왑하면서 정렬된다. 그 모습이 마치 거품이 올라오는 모습과 같이 버블소트라 불림 출처 : https://www.youtube.com/watch?v=nqNPYD3wo-4 출처 : https://www.youtube.com/watch?v=RCnyz-Bfkmc 2021. 5. 17.
이진트리 손코딩 class binary_search_tree: def __init__(self, head): self.head = head # 노드삽입 def insert_node(self, value): self.base_node = self.head while True: #True가 될때까지 돌려라 if value < self.base_node.value: # head값 , 즉 기준값이 입력값보다 클때 # 입력값은 왼쪽노드로 붙어야한다 if self.base_node.left != None: # 왼쪽노드에 뭔가 있다면 self.base_node = self.base_node.left # 왼쪽노드를 기준값으로 밀고 한바퀴 더 돌아보자 else: # # 입력값은 기준값의 왼쪽노드로 설정 self.base_node.lef.. 2021. 5. 14.
Tree의 구조 Tree의 종류 Array , linkedlist, stack, queue 말고 트리구조는 부모,자식 구조 그중 바이너리트리 바이너리트리와 바이너리 서치 트리가 있으며 바이너리 서치 트리는 오른쪽 노드값들은 현재값보다 크게 이루어져 있다 왼쪽은 반대로 작은 값들로 이루어져있다 밸런스 좌우대칭이 무조건 완벽하게 맞기 보다는 적절하게 좌우대칭이 되어있으면 밸런스가 맞다 라고 한다 완전이진트리 왼쪽부터 차례대로 채워져 있으면 완전이진트리 풀 바이너리 트리 자식노드가 아예 없던지, 있으려면 2개가 꽉 채워져 있어야 하는 트리 퍼펙 바이너리 트리 완벽한 트리 출처 : https://youtu.be/LnxEBW29DOw 2021. 5. 14.
재귀함수란? 추상적인 실체하지 않는 구체적이지 않은 걸 수학적 귀납법처럼 귀납방식으로 접근하는 것 재귀함수란 자기 자신을 호출하는 함수 종료 조건이 만족할때까지 반복적으로 호출 출처 : https://www.youtube.com/watch?v=a4Qy4tSadSI 출처 : https://www.youtube.com/watch?v=aPYE0anPZqI 2021. 5. 14.
ADT(추상자료형)와 자료구조 (2) (스택) Stack(스택) 동적으로 처리되는 것이 특징 class Stack: def __init__(self): self.data = [] # 동적처리(리스트값이 정해져있지 않음, 대괄호만 선언 및 저장) class Stack: def __init__(self): self.data = [] def push(self, item): self.data.append(item) def pop(self): if len(self.data) > 0: return self.data.pop() return "The stack is empty" #연결리스트를 활용하여 스택을 구현한 방법 class LinkedListNode: def __init__(self, data): self.data = data self.next = None.. 2021. 5. 13.
ADT(추상자료형)와 자료구조 (1) (연결리스트,큐) 핵심 : ADT(Abstract Data Type)와 연결리스트, 큐, 스택 앞 장에서는 파이썬의 기본자료형(숫자, 문자열, 리스트, 딕셔너리 등)에 대해 배움 ADT는 추상적으로 필요한 기능을 나열한 일종의 명세서(로직) ADT는 기본자료형(대표적으로 리스트, 숫자, 문자열)을 활용하여 사용자에 의해 구현 (즉 프로그래머의 설계에 따라 자유롭게 구성됨) linked-list(연결리스트) 연결은 프로그래밍에서 참조의 기능으로 구현됨 연결리스트는 리스트의 길이를 별도로 지정해줄 필요없다. 연결리스트는 별도의 인덱스를 지정할 필요없이 연결되는 구조 연결리스트의 각 요소는 참조하는 노드에 저장 # 연결리스트의 노드를 저장하는 첫 단계 class Node: def __init__(self,value,next=N.. 2021. 5. 13.
Data Structure. 자료구조 최종목적!! 자료구조와 알고리즘을 이해하며 프로그래밍하는 것 자료구조란 자료를 쉽게 관리하기 위해 다양한 구조로 묶는 것 자료구조는 왜 생겨났는가 ? 실생활에서 발생하는 대용량의 다양한 데이터를 효율적으로 처리(저장)하기위해 (아직 대용량의 다양한 데이터를 다뤄본적이 없기 때문에 그 필요성을 느끼지 못하지만, OOP도 마찬가지로 효율적으로 관리하고 다른 프로그래머들과 소통하기 위함이라 판단된다) 자료구조의 다양한 활용 프로그래밍 언어별로 다양한 자료형이 생겨났고, 파이썬에서는 리스트와 튜플을 통해 자료구조의 기본인 배열을 구현할 수 있게 되었다. 여기서 배열이란? 각각의 변수를 하나의 변수에 여러 개의 인덱스로 묶는 것 파이썬에서는 배열을 리스트와 튜플로 구현하고 활용 자료구조와 효율성 Big O 표기법.. 2021. 5. 13.
데이터 스트럭처란? (비유활용, 오리엔테이션) 현신을 프로그래밍적으로 "표현"하는 것 트리구조 SET 구조 (밴다이어그램) 그래프 구조 ... "큰" 데이터를 효율적으로 관리하는 것 데이터스트럭처를 왜 공부해야하지? 이해도 안되고 공감도 안될 수있다 포기하지말고 정기적으로 다시 돌아와서 유보하자 출처 : www.youtube.com/watch?v=OH7prOt3vQA 2021. 5. 13.
객체지향 프로그래밍이 뭔가요? 지금까지 한 코딩들은 규모가 크지않아서 크게 필요성을 느끼지 못한 방법이지만 규모가 큰 프로그래밍을 할때는 사용하게 되는 방법 데이터와 기능이 클래스로 '캡슐화'된 컴퓨터 자원의 묶음을 "객체"라고 한다 클래스라는 모양틀을 만들어서 흙을 모양틀에 넣고 구우면 모양과 용도가 뚜렷한 벽돌이 나오듯이 {은닉성} 내부 구조는 private하게 감춰놓고 외부에서 조작할 수 있는 명령어만 public으로 공개해 놓는 것 {상속} 부모클래스에서 메소드를 물려받고, 필요한 부분만 추가해주면 된다 (비교적 추상적인 부모클래스에서 구체적인 자식클래스를 만든다) {다형성} 부모클래스에서 정의된 메소드의 작업이 자식클래스에서 다른걸로 override 대체될수있다는 걸 다형성이라 한다 {상속과 인터페이스} 상속은 트리구조의 상.. 2021. 5. 11.
728x90

티스토리툴바