전공공부

설명 처음에는 이분탐색 느낌으로 풀 수 있을까 싶었는데 그런 느낌 보다는 root 값이 위치한 곳을 찾아야 한다. 왼쪽의 경우에는 어찌 어찌 찾아 가겠으나 오른쪽에 있는 문제들은 결국 같은 로직으로 찾을 수 없으니 직접 preOrder의 첫번째 부분이랑 inOrder의 preOrder의 첫번째 부분과 같은 부분을 찾아야 한다. 참고로 전위 순회는 root -> left -> right이니 처음 나오는 곳들이 모두 해당 노드의 root가 되는 것이다. 그래서 루트 위치찍고 inOrder의 경우에는 root 위치로 부터 다음 left,right를 주기 위한 조건으로 사용하게 된다. 위 말이 이해가 되지 않는다면 내가 참고한 블로그 링크를 참조하면 되겠다. [BOJ] 백준 4256번 트리 (Java) #425..

설명 다른 형태로 더 깔끔하게 풀 수 있지 않을까 하는 의문이 남았던 코드다. 중간에 버리고 다른 자료구조로 짜려다가 조건들을 누락한게 보여서 하나하나 추가 했더니 코드가 길고 살짝 더러워졌다. 조건중에 주의 할 점은 두 노드의 부모는 다르지만, 두 부모가 형제(sibling)일 때 두 노드를 사촌이라고 한다. 즉, 부모가 형제 상태이여야 사촌이라고 할 수 있다. depth만 같다고 사촌이 아니고 그러니, 부모의 부모까지 한 노드로 연결된지 유무를 파악하는 코드가 필요하다. 코드 package tree; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.*; public class BOJ_9489 { stat..

설명 진작 맞추고 ==을 써서 틀렸었던 문제다. Integer와 같이 Wrapper class의 비교가 필요할때는 equals로 비교를 하는 것이 안전 한 것 같다. ==을 쓰면 아래 코드의 이 중 포문에서 node.get(i) == node2.get(j) 를 쓰면 25%에서 무조건 틀렸습니다가 뜬다. 그래서, 다른 사람 풀이를 참고했는데 사실상 다를 것이 없어서 일일이 넣어보면서 찾아냈는데 equals를 사용하니 맞았다. 우선, 코드 자체는 dfs로 아래 두 정점에 대해서 각 부모를 탐색해서 올라가는 식으로 구현하였다. 이런식으로 구현하면 처음 만나는 부모 노드가 가장 깊이가 깊은 노드이므로 별도의 신경을 쓰지 않고 구현 할 수 있다. 코드 import java.io.BufferedReader; imp..

설명 트리의 각 노드별로 출발해서 어디가 제일 긴 edge 값을 가지는 것인지 판별하는 문제였다. N이 10000이여서 10000*10000 해보니 1억정도라서 아래와 같이 코드를 짜서 모든 노드에서 출발해서 탐색하는 식으로 풀었는데 다른 사람의 풀이를 보니 루트로 부터 한 번 돌리고 루트로 부터 가장 먼 노드를 구해서 탐색하는 식으로 구현하는 방법도 있었다. 사실 탐색 문제의 경우 처음 길을 잘 들여 놓으면 너무 쉬운 문제들이라 크게 설명 할 것이 없다. 초보자라면 차근 차근 재귀의 형태를 실제로 그려보면서 푸는 것도 좋은 방법일듯 하다. 코드 package tree; import java.io.BufferedReader; import java.io.IOException; import java.io.I..

설명 조건을 잘 보면 리프노드에서 빗물이 고여있고 이때, 루트로 부터 시작한 이 빗물이 각 리프노드까지 갔을때의 평균치를 구하면된다. 예시 20/3 = 6.6666666667 이런식으로 구현하면 된다. 재귀적으로 깊이 우선 탐색으로 구현하고 이때의 값을 구해준다. 참고 할 점은 int로 리턴해줘야 시간초과가 나지 않는다. double return시 시간초과가 난다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static List[] tree; static boolean visited[]; public sta..

설명 생각과 달리 예외 상황에서의 처리가 부족해서 시간이 오래걸렸던 문제다. DFS를 간단히 돌면서 카운트하면 될 줄 알았지만 루트가 기가노드일때의 상황을 고려를 충분히 하지 않아서 시간이 걸렸다.(R == idx && list[idx].size() >= 2 일때) 그리고, 기가 노드 속으로 들어 갔을때 거기서 부터 2개 이상의 가지로 나뉠때 카운트를 충분히 고려하지 않아서 처음에 헷갈렸던 문제다. (cnt -= 부분) 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.*; public class Main { static class Node { int n..

설명 어떻게 풀지만 정하고 제대로 나아갔으면 쉽게 풀었을텐데 배열의 형태로 자꾸 구현하려고 하니 막혔다. 하지만, 다른 사람들의 풀이법을 알고보니 LinkedList 형태로 풀면 정말 쉽게 풀 수 있는 것이다... 그래서 아래와 같은 형태로 구현하고 진행하면 되는 형태였는데 사실 이건 풀이법을 어떻게 구현할지를 떠올리는 것이 문제의 대부분을 차지 할 것 같다. 조금 쉬운 문제였는데 스스로 풀지 못해서 아쉽다. +) 구현에 도움을 준 블로그 [백준] 5639번: 이진 검색 트리 - JAVA 🔗 문제 링크 BOJ 5639번: 이진 검색 트리 1️⃣ 트리 직접 그리기 📝 풀이 과정 전위 순회의 경우 처음 탐색한 값이 항상 root이기 때문에 먼저 처음 값을 root로 설정해 주었다. 이후 반복문을 돌며 gir..

설명 이전에 같은 문제를 풀었던 이력이 있어서 풀었는데 거의 이전과 동일한 풀이법이 나와서 조금 놀랐다. 트리 형태를 갖추고 해당 노드를 제외하고 리프노드의 갯수를 찾기 위한 로직인데 root가 지워지면 리프노드의 갯수를 셀 수 있는 트리의 형태가 되지 않고 이를 제외한 나머지 경우에서는 깊이 우선 탐색 법으로 탐색을 하면서 찾아서 리프 노드의 갯수를 세는 형식으로 풀었다. 코드 package tree; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; import java.util.StringTokenizer; public class BOJ_106..