(11752) 트리의 부모 찾기

문제 문제 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다. 출력 첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다. 문제 풀이 주어진 트리에서 각노드의 부모를 구하는 문제이다. BFS(Binary Find Search) 알고리즘을 활용하여 해당 문제를 해결 할 수 있었다. 노드의 개수 n과 트리의 연결 정보를 입력으로 받아 ArrayList 배열을 이용하여 인접 리스트를 구성한다. static ArrayList[] tree; 인접 리스트로 구성된 값들..

• format_list_bulleted BackJoon/Algorithm
• · 2023. 3. 27.
• textsms

이진 탐색 트리(Binary Search Tree)

이진 탐색 트리(Binary Search Tree) 이진트리는 아래의 규칙을 가지고 있는 자료구조이다. 왼쪽 자식 노드의 키는 부모 노드의 키보다 작다. 오른쪽 자식 노드의 키는 부모 노드의 키보다 크다. 각각의 서브 트리도 이진 탐색 트리를 유지한다. 중복된 키를 허용하지 않는다. 특징 이진 탐색 트리 규칙에 의해 데이터가 정렬된다. 이진 트리에 비해 탐색이 빠르다 (균형 유지) 균형상태 복잡도 O(logN) 불균형상태 복잡도 O(N) 이진 탐색 트리 - 삽입 Root 부터 비교를 시작 한다(중복 키 발견 시 노드 추가하지 않고 종료 된다.) 삽입할 키가 현재 노드의 키보다 작으면 왼쪽으로 이동한다. 삽입할 키다 현재 노드의 키보다 크면 오른쪽으로 이동한다. Leaf 노드에 도달 후 데이터를 입력한다...

• format_list_bulleted Zero-Base/자료구조-알고리즘
• · 2023. 3. 27.
• textsms

StringTokenizer, StringBuilder, StringBuffer

StringTokenizer StringTokenizer 클래스는 문자열을 구분자(delimiter)를 기준으로 분리하는 데 사용되는 Jaca 내장 클래스이다. 구분자는 문자열에서 분리하고자 하는 구분 기호를 의미한다. 토큰(Token) 자바에서 토큰(Token)은 코드를 해석하고 처리하는 과정에서 최소 단위로 쪼개어진 문자열을 의미한다. 토큰의 용도를 아래와 같다. 1. 자바 프로그램에서 소스 코드를 구문 분석하는 데 사용이 된다. 예를 들어, 자바 컴파일러는 소스 코드를 토큰으로 분리하여 이를 분석하고 컴파일한다. 2. 자바에서 제공하는 Scanner 클래스와 같은 입력 스트림 클래스에서 입력을 읽어들이는 데 사용된다. Scanner 클래스는 입력 스트림에서 토큰 단위로 데이터를 읽어들일 수 있다. ..

• format_list_bulleted Language/Java
• · 2023. 3. 27.
• textsms

숫자의 표현

문제 문제 풀이 반복문을 1 ~ n 까지 수행하고 2중 반복문으로 하나씩 더해가면서 n 값과 같으면 answer++ 더 커지게 되면 반복문을 멈추는 식의 방법으로 접근. 나의 답안 public static int solution(int n) { int answer = 0; for (int i = 1; i n) { break; } num++; } } return answer; }

• format_list_bulleted Programmers 문제풀이/Lv.2
• · 2023. 3. 26.
• textsms

이진 변환 반복하기

문제 문제 풀이 이진법 문자열에서 0의 개수를 세어주는 반복문과 0을 제거하는 함수, 그리고 남은 문자열 길이에 맞춰서 이진수로 변환해주는 함수를 사용을 하면 쉽게 풀 수 있는 문제이다. 나의 답안 public static int[] solution(String s) { int countZero = 0; int count = 0; while (!"1".equals(s)) { count++; for (char c : s.toCharArray()) { if (c == '0') countZero++; } s = s.replace("0", ""); s = Integer.toBinaryString(s.length()); } return new int[]{count, countZero}; }

• format_list_bulleted Programmers 문제풀이/Lv.2
• · 2023. 3. 26.
• textsms

올바른 괄호

문제 문제 풀이 스택 자료구조를 이용하여 괄호의 상태에 따라 push와 pop을 해주면 되는 문제이다. 나의 답안 static boolean solution(String s) { boolean answer = true; Stack stack = new Stack(); if (s.charAt(0) == ')') return false; for (char c : s.toCharArray()) { if (c == '(') { stack.push(c); } else { if (stack.isEmpty()){ return false; } else { stack.pop(); } } } if (!stack.isEmpty()) return false; return answer; }

• format_list_bulleted Programmers 문제풀이/Lv.2
• · 2023. 3. 26.
• textsms