Algorithm283 [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. [2020 카카오 기출] 기둥과 보 설치(JAVA) 문제: https://programmers.co.kr/learn/courses/30/lessons/60061 sooooooyn님의 솔루션으로 해결하였습니다. (https://sooooooyn.tistory.com/32) 기둥과 보를 설치/삭제 시에 어떻게 따져주는 지에 따라 난이도가 달라지는 문제입니다. 서치했던 솔루션 중에 굉장히 심플한 솔루션이라고 생각합니다. 간단하게 두 가지로 모든 경우를 처리합니다. 1. kidoong[N][N], bo[N][N] 으로 기둥과 보를 표현 2. 삭제 입력이 들어오면 일단 삭제 시켜본 후에, 삭제 시킨 좌표와 연관이 있는 기둥이나 보가 설치 불가능하다고 판정이 나는 경우 롤백시킵니다. 코드: https://github.com/cotchan/algorithm/blob/.. 2021. 7. 1. 이전 1 ··· 12 13 14 15 16 17 18 ··· 71 다음
