전체 글56 1번 풀이 보호되어 있는 글 입니다. 2025. 3. 4. UnionFind 알고리즘 개념과 구현 * UnionFind- 유니온 파인드 알고리즘은 서로소 집합 ( Disjoint Set ) 을 관리하는 알고리즘- 같은 그룹인지 판별 할때 쓰는 isConnected() 함수- 두 그룹을 합칠떄 쓰는 Union() 함수를 사용한다. 1. 연결 요소가 존재하는가?- isConnected() 함수의 로직은 2개의 node가 포함된 루트 노드가 같은지 다른지를 판단하여같으면 연결 요소가 존재한다고 판단하고 True 반환. 다르면 연결 요소가 없다고 판단하여 False 반환. 2. Graph Cycle Detection- union() 함수를 사용하여 2개의 node를 합칠때 두개의 node의 루트노드가 다를때 union 된다.하지만 두개의 루트노드가 같을때 union 할시 Cycle 발생. - 즉 두개의 no.. 2025. 3. 3. 집합의 표현 ( 백준 1717번 ) https://www.acmicpc.net/problem/1717 * UnionFind 알고리즘 문제* 연산이 주어지는데- 0이면 a가 포함되어있는 집합과 b가 포함되어 있는 집합을 합친다는 의미- 1이면 두 원소가 같은 집합에 포함되어 있는지 확인하는 연산* 1연산을 진행했을때 포함되었으면 YES, 아니면 NO를 출력하면 된다. UnionFind 알고리즘 사용하기만 하면 풀리는 문제라서 개념은 따로 정리하겠다.아래는 코드. import java.io.*;import java.util.*;public class BOJ1717 { static int[] parents; public static void main(String[] args) throws IOException { Buff.. 2025. 3. 3. 평범한 배낭 ( 백준 12865 ) https://www.acmicpc.net/problem/12865* 잘 알려진 WellKnown 문제.* 포스팅한 문제중 카드 구매하기 문제와 비슷한 유형이다.* 카드 구매하기의 dp[] 배열의 의미는 dp[i] : i개의 카드팩을 구매 하기위한 최대 금액* 평범한 배낭 문제의 dp[][] 배열의 의미는dp[i][w] : i개의 물건을 고려했을때 무게 w가 가지는 최대 가치 ( value )* 두 문제의 차이점은- 카드팩은 i개의 카드팩을 구매하기 위한 금액 2가지의 변수가 존재하지만- 평범한 배낭은 i개의 물건을 고려하기 위한 w무게의 가치 즉 3가지의 변수를 고려해야한다. - 현재 무게값을 빼고 새로운 가치를 더한다- (현재 물건갯수 -1)와 같은 무게값과 비교해서 더 큰값을 갱신. * 카드팩 구매.. 2025. 3. 2. 카드 구매하기 ( 백준 11052 ) https://www.acmicpc.net/problem/11052 * dp 문제이다.* 인덱스가 카드 갯수이고 값이 가격이다* pack[1]의 뜻은 카드팩 1개를 지불해야하는 금액* dp[1]의 뜻은 카드팩 1개를 지불해야하는 최대 금액 (최댓값)* 카드 N개 구매시 최댓값을 계산* 차례대로 카드 1개 구매시 최댓값을 dp 배열에 저장 후 출력 * 점화식은 Math.max(dp[i], pack[j] + dp[i-j])* j+(i-j)개의 최댓값을 갱신하면 된다. 즉 i개의 최댓값을 인덱스 별로 계산. import java.io.*;import java.util.*;public class BOJ11052 { public static void main(String[] args) throws IOEx.. 2025. 2. 28. 푼 dp 유형 정리 1. 초급 DP * 1 2 3 더하기https://www.acmicpc.net/problem/9095 - 간단하게 첫번째 두번째 세번째 경우의 수만 구하면 규칙이 보이는 문제.- 여기서 dp는 점화식을 세우기 전에 초기값을 먼저 할당하고 점화식을 세우는게 중요하다고 느낌 * 1로 만들기https://www.acmicpc.net/problem/1463 * 계단 오르기https://www.acmicpc.net/problem/2579 * 포도주 시식https://www.acmicpc.net/problem/2156 - 둘다 3번연속 선택 못 한다는 조건이 존재- 3개의 초기값을 설정 후에 점화식을 세워야함- 계단 오르기는 마지막 계단은 꼭 밟아야 하기때문에 점화식을 세울때 현재 밟고 있는 계단은 꼭 값으로 포함.. 2025. 2. 27. 이전 1 2 3 4 ··· 10 다음
