Meluu_의 코딩 공부 일지

백준 20303번 : 할로윈의 양아치 [자바]

🧫 문제 분석 ✔️ 출처할로윈의 양아치 골드 2 📖 문제2차원 DP로 좀 많이 복잡하게 풀었다.시간 제한 거의 닿을정도로 ㅋㅋ.. 유니온-파인드Set + 넵샥 알고리즘으로 풀었다.그리고 다른사람 풀이를 봤더니 1차원으로 충분히 가능하다는 것이다. 이번 풀이의 문제점Set으로 아이들의 값을 굳이 배열로 만듦경로 압축을 했어도 중간 부모가 있음을 알지 못했음 (항상 최상위 부모를 찾을려면 find 할 것)1차원 냅샥을 생각했지만 정방향으로만 생각해서 중복 연산될거라고 한 점 - 이는 역방향으로 하면 중복연산하지 않는다. 🔅 문제 풀이import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.IOException;impor..

배낭 문제

일반적으로 배낭문제는정해진 무게 안에 가장 가치 있는 물건을 고르는 것 이다. 이번 포스팅에서는 배낭 문제의 3가지 유형 (0/1, 무한, 개수제한)에 대해 이해해보려한다.사실 배낭문제도 2차원 배열을 활용한 DP 문제다 따라서 제일 먼저 문제를 보고 할 일은 최적 부분 구조 + 부분 반복 문제 확인하는 것이다. 이전 상태 유지 + 개수 제한 일 때는 중복 사용 방지를 위해 2차원 배열을 사용이 유리할 수 있다. 개수제한일 때를 생각해보면 1차원 배열 사용시 중복 사용될 가능성이 있다. 제한이 2개일때 배낭 무게 최대 무게 6아이템 1개에 대하여 무게 2, 가치 10 이라하면dp = {0, 0, 10, 0, 20, 0, 30} 이런식으로 3번 같은 아이템을 사용해 버린다. 때문에 2차원 배열로 같은..

백준 1106번 : 호텔 [자바]

🧫 문제 분석 ✔️ 출처호텔 골드 4 📖 문제배낭문제처음에는 우선 가격대비 효율이 가장 좋은 도시를 찾아서 C / 도시의 고객수 * 가격 + C % 도시의 고객수 를 만족하는 모든 도시의 최소값을 구할라했으나이는 불가능했다. 가격 대비 효율을 단순히 (고객수 - 가격) 순으로 내림차순 정렬하려했으나4 91 5 위의 경우 4 9 가 더 효율이 좋다고 판단해버린다. 즉, 완전 잘못 설계했다. DP로 풀어야하는 문제이다. 각 도시에 대하여 1~C 까지의 가격 최솟값을 구하면된다. 1. 현 도시의 홍보만으로 c를 채우는 경우2. 현 도시의 홍보 1개만 사용하고 나머지 c를 다른 최솟값으로 채우는 경우3. 이전 도시까지와 현재 도시를 비교하여 최솟값을 갱신 그런데 이 문제는 1차원 DP로도 충분히 풀 수 ..

🧫 문제 분석 ✔️ 출처벽 부수고 이동하기 4 골드 2 📖 문제 그래프 탐색 문제기존 벽 부수기와 달리 벽을 부쉈을때 이동가능한 칸의 개수를 부순 자리에 출력하고 벽이 아닌 곳 즉, 0인곳은 그대로 0 을 출력한다. 벽을 부쉈을때 마다 0을 탐색하는것보다 미리 0의 영역을 나눠서 탐색하여 해당 영역의 0의 개수를 구해놓고 각 벽의 위치에서 상하좌우 인접한 칸이 0인지 확인후 해당 칸의 영역에 구해놓은 0의 개수를 더하는 식으로 하면된다. 중요한 점은 영역 중복 연산 처리이다. boolean 이중 배열로 했다가 메모리초과를 계속당했다. Set을 사용하여 해결하였다.✔️ Set.claer()에 대해서set이 가능한 이유는 상하좌우 4가지에 대해서만 영역을 체크하기 때문이다.clear()메서드는 모든 s..

