전공공부/알고리즘&자료구조
-
기본정렬전공공부/알고리즘&자료구조 2020. 6. 11. 13:01
선택, 버블, 삽입, 쉘, 퀵, 합병, 힙, 계수, 기수 정렬 모두 오름차순을 기준으로 정렬 1. 선택 정렬 첫번째 원소부터 마지막 원소까지 정렬을 한다고 했을때 전체 배열 중 가장 작은 원소를 찾아 첫번째 원소부터 순서대로 교환해가며 최솟값을 차례대로 넣는 정렬이라고 할 수 있다. 그래서 총 n번, 나머지 원소들 n-1, n-2, n-3, ... 개의 원소와 비교하게 되므로 시간복잡도는 O(n^2)이다. 2. 버블 정렬 거품이 수중위로 올라가는 것처럼 인덱스를 첫번째에서 마지막으로 이동하는 도중 해당 위치에서의 값이 다음 인덱스의 값보다 크면 교환하여 값이 큰 원소를 마지막으로 계속해서 밀어내는 정렬 방법이라고 할 수 있다. 즉 마지막위치에 최댓값을 쌓아가는 방식으로 정렬한다. 시간복잡도는 O(n^2)..
-
오목 AI 제작 - MIN_MAX 전략을 통한 필승 수 구현전공공부/알고리즘&자료구조 2020. 4. 26. 14:09
탐색을 적용시킨 오목 AI를 구현해보고 싶어서 3일동안 AI 제작을 진행하게 됐습니다. 먼저 19*19 바둑판 맵을 다 탐색을 하여 돌의 연결상태를 확인한 후 각 돌의 연결 상황마다 가중치를 부여했습니다. 그 후 Search 함수를 통해 탐색 과정에서 AI끼리 각자 가지치기 방식으로 최적의 수를 두어나갑니다. 탐색 중 상대방이 이기는 경우가 발생 하면 return 하여 가지가 갈라지는 분기점으로 돌아가 재 탐색을 시작합니다. 그렇게 탐색하는 도중 자신의 AI가 이기는 상황이 발생하면 맨 처음 좌표값을 저장한 후 그 이후부터는 모든 상황에 대해 return하여 탐색을 종료시켜 제작하였습니다. 최대 깊이 탐색은 현재 시점으로부터 30수까지 설정해 놓았습니다. 그 이유는 웬만하면 승부가 나는 시점까지 도달하고..
-
최소공통조상 (LCA, Lowest Common Ancestor)전공공부/알고리즘&자료구조 2020. 1. 26. 19:31
최소공통조상은 트리에서 말 그대로 가장 가까운 공통 조상을 뜻한다. 참고링크: https://www.crocus.co.kr/660 LCA(Lowest Common Ancestor) 알고리즘 LCA(Lowest Common Ancestor) 알고리즘이란? LCA 알고리즘이란 영어 해석 그대로 최소 공통 조상을 찾는 알고리즘이고, 두 정점 u, v(혹은 a, b)에서 가장 가까운 공통 조상을 찾는 과정을 말한다. 예를들어 다음.. www.crocus.co.kr 코드로 구현시 핵심은 먼저 조상의 max_depth 지정이다. 이때 이 max_depth는 2^depth번째 조상을 구하기 위한 변수이기 때문에 조상을 구하는 최대 깊이는 log2(노드 최대 개수)를 올림한 값이 된다. 예를들어 노드 최대 개수가 3이..
-
Union-Find, 최소신장 트리 (MST, Minimum Spanning Tree)전공공부/알고리즘&자료구조 2020. 1. 26. 18:50
최소신장트리는 그래프에서 일부 간선을 선택해서 만든 트리이다. 이때 간선의 개수는 노드의 개수가 n개라고 했을 때 n-1개가 된다. 간선을 선택하는 방법은 greedy 한 방법으로 가장 최소의 비용이 드는 간선을 선택하고 이미 선택이 돼 있는 2개의 노드를 선택하지 않는 조건을 지켜가며 트리를 구성하게 된다. 참고 링크: https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html [알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 관련 예제 백준: 1922 네트워크 연결 https://www.a..
-
위상정렬 (topological sorting)전공공부/알고리즘&자료구조 2020. 1. 26. 18:31
참고: https://gmlwjd9405.github.io/2018/08/27/algorithm-topological-sort.html [알고리즘] 위상 정렬(Topological Sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 위상 정렬(Topological Sort)을 이용한 기본적인 해결 방법 위상정렬 순서 1. 진입 차수가 0인 정점(즉, 들어오는 간선의 수가 0)을 선택 진입 차수가 0인 정점이 여러 개 존재할 경우 어느 정점을 선택해도 무방하다. 초기에 간선의 수가 0인 모든 정점을 큐에 삽입 2. 선택된 정점과 여기에 부속된 모든 간선을 삭제 선택된 정점을 큐에서 삭제 선택된 정점에 부속된..
-
순열과 조합전공공부/알고리즘&자료구조 2020. 1. 12. 22:33
조합 출력 문제 출처:https://www.acmicpc.net/problem/1256 1256번: 사전 첫째 줄에 N, M, K가 순서대로 주어진다. N과 M은 100보다 작거나 같은 자연수이고, K는 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 소스코드 순열 출력 문제 출처:https://www.acmicpc.net/problem/1722 1722번: 순열의 순서 첫째 줄에 N(1≤N≤20)이 주어진다. 둘째 줄의 첫 번째 수는 소문제 번호이다. 1인 경우 k(1≤k≤N!)를 입력받고, 2인 경우 임의의 순열을 나타내는 N개의 수를 입력받는다. N개의 수에는 1부터 N까지의 정수가 한 번씩만 나타난다. www.acmicpc.net 소스코드
-
확장 유클리드 호제법전공공부/알고리즘&자료구조 2020. 1. 12. 22:24
유클리드 호제법을 활용하여 최대공약수를 구할 수 있다. 그리고 유클리드 호제법을 응용하여 일차방정식의 해를 쉽게 구할 수 있는 방법이 확장 유클리드 호제법 방법이다. ax + by = c 라는 방정식이 있다고 하자. 1. 좌변과 우변의 공약수가 있는 경우 약분을 하고, 우변의 값이 gcd(a,b)의 배수인 경우 gcd(a,b)로 변경한 후 해를 구한다. 그래서 gcd(a,b)가 서로소인 경우 우변을 1로 놓을 수 있다. 반대로 예를들어 162x+42y=19의 경우 19가 gcd(162,42)=6의 배수가 아니므로 해가 존재하지 않는다. a,b,c가 입력값으로 주어져 있다고 하자 먼저 확장 유클리드 호제법을 적용하기 전에 gcd(a,b)의 값이 1이라면 그렇다면 먼저 방정식을 ax + by =1 로 변환 ..
-
트라이 (Trie)전공공부/알고리즘&자료구조 2020. 1. 12. 21:53
출처: https://www.crocus.co.kr/1053 [Crocus] 트라이(Trie) 자료구조 목차 1. 트라이(Trie)란? 2. 트라이(Trie) 이해하기 3. 트라이(Trie)의 단점 4. 트라이(Trie) 접목하기 5. 트라이(Trie) 문제 풀어보기 트라이(Trie)란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합.. www.crocus.co.kr 트라이 (Trie)란? 문자열에 특화된 자료 구조인 트라이(Trie)는 문자열 집합을 표현하는 트리 자료구조이며, 우리가 원하는 원소를 찾는 작업을 O(n)에 (단어길이 만에) 해결 할 수 있는 자료구조이다. 알파벳을 저장하려면 Trie 구조체 안에 Trie* next[26] 과 같이 포인터배열로 정의 할 수 있다. 그리고 f..