본문 바로가기

Dot Algo∙ DS/알고리즘 개념

[알고리즘] 외판원 순회 문제(TSP: Travelling Salesman Problem) 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 6. 15. [알고리즘] 외판원 순회 문제(TSP: Travelling Salesman Problem) 정리 (Java) 외판원 순회 문제 (TSP: Travelling Salesman Problem) TSP(Travelling Salesman Problem, 일명 ‘여행하는 외판원 문제’)는 조합 최적화(Combinatorial Optimization) 문제로 전산학에서 연구된 가장 유명한 문제 중 하나다. 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 즉 해밀턴 순환에 저비용 조건만 추가..
[알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 6. 12. [알고리즘] 소수(Prime Number) 구하기 - 에라토스테네스의 체 (Java) 소수 소수(prime number)는 정수론의 가장 중요한 연구 대상 중 하나로, 양의 약수가(1보다 큰 자연수) 1과 자기 자신만을 약수로 가지는 수를 의미한다. 소수의 반대말로, 세 개 이상의 양의 약수를 갖는 자연수를 합성수라고 부른다. 예를 들어, 5는 1×5 또는 5×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수이다. 그러나 6은 자신보다 작은 두 숫자(2×3)의 곱이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다. 소수 구하기 주어진 수가 소수인지 판별하는 문제는 소수에 관련된 가장 기초적인 문제이다. 주어진 수 n이 소수인지를 판단하는 가장 단..
[알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 5. 31. [알고리즘] 비트(Bit)와 비트마스크(BitMask) 정리 (Java) 비트(bit) 비트(binary digit)는 데이터를 나타내는 최소 단위로 이진수의 한자라인 0 또는 1의 값을 가진다. 부호 없는 N비트 정수형 변수는 N자리의 이진수로 나타낼 수 있다. 이때 비트가 표현하는 값은 2^0 ~ 2^N-1까지이다. 여기서 2^N-1에 해당하는 비트값을 최상위 비트(Most Significant Bit)라 하고, 2^0에 해당하는 비트값을 최하위 비트(Least Significant Bit)라고 한다. 예를 들어 부호없는 4비트 정수형은 네 자리 이진수로 표시할 수 있는 모든 정수를 나타낼 수 있다. 아래 그림과 같이 4칸의 공간에 이진수 0 또는 1을 넣은 모든 경우의 수를 의미한다. 이때 비트가 표현하는 값은 2^0~2^3이다. 여기서는 2^3이 최상위 비트이고 2^0..
[알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 5. 30. [알고리즘] 분할정복 알고리즘 정리 (합병 정렬, 퀵 정렬, 이진 탐색) (Java) 분할정복(divide and conquer) 알고리즘 분할정복 알고리즘 (Divide and conquer algorithm)은 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 대표적인 예로는 정렬 알고리즘 중에서 퀵 정렬이나 합병 정렬과 이진 탐색, 선택 문제, 고속 푸리에 변환(FFT) 문제들이 대표적이다. 정렬 알고리즘 비교 선택 정렬과 삽입 정렬의 최대 실행시간은 O(n^2)이다. 입력하는 배열의 크기가 크다면 이 알고리즘으로 정렬하는데 매우 오랜 시간이 걸릴 수 있다. 반면 분할정복 알고리즘을 사용하는 합병 정렬의 실행시간은 모든 경우에 대해 O(nlgn)으로 , 퀵 정렬은 최대 O(n^2)이지만 최선이나 평균의 경우 O(nlgn)으로 비교적 빠른 시간을 갖는 것을..
[알고리즘] 백트래킹(Backtracking) 가지치기 기법 (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 5. 12. [알고리즘] 백트래킹(Backtracking) 가지치기 기법 (Java) 백트래킹 Backtracking 백트래킹은 조건 만족 문제(CSP; Constrain Satisfication Problems)를 해결하기 위해 사용하는 알고리즘이다. 이는 어떤 조합을 탐색하는데 무작정 그리디하게 모든 곳을 탐색하는 것이 아니라 조건에 만족하지 않으면 왔던 길을 되돌아가 조건이 만족하는 부분에 한해 완전 탐색하는 것이다. ❐ 백트래킹의 대략적인 흐름은 다음과 같다. 1. 어떤 노드의 유망성(탐색 가능성) 체크 1-1. 탐색 가능하면 그대로 탐색 1-2. 탐색이 가능하지 않으면 그 노드의 부모노드로 되돌아간 후 다른 자식노드를 탐색 BACK! - ✂️가지치기 그래서 백트래킹(되추적)이라고 불리는 것이다. DFS + 백트래킹? DFS는 모든 노드를 방문하고자 하는 경우에 주로 사용한다. D..
[알고리즘] 문자열 매칭 알고리즘 KMP (Java)
Dot Algo∙ DS/알고리즘 개념 2021. 5. 11. [알고리즘] 문자열 매칭 알고리즘 KMP (Java) 문자열 매칭 알고리즘 특정한 글이 있을 때 그 글 안에서 하나의 문자열을 찾는 알고리즘이다. 워드파일 또는 웹 브라우저 DB에서 문자열을 검색할 때 패턴 매칭 알고리즘을 사용하여 검색 결과를 표시한다. 단순 문자열 알고리즘 가장 간단한 문자열 매칭 알고리즘으로, 말 그대로 하나씩 확인하는 방법을 사용한다. 검색할 문자열 ABDEGH 찾는 문자열 DE 가장 앞부분부터 찾는 문자열이 매칭될 때 까지 탐색을 시작한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어지지 않았다면 한 칸씩 옆으로 이동시킨다. 검색할 문자열 A B D E G H 찾는 문자열 D E 매칭이 이루어졌으면 탐색을 종료한다. 검색할 문자열 A B D E G H 찾는 문자열 D E 코드 이 알고리즘은 이중포문으로 시간..
[알고리즘] DP문제에서 Top-down과 Bottom-up 어떻게 판단할까?
Dot Algo∙ DS/알고리즘 개념 2021. 5. 2. [알고리즘] DP문제에서 Top-down과 Bottom-up 어떻게 판단할까? Top-down vs Bottom-up DP문제를 풀 때 항상 고민하는 것은 'Top-down으로 풀어야하나 Bottom-up으로 풀어야하나' 이다. 그래서 다른 개발자들은 어떻게 접근하는지 참고해보자. Top-down은 언제 사용하는게 좋을까? → Generally, I recommend the top-down solution when either of the following is true: It's not easy to see in what order the sub-problems should be solved if you were going to solve them bottom-up. This is sometimes the case if the relationship between the sub-..
[알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로
Dot Algo∙ DS/알고리즘 개념 2021. 4. 29. [알고리즘/그래프] 크루스칼(Kruskal) 최소 신장 트리 vs 다익스트라(Dijksta) 최단 경로 그리디 알고리즘 과정 해 선택 실행 가능성 검사 해 검사 크루스칼(Kruskal)과 그리디 알고리즘 최소 신장트리는 사이클을 형성하지 않고 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리이다. 최소 신장 트리를 구축하는데 한 가지 중요한 제약은 최소 신장 트리 내에 사이클이 형성되어서는 안된다는 것이다. 크루스칼 알고리즘 동작 방식 1) 그래프 내의 모든 간선의 가중치에 대해 오름차순으로 정렬한다. 2) 1)의 간선을 차례대로 순회하면서 최소 신장 트리에 추가한다. (사이클 생성 x) 그리디 과정으로 다시 보면 다음과 같다. 해 선택 : 가장 작은 가중치의 간선 선택 실행 가능성 검사 : 사이클 생성 여부 파악 (사이클 생성되면 x) 해 검사 : 모든 정점이 하나의 집합에 있는지 확인 다익스트라(..

티스토리툴바

티스토리툴바