본문 바로가기
  • 개발 삽질 블로그

프로그래밍46

백준 10974: 모든 순열 https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 이 문제는 모든 순열을 출력하는 문제다. 원소가 1부터 증가하는 정수이기 때문에 배열 말고 for문을 이용하였다. import java.util.*; public class Main { public static void pick(int a[], int m, int toPick) { if(toPick==0) { for(int i=0; i 2022. 10. 13.
백준 10973: 이전 순열(JAVA) https://www.acmicpc.net/problem/10973 10973번: 이전 순열 첫째 줄에 입력으로 주어진 순열의 이전에 오는 순열을 출력한다. 만약, 사전순으로 가장 처음에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 이전에 풀었던 다음 순열 문제를 조금만 변형하면 되는 문제다. 전체적인 알고리즘 논리는 같다. 부등호 방향만 반대로 해주면 된다. import java.util.*; public class Main { public static void swap(int [] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static boolean nextPermutation(int[] a) .. 2022. 10. 12.
백준 10972: 다음 순열(JAVA) https://www.acmicpc.net/problem/10972 10972번: 다음 순열 첫째 줄에 입력으로 주어진 순열의 다음에 오는 순열을 출력한다. 만약, 사전순으로 마지막에 오는 순열인 경우에는 -1을 출력한다. www.acmicpc.net 어떤 순열이 주어지면 사전순으로 다음에 오는 순열을 구하는 문제이다. 알고리즘 분류는 수학과 조합론이다. 1 2 3 4 1 2 4 3 1 3 2 4 ... 1) 배열의 끝부터 a[i] > a[i-1] 인 구간을 찾는다. 2) a[i-1]과 a[i...last]까지 중 가장 작은 값의 자리를 바꾼다. 이때 a[i...last]는 내림차순으로 정렬되어있으므로 (-> 1전 과정을 찾기 전까지는 a[i] 0 && a[i-1] >= a[i]) { i--; } // .. 2022. 10. 12.
순열과 조합 1)순열 import java.util.*; public class Main { public static void solution(char []item, char []bucket, int k) { if( k == 0 ) { //다 뽑았으면 출력 for(int i=0; i 2022. 10. 12.
멱집합(PowerSet) a가 들어가거나 안 들어가거나 b가 들어가거나 안 들어가거나 ... f가 들어가거나 안 들어가는 모든 경우의 수는 2^n이다.(n은 원소의 개수) pick이라는 boolean 배열을 두고 해당 인덱스에 원소를 뽑았을 경우 true, 안 뽑았을 경우를 false라고 두고 재귀적으로 구현했다. import java.util.*; public class Main { private static char data[] = {'a', 'b', 'c', 'd', 'e', 'f'}; private static boolean [] pick = new boolean[6]; private static int n = data.length; public static void main(String[] args){ powerSet(.. 2022. 10. 12.
Counting Cells in Blob(Blob 셀 수 세기) 재귀를 이용하여 구현하였다. public class Main { //이차원 배열로 이미지 표현 static int arr[][] ={ {1,0,0,0,0,0,0,1}, {0,1,1,0,0,1,0,0}, {1,1,0,0,1,0,1,0}, {0,0,0,0,0,1,0,0}, {0,1,0,1,0,1,0,0}, {0,1,0,1,0,1,0,0}, {1,0,0,0,1,0,0,1}, {0,1,1,0,0,1,1,1}}; //상수로 컬러 표현 public static final int BackgroundColor = 0; public static final int ImageColor = 1; public static final int AlreadyCounted = 2; public static void main(Strin.. 2022. 10. 12.

티스토리툴바