본문 바로가기

Programming/Python

 (36)
[Python] Heap & Heapq Heap 그리고 Heapq 모듈 본 문서에는 자료구조 힙(Heap)과 파이썬 모듈 Heapq에 관하여 공부한 내용을 기록한다. Heap 이란? 완전 이진 트리 중 하나로 우선순위 큐를 위하여 만들어진 자료구조다. 여러개의 값들 중 최댓값 또는 최솟값을 빠르게 찾아내기 위하여 고안된 자료구조다. (역시 모든 것은 필요에 의해 만들어진다.) 힙은 일종의 반정렬 상태를 유지한다. 큰 값이 상위 레벨에 있꼬 작은 값이 하위 레벨에 존재한다. 즉, 부모 노드의 키 값이 자식 노드의 키 값 보다 항상 큰(또는 작은) 이진 트리를 의미한다. 힙은 중복된 값을 허용한다. (이진 트리는 중복 값을 허용하지 않는다.) Heap의 종류 힙은 Max Heap, Min Heap으로 나뉘어진다. MaxHeap 부모 노드의 키 값..
[Python] 인접 행렬과 인접 리스트 인접 행렬 & 인접 리스트 그래프에 대한 이해가 부족하다고 느껴 다시 공부를 진행하고 있다, 본 문서에서는 그래프를 코드로 구현하는 방법에 대하여 기재한다 알고리즘 문제를 접하다보면 Graph 문제를 심심치 않게 접할 수 있다. 이러한 문제들을 풀때는 현재 그래프의 모습을 모델링한 이후 푸는것이 일반적이다. 이 때 , 모델링한 그래프의 연결관계를 나타내는 방법은 크게 두가지로 나뉜다. 1. 인접 행렬 2. 인접 리스트 위 두가지 방법에 대해 순차적으로 살펴보도록 한다. 1. 인접 행렬 인접 행렬이란, 이름 그대로 그래프의 연결 관계를 행렬로 표현하여 이차원 배열로 나타내는 방식을 의미한다. 인접 행렬 adj[i][j] 을 아래와 같이 정의할 수 있다. adj[i][j] : 노드 i에서 j로 가는 간선이 ..
[Python] 선택 정렬, 거품 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬 정렬 - Sort 선택 정렬 - Selection Sort 설명 선택 정렬 알고리즘은 정렬되어 있지 않은 데이터 중 가장 작은 데이터를 선택하여 맨 앞부터 순서대로 정렬해 나아가는 알고리즘이다. 선택 정렬은 정렬된 값을 배열의 맨 앞부터 하나씩 채워나가게 된다. 따라서, 뒤 index 로 갈수록 비교 범위가 1씩 감소한다는 특성을 갖는다. 입력 배열이 이미 정렬되어 있거나 말거나 상관없이 동일한 연산량을 갖기 때문에 최적화의 여지가 적어 성능이 떨어지는 편이다. 루프문을 통해 모든 인덱스에 접근해야 하기 때문에 기본적으로 O(N) 시간을 소모하며, 최소값을 찾으면 현재 인덱스와 최소값을 서로 swap해야 하기 때문에 O(N) 시간을 필요로 하게 된다. 오름차순 정렬 기준으로 최소값을 찾기 위해 비교는 여..
[Python] BFS & DFS BFS & DFS BFS (Breath - First - Search)7u7jujjjuuujjjj from collections import deque # BFS (Breath - First - Search), 너비 우선 탐색 구현 graph = { # dictionary 'A': ['B'], 'B': ['A', 'C', 'H'], 'C': ['B', 'D'], 'D': ['C', 'E', 'G'], 'E': ['D', 'F'], 'F': ['E'],..
bisect Python bisect 알고리즘 문제를 풀다 보면 이진 탐색을 써야할 경우가 존재한다. 이러한 문제를 풀 때 마다 이진 탐색 알고리즘을 작성하는 것은 다소 효율적이지 못하다. 이번에는 Python의 이진 탐색 모듈, bisect에 대해 알아보도록 한다. 일반적 이진탐색 다른 언어 또는 파이썬을 이용하여도 이 기능을 모르는 경우에는 이진탐색 함수를 직접 작성한다. def bisect(a, x, lo=0, hi=None): if lo < 0: raise ValueError(&#39;lo must be non-negative&#39;) if hi is None: hi = len(a) while lo < hi: mid = (lo + hi) // 2 if a[mid] < x: lo = mid + 1 else: ..
DFS Concept & Implementation DFS (Depth Frist Search) 1. 개념 파이썬 DFS 구현 스택을 사용하여 구현 아래와 같은 그래프 예시를 통한 DFS 시뮬레이션 출력 기존 입력 새로운 입력 ( 자손 ) A A B C D D B C H I I B C H K L L B C H K K B C H H B C C B G G B B E F F E J J E E 탐색 결과 : A -> D -> I -> L -> K -> H -> C -> G -> B -> F -> J -> E 2. 구현 graph = { &#39;A&#39; : set([&#39;B&#39;, &#39;C&#39;, &#39;D&#39;]), &#39;B&#39; : set([&#39;A&#39;, &#39;E&#39;, &#39;F&#39;]), &#39;C&#..
BFS Concept & Implementation BFS (Breath First Search) 1. 개념 파이썬 BFS 구현 큐를 사용하여 구현 아래와 같은 그래프 예시를 통한 BFS 시뮬레이션 출력 기존 입력 새로운 입력 ( 자손 ) A A B C D B C D E F C D E F G D E F G H I E F G H I F G H I J G H I J H I J I J K L J K L K L L 탐색 결과 : A -> B -> C -> D -> E -> F -> G -> H -> I -> J -> K -> L 2. 구현 graph = { &#39;A&#39; : set([&#39;B&#39;, &#39;C&#39;, &#39;D&#39;]), &#39;B&#39; : set([&#39;A&#39;, &#39;E&#39;, &#39;F&#39;..
BFS&DFS DFS & BFS 개념과 구현 탐색 알고리즘과 자료구조, 직관적으로 이해하기 DFS, BFS 등의 용어는 컴퓨터공학 계열 전공자 또는 개발 관련 공부를 진행해본 사람들이라면 한 번씩은 모두들 들어보았을 것이다. 들어보긴 들어봤으나, 그 개념과 구현은 생각보다 쉽지만은 않다. 이들을 탐색할 때 쓰이는 트리와 스택 또는 큐와 같은 자료구조까지 알아야 할 것들이 너무 많기도 할 뿐더러 이러한 알고리즘을 처음 접할때는 왜 stack queue등이 필요한지 잘 와닿지 않는다. 이것부터 알아보도록 하자! 자료구조가 왜 필요해? 한 예시를 들어보자. 어떠한 게임을 진행하면서 가능한 모든 경우의 수들을 생각해보고, 그 이후의 경우의 수도 모두 확인해보고자 할 때 우리는 기억에 용이함을 위하여 메모지에 메모 또는 머리속..

티스토리툴바