자료구조와 알고리즘

소수란? What is Prime Number? 1과 자기 자신 외에는 나누어 떨어지는 정수가 없는 양의 정수 소수 판별법: 정수N에 대해 2~N-1까지 나누어 보는 방법 2~sqrt(N)까지의 정수로 나누어 보는 방법 에라토스테네스의 체 주어진 정수 N보다 작은 모든 소수를 구한다 #include #include using namespace std; int number = 120; // 구하고자 하는 소수의 범위 int primeNum[121]; void primeNumberSieve() { // primeNum 배열 초기화 for (int i = 2; i

유클리드 알고리즘 최대공약수를 구하는 알고리즘이다. GCD 관련 법칙 if u>v GCD(u, v) == GCD(u - v, v) 교환법칙 GCD(u, v) == GCD(v, u) 임의의 두 정수 u, v에 대해 v가 u보다 크다면 v와 u의 값을 바꾼다. u = u - v u가 0이면 v가 최대공약수 0이 아니면 1로 돌아감 알고리즘의 구현 int get_gcd(int u, int v) { int t; while (u>0) { if(u0) { t = u%v; u = v; v = t; } return v; } int gcd_recursion(int u, int v) { if(v==0) return v; else return gcd_recursion(v, u%v); }

경험적 분석과 수학적 분석 분석은 알고리즘을 선택하기 위한 방법 자원을 어떻게 소모하느냐가 중요. 시간 VS 자원 경험적 분석(Empirical Analysis) 실제 코드를 작성 후 실행하여 시간 측정 데이터 수를 다르게 하여 함수 관계 유추 (테스트케이스) 수학적 분석(Mathematical Analysis) 최악의 경우와 최선의 경우 (경험적 알고리즘) Worst Case 가장 많은 시간과 자원을 필요로 하는 경우 Best Case 가장 적은 시간과 자원만이 소요되는 경우 Average Case 개념 모호 알고리즘 분석 예 (수학적 알고리즘) For문을 수학적으로 돌리는 예시 알고리즘의 유형 상수 입력자료수와 상관없이 일정한 실행시간 ex 해쉬 검색 알고리즘 등 log N Divide&Conquer..

지금까지 듣던 강의의 내용을 옮겨적으려고 한다. 알고리즘의 정의 주어진 문제를 해결하기 위한 동작들의 유한집합 자료구조 알고리즘의 객체 구조화되고 조직화된 자료의 저장, 추출, 관리 방법 추상데이터 타입 (Abstracted Data Type) 배열 스택 큐 트리 등이 있음 알고리즘의 선택 하나의 문제에 대해 여러 알고리즘이 존재 ex) 어딘가에 이동할 때 지하철을 탈 수도 차를 탈 수도 있음 절대적으로 완벽한, 최상의 알고리즘은 없다 속도와 자원의 상관관계 속도가 빠르면 자원이 많이 들고, 자원이 적게 들면 속도가 느리다. 따라서 상황에 맞게 선택해서 사용. (메모리의 용량 등 고려)

그래프의 탐색 : 그래프에서 모든 정점들을 중복 없이 한 번씩 방문하는 방법 일반적인 탐색 방법으로 DFS(깊이우선탐색)과 BFS(너비우선탐색)이 있다. 두 탐색 방식의 이해는 유튜브 영상 하나를 보며 하게 되었는데 정리가 잘 되어있어 이해하기 쉬웠다. https://youtu.be/_hxFgg7TLZQ 깊이 우선 탐색 (DFS, Depth-First Search) 한 방향으로 갈 수 있을 때까지 가다가 더 이상 갈 수 없게 되면 가장 가까운 갈림길로 돌아와서 다른 방향으로 다시 탐색 진행된다. DFS는 Stack을 이용해 구현하게 된다. 너비우선탐색(BFS, Breadth-First Search) 깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모..

수업 시간에 string 몸 풀기로 I love C++의 글자를 출력할 때마다 밀어 뒤로 보내는 문제를 풀었다. 오랜만에 C++를 다시 잡으려니 문법도 기억이 나지 않고 어떻게 시작을 해야 할 지 막막했다. #include #include using namespace std; int main() { string str; char temp; getline(cin, str); // cin.getline은 string에서 쓸 수 없음 for (int i = 0; i < str.size(); i++) { temp = str[0]; str.erase(0, 1); str.push_back(temp); cout