공부/파이썬19 [알고리즘]깊이 우선 탐색(DFS), 너비 우선 탐색 (BFS)란? 깊이 우선 탐색 (DFS Depth-First Search) 이란? 그래프에서 특정한 경로로 탐색하다 특정한 상황에서 깊은 부분을 우선적으로 탐색하고 다시 돌아가 다른 경로로 탐색하는 알고리즘이다. 그래프는 최대한 가까우면서 낮은 숫자를 가진 노드를 방문한다. DFS는 스택 자료구조를 이용하며 상세한 구조 동작은 아래와 같다. 탐색 시작할 노드를 스택에 삽입하고 *방문 처리한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있다면 그 인접 노드를 스택에 넣고 방문 처리를한다. 방문하지 않은 인접 노드가 없다면 스택에서 최상단 노드를 꺼낸다. 2번의 과정을 더 이상 할 수 없을 때까지 반복한다 *방문 처리란?: 스택에 한 번 삽입이되어 처리된 노드가 다시 삽입되지 않도록 체크하는 것을 말한다. 너비 우.. 2022. 6. 21. [알고리즘] 그래프란? 그래프(Graph)란? : 노드(Node)= (정점 Vertex)과 간선(Edge)으로 구성되어 있다. 그래프를 탐색한다라는 의미는 하나의 노드를 시작으로 다른 다수의 노드를 방문하는 것을 의미한다. 트리와 그래프는 비슷하지만 그래프는 위 B->C->E->D->B처럼 루프 형성이 가능하다. 두 노드가 간선으로 연결되어있다는 의미는 두 노드가 인접하다는 의미와 동일하다. 프로그래밍에서는 그래프는 *두가지 방식(행렬(Matrix), 리스트(List))으로 표현이 가능한데 *인접 행렬(Adjacency Matrix) 방식 : graph =[[]] *인접 리스트(Adjacency List) 방식 : graph=[ [] for _ in range(n)] 이 두 방식의 차이점은 아래와 같다 행렬 방식에서는 모든 관.. 2022. 6. 21. [자료구조]해시(HASH)란? 해시란 무엇인가? 데이터를 다루는 방법 중의 하나로써 검색과 저장이 파이썬의 키(KEY)와 밸류(VALUE)와 비슷하게 활용되며 KEY를 활용하여 값에 직접적으로 접근이 가능한 구조로, 평균 시간복잡도가 O(1)으로 빠른 기법이다. 속도가 빠를 수 있는 이유를 위 그림으로 이해해보자. 해시 테이블을 사용하지 않은 데이터 뭉치라면 필요한 값을 찾기 위해서는 배열의 데이터 값을 처음부터 하나하나 둘러보게 되는데 위의 그림처럼 해시 함수를 적용한 테이블을 사용한 형태를 사용하게 된다면 key값에 해시를 적용해 고유한 인텍스를 통해 데이터를 한번만 검색하면 되기 때문이다. 해시함수는 무엇인가? 위의 그림처럼 키를 해시테이블 내의 버킷(=hashes=해시값)으로 매핑 시키는것 입력값의 형태는 다양하고(보통 문자열.. 2022. 6. 17. [알고리즘] 퀵 정렬[Quick sort]이란? 분할 알고리즘의 하나로 평균적으로 굉장히 빠른 시간 복잡도를 갖고 있는 정렬 방법이다. 기준이 되는 데이터 값을 정하고 (이를 피벗(Pivot)이라고 칭한다.) 이를 중심으로 피벗 앞에는 피벗보다 작은 값이 오고 피벗 뒤의 값에는 피벗보다 큰 값이 온다. 이렇게 두 개의 작고, 큰 부분들을 나누는 것을 분할이라고 부르며 분할되어진 두개의 리스트에 대해 재귀적으로 이 과정을 반복하여 정렬한다. 코드는 아래와 같다. def quick_sort(li): if len(li) pivot: more.append(i) else: equal.append(i) return quick_sort(less)+equal+quick_sort(more) 2022. 6. 17. [알고리즘] 삽입 정렬(Insertion Sort) 삽입 정렬(insertion sort)란? 데이터를 하나씩 확인하면서 , 각 데이터를 적절한 위치에 삽입 하는 정렬 방법이다. 더불어 삽입 정렬은 특정한 데이터가 정렬 되기 이전에 앞까지의 데이터들은 이미 정렬 되어있다고 가정하고 그 리스트에서 적절한 위치에 삽입이 되어지는 알고리즘이다. 데이터가 필요할 때만 위치를 바꾸므로 실행시간 면에서 효율적인 정렬 방식이다. 선택 정렬과 같이 동작원리를 직관적으로 이해하기 쉬운 알고리즘이다. def insertion_sort(li): for i in range(1, len(li)): for j in range(i, 0, -1): # 인덱스 i부터 1까지 감소하며 반복하는 문법 if li[j] < li[j-1]: li[j], li[j-1] = li[j-1], li[.. 2022. 6. 13. [알고리즘] 버블 정렬 (bubble sort) 버블정렬(bubble sort) 란? 서로 이웃한 두 원소의 크기를 비교한 결과 순서대로 정렬되어 있지 않으면 교환을 반복하여 정렬을 진행하는 알고리즘이다. 구체적으로 말하자면 첫 번째 데이터와 두 번째 자료를, 두 번째 자료와 세 번째 자료를 ···· 이런 식으로 마지막 자료까지 서로 크기를 비교하여 교환하며 정렬하는 방식이다. 이렇게 첫번째 회전이 수행이 되고나면 가장 큰 자료가 맨 뒤로 가게 되며 두번째 회전부터는 맨마지막의 자료를 정렬에서 제외하고 이 과정을 반복한다. 가장 간단하지만 비효율적인 알고리즘이다. 이는 위의 예시와 같이 목록이 이미 정렬이 되어있어도 모든 항목을 검사하기 때문에 많은 시간복잡도가 걸리기 때문이다. 코드는 아래와 같다. def bubble_sort(li): n = len.. 2022. 6. 13. [자료구조] 스택(Stack)과 큐(Queue) 스택(Stack) 스택이란 나중에 넣은 데이터가 먼저 반환이 될 수 있도록 설계한 메모리 구조를 의미한다. LIFO(Last In Firt Out), 선입후출이 라고도 한다. 실생활에서의 예시는 윈도우 운영체제를 들수있다. (컴퓨터를 실행시 가장 먼저실행되고 종료시 가장늦게 꺼진다.) 파이썬으로 구현한 스택의 클래스는 아래와 같다. 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() else: return None def return_stack(self): return self.d.. 2022. 6. 8. 내장 함수 set 함수 사용법 SET 함수의 선언법 set 함수는 딕셔너리와 비슷하지만 key가 없고 값만 존재한다. set 함수는 자동으로 중복된 값을 제거해준다. set의 선언은 set([])을 이용하거나 중괄호를 선언하고 바로 값을 삽입하면 된다 아래 예시로 확인해보자. SET 함수의 이용법 set에서 원소의 추가는 add를 사용한다. set에서의 여러 값의 추가는 update를 사용한다. set에서의 제거는 remove 함수 혹은 discard 를 사용한다 이 둘의 차이는 remove는 set 함수내에 값이 없으면 오류를 보여주고 discard를 이용하면 안에 값이 없더라도 에러가 발생하지 않는다. 아래 예시를 통하여 확인해보자. 2022. 6. 1. 이전 1 2 3 다음
