열정 도토리

근사해가 얼마나 최적해에 가까운지를 나타내는 것을 근사 비율이라고 한다. 근사해 값과 최적해 값의 비율로서, 1에 가까울수록 정확도가 높다. 이때, 근사 비율을 계산하려면 최적해를 알아야 하는 모순이 발생한다. 따라서, 최적해를 대신할 수 있는 간접적인 최적해를 찾고, 이를 이용해 근사 비율을 계산한다. 1. TSPTSP 를 위한 근사 알고리즘을 생각하려면, 다항식 시간을 가지는 유사한 알고리즘을 활용할 수 있다. TSP 와 비슷한 특성을 가지는 MST (최소 신장 트리) 가 있다. MST 는 모든 점을 사이클 없이 연결하는 트리 중에서 가중치 합이 최소인 트리이다. [Step 1 : MST 찾기 ] 크루스컬 또는 프림 알고리즘을 사용한다. [Step 2 : DFS 깊이 우선 탐색 진행] [Step 3..

1. 백트래킹 기법해를 찾는 도중에 막히면 되돌아가서 다시 해를 찾는 기법으로, 최적화 문제와 결정 문제를 해결한다. 깊이 우선 탐색을 진행한다. 모든 경우의 수를 확인하는 상태 공간 트리에서는 이파리 노드 수만 계산해도 (n-1) ! 이다. 이진트리로 계산해도 최악의 경우 2^n 개의 노드를 탐색해야 한다. 이는 시간이 오래 걸리기 때문에, 백트래킹 기법의 가지치기를 하면 효율적이다. 1-1. TSP1-2. n-QueensQueen 은 같은 행, 열, 대각선에 위치할 수 없다. 이 문제도 상태 공간 트리로 탐색하면 4^4=256 의 해가 있다. 하지만 백트래킹 기법을 사용하면 최초 해를 발견하기 까지 27번의 탐색만 하면 된다. 1-3. 부분집합의 해1-4. 그래프 색칠하기2. 분기 한정 기법백트래..

✳️ 1. 버블 정렬이웃하는 숫자를 비교하여 작은 수를 앞쪽으로 이동시키는 과정을 반복한다. 이렇게 입력을 전체적으로 1번 처리하는 것을 패스 (pass) 라고 한다. 1번의 패스가 끝나면, 가장 큰 수 (90) 이 가장 마지막에 위치하며 자리를 확정 짓게 된다. 시간 복잡도1,2번 줄의 for 문을 보면 비교횟수는 (n-1) + (n-2) ... {n-(n-1)} = n(n-1) /2 이다.4번에서 자리 바꿈의 시간은 O(1) 이다. => O(n²) * O (1) = O(n²) ✳️ 2. 선택 정렬입력 배열에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음에는 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여 1번 원소와 자리를 바꾼다. 시간 복잡도안쪽 for 문이 한 번에 도는 횟..

1. P 문제P (polynomial) 문제 집합은 다항식 시간 복잡도를 가진 알고리즘이다. 다항식보다 큰 시간 복잡도를 가진 알고리즘은 여러가지가 있는데, 그 중 하나가 NPC 문제 집합이다. 2. NPC 문제NPC 문제는 지수 시간의 시간 복잡도를 가진다. NPC 알고리즘의 특징은 어느 하나의 NPC 문제에 대해서 다항식 시간의 알고리즘을 찾아내면, 모든 다른 NPC 문제도 다항식 시간에 해를 구할 수 있다. 이를 추이 관계 (transitive) 라고 한다. 문제의 변환 (polynomial time reduction) 이란 문제 A를 해결하기 위해 문제 B를 해결하는 알고리즘을 사용하는 것이다. 그러기 위해서는 문제 A의 입력을 문제 B의 입력 형태 (format) 으로 변환시켜야 한다. B 알..

4.2 최소 신장 트리 (MST)최소 신장 트리 (MInimum Spanning Tree) 란 주어진 가중치 크래프에서 사이클 없이 모든 점들을 연결시킨 드리들 중 간선들의 가중치 합이 최소인 트리이다. 이를 찾기 위해서는 사이클이 없도록 모든 점을 연결시키면 된다. 최소 신장 트리를 찾는 그리디 알고리즘으로는 크루스컬 (Kruskal) 과 프림 (Prim) 알고리즘이 있다. 📍Kruskal 알고리즘1. 그래프가 주어졌을 때 가중치 순으로 간선을 정렬한다. 그리고, parent 배열을 준비한다. 2. find() 를 통해 각 노드의 parent 를 찾는다. 처음에는 b 와 c의 parent 가 각각 b와 c로써 서로 다르다. parent 가 서로 다르다면 뒤의 것의 parent 를 앞의 것의 pare..

분할 정복 알고리즘 (Divide and Conquer) 이란 주어진 문제의 입력을 분할하여 문제를 해결하는 방식의 알고리즘이다. 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 이들의 해를 취합하여 원래 문제의 해를 얻는다. 여기서 분할된 입력에 대한 문제를 부분문제라고 하고, 부분문제의 해를 부분해라고 한다. 부분문제는 더 이상 분할할 수 없을 때까지 계속 분할한다. 3.2 퀵정렬1. 임의의 pivot 을 선정하고 가장 왼쪽의 값과 교환한다. 2. low 인덱스를 오른쪽으로 한 칸씩 이동시키다가 pivot 인 9보다 큰 값이 나오면 정지한다. 이후에는 high 인덱스를 왼쪽으로 한 칸씩 이동시키다가 반대로 Pivot 인 9보다 작은 값이 나오면 정지한다. 그리고선 low 인덱스와 ..

1. 알고리즘의 효율성 표현알고리즘의 효율성은 수행 시간 (시간 복잡도) 또는 알고리즘이 수행하는 동안 사용되는 메모리 크기 (공간 복잡도) 로 나타낼 수 있다. 시간 복잡도는 알고리즘이 수행하는 기본적인 연산 횟수를 입력 크기에 대한 함수로 표현한다. 만약, n장의 카드 중에서 최대 숫자를 찾아야 한다면, (n-1) 번 비교를 해야 한다. 입력 크기 n이 커질수록, 연산 횟수는 더 많아질 것이다. 그래서 시간 복잡도는 "입력 크기 n에 따라, 연산 횟수가 얼마나 늘어나는지"를 보여주는 것이다. 함수 형태로 보면 f(n)=n−1이고, 이걸 우리는 입력 크기 n에 대한 함수 표현이라고 말한다. 따라서 시간복잡도는 (n-1) 가 된다. 알고리즘의 복잡도를 표현하는 방법에는 "최악 경우 분석", "평균 경우..

파이썬에서 스페이스 바 기준으로 입력 여러 개 받기 map(int, input().split()) input() 괄호 안에는 입력 시 뜨는 메시지를 넣을 수 있다. 이 경우에는 생략 가능 ex. input("숫자를 입력하세요: ) input.split() 공백을 기준으로 분할하여 문자열 리스트로 만든다. 괄호 안에 특수 문자를 넣으면 해당 특수 문자를 기준으로 분할할 수 있다. 공백의 경우엔 생략 가능 map(함수, 이터러블) -함수 int() 함수는 정수형으로 형변환 해준다. 파이썬에서 모든 입력은 문자열이기 때문. -이터러블 리스트, 튜플 등 반복 가능한 객체. 위의 input.split() 을 통해 문자열 리스트를 만들었다. 예시 a, b = map(int, input().split()) # 1 2..