Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처트리의 순회 골드 1 📖 문제이진 트리 (완전 이진 트리 X) 이기에 한쪽으로 기울어긴 트리가 가능하다. 때문에 직접 배열로 이진트리를 만들 생각을 하면 안된다. 순회 특징후위 순회는 마지막이 항상 중앙노드다. 중앙 순회는 중앙노드 기준으로 왼쪽, 오른쪽 서브트리를 갖는다. 중앙노드, 서브트리, 왼쪽 끝 오른쪽 끝 노드를 알 수 있는데 어떻게 해야 전위순회를 할 수 있을까 분할 정복을 이용하면 쉽게 알 수 있다.후위 순회의 마지막 노드는 항상 중앙노드이므로 중앙 노드를 얻고 이 노드의 중앙 순회에서 위치를 얻은다음 중앙 순회에서 중앙 노드를 기준으로 왼쪽을 서브트리, 오른쪽을 서브트리로 나눠서 분할한다. 나눠지면 또 그 서브트리에서의 후위 순회의 마지막 노드는 그 서브트리의 중..

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

🧫 문제 분석 ✔️ 출처호텔 골드 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..