문제풀이/백준83 [JAVA] BOJ 백준 1967번 - 트리의 지름 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1967 2. 내가 푼 방법 이제 그래프 문제를 보면 시간초과가 날까봐.. 최대한 중복되는 경로를 안갖도록 고민하다가 빅오 O(n)으로 해결했다. 리프 노드에서 리프 노드로 이동하는 지름이 최대가 되도록 하는 방법을 찾기 위해 두 개의 값을 확인하면 된다. 자식 노드 중 가장 큰 값 자식 노드 중 가장 큰 값 2개 합친 값 자식 노드 중 가장 큰 값은 리프 노드 ~ 현재 노드까지 중에서 가장 큰 지름을 가지는 경로이고, 자식 노드 중 가장 큰 값 2개 합친 값은 현재 노드를 기준으로 꺾여 리프 노드 ~ 리프 노드까지 중에서 가장 큰 지름을 가지는 경로이다. 따라서 처음 입력값도 자식 노드.. 2023. 5. 23. [JAVA] BOJ 백준 2250번 - 트리의 높이와 너비 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/2250 2. 내가 푼 방법 메모리 초과가 관건이었다. 무조건 배열을 선언하더라도 사용할 만큼만 선언해 주었다. 이진트리를 저장하기 위해 선언한 arr 배열 루트 노드를 찾기 위해 선언해 준 isRoot 배열 depth 당 최소, 최대 열을 저장해 주기 위한 square 배열 주의할 점은 arr 배열과 squre 배열은 반드시 필요하다고 생각했기 때문에, 루트를 찾기 위한 isRoot 배열을 int 형으로 선언해 주면 바로 메모리 초과가 걸린다는 것이다. boolean 형으로 선언해 주는 것이 중요하다고 느꼈다. (근데 어쩌면 square 배열에서 N+1로 무조건 선언하는게 아닌 dept.. 2023. 5. 22. [JAVA] BOJ 백준 15681번 - 트리와 쿼리 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/15681 2. 내가 푼 방법 문제를 보고 쉽겠다고 생각해서 연결리스트로 각 노드들의 자식들을 저장해 놓는 방식을 채택했더니 메모리 초과가 떴다. 그래서 그냥 배열 하나로 끝내는 방법이 있을 것 같아서 고민하다가 DP 알고리즘를 이용해 자식 노드들의 하위 자식들을 먼저 채워 넣은 후에 루트 노드까지 카운팅되도록 코드를 짰다. public static int parentDFS (List[] list, int v, int[] parent) { parent[v] = 1; for (Integer i : list[v]) { if (parent[i] == 0) { parent[v] += parent.. 2023. 5. 20. [JAVA] BOJ 백준 1005번 - ACM Craft 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1005 2. 내가 푼 방법 연결리스트를 사용해서 단방향 그래프를 그려주었다. 이때 그래프 방향은 더 늦게 지어지는 건물에서 더 먼저 지어져야 하는 건물 방향으로 연결해 주었다. for (int k = 0; k < K; k++) { st = new StringTokenizer(br.readLine()); int v1 = Integer.parseInt(st.nextToken()); int v2 = Integer.parseInt(st.nextToken()); list[v2].add(v1); } bfs 함수를 통해 정답을 도출해 냈는데, while문을 통해 BFS 알고리즘을 구현하는 것은 기본.. 2023. 5. 19. [JAVA] BOJ 백준 1043번 - 거짓말 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/1043 2. 내가 푼 방법 핵심은 각 파티마다 참석한 사람들을 union-find를 이용해 같은 부모를 가지는 방법으로 연결시켜 준다. 그 후에 진실을 아는 사람들의 부모를 true로 변경해 줌으로써 문제를 풀 수 있다. union-find 알고리즘은 두 정점이 같은 그래프에 속하는지 확인할 수 있는 알고리즘이다. 아래의 find 함수와 union 함수를 사용해 구현할 수 있는데, find함수는 입력받은 x의 부모를 찾는 함수이고 union 함수는 입력받은 a와 b가 같은 부모를 가진다는 설정해 주는 함수이다. parent 배열의 초기값으로 자기 자신을 부모로 가지기 때문에. 두 정점이.. 2023. 5. 18. [JAVA] BOJ 백준 2617번 - 구슬 찾기 목차 문제 내가 푼 방법 자바 코드 결과 및 회고 1. 문제 https://www.acmicpc.net/problem/2617 2. 내가 푼 방법 플로이드 와샬을 사용해서 가중치를 가져야 하는 방법까지 딱 거기까지만 생각해 냈다. 그 후에 가중치를 어떻게 카운팅해서 정답을 구하는지가 관건이었던 것 같다. 먼저 단방향 그래프로 v1이 v2보다 더 무거우므로 v2에서 v1으로 갈 때 더 무거운 가중치를 가지도록 설정했다. 그 후, 플로이드 와샬 알고리즘을 이용해 가중치를 합해주었다. int[][] arr = new int[N+1][N+1]; for (int i = 0; i < M; i++) { st = new StringTokenizer(br.readLine()); int v1 = Integer.parseI.. 2023. 5. 17. 이전 1 ··· 9 10 11 12 13 14 다음
