Algorithm10

• 

  [Algorithm] 위상 정렬(Topology Sort) 위상 정렬(Topology Sort)에 대해서 공부하고 정리한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 위상 정렬(Topology Sort)이란? 방향 그래프에서 간선으로 주어진 정점 간 선후관계를 위배하지 않도록 나열하는 정렬입니다. 쉽게 이야기 하자면 '순서가 정해져 있는 작업'을 차례로 수행해야 할 때, 그 순서를 정렬하기 위해 사용합니다. 위상 정렬의 실생활 예시는 대학교의 선수 과목 구조를 예로 들 수 있습니다. 웹 프로그래밍 과목을 듣기 위해 컴퓨터 기초, 컴퓨터 프로그래밍 그리고 UNIX 시스템 과목을 먼저 들어야 합니다. 이렇게 순서가 있는 작업이 있을 때 작업을 정확하게 정렬해주는 위상 정렬 알고리즘을 사용합니다. 위 예시의 순서를 찾는다면 아.. Algorithm 2022. 10. 11.

• 

  [Algorithm] LCS(최장 공통 부분 수열) LCS(최장 공통 부분 수열)에 대해서 공부하고 정리한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! LCS(최장 공통 부분 수열)이란? '두 문자열을 비교할 때 공통적으로 나타나는 부분 문자열 중 가장 긴 것' 이해를 위해 예를 들어 "ACAYKP" 문자열과 "CAPCAK" 문자열이 주어졌다면, ACAYKP CAPCAK 두 문자열을 비교할 때 공통적으로 나타나는 부분 문자들 중 가장 긴 것은 ACAK이고 길이는 4입니다. LCS(최장 공통 부분 수열) 동작 과정(LCS 길이 구하기) 위에서 예를 든 "ACAYKP"와 CAPCAK" 문자열의 LCS 길이를 구한다면 어떻게 구해야할지 생각해봅시다. ↪ LCS는 다이나믹 프로그래밍을 이용하여 풀 수 있는데, 2차원 배.. Algorithm 2022. 9. 10.

• 

  [Algorithm] 크루스칼(Kruskal) 크루스칼 알고리즘에 대한 내용을 정리해보려고 합니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! 크루스칼 알고리즘이란? 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘입니다. 그리디 알고리즘으로 분류됩니다. 그렇다면 크루스칼 알고리즘에 대해서 생각해봅시다. 아래 그림과 같은 그래프를 가장 적은 비용으로 모든 노드를 연결하기 위해선 어떻게 해야할까요? 의외로 간단합니다. 간선의 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. ↪ 간선 정보를 오름 차순으로 정렬하고 비용(거리)이 적은(짧은) 순서대로 그래프에 포함시키면 됩니다. 일단 위 그림과 같이 모든 간선 정보를 저장합니다. 노드 1번부터 7번까지의 모든 간선 정보를 저장한 것이고, 노드6.. Algorithm 2022. 9. 5.

• 

  [Algorithm] 이분 탐색(Binary Search) 이분 탐색에 대한 내용을 정리해보려고 합니다. 이분 탐색 정렬되어 있는 배열에서 특정 데이터를 찾기 위해 모든 데이터를 순차적으로 확인하는 대신 탐색 범위를 절반으로 줄여가며 찾는 탐색 방법입니다. 이분 탐색을 사용해야하는 이유 ? 우리가 일반적으로 알고있는 선형 탐색의 경우에는 앞에서부터 순차적으로 탐색하기 때문에 시간 복잡도는 배열의 원소의 개수 만큼(O(n))이 됩니다. 만약 원소의 개수가 무수히도 많아진다면 굉장히 비효율적인 알고리즘이 되겠죠. 하지만 이분 탐색은 탐색 범위를 절반으로 나누어서 탐색하기 때문에 시간 복잡도는 O(log n)로 탐색이 가능합니다. 이분 탐색 동작 이분 탐색의 동작을 알아보도록 하겠습니다. 예를 들어서 배열 arr = {1, 3, 5, 7, 9, 10, 13, 15} .. Algorithm 2022. 8. 31.

• 

  [Algorithm] 유니온 파인드(Union-Find) 그래프 알고리즘 중 Union-Find 에 대해서 공부한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 유니온 파인드(Union-Find)란? 여러개의 노드가 존재할 때 두개의 노드를 선택해서, 현재 두 노드가 서로 같은 그래프에 속해있는지 판별하는 알고리즘입니다. 그래프에서 사이클이 존재하는지 여부를 판별할 때 유용하게 사용됩니다. 유니온 파인드(Union-Find) 그림 설명 위 그림과 같이 여러개의 노드가 모두 연결되지 않고, 자기 자신만을 집합의 원소로 가질 때 모든 값이 자기 자신을 가르키도록 합니다. 그리고 표를 보면 i는 노드 번호, parent[i]는 부모 노드 번호를 의미합니다. 즉, 자기 자신이 어떤 부모에 포함되어있는지를 의미합니다. 자 이제, .. Algorithm 2022. 8. 28.

