본문 바로가기
반응형

Algorithms119

[알고리즘] 미로 만들기 포인트 미로를 만드는 만드는 방법? 벽을 몇개를 부수고 들어가야 하는 가? 를 묻는 문제 입니다. 저는 이를 다익스트라 알고리즘 (이진 힙) 을 적용하여 해결하였습니다. 다익스트라 알고리즘은 시간 복잡도 O(E + VlogV) 가집니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python import heapq n = int(input()) data = [list(input()) for _ in range(n)] q = [] distance = [[987654321] * n for _ in range(n)] distance[0][0] = 0 q.append((0, 0, 0)) dx = [0, 0, 1, -1] dy = [1, -1, 0, 0] while q: cost, x, y = hea.. 2021. 6. 16.
[알고리즘] 암호 만들기 포인트 백트랙킹을 이용하여서 암호를 조합하는 문제 입니다. 문제 조건에서는 모음 1개 자음 2개 이상을 조건으로 갖고 있어 이를 해결하기 위해 재귀함수의 파라미터로 정의하여 사용하였습니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python n, m = map(int, input().split()) data = input().split() data.sort() answer = set() sel = [] def go(index: int, cnt: int, one: int, two: int) -> None: global answer if cnt == n: if one >= 1 and two >= 2: answer.add(''.join(sel)) return if index >= len(dat.. 2021. 6. 10.
[알고리즘] Max Area of Island 포인트 주어진 지도에서 섬들이 여러 개가 있다. 이 중에 제일 큰 섬의 크기를 구하라. 가 쟁점입니다. 그러면 섬의 크기는 어떻게 구할까요? 섬의 크기는 BFS 알고리즘을 이용하여 1 인 지점을 순회를 하면서 방문 배열의 표시를 해주면서 섬의 크기를 늘려가는 방식으로 구해줍니다. 어떻게 보면 너비 우선 탐색에 제일 기본형일고 할 수 있습니다. 🧶문서는 항상 수정될 수 있습니다. 비판은 환영합니다. python class Solution: def bfs(self, row: int, col: int, visited: list, n: int, m: int, grid: list) -> int: q = deque() q.append([row, col]) visited[row][col] = 1 cnt = 1 dx .. 2021. 6. 1.
[알고리즘] Maximum Subarray + 배열에서 부분 최대합을 구하는 방법 어느 순간 1100 명께서 저의 글을 읽어 주셨습니다. 정말 부족한 글이지만 잘 쓰도록 하겠습니다. 포인트 배열에서 부분합을 구하는 방법은 정말 다양하게 있을 수 있습니다. 먼저 LeetCode 문제를 풀어보고 이어서 다른 것들도 써보는 시간이면 좋겠습니다. 저는 다이나믹 프로그래밍으로 해결을 하였습니다. O(n) 즉, 배열을 전부 순회를 하는 경우 답을 구할 수 있다는 뜻입니다. 값을 계속 저장을 해나가면서 만약 더하려고 하는 값이 0 이하일 경우 0으로 초기화한 후 계속해서 더해나가는 것입니다. python class Solution: def maxSubArray(self, nums: List[int]) -> int: result = 0 presum = 0 # DP 를 이용한 방법 for index .. 2021. 5. 17.
반응형

티스토리툴바