공부하는 신입의 기록 공부하는 신입의 기록

알고리즘 공부순서가 뒤죽박죽.. ㅎㅎ 개념을 알고난 뒤 다시 정리해야겠다.이번 포스팅과 다음 포스팅은 탐욕 알고리즘과 다이나이믹 프로그래밍에 대해서 하겠습니다. 1. 탐욕 알고리즘이란 - 현재 상황에서 가장 좋아보이는 답을 선택합니다. - 각 부분에서 최적을 선택하면 전체에서 최적이 될 것이라는 가정을 전제로 합니다. - 기본적으로 값이 큰 경우대로 극단적으로 문제를 접근합니다. 2. 탐욕 알고리즘의 사용 예 ① 분할 가능 배낭문제 - 여행가가 가지고 있는 배낭에는 담을 수 있는 무게의 최댓값이 정해져있고, 일정 가치와 무게가 있는 짐들을 배낭을 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 문제 ② 최소수의 동전으로 거스름돈 내주기 - 거스름돈을 내줄때 가장 적은 양의 동전을 내주는 문제 ex 1) ..

블로그 https://blog.naver.com/ndb796/221230945092 와 https://www.geeksforgeeks.org/depth-first-search-or-dfs-for-a-graph/ 을 참고하였습니다. 1. DFS (Depth First Search) - 깊이 우선 탐색이란?? - Stack을 사용하며 해당 노드에서 다음 노드로 넘어가기 전 완벽하게 탐색하는 알고리즘입니다. - 재귀함수를 사용하고, 넓게 탐색하기 전 깊에 탐색합니다. 2. DFS 의 과정 ① 9개의 노드들이 존재합니다. ② 시작노드 1을 Stack에 삽입하며 시작합니다. ③ 1의 노드 인접한 노드들을 차례로 순회하며 Stack에 넣고 방문처리합니다. ④ 더이상 노드 2의 인접노드는 없으므로 다시 1의 인접노드..

블로그 https://blog.naver.com/ndb796/221230944971 와 https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/ 을 참고하였습니다. 1. BFS (Breath First Search) - 너비 우선 탐색 이란?? - 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법으로 깊게 탐색하기 전 넓게 탐색 하는 알고리즘입니다. - Queue를 사용하며, 시작노드에서 거리에 따라단계별로 탐색합니다. 2. BFS의 과정 ① 9개의 노드들이 존재합니다. ② 노드 1을 시작 노드로 큐에 삽입하며 시작합니다. ③ 노드 1에 연결되는 노드2와 3을 차례대로 큐에 삽입합니다. ④ Queue의 2 노드를 방문하지만 연결..

유클리드 호제법은 최대공약수를 구하는 알고리즘 중 하나입니다.최대공약수를 구하면 최소공배수도 구할 수 있겠죠?? ㅎㅎ간단하므로 짧게 정리!! 1. 유클리드 호제법이란? - 유클리드 호제법은 2개의 자연수 또는 정수의 최대공약수를 구할 수 있습니다. * 호제법 : 두수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘 2. 유클리드 호제법 이해 ▶ 자연수 또는 정수 A, B에 대해 A를 B로 나눈 나머지를 R이라고 하면 A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다. ① A와 B라는 두 정수가 있고, A가 B보다 큰 값이라고 가정합니다. ( A > B ) ② A를 B로 나눈 나머지가 R이라고 합니다. ( A mod B == R ) ③ R이 0이라면 최대 공약수는 B 입니다. ( A mod..

기본적인. 소수 구하는 알고리즘익히고있자~~ 1. 에라토스테네스의 체란? - 고대 그리스 수학자 에라토스테네스가 발견한 소수를 찾는 방법입니다. * 소수란? 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수 2. 에라토스테네스의 이해 (출처 : 위키백과) ① 2부터 소수를 구하고자 하는 구간( 1 ~ 120 )을 정합니다. ② 2는 소수이므로 Prime numbers로 지정하고, 2의 배수를 모두 지웁니다. ③ 남은 수 중에서 3은 소수이므로 Prime numbers로 지정하고, 3의 배수를 모두 지웁니다. (지울 때 겹쳐지는 수는 무시하고 진행합니다. ) ④ 5, 7, 11, 등 남은 수들을 위와 같은 과정으로 반복하면 Prime numbers 을 알 수 있습니다. 3. 에라토스테네스의 구현1234..

Union-Find에 이어서 Kruskal ...익숙해지자!!Kruskal 이해하는데 https://blog.naver.com/ndb796/221230967614 님의 블로그 도움 많이 되었습니다. 1. Kruskal Algorithm 이란? - 최소 비용 신장 트리(MST)를 만들기 위한 대표적인 알고리즘입니다. - 그래프에서 가중치가 할당된 간선의 모든 정점을 비교하여 최소 비용으로 연결하여 최적 답을 구합니다. * 신장 트리(Spanning Tree) : 그래프내의 모든 정점을 포함하는 트리, n개의 정점이 가지는 최소 간선의 수는 n-1개이다. 최소 비용 신장 트리(Mininum Spanning Tree) : 간선간의 가중치를 고려하여 가장 작은 가중치의 최소 비용의 Spanning Tree를 선..

혼자 공부삼아 끄적끄적...참고한 블로그는 https://blog.naver.com/ndb796/221230967614 입니다. 좋은 내용 감사합니다. 1. Union-Find 이란? - 대표적인 그래프 알고리즘입니다. - 서로소 집합 (Disjoint-Set) 그리고 병합 찾기 집합 (Merge-Find-Set), 합집합 찾기(Union-Find) 이라고도 부릅니다. - 서로소 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 서로 같은 집합에 속하는지 판별하는 알고리즘입니다. 2. Union-Find 연산 ① 초기화 - 특정한 노드의 부모를 찾을 수 있도록 만들어 준다.1234567 int getParent(int parent[], int x) { if(parent[x]==x) { return x;..

알고리즘 공부를 하면서 여러 정렬에 대한 이해가 필요한데, 그중에서도 퀵정렬에 대해 알아보고자 먼저 글을 정리해보았다. 1. 퀵 정렬(Quick Sort)의 이해 - 퀵 정렬(Quick Sort)는 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘입니다. - 퀵 정렬은 분할 정복(divide-and-conquer) 전략을 사용하는 재귀 알고리즘 입니다. - 퀵 정렬 단계 ① 리스트의 여러 요소 중 하나의 *pivot을 골라 pivot보다 작은 값들은 왼쪽, 큰 값들은 오른쪽으로 보내 분할합니다. * pivot은 정렬의 기준값이 된다. ② 이후 분할된 리스트들을 재귀적으로 정복합니다. ③ 재귀적으로 정렬이 끝났다면 결합된 상태로 정렬되었습니다. 퀵 정렬(Quick Sort) 난수열에 대해 퀵 정렬을 실행한 ..