728x90 반응형 BASE34 [Code Tree] 시뮬레이션 - 격자 안에서 밀고 당기기 시뮬레이션 - 격자 안에서 밀고 당기기 밀고 당기는 작업이란, 주어진 숫자들을 특정 방향으로 1칸씩 미는 작업을 말한다. 2차원 격자에서는 선택된 행에 대해, 적혀있는 숫자들을 왼쪽 혹은 오른쪽으로 한 칸씩 밀어주는 작업이 될 수 있고, 혹은 선택된 열에 대해 적혀있는 숫자들을 위 혹은 아래 방향으로 한 칸씩 밀어주는 작업이 될 수도 있다. 예를 들어, 오른쪽으로 한 칸씩 숫자들을 밀어준다고 해보자. # 1. n번째 원소를 temp에 저장 temp = a[n - 1] # 2. 나머지 원소를 오른쪽으로 shift for i in range(n - 1, 0, -1): a[i] = a[i - 1] # 3. temp를 첫 번째 원소에 기록 a[0] = temp 2차원 격자가 주어졌을 때 위쪽으로 숫자들을 한 칸.. 2023. 5. 22. [Code Tree] 시뮬레이션 - 격자 안에서 완전탐색 시뮬레이션 - 격자 안에서 완전탐색 완전탐색이란, 모든 가능한 경우를 다 따져보는 방법이다. 장점 : 코드 짜기가 쉽다. 단점 : 수행시간이 비교적 오래 걸린다. => 시간복잡도를 계산해보고 시간초과가 나지 않는다면 무조건 쓰는 것이 좋다. 완전탐색을 구현할 수 있는 방법은 For문 기반으로 구현하는 것과, 재귀함수 기반의 Backtracking(Brute Force) 기법을 이용하는 방법이 있다. 격자 안에서 탐색을 하는 경우는 For문을 기반으로 구현하면 된다. 예시 문제 - 행복한 수열의 개수 1이상 100이하의 숫자로만 이루어져 있는 n * n 크기의 격자 정보가 주어집니다. 이때 행복한 수열이라는 것은 다음과 같이 정의됩니다. 행복한 수열 = 연속하여 m개 이상의 동일한 원소가 나오는 순간이 존.. 2023. 5. 22. 알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘) 알고리즘 - 최단 경로 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘) 1. 최단 경로 알고리즘 최단 경로 문제란 가중 그래프에서 간선의 가중치의 합이 최소가 되는 경로를 찾는 문제이다. 1) 최단 경로 문제의 종류 단일 출발 (single-source) 최단 경로 어떤 하나의 정점에서 출발하여 나머지 모든 정점 까지의 최단 경로를 찾는 문제 단일 도착 (single-destination) 최단 경로 모든 정점에서 출발하여 어떤 하나의 정점까지의 최단 경로를 찾는 문제로 그래프 내의 간선들을 뒤집으면 단일 출발 최단거리 문제로 바뀔 수 있다. 단일 쌍(single-pair) 최단 경로 모든 정점 쌍들 사이의 최단 경로를 찾는 문제 2) 주요 알고리즘 BFS (완전탐색 알고리.. 2021. 2. 3. 알고리즘 - 단절점 (Articulation Points / Cut Vertices) 알고리즘 - 단절점 (Articulation Points / Cut Vertices) 1. 단절점이란? 무향 연결 그래프 G에서 하나의 정점과 연결된 간선들을 제거했을 때 두 개의 연결 그래프로 나뉘어 진다면 해당 정점은 단절점이다. 예를 들어 5에 있는 간선들을 모두 제거해도 그래프가 두 개로 나누어지지 않기 때문에 5는 단절점이 아니다. 그러나 4에 있는 간선들을 모두 제거할 경우 두 개의 연결 그래프로 나뉘어지기 때문에 단절점이다. 2. 단절점 찾기 - 무향 연결 그래프 G에서 어떤 정점 A에 연결된 정점들에 대해서 우회 경로 (정점 A를 거치지 않는 경로)가 없는 경우가 존재한다면 A는 단절점이다. orderV : 정점 V의 방문순서 lowV : 정점 V의 low (V 이후에 방문하는 정점들 중 .. 2021. 2. 3. 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 알고리즘 - 최소 공통 조상 (LCA, Lowest Common Ancestor) 정점 A와 정점 B가 각각 자신을 포함하여 조상을 따라 거슬러 올라 갈 때 처음 공통으로 만나게 되는 정점이다. 정점 A혹은 A의 조상이면서 정점 B 혹은 B의 조상인 정점들 중 가장 깊은 정점이다. 8과 9의 공통 조상들은 1, 2, 4 / 8과 9의 최소 공통 조상은 4 3과 6의 공통 조상들은 1, 3 / 3과 6의 최소 공통 조상은 3 8과 5의 공통 조상들은 1, 2 / 8과 5의 최소 공통 조상은 2 [ 최소 공통 조상 구하기 ] - 최상위 조상 정점을 시작으로 DFS 혹은 BFS를 수행하여 각 정점의 깊이와 부모 정점을 저장한다. - 정점의 부모를 따라 하나씩 올라가 LCA를 찾는다. 시간복잡도 : 트리의 깊이.. 2021. 2. 3. 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) 알고리즘 - 크루스칼 알고리즘(Kruskal's Algorithm), 프림 알고리즘(Prim's Algorithm) jina-developer.tistory.com/114 자료구조 - 최소 신장 트리 (MST, Minimum Spanning Tree) [개요] 1. 트리란? 1) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲이다. 2) 무향 그래프 G가 순환이 없는 연결 그래프이면 G는 트리이다. - G는 순환이 없고, 단순 그래프에서 간선을 추가할 경우 jina-developer.tistory.com 1. 크루스칼 알고리즘(Kruskal's Algorithm) 1) 순서 모든 간선들의 가중치를 오름차 순으로 정렬 가중치가 가장 작은 간선을 선택 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연.. 2021. 2. 2. 이전 1 2 3 4 ··· 6 다음 728x90 반응형
