전공공부

설명 단절점과 단절선을 구하는 문제로 다음 블로그를 참고해서 문제를 풀었다. (https://loosie.tistory.com/522) 보니깐, 단절선이 생기는건 무조건 삭제가 되는게 맞고 단절점에 경우에는 아래로 나오는 간선의 갯수가 2개 이상이면 무조건 잘리는 구조다. 단절점이 리프노드이거나 루트 노드가 아니면 단절점으로 쓸 수 있다. 처음에는 실제로 나오는 요청대로 받아서 트리인지 여부를 검사하는 코드를 짜려고 하다가 너무 길어지는 듯해서 이상했는데 이렇게 쉬운 풀이가 있을줄 몰랐다. 생각의 전환이 필요한 듯 하다. 코드 package tree; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.Arra..

설명 방문 여부를 체크하는 일반적인 그래프의 탐색을 구현하였다. 하지만, visited 처리 중 처음 스타트 지점의 처리를 잘 못해서 result가 이미 셋팅된 경우에는 다시 셋팅을 반복하지 않도록 방문 여부를 체크하지 못한 스타트 지점의 처리를 해주었는데 조금 아쉬운 코드이다. 코드 package tree; import java.util.*; public class BOJ_11725 { static int result[]; static boolean visited[]; static List[] list; public static void main(String[] args) throws Exception{ Scanner sc = new Scanner(System.in); int N = sc.nextInt..

1. 트리 트리(Tree)는 계층적인 구조를 표현하는 자료 구조로, 노드와 간선으로 이루어져 있습니다. 트리는 다양한 분야에서 활용되며, 중요성은 데이터 구조와 알고리즘 이론을 이해하는 데 필수적입니다. 2. 트리의 정의 1. 비어 있거나(노드의 개수가 0개), 노드의 개수가 1개 이상이며 방향 간선이 존재함. 2. 사이클이 없음 3. 모두 연결된 연결 그래프임 풀어쓰면 노드 끼리 모두 연결된 그래프이면서 사이클이 존재하지 않고 노드가 V개 일때, 간선이 V - 1인 것이 트리이다. 3. 트리의 구성 요소 노드(Node) 트리의 기본 단위로, 데이터를 저장하는 요소입니다. 각 노드는 값과 부가적인 정보를 가질 수 있습니다. 간선(Edge) 노드들을 연결하는 선으로, 부모 노드와 자식 노드를 연결합니다. ..

설명 트리에 대해서 별도의 이해가 없었고 이때, 문제의 구현을 위한 설명만을 보고 풀었다. 그리고, 설명 게시판을 많이 참고하였는데 이 문제는 들어오는 간선이 1개 이상이고 간선이 아예 없는 루트 노드 하나가 존재하는 것을 찾아야 한다. 그런데 어이가 없던 것이 이렇게 구현을 하고 아무리 돌려도 틀렸습니다가 떠서 질문 게시판을 다시 봤더니 0 0인 케이스도 가능하다고 한다. 즉, 아무 노드가 없을때도 트리가 된다고 한다. 아무리 찾아봐도 잘 모르겠어서 chatGPT를 돌려서 트리에도 공집합 같은 트리가 존재하는지 봤더니 아래와 같은 답변을 얻었다. 더보기 공 트리는 트리가 아무런 노드도 가지고 있지 않은 경우를 가리킵니다. 즉, 노드가 존재하지 않고 아무런 관계도 형성되지 않은 상태를 말합니다. 이는 일..

설명 아래 그림처럼 접근했다. 16 6 들어오면 8 / 3 까지 기약 분수 형태로 GCD로 나눌 수 있고 이때 6개들은 그냥 배포하고 나머지 2/3에 대해서 정리하는 형태로 접근했다. 아래 그림을 보면 밑의 코드가 이해가 될 것이다. N = 2 , M = 5 2/5씩 하는데 이를 빼서 보면 4등분으로 나온다. 2/5 2/5 1/5 1/5 2/5 2/5 그러고 보니, 분자 만큼 나누어야 (2개의 빵을 5등분을 하려면 -> 4번 짜른다. 이렇게 생각하면된다.) 하는데 칼질의 갯수니 -1을 하면된다. 추가로, 마지막에 GCD로 나눈 기약분수 형태로 풀었으니 다시 복구 시켜야한다. 코드 package Math; import java.io.BufferedReader; import java.io.InputStrea..

설명 가성비가 안 좋은 것을 모두 select하고 이때, 가성비가 좋은 것을 후 순위로 선택하면서 Math.min 값을 줄여나가는 풀이로 풀어야 한다. 그리디 형태로 어떻게 풀까 싶었는데 도저히 떠오르지 않아서 풀이를 보고 해결했다. 조금 생각하기가 버거웠던 문제 코드 package Math; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_3343 { public static void main(String[] args) throws IOException { BufferedReader br = ne..

설명 최대공약수 * 최소공배수를 진행하면 내가 뽑을 수도 같은 숫자를 가질 수 있다는 것은 파악을 하였다. 하지만, 이를 서로소로 만들어서 풀 생각은 하지 못하였는데 그냥 1~N까지 모두 탐색하면 시간초과가 날것이 뻔하니 최대공약수로 나눠서 탐색하면 x,y값 모두 서로소가 되고 이때 최대 공약수를 곱해서 GCD 여부가 같은지 체크하면 된다. 6 * 180 = 30 * 36 -> x,y 모두 서로소로 만들기 위해서 모든 변수에 GCD로 나눈다. => 1 * 30 = 5 * 6 이런 형태가 나올 것이고 이를 아래와 같은 코드로 구현하였다. 코드 package Math; import java.io.BufferedReader; import java.io.InputStreamReader; import java.u..

설명 에리스토테네스의 체를 활용하고 이때 팰린드롬을 확인 하기 위해서 각 소수에 대해서 거꾸로 돌려서 같은지 체크한다. 코드 package Math; import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.StringTokenizer; public class BOJ_1990 { static boolean [] isPrime; public static void main(String[] args) throws Exception{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer tk = new StringTo..