분류 전체보기361 [BOJ]4195번: 친구 네트워크 문제: https://www.acmicpc.net/problem/4195 유니온, 파인드 문제입니다. 주어지는 친구 관계가 최대 10만이고, 한 번 친구 관계를 조회할 때 최대 10만개까지 노드를 탐색할 수 있습니다. (BFS, DFS 기준) 그러므로 O(10만^2) 으로 시간초과가 납니다. 그래서 노드 탐색 시간을 log시간으로 줄여야 시간 초과를 해결할 수 있습니다. 노드 탐색 시간을 log 시간으로 내리는 방법은 친구 관계가 주어질 때 마다 유니온, 파인드를 사용하여 컴포넌트 간에 연결 관계를 맺어줍니다. 새로운 관계를 맺는다면 친구 관계는 component1 + component2의 합이 될 것이고 이미 맺어진 관계(같은 컴포넌트에 속함)라면 component1 이나 component2 중 하나의.. 2022. 3. 2. [BOJ]1976번: 여행 가자 문제: https://www.acmicpc.net/problem/1976 N제한이 작으므로 완전 탐색으로 해결할 수 있습니다. 여행 계획 E-C-B-C-D를 예시로 설명해보면, 여행 계획을 출발지-도착지 관계로 E-C, C-B, B-C, C-D로 나눈 후 각 각을 방문할 수 있는지 DFS로 조사합니다. 시간복잡도는 O(N^2*M)으로 최악의 경우에도 O(40,000,000)이므로 시간 제한에 걸리지 않습니다 :) 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ1976.java 2022. 3. 2. [BOJ]16562번: 친구비 문제: https://www.acmicpc.net/problem/16562 그래프 문제입니다. 1. 주어진 간선(친구 관계)을 활용하여 전체 N개의 노드를 몇 개의 컴포넌트로 나눕니다. - 예제의 경우 2개의 컴포넌트로 나뉩니다. (1-3, 2-4-5) 2. 각 컴포넌트를 탐색하기 위한 최소 비용을 구합니다. 3. 각 컴포넌트를 탐색하기 위한 최소 비용들의 합이 K 이하라면 모든 사람과 친구가 될 수 있고, K 초과면 불가능합니다. 코드: https://github.com/cotchan/algorithm/blob/main/BOJ/BOJ16562.java 2022. 3. 2. 결합 인덱스 개인 공부 목적으로 작성한 글입니다. 아래 출처를 참고하여 작성하였습니다. 목차 결합 인덱스란 결합 인덱스 내 컬럼 순서의 중요성 1. 결합 인덱스란 결합 인덱스란 인덱스를 생성할 때 두 개 이상의 컬럼을 합쳐서 인덱스를 만드는 것을 말합니다. 주 용도는 SQL에서 WHERE절의 조건 컬럼이 2개 이상 AND로 연결되어 함께 사용되는 경우에 많이 사용합니다. 결합 인덱스는 AND 조건으로 검색되는 경우 성능에 중요한 역할을 합니다. 2. 결합 인덱스 내 컬럼 순서의 중요성 결합 인덱스를 생성할 때 컬럼 순서는 매우 중요합니다. 아래 그림은 결합 인덱스를 (SEX, NAME)과 (NAME, SEX)로 설정했을때의 차이를 나타냅니다. 결합 인덱스에서는 첫 번째 조건에서 최대한 많은 데이터를 걸러내서 두 번째.. 2021. 10. 29. 이전 1 ··· 12 13 14 15 16 17 18 ··· 91 다음
