반응형 Computer Science/Data Structure12 [자료구조] DFS 정복을 위한 재귀 연구 프로젝트 재귀함수를 빠르게, 쉽게 작성하려면 어떻게 해야 할까?? 문제마다 재귀함수로 접근을 하려고 하면 항상 머릿 속이 하얘지고 머리가 아파오기 때문에 많은 분석을 통하여 나름의 작성 법칙을 만들어 보기로 했다. 여러 dfs 문제 코드를 보면서 그 속에서 공통점을 찾아보자. 재귀를 작성할 때 헷갈리는 것들 - while을 쓸지 if를 쓸지 - while을 쓸지 for를 쓸지 - return을 쓸지, return으로 무엇을 넘겨줄지 - 재귀함수로 무슨 인자를 넘겨줄 것인가 - 백트래킹을 어떻게 할것인가? 즉 말단 노드에서 어떻게 처리할 것인가 연구(계속 업데이트 중) - 재귀함수에서 while을 쓰면 엄청 복잡해짐 - 재귀함수는 보통 while 보다는 for/if 안에 들어있음 / 아님 아예 밖에 있거나 - 백트.. 2021. 4. 4. [자료구조] 그래프- 깊이우선탐색(dfs)와 너비우선탐색(bfs) 구현 ** '파이썬 알고리즘 인터뷰(박상길 저)' 내용을 참고하여 작성하였습니다. 그래프: 객체의 일부 쌍들이 '연관되어' 있는 객체 집합 구조 오일러 경로: 모든 간선을 한번씩 방문(= 한붓 그리기) 해밀턴 경로: 모든 정점을 한번씩 방분 그래프 순회: 그래프 탐색이라고도 불리며 그래프의 각 정점을 방문하는 과정 그래프 순회에는 깊이우선탐색(Depth-First Search)와 너비우선탐색(Breadth-First Search)가 있다. 일반적으로 DFS가 BFS에 비해 더 널리 쓰인다. DFS - 스택이나 재귀로 구현. 백트래킹을 통해 뛰어난 효용을 보인다. BFS - 큐로 구현한다. BFS는 재귀로는 구현 불가능. * 백트래킹: 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 .. 2021. 4. 3. [자료구조] 해시테이블의 개념- 개별 체이닝, 오픈 어드레싱 방식 해시테이블: 해시테이블 또는 해시맵은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추상 자료형을 구현하는 자료구조다. 해시테이블의 핵심은 해시함수다. 해시함수란 임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수를 말한다. 해시테이블을 인덱싱하기 위해 이처럼 해시 함수를 사용하는 것을 해싱이라고 표현한다. 해싱은 정보를 가능한 빠르게 저장하고 검색하기 위해 사용. 즉, 최적 검색이 필요한 분야에 사용한다. # 좋은 해시함수의 특징 - 해시 함수 값 충돌의 최소화 - 쉽고 빠른 연산 - 해시 테이블 전체에 해시값이 균일하게 분포 - 사용할 키의 모든 정보를 이용하여 해싱 - 해시테이블 사용 효율이 높음 충돌 처리에는 두가지 방법이 존재한다. 개별체이닝 방식과 오픈 어드레싱 방식 개별체이.. 2021. 4. 3. [자료구조] 큐queue 정의 및 데크deque와 힙큐heapq 사용법 큐는 시퀀스의 한쪽 끝에는 엔티티를 추가하고, 다른 반대쪽 끝에는 제거할 수 있는 엔티티 컬렉션이다. 큐는 FIFO(First-In-First-Out) 선입선출의 구조를 가진다. 간단히 말하면 선착순이다. 맛집에서 줄을 서는 것과 같다. 큐는 스택과 마찬가지로 리스트로 큐의 모든 연산을 구현할 수 있다. 하지만 동적 배열인 리스트는 큐연산에 적합하지 않아서 데크(deque)라는 별도의 자료형을 써야 좋은 성능을 낼 수 있다. 데크 : 더블엔디드큐(Double Ended Queue)의 줄임말로, 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상자료형이다. 데크는 pop( )과 popleft( ) 모두 시간복잡도 O(1)을 가지므로 매우 성능이 좋은 자료형이다. import collections .. 2021. 3. 31. [자료구조] 스택(stack) 정의 및 사용법 스택: 요소의 컬렉션으로 사용되는 추상 자료형이다. 주요 연산으로 push( )와 pop( )이 있다. 스택은 LIFO(Last-In-First-Out) 후입선출 구조를 가진다. 이는 쌓아둔 접시를 떠올리면 쉽게 알 수 있다. 접시는 가장 위에 있는, 즉 가장 나중에 쌓아올린 접시부터 꺼내 사용한다. 프링글스를 가장 나중에 들어간 것부터 먹는 거랑 같은 원리. 리스트가 스택의 모든 연산을 지원한다. 연결리스트를 아용하여 스택을 구현할 수 있지만, 리스트가 스택의 모든 연산을 지원하기 때문에 리스트를 그냥 쓰면 된다. Class Node: def __init__(self, item, next): self.item = item self.next = next Class Stack: def __init__(se.. 2021. 3. 31. [자료구조] 연결리스트(리스트 변환, 뒤집기) by 파이썬 연결리스트는 데이터 요소의 선형 집합으로, 데이터의 순서가 메모리에 물리적인 순서대로 저장되지는 않는다. 특징 - 동적으로 새로운 노드를 삽입하거나 삭제하기 간편 - 배열과 달리 특정 인덱스에 접근하기 위해서는 전체를 순서대로 읽어야 하므로 상수시간에 접근할 수 없다. 즉 탐색에 O(n)이 소요. 반면 시작 또는 끝 지점에 아이템을 추가/삭제/추출하는 작업은 O(1)에 가능 유용하게 쓰일 코드 스니펫들을 작성해보았다. Class ListNode(): def __init__(self, val=0, next =None): self.val = val self.next = next # linkedList --> List def nodeToList(head): lst = .. 2021. 3. 29. 이전 1 2 다음 반응형
