본문 바로가기

전체 글264

[코딩 + 알고리즘 완주반] 22일차. 최소 신장 트리 # 신장 트리 (Spanning Tree) 그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프 모든 노드 포함, 모든 노드 서로 연결, 사이클 존재하지 않음 # 최소 신장 트리 (Minimum Spanning Tree, MST) 가능한 신장 트리 중에서 간선의 가중치 합이 최소인 Spanning Tree Kruskal's algorithm(크루스칼 알고리즘), Prim's algorithm(프림 알고리즘) # Kruskal's algorithm(크루스칼 알고리즘) 가중치가 가장 작은 간선부터 연결 ( 사이클일 경우 넘어감 ) # Union-Find 알고리즘 - 사이클이 생기는지 확인하는 알고리즘 Disjoint Set을 표현할 때 사용하는 알고리즘으로 트리 구조를 활용하는 알고리즘 Di.. 2021. 4. 9.
[LEET CODE] 77. Combinations # Problem Given two integers n and k, return all possible combinations of k numbers out of the range [1, n]. You may return the answer in any order. Constraints: 1 2021. 4. 9.
[코딩 + 알고리즘 완주반] 21일차. 최단 경로 알고리즘 # 최단 경로 문제 두 노드를 잇는 가장 짧은 경로 찾기 가중치 그래프에서 간선의 가중치 합이 최소가 되도록 하는 경로 # 단일 출발 및 단일 도착 최단 경로 문제 특정 노드에서 특정 노드에 도착하는 가장 짧은 경로 찾기 # 단일 출발 최단 경로 문제 특정노드와 그래프 내 모든 노드 각각의 가장 짧은 경로 찾기 # 전체 쌍 최단 경로 그래프 내 모든 노드 쌍에 대한 최단 경로 찾기 # 다익스트라 알고리즘 - 너비우선 탐색(BFS)과 유사 하나의 정점에서 다른 모든 정점 간의 각각 가장 짧은 거리 구하기 (단일 출발 최단 경로 문제) 첫 정점을 기준으로 연결되어 있는 정점들을 추가해가며, 최단 거리를 갱신 # 우선순위 큐를 활용한 다익스트라 알고리즘 초기 첫 정점의 거리는 0, 나머지는 무한대로 저장 우선.. 2021. 4. 9.
❗️[LEET CODE] 46. Permutations ( 객체 복사 ) # Problem Given an array nums of distinct integers, return all the possible permutations. You can return the answer in any order. Constraints: 1 List[List[int]]: return list(itertools.permutations(nums)) itertools 모듈의 permutations 함수는 튜플 모음을 반환 # 객체 복사 파이썬에서는 모든 것이 객체이기 때문에 '=' 를 이용하면 객체의 참조가 복사되기 때문에 원래의 값을 변경하면 참조한 값도 변경된다. 리스트의 경우 a[:], a.copy() 를 이용하면 값을 복사한 다른 객체를 생성 복잡한 리스트의 경우 a.copy.deep.. 2021. 4. 7.
[LEET CODE] 17. Letter Combinations of a Phone Number # Problem Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters. Constraints: 0 List[str]: def dfs(index, path): # 끝까지 탐색하면 백트래킹 if len(path) == len(digits): result.append.. 2021. 4. 7.
[LEET CODE] 200. Number of Islands # Problem Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water. Constraints: m == grid.length n == grid[i].length 1 = len(grid) or \ j = len(grid[.. 2021. 4. 6.
반응형

티스토리툴바