개발 쥬스

🔗 문제 링크: https://www.acmicpc.net/problem/1167🔍 해결 과정문제 예시를 바탕으로 트리를 만들어보면 다음과 같습니다.여기에서 1번 노드와 6번 노드까지의 거리가 11로 트리에서 가장 최대의 거리를 나타내므로 11이 이 트리의 지름값이라고 할 수가 있습니다. 만약 노드 V의 최대 개수가 최대 10만개가 아니고 매우 작은 값이었다면 단순하게 모든 노드를 시작점으로 했을 때의 dfs를 돌려서 최대 거리값을 구했겠지만 노드의 개수가 최대 10만개이기 때문에 모든 노드마다 dfs를 돌리기에는 시간 복잡도 O(V^2)이 나오기 때문에 다른 방식을 고민하는 일에 시간을 많이 쓴 문제였습니다. 과정을 세우기에 앞서서 다음과 같은 공식을 알아야 합니다.1️⃣ 임의의 노드 a를 한 시작..

🔗 문제 링크: https://www.acmicpc.net/problem/1068 🔍 해결 과정트리에서 특정 노드를 제거했을 때 그 특정 노드의 자식까지 전부 삭제를 해준 후 남은 리프 노드의 수를 반환하는 문제이므로 다음과 같은 과정을 세웠습니다.1️⃣ 트리에서 특정 노드가 리프노드인지 확인할 boolean형 배열 isLeaf를 만든다.2️⃣ 현재 트리에서 리프 노드를 찾아 isLeaf 배열을 수정한다. 아직 이 땐 특정 노드가 제거되지 않은 상태이다.3️⃣ 수정한 배열 isLeaf를 활용하여 리프 노드이면 리프 노드의 부모를 계속적으로 거스르며 삭제 제거 대상의 노드가 나오는지 탐색한다.4️⃣ 리프 노드의 부모들 중 제거 대상의 노드가 존재하지 않으면 리프 노드의 개수를 카운트한다. 노드의 개수의..

🔗 문제 링크: https://www.acmicpc.net/problem/20166🔍 고찰 과정dfs를 활용하여 신이 좋아하는 문자열에 도달하는 경우의 수를 구하면 될 것 같다는 생각이 들었습니다. 하지만 위 문제는 다음과 같은 변수가 존재했습니다. ❗️타일을 지나갔던 곳은 다시 지나갈 수 있음❗️타일의 양끝 밑 대각선 양 끝을 넘어가는 경우는 다시 처음으로 돌아가거나 마지막으로 돌아갈 수 있음❗️방문한 순서가 다른 경우는 서로 다른 경우로 취급함 위 변수를 토대로 최악의 경우에서 나올 수 있는 연산량을 계산해보면 다음과 같습니다.🎲 타일의 최대 크기 (N과 M 각각 최대 10): 10 x 10 = 100🎲 주어지는 신이 좋아하는 문자열의 최대 개수 k = 1000🎲 신이 좋아하는 문자열의 최대..

🔗 문제 링크: https://www.acmicpc.net/problem/3649🔍 해결 과정결론적으로 이진탐색 방법을 활용하여 문제를 해결하였습니다. 처음에는 나노미터의 값을 인덱스로 받고 나노미터의 값이 존재하는지의 여부를 나타내는 배열을 활용하여 문제를 해결하려고 하였으나 문제에서 x의 최댓값은 20이므로 나노미터의 최댓값은 2억이 되어 Java에서 정수형 변수의 크기가 4 byte라는 점을 고려하면 762.94MB가 되어 메모리의 최댓값인 256MB를 훌쩍 넘깁니다.  그래서 다른 방법을 생각한 결과가 이진탐색이었습니다. 이진탐색의 방법을 활용하면 목표로 하는 x의 값이 처음 일치했을 때 곧바로 |l2 - l1|의 값이 최대인 지점을 바로 구할 수가 있으며 또한 시간 복잡도 O(log n)에 ..

🔗 문제 링크: https://www.acmicpc.net/problem/4358🔍 고찰 과정자료구조를 활용하여 특정 종이 입력한 빈도수를 저장하고 비율을 출력하는 방식을 생각했습니다.사용한 자료구조는 TreeMap 형태의 자료구조를 사용했는데 그 이유는 key 값을 사전순으로 정렬을 해야 하는데 TreeMap은 문자열을 key값으로 입력 시 key 값을 사전순으로 정렬을 해주는 기능을 가지고 있기 때문입니다. 참고로 Java에서 TreeMap 형태의 자료구조는 Red-Black Tree라는 자료구조를 사용하여 키를 정렬하는데 자가 균형 이진 탐색 트리의 일종으로 키의 삽입, 삭제, 탐색이 모두 O(log n) 시간 복잡도를 가지고 있습니다.✏️ 코드import java.io.*;import java..

🔗 문제 링크: https://www.acmicpc.net/problem/1189🔍 해결 과정왼쪽 아래에서 오른쪽 위까지의 다양한 경로 중 k번 이동한 경로와 일치한 경우의 수를 구하는 문제이고, R과 C의 최댓값이 5이므로 dfs(Depth-First Search) 방식을 활용하여 오른쪽 위에 도달했을 때 k번 이동했는지의 경우를 확인하고 일치하면 경우를 세어주는 과정으로 코드를 구현하였습니다. dfs를 활용했을 때 O(R x C) 의 시간복잡도를 가지므로 제한 시간 안에 프로그램을 실행할 수가 있습니다. ✏️ 코드import java.io.*;import java.util.StringTokenizer;public class Main { private static final char BLOCK..