CS/알고리즘, 자료구조6

• [알고리즘 특강 6일차] 서로소 집합, 위상정렬, 최소 신장 트리, 최소 공통 조상 (Disjoint Set, Union-Find, DAG; Directed Acyclic Graph, Topological Sort, MST; Minimum Spanning Tree, Kruskal, Prim, LCA; Lowest Common Ancestor) 최소 신장 트리 (MST; Minimum Spanning Tree) 트리란? (Tree) 무향 그래프 G가 순환 없는 연결 그래프이면 G는 트리입니다. 숲이란? (Forest) 무향 그래프 G가 순환이 없는 그래프이면 G는 숲입니다. 신장 트리란? (Spanning Tree) 무향 연결 그래프 G의 부분그래프이며, G의 모든 정점을 포함 트리인 그래프입니다. 무향 연결 가중 그래프 S에서 간선의 가중치의 합이 최소인 신장 트리 (Spanning Tree) 입니다. 때문에 최소 신장 트리의 답은 여러 개가 될 수 있습니다. 신장 트리 탐색 종류 DFS Spanning Tree BFS Spanning Tree 크루스칼 알고리즘 (Kruskal) 프림 알고리즘 (Prim) 크루스칼 알고리즘 (Kruskal) .. CS/알고리즘, 자료구조 2022. 7. 25.

• [알고리즘 특강 4일차] 확장 유클리드 호제법, 베주 항등식, 에라토스테네스의 체 알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다. 내용이 이상하다면 지적해주시면 감사하겠습니다. 👍 벌써 알고리즘 특강 4일차 입니다. 정수론에 대해서 배웠는데 소수와 최대공약수와 관련된 알고리즘 이었습니다. 유클리드 호제법 유클리드 호제법은 2개의 자연수의 최대 공약수를 구하는 알고리즘 입니다. 두 개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 a와 b의 최대공약수는 b와 r의 최대공약수와 같다 성질을 이용합니다. 이제부터 자연수 a, b의 최대공약수를 gcd(a, b)라고 하겠습니다. (단, a > b) 그렇다면 gcd(a ,b)는 어떤 식으로 찾아지는 걸까요? (a % b) = ? 60 %.. CS/알고리즘, 자료구조 2022. 7. 24.

• 

  [알고리즘 특강 3일차] 인덱스 트리 (indexed tree, 이진 트리 응용) 알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다. 내용이 이상하다면 지적해주시면 감사하겠습니다. 👍 벌써 알고리즘 특강 3일차 입니다. 오늘 계속 조금씩 뭔가 빼먹으면서 문제를 풀었기에 틀릴 때가 많았습니다. 먼저 오늘 배웠던 것 중에 가장 어렵다고 느껴졌던 인덱스 트리에 대해 알아보겠습니다. 인덱스 트리 사용 이유 먼저 인덱스 트리를 사용하는 이유에 대해 알아보겠습니다. 한 개발자가 와서 저한테 이런 문제를 줬습니다. 이 배열 안에 있는 연속되는 숫자의 합을 구하는 프로그램을 구현해줘 😃 저는 여느때와 다름 없이 배열을 초기화여 입력값을 받고 숫자를 더할 배열를 범위를 입력받고 더했습니다. for (int idx =.. CS/알고리즘, 자료구조 2022. 7. 20.

• [알고리즘 특강 2일차] 시간복잡도의 응용 - (2-pointer, 슬라이딩 윈도우, 부분배열, 파라메틱 서치, 이분 검색) 알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자 세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다. 내용이 이상하다면 지적해주시면 감사하겠습니다. 👍 안녕하세요 이 포스팅은 알고리즘 2일차로 시간복잡도 응용편입니다. 시간복잡도 줄이는 방법들 문제 풀이와 함께 아래와 같은 기법들을 배웠습니다. 어디선가 한번쯤 사용해보았지만 ‘의식'하고 풀지는 않았던거 같습니다. 문제를 푸는데 많은 도움이 되는 기법들이니 꼭 숙지하고 가야합니다. 투 포인터 기법 투 포인터 기법이란 ? 투 포인터는 연속되고 가변적인 부분 배열을 이용하여 특정 조건을 일치시키는 알고리즘 입니다. 즉, 정렬되어 있을 때 사용할 수 있습니다. 투 포인터 언제 사용하는데? 2-포인터 기법은 보통 두 데이터를 .. CS/알고리즘, 자료구조 2022. 7. 19.

• 

  [알고리즘 특강 2일차] 시간복잡도의 이해 알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다. 내용이 이상하다면 지적해주시면 감사하겠습니다. 👍 안녕하세요 오늘은 알고리즘 2일차로 시간복잡도와 공간복잡도를 공부하겠습니다. 시간복잡도 (Time Complexity) 시간복잡도를 표기할 때는 보통 빅-오(Big-Oh) 표기법으로 최악의 경우 (Worst Case)의 연산 횟수를 나타냅니다. 이제는 문제를 풀을 때 구현은 기본이고 “시간복잡도"를 줄이는 훈련을 의식적으로 연습해야 합니다. 시간복잡도의 종류 상수형 (O(1)) 길이가 N인 배열에서 M번 째 배열값 출력 로그형 (O(logN)) N개의 정렬된 수열에서 이분탐색을 통해 특정 숫자를 탐색 우선순위 큐, 힙에.. CS/알고리즘, 자료구조 2022. 7. 19.

• [알고리즘 특강 1일차] 알고리즘이란, 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)의 이해와 활용 알고리즘 특강을 들으면서 인상 깊었던 내용을 정리합니다. 자세한 개념보다는 알고리즘의 '이해' 그리고 '활용'(팁)에 중점을 두었습니다. 내용이 이상하다면 지적해주시면 감사하겠습니다. 👍 안녕하세요 오늘은 알고리즘 1일차로 DFS와 BFS를 공부하였습니다. 아직 알고리즘 초보자로 많은 고생을 하고 있었는데 아래 내용을 듣고 배우면서 너무 유익하다고 느껴 기록하고 공유하고 싶어서 포스팅 합니다 ! 먼저 알고리즘 이란 ? 알고리즘이란 뭘까요 ? 알고리즘은 수학자 알콰리즈미(Al-Khwarizmi)에서 유래했고 '문제를 해결하기 위한 여러 동작들의 모임'을 의미합니다. 먼저 알고리즘은 완전탐색이 시작입니다. 저희는 이런 알고리즘을 이용하기 위해서는 복잡한 구조의 코드를 정확하게 구현할 수 있어야 합니다. 물론.. CS/알고리즘, 자료구조 2022. 7. 18.