cornarong의 블로그

설명 가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다. 그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다. 예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다. N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하 시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다. 입력 첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다. N은 가장 윗줄에 있는 숫자의 개수를 의 미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다. 출력 첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다...

순열이란 서로다른 n개 원소중 r개를 선택하여 일렬로 나열하는 경우의 수를 말한다. 예를들어 A/B/C/D 4개 중 3개의 원소를 뽑았다면 선택된 원소는 ABC ACD ABD BCD 4가지가 된다. 이렇게 위치와 순서 상관없이 단순하게 뽑아낸 것을 조합이라고 하는데 여기서 원소들의 순서와 위치를 다르게 하여 일렬로 나열 하는 것을 순열이라고 한다. 즉 순열은 위치와 순서가 있는 조합이다. 위의 4가지 조합 중에 하나인 ABC를 위치와 순서에 따라 나열하는 경우 ABC ACB BAC BCA CAB CBA - 6가지의 경우의 수가 생긴다. 즉 ABC의 경우의 수 6 ACD 의 경우의 수 6 BCD 의 경우의 수 6 ABD의 경우의 수 6 이렇게 해서 A/B/C/D 4개 중 3개의 원소를 뽑는 순열의 경우의 ..

설명 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해 줄 수 있는 최소 개수를 구하라. 각 단위의 동전은 무한정 쓸 수 있다. 입력 첫 번째 줄에는 동전의 종류개수 N(1

설명 정보올림피아드대회에서 N개의 문제를 풀려고 합니다. 각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다. 제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다. (해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.) 입력 첫 번째 줄에 문제의 개수N(1

설명 트럭은 C킬로그램 넘게 태울수가 없다. C를 넘지 않으면서 바둑이들을 가장 무겁게 태우고 싶다. N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요. 입력 첫 번째 줄에 자연수 C(1

설명 N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고, 그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요. 둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어 합니다. 예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다. 입력 첫 번째 줄에 자연수 N(1 레벨은 1 2 3 4 5 6 / sum의 인덱스는 0 1 2 3 4 5 DFS(0, 0); System.out.println(result); } } 정리 : 처음 ..

설명 현수의 위치와 송아지의 위치가 수직선상의 좌표 점으로 주어지면 현수는 현재 위치에서 송아지의 위치까지 다음과 같은 방법으로 이동한다. 송아지는 움직이지 않고 제자리에 있다. 현수는 스카이 한 번의 점프로 앞으로 1, 뒤로 1, 앞으로 5를 이동할 수 있다. 최소 몇 번의 점프로 현수가 송아지의 위치까지 갈 수 있는지 구하는 프로그램을 작성하세요. 입력 첫 번째 줄에 현수의 위치 S와 송아지의 위치 E가 주어진다. 직선의 좌표 점은 1부터 10,000까지이다. 출력 점프의 최소횟수를 구한다. 답은 1이상이며 반드시 존재합니다. 풀이. public class Main { int[] arr = {1, -1, 5}; // 뻗어나갈 3가지 자식노드 Queue Q = new LinkedList(); publi..

재귀함수란 자기자신을 호출하는 함수, 반복문의 형태 아래의 DFS(int n)함수는 내부에서 자기자신을 호출하는 재귀함수이다. public void DFS(int n){ if(n==0) return; else { DFS(n-1); // 자기자신 호출 } } public static void main(String[] args) { Main T = new Main(); T.DFS(3); } retrun은 값을 반환해주는 역할이지만 void에서는 함수 종료의 의미도 갖고있다. 처음에는 if ~ else 조건으로 종료 조건을 사용하여 연습하는 것이 좋다고 한다. -> 무한루프 방지 재귀함수는 스택프레임을 사용한다. T.DFS(3)을 호출하면 호출하는 순서대로 아래의 그림처럼 스택메모리에 프레임형태로 담긴다. D..

설명 임의의 N개의 수를 오름차순으로 정렬한 다음 M이 주어지면 이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다. 입력 첫 줄에 한 줄에 자연수 N(3 m) { right = middle-1; middle = (left+right)/2; // middle보다 m이 크다. -> left를 우축으로 이동. }else{ left = middle+1; middle = (left+right)/2; } } System.out.println(result); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = s..

설명 N개의 평면상의 좌표(x, y)가 주어지면 모든 좌표를 오름차순으로 정렬하는 프로그램을 작성하세요. 정렬기준은 먼저 x값의 의해서 정렬하고, x값이 같을 경우 y값에 의해 정렬합니다. 입력 첫째 줄에 좌표의 개수인 N(3 그외 사용자 기준 정렬 오늘은 Comparable 인터페이스의 compareTo 메서드를 오버라이드하여 풀어본다. 풀이. import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; class Point implements Comparable{ public int x, y; Point(int x, int y){ this.x = x; this.y = y; } @Override public int..