🧫 문제 분석 ✔️ 출처공항 골드 2 📖 문제 서로소 집합의 경로 압축 방법을 사용하여 풀었다. 각 게이트는 도킹 가능한 게이트를 가리킨다. 처음에는 각자 자신을 가리키지만 비행기 도킹시 각 게이트는 자신의 게이트는 이미 도킹되었으므로 도킹 가능한 게이트를 가리켜준다. 만약 가리킨 게이트가 0이라면 이는 더이상 도킹할 수 없다는 의미이다. 예제 2번을 예시로 들어보면2 2 3 3 4 4 비행기 순서 1 2 3 4 게이트 1 2 3 4 게이트가 가리키는 도킹 가능 게이트 1) 1번째 비행기 도킹1 2 3 4 2번째에 도킹후 2번 게이트는 방문처리후 -1로 이전 게이트를 가리키게 한다. 1 1 3 4 2) 2번째 비행기 도킹1 2 3 4 2번째 도킹 시도시 이미 방문을 했기에 가리..

🧫 문제 분석 ✔️ 출처1의 개수 세기 골드 2 📖 문제 BigInteger 로 풀었는데 굳이 안써도 long타입으로 커버쳐지나보다.2^i 인 수의 1의 개수를 누적합으로 구하는데 너무 큰 범위까지 구해서 그렇다.10^16이하까지만 구하면됐는데 ... 포스팅한 이유는 사실 다른사람의 코드를 이해하기 위함이다. https://tussle.tistory.com/1022 이 분의 풀이를 이해하고 정리해보겠다.i = i번째 자리일때 최댓값까지의 1의 개수 i = 2 이면 000~ 111 까지의 1의 개수를 구하는 것이다. i = 3 : 0000 ~ 1111까지의 1의 개수 2^n일때 1의 개수 dp[n] = dp[n-1] * 2 + 2^n if (n == 0) dp[0] = 1;이런 점화식이 나오는데..

🧫 문제 분석 ✔️ 출처텀 프로젝트 골드 3 📖 문제 그래프 탐색을 하되 Stack + Set 조합으로 풀었다. 근데 DFS로 푸는게 정석인가보다. test case142 1 2 3answer : 2wrong : 무한루프 DFS로 다시 풀었을때 시간 초과가 났던 문제의 코드 private static void dfs(int current) { visited[current] = true; int next = students[current]; if (!visited[next]) { dfs(next); } else { if (finished[next]) return; // 이미 팀 구성을 한 학생이면 더이상 탐..

🧫 문제 분석 ✔️ 출처음악프로그램 골드 3 📖 문제 위상정렬 문제로 간단하게 위상정렬 풀이를 하면된다.진입차수가 0인 것만 BFS 탐색을 해주고 중복 탐색을 하지 않게 처리만 잘 해주면 간단한 문제다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static StringBuilder sb = new StringBuilder(); static int[] indegree; static List[] graph; static boolean[] visited; static int orderCount = 0; public static void main(String[] args) throws IOExcepti..

🧫 문제 분석 ✔️ 출처세 용액 골드 3 📖 문제 기존 두 용액 문제에서전체를 투포인터로 두고 투 포인터를 제외한 곳을 이분탐색으로 해서 풀려했으나당연히 모든 용액이 3가지씩 조합되지 않기에 계속해서 틀렸다. 나의 약한 부분중 하나가 이런 부분인 것 같다. 꼭 3개이상 , 여러개 등 조합해야하는 문제나 비슷한 문제들을 만나면하나를 고정하고 푼다는 이런 생각을 떠올리지 못한다. 까먹지 않기위해 블로그에 박제한다. 그리고 기껏 long type으로 계산해야한다고 메모해놓고 또 (long)으로 캐스팅안해서 틀렸다... 🔅 풀이 시도 import java.io.*;import java.util.*;public class Main { static int[] solutions; static in..

🧫 문제 분석 ✔️ 출처두 배열의 합 골드 3 📖 문제 누적합 + HashMap 문제 부 배열은 연속된 i~j까지의 합을 의미한다. A와 B의 부배열의 합이 T가 되는 쌍의 개수를 구한다. A배열에서 나올 수 있는 모든 누적합을 구하고, (key : 누적합, value : 개수)로 해시 맵에 저장한다.B배열도 마찬가지로 진행한다. 예시A배열의 누적합1 4 5 7 3 4 6 1 3 2이것들을 다 Map 에 저장 B배열을 키값(b배열 누적합)으로 순회하면서 T-(b배열의 누적합)이 A누적합이 저장된 해시 맵에 있는지 확인후개수를 곱해서 구한다. 47퍼에서 틀렸었는데 개수는 Integer 범위를 넘어설 수 있기때문이다. 따라서 Long 타입으로 변경해주었다.🔅 문제 풀이import ja..