본문 바로가기

Programming/Algorithm

(8)

[Python] 프로그래머스 - 무인도 여행 파이썬 풀이 import sys sys.setrecursionlimit(10000) def dfs(x, y, maps, visit): val = 0 if x = len(maps[0]): return val if y = len(maps): return val if visit[y][x] is True: return val if maps[y][x] == "X": return val visit[y][x] = True return int(maps[y][x]) + dfs(x - 1 , y, maps, visit) + dfs(x + 1 , y, maps, visit) + dfs(x, y - 1, maps, visit) + dfs(x, y + 1, maps, visit) def solution(..

[Algorithm] Union - Find (Python 구현) 유니온 파인드 파이썬 구현하기 / union - find by Phython 유니온 / 파인드는 현재 노드들이 같은 그룹에 속해 있는지 확인하고 같은 그룹으로 만드는 병합이 필요할 때 사용하는 알고리즘입니다. find 알고리즘 구현 par = [ -1 for i in range(N + 1) ] # 루트를 담을 배열 def find(x): # 루트를 찾아주는 함수 if par[x] 아직 연결된 적이 없음 par[x] = find(par[x]) # 자신의 부모를 부모->부모 를 재귀로 루트 부모를 찾음 return par[x] # 루트 부모를 리턴 par 이라는 배열에는 각 노드의 부모를 담아 놓습니다. par 배열의 index는 각..

[Algorithm] 재귀를 통한 순열(permutation) 구현(+ python 내장 함수 이용) 순열이란, N개의 원소에서 원하는 개수를 뽑을 때, 순서까지 고려하는 것을 말합니다. 예시) [1, 2, 3] 배열에서 2개의 원소를 선택할 경우 => (1, 2), (1, 3), (2, 3), (2, 1), (2, 3), (3, 1), (3, 2) 위와 같은 결과처럼 (1, 2), (2, 1)의 경우는 서로 다른 것으로 판단합니다. 🥸 재귀를 통한 코드 구현 test = [1, 2, 3] test_len = len(test) N = 2 # 뽑을 순열의 개수 visit = [0] * test_len # 해당 index의 값을 사용했는지 여부 arr = [0] * N # 현재 순열을 담을 배열 arr_list = [] # 모든 순열을 담을 배열 def permutaion(level): if level >=..

[Algorithm] 플로이드 와샬(Floyd Warshall) 알고리즘(ft.파이썬) 🚩 플로이드 와샬 알고리즘 파이썬 구현 플로이드 와샬은 다익스트라 알고리즘과 같이 최단거리 혹은 최소비용을 구하는 알고리즘입니다. 플로이드 와샬은 다익스트라 알고리즘과는 달리 모든 노드에서 다른 모든 노드들까지의 최소 거리(혹은 최소비용)을 구하기 때문에 "어딘가를 경유한다."라는 조건이 주어질 때, 사용을 고려하기 좋은 알고리즘 입니다. 다만, 출발점(s), 도착지점(e), 경유지(p)에 모든 노드를 고려해야하므로 시간 복잡도는 O(N^3)으로 큰 편 입니다. 즉, 문제에서 주어진 노드(N)의 최댓값을 고려해 미리 계산해 사용할 가치가 있는 알고리즘인지 고려해봐야합니다. ✏️ 플로이드 와샬 알고리즘 위 그림의 경우는 출발지점이 1번 노드, 도착지점이 4번 노드인 경우 입니다. 1 -> 4로 가는게 경유..

[Algoritm] 행렬 회전 (Python 구현) 프로그래머스에서 제공하는 카카오 2020년 신입 개발자 블라인드 코딩 테스트 1차 문제 3번을 풀어 보았다. https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 해당 문제는 어떤 알고리즘을 사용할 것인가를 알아내는 것보다 구현력이 필요한 문제였다고 생각한다. 해당 문제의 경우 제한 사항의 크기가 작기 때문에 모든 경우를 확인하는 완전 탐색으로 풀이가 가능한데, 행렬의 회전과 범위를 설정하는 것이 중요했다. 문제를 해결하기 위해서는 2차원 행렬의 회전을 구현해야 ..

[Algorithm] 최대 공약수, 최소 공배수 구하기 GCD(Greatest Common Divisor) 최대 공약수 구하기 유클리드 호제법 사용 def gcd(a, b): while b: a, b = b, a % b return a a = b x q + r 이라고 했을 때, GCD(a, b) = GCD(b, r)를 만족한다. 간단 증명: 수학적으로 증명하는 방법이 있지만 이해를 위해서 간단히 설명하자면 아래와 같이 표현할 수 있다. b = r x m + n으로 표현할 때, n이 0이라면 b = rm으로 표현된다. 즉, b와 r의 최대 공약수 GCD(b, r) = m이 된다. a = bq + r = rmq + r = r(mq + 1) 이므로 GCD(a, b) = r 이다. => GCD(a, b) = GCD(b, r) = GCD(r, 0) = r LCM(Lo..

[Java] Kruskal's Algorithm 크루스칼 알고리즘 - 최소 신장 트리(MST) 최소 신장 트리 MST(Minimun Spanning Tree) - 크루스칼 알고리즘 자바 구현 🧐 최소 신장 트리 MST(Minimun Spanning Tree)란? 최소한의 가중치를 사용하여 모든 정점이 연결되어 있을 수 있게하는 기법이다. 예시) 도시들은 모두 다리로 연결되어있을 때, 모든 도시를 갈 수 있게 다리를 연결하되 최소한의 다리 길이만을 사용하는 방법 (도시가 가로등으로 다리가 전선으로 바뀔수도 있다.) 네비게이션의 최단 경로 모든 정점(node 혹은 vortex)가 연결될 수 있는 경로 중 가장 적은 가중치(여기선 거리)를 사용하는 경로 주의사항 여기서 연결이란 다른 노드를 거쳐서 가는 것을 포함한다. 간선 혹은 브랜치(노드를 이어주는 선, 거리)는 방향성을 갖지 않는다.(연결만 되어있..

[Java] Dijkstra Path 다익스트라 알고리즘 구현(ft. 우선순위 큐) 쉽지만 복잡한 다익스트라 알고리즘 🤔 다익스트라 알고리즘은 왜 쓸까? ❗️최단 경로를 구하는 알고리즘 중 하나이다. 특정 지점에서 목표 지점으로 가장 적은 비용을 들이며 가야할 때 사용할 수 있다. 예) A에서 D로 가는데 걸리는 비용은 최소 값은? A -> D = 5 A -> B -> D = 5 A -> C -> D = 3 따라서 실제 최소 비용 지불하는 경로는 A -> C -> D 이다. 🥸 다익스트라 알고리즘 로직 1. 시작지점과 연결된 노드들과의 비용을 구한다. Result List 연결된 노드 A B C D E 비용 0 3 1 5 무한 출발 지점이 A일 때, 자기 자신에게 가는 비용은 없으니 0 A에서 E와 같이 바로 연결된 경로는 없을 때, 비용을 무한(영향을 주지 않는 아주 큰 값)으로 한다..

이전 1 다음

728x90

티스토리툴바