알고리즘
-
LCS 알고리즘알고리즘 2024. 6. 16. 15:07
1. LCS 알고리즘이란❓최장 공통 부분수열(Longest Common Subsequence)연속되지 않은 부분 문자열을 찾는 것 최장 공통 문자열(Longest Common Substring)연속되는 부분 문자열을 찾는 것 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있습니다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 됩니다. 최장 공통 문자열(Longest Common Substring)은 BCD입니다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능합니다.2. 최장 공통 문자열 (Longest Common Substring) 최장 공통 부분 문자열(Longest Common Subsequen..
-
그래프(Graph)와 행렬(matrix)알고리즘 2023. 9. 22. 17:09
❓그래프 Vertex(정점)과 Edge(간선)으로 이루어진 자료구조 정점과 정점 사이의 관계를 Edge(간선)으로 표현한다. 그래프 구성 요소 Vertex/Node(정점) : Node 혹은 Vertex 라고 표현하며 그래프에서 각각 지점을 의미한다. (위 그림은 1, 2, 3 등) Edge/Link(간선) : Node 와 Node 혹은 Vertex 와 Vertex등 각 정점들을 연결하는 선을 의미한다. (그래프 사이 선) Weight(가중치) : 간선을 통해 이동하는데 소요되는 비용등을 표시하는 곳에 사용한다. ( 표기되어 있지 않지만 간선과 간선사이의 비용등을 나타냄 ) Direction Graph : 방향이 있는 그래프를 의미하고 간선의 방향에 따라 이동만 가능한 경우에 사용된다. Undirected..
-
깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)알고리즘 2023. 8. 10. 09:52
그래프를 탐색하는 방법에는 크게 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS) 가 있다. ❓그래프는 링크 추가 예정 1. 깊이 우선 탐색(DFS, Depth-First Search) 루트 노드 혹은 임의의 한 노드에서 시작하여 연결된 노드의 끝까지 탐색을 진행한 후 다음 노드로 넘어가는 것을 말한다. 가장 마지막에 들어온 값들이 먼저 나가는 LIFO(Last In First Out) 스 구조를 가진다. 모든 노드를 방문하고자 할 경우 선택한다. 구현 자체는 간단하지만 너비 우선 탐색(BFS) 보다는 느리다. def DFS(graph): visited = [False] * len(graph) visited[0] = True stack = graph[0] answer = [1] while stack: ..
-
이진 탐색(Binary Search)알고리즘 2023. 3. 2. 22:53
1. 이진 탐색(Binary Search)란? 정렬된 리스트를 반으로 나누어 필요한 부분으로 범위를 제한하여 값을 찾아가는 방식 찾고자 하는 범위가 넓은 경우 매우 효율적으로 사용이 가능 2. 이진 탐색(Binary Search)조건 원소가 오름차순이든 내림차순이든 정렬이 되어있어야 한다. 원소에 랜덤으로 값을 접근할 수있어야 한다. 3. 이진 탐색(Binary Search)특징 이진 탐색을 사용하면 일반적인 선형 탐색을 시행하는 것에 비해서 시간 복잡도가 훨씬 줄어든다. 적은 양의 데이터의 경우 모든 값들을 탐색하는데 그렇게 많은 시간이 소요되진 않는다. 하지만 데이터의 갯수가 100만개 이상 등 많은 데이터들 중에서 내가 원하는 값을 찾는 경우 선형 탐색의 경우는 1~100만 까지 모든 수를 탐색해보..
-
DP(Dynamic Programming) 동적 프로그래밍알고리즘 2023. 2. 15. 16:57
1. DP(Dynamic Programming) 이란? 각각의 작은 문제들을 해결한 값들을 저장하여 나중의 큰 문제를 해결할 때 결과들을 합산하여 구하는 것 메모리를 많이 사용하는 대신 연산 속도를 높여준다. 2. DP(Dynamic Programming) 조건 DP(Dynamic Programming)은 작은 값들을 기억했다가 큰 문제를 해결할 때 그 값들을 활용하여 푸는 구조를 가지고 있다. 조건으로는 아래 두 조건을 만족해야 적용할 수 있다. 부분 최적 구조 : 작은 문제의 결과를 모아서 큰 문제를 해결할 수 있는 구조 중복되는 부분 문제 : 동일한 작은 문제들을 반복적으로 해결할 수 있어야 한다. 3. DP(Dynamic Programming) 특징 DP는 메모리를 많이 사용한다고 말을 했는데 이..
-
탐욕 알고리즘(Greedy Algorithm)알고리즘 2023. 1. 23. 21:48
1. 탐욕 알고리즘(Greedy Algorithm) 이란? 선택의 순간에서 눈앞의 최적의 선택만을 따라가 최종적으로 답을 도출해내는 방법. 알고리즘을 푸는데에 있어서 최소한의 아이디어를 떠올릴 수 있는지를 물어보는 문제유형 Greedy Algorithm은 매 순간마다 그 상황에서 최적의 값이라고 생각하는 것을 따라가지만 전체적으로 봤을 경우 그 값이 최적의 값이라고 할 수 없다. 2. 탐욕 알고리즘(Greedy Algorithm)의 문제 해결 방식 선택 절차 : 현재 상태에서 최적의 값을 선택 적절성 검사 : 선택한 값이 문제의 조건과 일치하는지 비교 해답 검사 : 문제가 해결되었는지 판단 후 해결되지 않았을 경우 위의 과정을 반복 Greedy Algorithm은 항상 최적의 값을 찾아내는 것이 아니다...