전체 글170 [DB] INDEX란? (with. 클러스터링 & 논-클러스터링) 인덱스를 사용하는 이유 SELECT * FROM customer WHERE first_name = 'Minsoo';first_name이 Minsoo인 튜플을 찾기 위해 full Scan이 진행된다.사용 이유조건을 만족하는 튜플을 빠르게 조회빠르게 정렬(order by)하거나 그룹핑(group by)하기 위해인덱스를 거는 방법SELECT * FROM player WHERE name = 'Sonny'SELECT * FROM player WHERE team_id = 105 AND backnumber = 7;위 조회 쿼리에서 사용할 인덱스를 걸어보자CREATE INDEX player_name_idx ON player (name)CREATE UNIQUE INDEX team_id_backnumber_idx ON p.. 2024. 7. 21. BOJ 4386 - 별자리 만들기 https://www.acmicpc.net/problem/4386 접근전형적인 최소 스패닝 트리 문제이다. 따라서 크루스칼을 이용하였다.이번 문제는 별들 사이의 거리를 직접 점과 점 사이의 거리를 이용하여 구해야 한다.그 외에는 쉽게 해결 가능하다. #include #include #include #include #include #include using namespace std;int n;typedef pair > p;vector edges;vector> vertices;int parent[101];int find_parent(int x) { if (parent[x] == x) return x; return parent[x] = find_parent(parent[x]);}void union_.. 2024. 7. 15. BOJ 7579 - 앱 https://www.acmicpc.net/problem/7579 접근앱 중 최소비용으로 최대의 메모리를 확보하는 문제이다.휴대폰 메모리 M이 정해져있기 때문에, 냅색 문제로 해결할 수 있다.냅색 문제에서 weight와 value는 각각 앱의 비용과 앱의 메모리를 의미한다. 기존 냅색 문제에서 DP[i][j]의 의미는 i번째 앱 시점에서 j의 코스트로 가지는 최대 메모리 사용량이다.이중for문을 돌면서 DP[i][j]를 구하면된다. 그리고 마지막에 DP[i][j]가 M이상인 것 중 첫번째가 답이 된다.왜냐하면 i번째를 살펴볼때 j가 0부터 total(사용할 수 있는 최대 코스트)까지를 살피는 경우는 i번째 앱이 포함될 수도 있고 아닐 수도 있기 때문이다. 코드#include #include #inclu.. 2024. 7. 12. BOJ 1477 - 휴게소 세우기 https://www.acmicpc.net/problem/1477 접근휴게소 간 거리가 최소가 되는 거리를 찾는 문제이다.최소 거리를 찾는 문제이므로 매개변수 탐색을 통해 해결할 수 있다. 무엇을 기준으로 이분적으로 구분을 하면될까?휴게소 사이 (+ 시작지점과 끝지점 포함)에 새로운 휴게소를 건설한다는 가정하에 N의 거리를 두고 새로운 휴게소가 지어진다고 가정해보자.이렇게 되면 우리는 휴게소 사이에 둘 새로운 휴게소를 두는 지점을 이분적으로 탐색하면 된다. 예제 1번을 예를 들면휴게소 사이에서 어떤 거리 D을 기준으로 새로운 휴게소가 세워진다. 만약 휴게소 사이를 D으로 나누었을 때, 새롭게 세워진 휴게소가 M개가 넘는다면D를 늘려야 하므로 left = mid+1을 하면 된다. 반대로 새롭게 세워진 휴게.. 2024. 7. 12. BOJ 17404 - RGB 거리 2 https://www.acmicpc.net/problem/17404 접근기존 RGB 거리 문제에서 첫 번째 집과 마지막 집의 색을 고려하는 조건이 추가된 문제이다.DP를 이용하여 풀게되면 마지막 집을 칠할 때, 첫번째로 어떤 집을 선택했는지 알 수 없다.따라서, 첫 번째 집을 칠할 색을 저장하고 마지막 집의 색을 고려해야 한다. 첫 번째 집을 고르는 경우를 for문을 통해 선택하고, 기존 처럼 진행하면 된다.그러나 여기서 문제되는 부분이 있다. 첫 번째 집을 Red를 선택한다고 가정해보자.dp[1][1] = arr[1][1];for (int i = 2; i 위 코드에서 dp[i][1] = min(dp[i - 1][2], dp[i - 1][3]) + cost[i][1];을 하는 순간 dp[1][1] 대신.. 2024. 7. 1. BOJ 11404 - 플로이드 https://www.acmicpc.net/problem/11404 접근모든 도시끼리 이동하는 비용 최솟값을 구하는 문제이다.시작 도시와 도착 도시를 연결하는 노선은 하나가 아닐 수 있다.따라서, 모든 노드를 거쳐 시작 도시와 도착 도시를 이동하는 모든 노선을 확인해야 한다.이를 구현하기 적합한 알고리즘은 플로이드 와샬이다. 플로이드 와샬을 통해 중간 노드를 거쳐가는 모든 노선을 확인해보도록 하자.알고리즘은 매우 간단하다. 당연하지만, 시작 노드와 도착 노선 그리고 중간 노드를 모두 확인하기에 O(N^3)이 걸린다. 더보기#include #include #include #include using namespace std;#define MAX 9999999int n, m;int res[101][101];v.. 2024. 7. 1. 이전 1 2 3 4 5 6 ··· 29 다음