• 

  [Algorithm] 다익스트라(Dijkstra) 다익스트라 알고리즘을 공부한 내용을 바탕으로 작성한 내용입니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적 부탁드립니다! 다익스트라(Dijkstra)란? 하나의 정점에서 다른 모든 정점으로 가는 최단 경로를 구하는 알고리즘 중 하나입니다. 도착 정점뿐만아니라 다른 모든 정점을 방문하며 각 정점까지의 최단 경로를 찾게됩니다. 동작 과정 1. 출발 정점과 도착 정점을 정합니다. 2. '최단 거리 테이블'을 초기화합니다. 3. 현재 정점에서 인접한 정점 중 방문하지 않은 정점들을 구별하고 방문하지 않은 정점들 중 가장 최단 거리의 정점을 선택합니다. 4. 해당 정점을 거쳐서 특정한 정점으로 가는 경우를 고려하여 최단 거리를 업데이트합니다. 5. 3~4번을 반복합니다. 동작 예시 출발 정점은 .. Algorithm 2022. 8. 23.

• 

  [Algorithm] 최장 증가 부분 수열(LIS) DP 문제인 LIS 문제를 풀기 위해 LIS 알고리즘을 공부했습니다. 제가 공부한 내용을 바탕으로 작성했습니다. 잘못된 부분이 있을 수 있습니다. 잘못된 부분이 있다면 지적부탁드립니다! 최장 증가 부분 수열(LIS)이란? 수열이 주어지고 해당 수열에서 몇개의 수를 제거했을 때 부분 수열을 만들 수 있습니다. 부분 수열 중에서 오름 차순으로 정렬되고, 길이가 가장 긴 부분 수열을 최장 증가 부분 수열(LIS)이라고 합니다. 그렇다면 이해를 위해 예를 들어보도록 하겠습니다. {3, 5, 7, 9, 2, 1, 4, 8} 수열이 있습니다. 몇개의 수를 제거하여 부분 수열을 만들면 {3, 5, 7, 9, 2} {5, 7, 9} {3, 5, 7, 8} {3, 5, 7, 9} 등을 만들 수 있습니다. ✔ {3, 5,.. Algorithm 2022. 8. 17.

• 

  [Algorithm] 에라토스테네스의 체 위 짤은 인터넷을 돌아다니다가 재밌어서 가져와봤습니다. 무튼 글을 시작하자면 알고리즘 문제를 풀다보면 소수 판별하라는 문제가 종종 보입니다. 해당 문제를 해결하기 위해선 소수 판별하는 알고리즘을 사용해야 합니다. 그래서 알고리즘 중에 '에라토스테네스의 체'가 가장 시간 복잡도도 우수하기 때문에 머릿속에 저장할 겸 정리해보려고 합니다. 목차 소수란 에라토스테네스의 체에 대해서 에라토스테네스의 체 구현(C++) 소수란 소수는 1과 자기 자신만을 약수를 갖는 1보다 큰 자연수입니다. (참고로 1은 소수가 아닙니다.) 에라토스테네스의 체에 대해서 에라토스테네스의 체는 이름 그대로 무언가를 찾기 위해 체를 걸러내듯, 소수를 찾는 방법입니다. 알고리즘은 2부터 찾고자하는 수까지 나열하고 1을 지웁니다. 1 다음으로.. Algorithm 2022. 8. 2.

• 

  [Algorithm] 모듈러 연산(나머지 연산) 알고리즘 문제를 풀다보면 특정 값을 나눈 나머지를 리턴 또는 출력하라는 문제를 종종 볼 수 있다. 이렇게 주어지는 이유는 알고리즘 문제를 푸는 과정에서 결과 값이 매우 커서 오버플로우가 발생하기 떄문에 문제에서 친절하게 자료형 범위 내에서 계산이 되라고 모듈러 연산을 요구한다. 그런데 모듈러 연산을 요구하는 경우 단순히 결과 값에만 모듈러 연산을 수행하면 이미 결과 값은 너무 커져버려서 오버플로우가 발생한 경우이기 때문에 연산 과정 도중에 모듈러 연산을 적용해야 한다. 그렇다면 모듈러 연산을 적용하기 위해선 모듈러 연산 분배 법칙에 대해 알고있어야 한다. 모듈러 연산은 각 피연산자에 모듈러 연산을 적용 후에 계산한 결과에 대해 다시 한번 모듈러 연산을 적용하면 된다. 뺄셈에선 음수가 나오는 것을 방지하기.. Algorithm 2022. 8. 1.

• 

  [Algorithm] 유클리드 호제법 : 최대 공약수와 최소 공배수(C++) 코딩 테스트 문제 중에 최대 공약수, 최소 공배수를 요구하는 문제가 있습니다. 그래서 최대 공약수와 최소 공배수를 구할 때 자주 사용되는 알고리즘인 유클리드 호제법에 대해서 정리해보려고 합니다. 목차 유클리드 호제법이란 3개 이상의 수에 대한 최대 공약수 구하는 법 3개 이상의 수에 대한 최대 공배수 구하는 법 최대 공약수/최소 공배수 구현(C++) 유클리드 호제법이란 두 수의 최대 공약수를 구하는 알고리즘입니다. 유클리드 호제법을 사용하기 위해서는 MOD 연산에 대해서 알아야합니다. MOD 연산이란 ? 두 값을 나눈 나머지를 구하는 연산으로, 큰 수를 작은 수로 나눈 나머지를 구합니다. 그렇다면 유클리드 호제법 예시를 들어보도록 하겠습니다. 예를 들어 1112, 695 두 수의 최대 공약수를 구하고자합.. Algorithm 2022. 7. 20.