Coding Story

그림과 같은 이진트리에서 루트 노드 1에서 말단노드까지의 길이 중 가장 짧은 길이를 구하는 프로그램을 작성하라. 각 경로의 길이는 루트노드에서 말단노드까지 가는데 이동하는 횟수를, 즉 간선(에지)의 개수의 길이이다. DFS class Node{ int data; Node lt, rt; public Node(int val){ data=val; lt=rt=null; } } public class Main{ Node root; public int DFS(int L, Node root){ if(root.lt==null && root.rt==null) return L; // 말단 노드라면 레벨 리턴 else return Math.min(DFS(L+1, root.lt), DFS(L+1, root.rt)); // 자..

import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; class Main{ int answer=0; int[] dis={1,-1,5}; int[] ch; // 한번 방문한 것은 큐에 안넣기 위해 체크할 배열 Queue Q = new LinkedList(); public int BFS(int s, int e){ ch=new int[10001]; ch[s]=1; Q.offer(s); int L=0; // 루트 노드는 레벨이 0 while(!Q.isEmpty()){ int len=Q.size(); // 탐색하고자하는 레벨에 있는 원소의 개수 for(int i=0; i

이진트리 순회(넓이우선탐색 : 레벨탐색) import java.util.LinkedList; import java.util.Queue; class Node{ int data; Node lt, rt; public Node(int val){ data=val; lt=rt=null; } } public class Main{ Node root; public void BFS(Node root){ Queue Q = new LinkedList(); Q.offer(root); int L=0; while(!Q.isEmpty()){ int len=Q.size(); System.out.print(L+" : "); for(int i=0; i

https://www.acmicpc.net/problem/2447 2447번: 별 찍기 - 10 재귀적인 패턴으로 별을 찍어 보자. N이 3의 거듭제곱(3, 9, 27, ...)이라고 할 때, 크기 N의 패턴은 N×N 정사각형 모양이다. 크기 3의 패턴은 가운데에 공백이 있고, 가운데를 제외한 모든 칸에 별이 www.acmicpc.net 그림판으로 그려서 패턴을 분석해보았다. 빨간색 박스는 n이 3일 경우, 주황색 박스는 n이 9일 경우(공백으로 채워진 3x3 정사각형을 3의 패턴으로 둘러싼 형태), 노란색 박스는 n이 27일 경우이다(공백으로 채워진 9x9 정사각형을 9의 패턴으로 둘러싼 형태) 이 때 빈칸의 규칙을 찾아보면, n이 3일 경우 가운데 비어있는 부분의 좌표는 (1,1) 부터 시작해 1번째..

https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ static int cnt=0; static StringBuilder sb = new StringBuilder(); public static void main(String[] args) ..

https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputSt..

https://www.acmicpc.net/problem/10870 10870번: 피보나치 수 5 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new Buffe..

https://www.acmicpc.net/problem/10872 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine..

https://www.acmicpc.net/problem/15666 15666번: N과 M (12) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int n, m; public static int[] arr; ..

https://www.acmicpc.net/problem/15665 15665번: N과 M (11) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { public static int n, m; public static int[] arr, ..