윤만석

문제 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 6번만 키를 비교하였고, 그 결과가 다음과 같다고 하자. 1번 학생의 키 < 5번 학생의 키 3번 학생의 키 < 4번 학생의 키 5번 학생의 키 < 4번 학생의 키 4번 학생의 키 < 2번 학생의 키 4번 학생의 키 < 6번 학생의 키 5번 학생의 키 < 2번 학생의 키 이 비교 결과로부터 모든 학생 중에서 키가 가장 작은 학생부터 자신이 몇 번째인지 알 수 있는 학생들도 있고 그렇지 못한 학생들도 있다는 사실을 아래처럼 그림을 그려 쉽게 확인할 수 있다. a번 학생의 키가 b번 학생의 키보다 작다면, a에..

이진 트리는 매우 중요한 기본 자료 구조이다. 아래 그림은 루트 노드가 유일한 이진 트리이다. 모든 노드는 최대 2개의 자식 노드를 가질 수 있으며, 왼쪽 자식이 순서가 먼저이다. 노드 n개로 이루어진 이진 트리를 BT라고 하자. BT의 노드는 1부터 n까지 유일한 번호가 매겨져 있다. 아래 그림에 나와있는 BT의 루트는 3번 노드이다. 1번 노드는 오른쪽 자식만 가지고 있고, 4와 7은 왼쪽 자식만 가지고 있다. 3과 6은 왼쪽과 오른쪽 자식을 모두 가지고 있다. 나머지 노드는 모두 자식이 없으며, 이러한 노드는 리프 노드라고 부른다. BT의 모든 노드를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 총 세 가지가 있다. 이 세 방법은 아래에..

문제 조기 졸업을 꿈꾸는 종욱이는 요즘 핫한 딥러닝을 공부하던 중, 이미지 처리에 흔히 쓰이는 합성곱 신경망(Convolutional Neural Network, CNN)의 풀링 연산에 영감을 받아 자신만의 풀링을 만들고 이를 222-풀링이라 부르기로 했다. 다음은 8×8 행렬이 주어졌다고 가정했을 때 222-풀링을 1회 적용하는 과정을 설명한 것이다 행렬을 2×2 정사각형으로 나눈다. 각 정사각형에서 2번째로 큰 수만 남긴다. 여기서 2번째로 큰 수란, 정사각형의 네 원소를 크기순으로 a4 ≤ a3 ≤ a2 ≤ a1 라 했을 때, 원소 a2를 뜻한다. 2번 과정에 의해 행렬의 크기가 줄어들게 된다. 종욱이는 N×N 행렬에 222-풀링을 반복해서 적용하여 크기를 1×1로 만들었을 때 어떤 값이 남아있을지..

문제 n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다. 이와 같은 이진 트리의 인오더와 포스트오더가 주어졌을 때, 프리오더를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. 출력 첫째 줄에 프리오더를 출력한다. 풀이전략은 아래와 같습니다. 중위 순회 L M R 1 2 3 trav(M)=trav(L) + M + trav(R) >>루트가 2로 확정되면 2 기준으로 좌 = trav(L) 2 기준으로 우 = trav(R) 후위 순회 L R M 1 3 2 후위순회의 마지막은 무조건 루트 >>루트가 2로 확정 trav(M)=t..

문제 Moo는 술자리에서 즐겁게 할 수 있는 게임이다. 이 게임은 Moo수열을 각 사람이 하나씩 순서대로 외치면 되는 게임이다. Moo 수열은 길이가 무한대이며, 다음과 같이 생겼다. m o o m o o o m o o m o o o o m o o m o o o m o o m o o o o o Moo 수열은 다음과 같은 방법으로 재귀적으로 만들 수 있다. 먼저, S(0)을 길이가 3인 수열 "m o o"이라고 하자. 1보다 크거나 같은 모든 k에 대해서, S(k)는 S(k-1)과 o가 k+2개인 수열 "m o ... o" 와 S(k-1)을 합쳐서 만들 수 있다. S(0) = "m o o" S(1) = "m o o m o o o m o o" S(2) = "m o o m o o o m o o m o o o ..

문제 흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다. 주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다 위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 ..

문제 아래 과 같이 여러개의 정사각형칸들로 이루어진 정사각형 모양의 종이가 주어져 있고, 각 정사각형들은 하얀색으로 칠해져 있거나 파란색으로 칠해져 있다. 주어진 종이를 일정한 규칙에 따라 잘라서 다양한 크기를 가진 정사각형 모양의 하얀색 또는 파란색 색종이를 만들려고 한다. 전체 종이의 크기가 N×N(N=2k, k는 1 이상 7 이하의 자연수) 이라면 종이를 자르는 규칙은 다음과 같다. 전체 종이가 모두 같은 색으로 칠해져 있지 않으면 가로와 세로로 중간 부분을 잘라서 의 I, II, III, IV와 같이 똑같은 크기의 네 개의 N/2 × N/2색종이로 나눈다. 나누어진 종이 I, II, III, IV 각각에 대해서도 앞에서와 마찬가지로 모두 같은 색으로 칠해져 있지 않으면 같은 방법으로 똑같은 크기의..

class temp{ private String str; temp(String s){ str=s; } } public class Main { public static void main(String args[]) { temp t1=new temp("zz"); System.out.println(t1.toString()); } } //Devide_And_Conquer.temp@7c30a502 인스턴스의 내용을 print하고싶을때가 있습니다. 그럴때 이렇게 쓰면 내용이 아니라 클래스네임 @ 객체주소 해쉬코드 가 반환됩니다. 따라서 내용을 출력하고싶을때는 이때 temp 클래스의 toString을 오버라이딩하면됩니다. 1. toString 은 접근지시자가 protected이므로 , public 으로 오버라이딩해야합..

제너릭은 일반화 라는 의미를 가집니다. 그리고 그 일반화는 자료형에대한 일반화입니다. 만약 Box라는 클래스에 사과와 바나나를 넣어야한다면 1. 사과Box 와 바나나Box 클래스를 따로 작성할수 있습니다. 이렇게되면 코드가 많이 길어질 수 있습니다. 또한 사과Box 나 바나나Box나 제공하는 메소드가 같으므로 많이 겹치게 됩니다. 2. Object형을 인스턴스로 가지는 Box를 생성. 사과와 오렌지뿐아니라 뭐든지 담을 수 있는 박스가 만들어졌습니다. 하지만 이런경우 상자에 사과나 바나나를 꺼낼때 계속해서 형변환을 해주어야합니다. 3.제너릭 사용 제너릭을 사용하면 자료형에 의존적이지 않은 클래스를 정의할 수 있습니다. 이를 제네릭 클래스라고 부릅니다. class Box{ //타입매개변수 T를 사용하겠습니다..

1. 배열의 비교 1-1. 기본자료형에대한 배열의 비교 package Devide_And_Conquer; import java.util.Arrays; public class Main { public static void main(String args[]) { int[]a= {1,2,3,4}; int[]b= {1,2,3,4}; System.out.println(a==b); System.out.println(a.equals(b)); //위 둘은 참조값을 비교 //false //false int[]c=Arrays.copyOf(a,a.length); //Arrays 의 copyOf메소드는 새로운 배열을 생성하는 메소드이다 마찬가지로 System.out.println(a==c); System.out.println..