전체 글

MariaDB의 장점(MySQL과의 비교)

MySQL에서 떨어져나온 RDBMS이기에 익숙한 MySQL과의 문법 차이가 거의 없다. MariaDB는 오픈소스이기에 상업용으로도 사용이 가능하다. ⇒ MySQL은 상업적인 용도에서는 유료 더 나은 성능을 갖고 있다. 좀 더 개방적이고 활발한 개발을 할 수 있다. 호환성이 좋다. 더 많은 스토리지 엔진을 갖고 있다. 참고 자료 https://bongjacy.tistory.com/entry/MariaDB-Mysql-둘-중에-무엇을-설치하지 https://engkimbs.tistory.com/931

[BOJ] 17471. 게리맨더링 (Java)

문제 출처 백준 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 처음에 이 문제를 봤을 때, Union-Find 문제인 줄 알았으나, union-find로 접근하면 문제가 많이 복잡해진다. 해당 상황은 그래프가 서로 다 연결되어 있을 수 있지만, 구역을 나눔에 따라서 인접하고 인접하지 않고가 나뉘므로 생각을 다시 해봐야 한다. 필요한 개념 부분집합 구하기 그래프 탐색 → bfs 또는 dfs 풀이 N의 범위가 2≤N≤10 이므로, 시간 복잡도 안에 들어오므로 두 선거구로 나누는 부분은 부분집합을 재귀로 구현할 수 있을 것 같다. 선거..

그래프와 트리의 차이점

백준 16437 문제를 풀면서 그래프, 트리의 차이가 제대로 정리되어 있지 않다는 것을 알았다. 그래서 정리해보려고 한다. 그래프 2개 이상의 경로가 가능 노드들 사이에서 무방향/방향에서 양방향 경로를 가질 수 있다. 루트노드라는 개념이 없다. 부모-자식 관계라는 개념이 없다. 그래프의 순회는 DFS, BFS로 이루어진다. 그래프는 싸이클을 형성하거나 형성하지 않는다. 방향 그래프와 무방향 그래프로 나눠진다. 간선의 유무는 그래프에 따라 다르다. 트리 트리는 그래프의 특별한 케이스이고, "최소 연결 트리"라고도 한다. 두 개의 정점 사이에 반드시 1개의 경로만을 가진다. 한 개의 루트 노드만이 존재하며, 모든 자식노드는 한 개의 부모노드만을 가진다. 트리의 순회는 전위순회, 중위순회, 후위 순회로 이루어..

[BOJ] 16437. 양 구출 작전 - Java

백준 16437 문제 풀이 과정 처음에는 그래프 문제라고 생각했고, 깊이 우선 탐색을 해야한다고 생각해서 깊이 우선으로 방문하는 코드를 짰다. 가장 끝 정점을 알고 그 부분부터 시작하면서 양을 만나면 더해주고, 늑대를 만나면 빼주는 코드로 짰지만 맞지 않았다. 트리를 통해 풀었더니 제대로 된 답을 낼 수 있었다. 해당 문제는, 어떠한 섬에서도 1번 섬으로 가는 경로가 유일하기 때문에 가장 끝 노드인 자식 노드부터 차례대로 늑대, 양의 개수를 누적하면서 1번까지 오면 결과가 나올 수 있는 문제이다. 따라서 트리 자료 구조를 이용하면 되고, postOrder(후위 순회) 방식을 이용하면 쉽게 풀 수 있다. 트리의 순회 전위 순회(preorder traverse) : 뿌리(root)를 먼저 방문 (Root →..