728x90 Quality control (Univ. Study)/Algorithm Design40 Algorithm Design - 실습(GDC_LCM, Sort) GDC_LCM 최대공약수, 최소공배수를 구하는 과제이다. #include using namespace std; // 최대공약수를 계산하는 함수 int gcd(int a, int b) { int min, ans = 0; if(a>b){ min = b; } else{ min = a; } for (int i=1; ib){ base = a; } else{ base = b; } for (int i=base; ;i++) { if ((i%a == 0) && (i%b == 0)) { return i; } } } int main() { int a, b; cin >> a >>b; cout n; // 첫 번째 줄에서 n 을 입력받음 int* numbers = new int[n]; // 동적으로 정수 배열을 할당 // 두 번.. 2024. 3. 13. Algorithm Design - 복잡도 분석 Big O Big O notation으로 어떻게 표현되는 알고리즘이느냐에 따라 아예 수행이 불가능한 알고리즘이 될 수도 있다. 점근적 상한(Asymptotic Upper Bound) 방법을 이용하여 정의되고 표현한다. 주어진 복잡도 함수 f(n)에 대해서 g(n)∈O(f(n)) 이면 다음을 만족한다. n≥N인 모든 정수n에 대해서 g(n) ≤ c x f(n)이 성립하는 실수 c>0와 음이 아닌 정수 N이 존재한다. 이는 아래와 같이 그래프를 통해 살펴볼 수 있다. 어떤 함수 g(n)이O(n^2)에 속한다는 말은 그 함수는 어떤 임의의 N값보다 큰 값에 대해서는 어떤 2차함수 cn^2 보다는 작은 값을 가지게 된다는 것을 뜻한다. (그래프 상에서는 아래에 위치) 반대로 어떤 알고리즘의 시간복잡도가 O(f(.. 2024. 3. 13. Algorithm Design - Intro/Data structure Intro 이전에도 타과의 알고리즘 강의를 청강해서 들었으나 실습이 포함된 실습과목을 통해 직접 코드 설계하는 실력도키우고 설계학점도 채울겸 알고리즘 설계 수업을 수강하게 되었고 해당 수업 내용을 정리하는 시리즈가 될 것이다. 우선 알고리즘이란 특정문제를 해결하기 위해 기술한 일련의 명령문이다. 본격적으로 구체적인 알고리즘들을 학습하기전에 복습겸 간단한 기초와 데이터 구조에 대해서 살펴보자. 알고리즘의 요건으로는 크게 세가지 정도로 볼 수 있다. - 완전성과 명확성: 수행결과와 순서가 완전하고 명확하게 명세되어야하고 순수하게 알고리즘이 지시하는대로 실행하기만하면 의도한 결과가 얻어져야하는 것이다. - 입력과 출력: 입력은 알고리즘이 처리해야할 대상으로 제공되는 데이터이고 출력은 입력데이타를 처리하여 얻은.. 2024. 3. 9. Lecture 16 - 강연결 요소 + 그리디 알고리즘(1) 강연결 요소 유향 그래프의 모든 정점 쌍에 대해서 양방향으로 경로가 존재하면 강하게 연결되었다고 한다. 그래프 전체 대신 강하게 연결된 부분 그래프에 대해서는 강연결 요소 (Strongly connected component)라고 한다. 아래는 강연결요소를 찾는 psuedo code이다. 수행 시간: Θ(|V|+|E|) 예시 그래프를 통해 자세히 살펴보자. 그리디 알고리즘 그리디 알고리즘(Greedy algorithm)은 이름처럼 눈앞의 이익만 취하고 보는 알고리즘을 뜻한다. 현재 시점에서 가장 이득인 것으로 보이는 해를 선택하는 행위를 반복한다. 많은 경우에 그리디 방식은 최적해를 보장하지 못하지만, 드물게 최적해가 보장되는 경우가 존재하므로 해당 특별한 case를 잘 알아두는 것이 중요하다. 그리디 .. 2023. 5. 15. Lecture 18 - Graph(2) 위상 정렬 (Topological Sorting) 우선 싸이클이 없는 유향 그래프에서 정의되는 문제이다. 간단하게 살펴보면 모든 정점을 정렬하되 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치해야 하는 정렬이다. 이때 복수의 위상 순서가 존재할 수 있다. 라면 끓이기에서 위상순서를 나타낸 그래프를 보면 위와 같다. Kahn 기반 알고리즘 다음은 Kahn 알고리즘 기반 위상 정렬의 psuedo code이다. topologicalSort1(G, v) { for ← 1 to n { 진입간선이 없는 정점 u를 선택한다; A[i] ← u; 정점 u와, u의 진출간선을 모두 제거한다; } ▷ 이 시점에 배열 A[1…n]에는 정점들이 위상정렬되어 있다 } 수행 시간은 Θ(|V|+|E|)이고.. 2023. 5. 8. Lecture 17 - Graph(1/4) 그래프 정점(vertex) 및 간선(edge)로 이루어진 자료구조이다. G = (V, E) 형태로 나타냄 (V: 정점 집합, E: 간선 집합) 두 정점이 간선으로 연결되어 있을 경우 인접하다고 한다. 종류 그래프의 종류를 나누는 기준은 다음과 같다. - 두 vertex 간 가능한 edge의 개수 - Edge의 방향 유무 - Loop의 유무 - 추가적으로 edge의 weight 유무에 따라 weighted, unweighted로 나눌 수 있음 인접 행렬을 이용한 그래프의 표현은 이해하기 쉽고 간선의 존재 여부를 Θ(1)만에 파악 가능하다. 그러나 그래프 정보를 저장하기 위해서만 Θ(𝑛^2) 시간이 소요되고 메모리 사용량도 크다는 점은 단점으로 작용한다. 간선의 밀도가 높은 그래프에서는 인접 행렬을 사용한 .. 2023. 5. 1. Lecture 14 - Dynamic Programming 동적 프로그래밍(Dynamic Programming) 동적 프로그래밍이란 큰 문제의 해답에 더 작은 문제의 해답이 포함되어 있으며, 이를 재귀호출로 구현할 때 같은 해답을 구하기 위한 중복 호출이 다수 발생하는 경우에 활용하는 문제해결 기법이다. 큰 문제의 해답에 더 작은 문제의 해답이 포함된 경우를 최적 부분 구조(Optimal Substructure)를 가진다고 한다. 동적 프로그래밍을 적용하는 문제는 아래와 같은 두 성질이 있다. ① 최적 부분구조(optimal substructure) - 큰 문제의 최적 솔루션에 작은 문제의 최적 솔루션이 포함된다. (점화식 형태로 표현) ② 재귀호출시 중복(overlapping recursive calls) - 재귀적 해법으로 풀면 같은 문제에 대한 재귀호출이 .. 2023. 4. 24. Lecture 13 - 집합의 처리 상호 배타적 집합 상호 배타적 집합은 서로 공유하는 원소가 없는 여러 집합들의 모임 (disjoint sets)으로 각 집합은 대표 원소로써 해당 집합을 나타낸다. 관련 연산을 보면 다음과 같다. ▪ Make-Set(𝑥) : 원소 𝑥로만 이루어진 집합을 생성 ▪ Find-Set(𝑥) : 원소 𝑥가 포함된 집합을 찾은 후 대표 원소에 대한 포인터를 반환 ▪ Union(𝑥, 𝑦) : 원소 𝑥가 포함된 집합과 원소 𝑦가 포함된 집합을 합쳐서 합집합 생성 시간 복잡도 분석 관련하여 총 𝑚회의 Make-Set, Find-Set, Union 연산이 있을 때 𝑛번의 MakeSet 연산이 포함된 상황을 가정한다. 대표적으로 그래프 구조에서의 connected component 관련 처리에 활용된다. 연결 리스트를 이용.. 2023. 4. 10. Lecture 11 - 해시 테이블 해시 테이블 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조이다. 트리에서도 값에 의해 위치가 달라지는 것 같지만 그것은 트리를 사람이 이해하기 쉽게 그렸을 때의 위치이며 메모리 상에서의 위치는 키 값에 따라 달라지는 것이 아니다. 평균 상수 시간에 삽입, 삭제, 검색이 가능하여 매우 빠른 응답을 요하는 응용에 유용하다. 예를 들면 119 긴급구조 호출과 호출번호 관련 정보 검색, 주민등록 시스템 등 에서 이용된다. 다만 해시 테이블은 최소 원소를 찾는 것과 같은 작업은 지원하지 않는다. 따라서 sorting같은 과정보다는 다순한 삽입 검색등의 과정에 적합한 자료구조이다. 위와 같이 검색키를 통해 주소계산을 하고 constant time으로 테이블에 값이 존재하는지 검색한다. 크기 13인 해시 .. 2023. 4. 3. 이전 1 2 3 4 5 다음 728x90
