minzzl

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

안녕하세용 오늘 dp 로 넘어가는 역사적인 날입니당 물론 익숙하지 않은 문제 접근 방식에 혼자서 풀지는 못했지만 ... 시도 해봤다는 것만으로도 너무 행복한 날입니당 ㅎㅎ * 제가 작성해가는 풀이는 아래의 블로그를 참고한것입니당 * https://gurumee92.tistory.com/164 프로그래머스 문제 풀이 N으로 표현 이 문제는 이시윤 강사님의 프로그래머스 강좌 "파이썬을 무기로, 코딩테스트 광탈을 면하자!"를 보고 정리한 내용입니다. 문제 URL N으로 표현 Contents 문제 지문 파악하기 강사님의 알고리즘 풀 gurumee92.tistory.com 문제 풀이 이 문제의 요점은 사칙연산을 통해서 number를 최소로 표현하는 N의 개수를 구하는 문제입니다. 먼저 예제를 들어서 문제를 파악해..

안녕하세요! 오늘은 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..

안녕하세요! 저는 드디어 그리디로 넘어왔습니당 그리디 문제는 처음에 갈피를 잡지 못하면 산으로 가게되는? 것 같습니다 ... 그래서 저는 한 세시간을 태우다가 돌아돌아 정답을 내었지요 .. 문제 풀이 처음에 생각했던 풀이는 dfs 였습니다. 그런데 시간초과 오류가 발생했고 .. 다른 풀이를 생각해내어야했습니다 ! 그래서 생각해낸 것은 "앞자리에 큰 숫자가 오는 것이 전체 수를 크게 만든다" 였습니다. 이에 stack을 활용하였습니당 ! stack을 사용한 이유는 담겨진 숫자의 제일 마지막 수와 새로 들어올 수의 크기를 비교하는 연산이 필요한데, 이 때 pop() 을 사용하는 것이 효율적이라고 생각했기 때문입니다. stack을 활용해서 이 문제를 푼다면 다음과 같이 풀이가 가능합니다. number = "4..

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

안녕하세용 좋은 아침입니당 사실 이 문제는 스스로 풀지 못했습니다 ... 우선 문제부터 살펴보겠습니다. 문제 풀이 해당 문제에서 가장 어려웠던 점이, 가장 큰 자리 수가 같을 때, 어떻게 대소 비교를 하느냐였습니다. 예를들어, [838,83] 과 [383,38] 이 입력 값으로 들어올 때를 가정해봅시다. 각 경우에서 만들 수 있는 가장 큰 수는 다음과 같습니다. [838, 83] -> "83883" [383, 38] -> "38383" 위와 같이 가장 큰 수를 만들기 위해, 어떠한 기준으로 수를 정렬해야할까요? 사실 정답은 간단했습니다. 일의 자리보다 큰 자리 수를 가진 수의 경우, 그 다음 자리수도 비교의 대상이 되도록 하면되는 것입니다. 이는, [383, 38] 이라는 수가 주어졌을 때, 맨 앞자리는..