minzzl

안녕하세요! 오늘은 파이썬 set 에 대해 정리해보겠습니다 ! 사실 지금껏 알고리즘 문제를 풀며 set()을 사용했던 경험은 별로 없는데요 .. 굳이 사용할 필요성을 못느꼈기 때문입니다 ㅎㅎㅎ ... 그런데 특정한 경우 set을 사용하면 연산이 빨라진다는 것을 확인했고 .. 그래서 이렇게 정리해보려고 합니다 ! x in s 제가 말한 특정한 경우는 x in s 연산입니다. 리스트에서 x in s 연산의 평균 시간 복잡도 : O(n) 세트에서 x in s 연산의 평균 시간 복잡도 : O(1) 이렇게 세트 연산에서 더욱 효율적인 이유는 무엇일까요? 파이썬의 set이 해시 테이블로 구현되어있기 때문입니다. 해시 테이블을 이해하려면 우선 해시 함수를 이해해야합니다. 해시 함수는 임의의 데이터를 인자로 받아, 특..

안녕하세요! 오늘은 Minimum spanning tree 에 대해서 정리해보려고 합니다. 저는 ... 아는게 없는 감자이기 때문에 .. https://victorydntmd.tistory.com/98 [알고리즘] MST(1) - 최소 신장 트리(Minimum Spanning Tree) 1. 최소 신장 트리 ( Minimum Spanning Tree )최소 신장 트리( MST )란, 주어진 그래프에서 최소한의 비용으로 트리를 만드는 것을 의미합니다.이전 글에서 살펴봤던 BFS, DFS는 각 규칙에 따라 모든 정점들 victorydntmd.tistory.com 해당 블로그를 참고하여 작성했습니다 !! 늘 모든 블로거분들에게 감사합니다 !!! 1. 최소 신장 트리란 최소 신장 트리 (Minimum Spann..

안녕하세용 오늘은 깊이 우선 탐색과 넓이 우선 탐색에 대해 공부해볼텐데요, 우선 깊이 우선 탐색입니당 그래프 탐색 하나의 정점으로 부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 ex) 특정 도시에서 다른 도시로 갈 수 있는지 없는지, 전자 회로에서 특정 단자와 단자가 서로 연결되어 있는지 깊이 우선 탐색(DFS, Depth-First Search) 깊이 우선 탐색이란 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하기 탐색하는 방법 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳으로부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사하다. BFS는 넓게..

안녕하세용 방금 전 stack과 queue를 끝냈습니당 ! 오늘은 Heap에 대해 집중 탐구 해 볼 예정입니당 힙에 대해 알기 전, 우리는 우선 순위 큐를 알아야합니다. https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html [자료구조] 힙(heap)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 해당 글을 보고 작성을 하였습니다! (작성자님 감사합니다 !!) 우선순위 큐 Priority Queue 우선 순위 큐란, 우선순위의 개념을 큐에 도입한 자료구조입니다. 데이터들이 우선순위를 가지고 있고 우선 순위가 높은 데이터들이 먼저 나갑니다. 자료구조 삭..

안녕하세요! 오랜만에 글을 쓰네요 :) 이런 저런 핑계들로 미루어왔다가.. 다시 돌아왔습니다 ^^ 거부해봐야 뭐하겠습니까 ~ 해야죠 ... 본론으로 들어가보겠습니다. 저는 지난번 이어나가던 프로그래머스 스택/큐 부분의 문제를 풀고 있습니다. 덱이 좋다라는것을 익히 들어왔지만, 뭔가 그냥 리스트를 써서도 queue 나 stack 의 형태로 문제를 풀 수 있었기 때문에 귀찮아서 굳이 덱을 쓰지 않았었습니다. 그런데 ... 문제의 난의도가 올라가니, 시간 초과나 효율성 부분에서 큰 차이를 보이는 것을 몸소 느꼈습니다 ...^^ 그래서 오늘은 덱에 대한 정리를 해보겠습니다! dequeue 이름은 큐와 비슷해보입니다. Dequeue 는 A Double-ended Queue 입니다. Double-ended 는 양끝..

안녕하세용 드디어 hash를 끝냈습니다람쥐 오늘은 스택/큐입니동동동 스택 Stack Stack은 쌓아올린다는 뜻입니다. 스택 자료구조는 데이터를 차곡 차곡 쌓어올린 형태의 자료구조입니다. 스택 특징 스택은 같은 구조와 크기의 자료를 정해진 방향으로 쌓을 수 있고, top으로 정한 곳을 통해서만 접근할 수 있습니다. top에는 가장 위에 있는 자료는 가장 최근 들어온 자료를 가리키고 있으며, 삽입되는 새 자료는 top이 가리키는 자료의 위에 쌓이게 됩니다. 스택에서 자료를 삭제할 때도 top을 통해서만 가능합니다. 스택에서 top을 통해 삽입하는 연산을 "push", top을 통한 삭제를 하는 연산을 "pop"이라고 합니다. 따라서 스택은 시간 순서에 따라 자료가 쌓여서 가장 마지막에 삽입된 자료가 가장 ..