공부방

서쪽의 사이트 n 개와 동쪽의 사이트 m개를 이을 다리를 놓을 때, 이 다리를 놓는 경우의 수를 구하는 문제이다. 구하는 방법은 간단하다. m개의 사이트에서 n개를 고르는 경우의 수는 m Combination n (mCn) 으로 해결할 수 있다. 이를 구하는 공식은 백준알고리즘 #1010 다리 놓기 문제 서쪽의 사이트 n 개와 동쪽의 사이트 m개를 이을 다리를 놓을 때, 이 다리를 놓는 경우의 수를 구하는 문제이다. 구하는 방법은 간단하다. m개의 사이트에서 n개를 고르는 경우의 수는 m Combination n (mCn) 으로 해결할 수 있다. 이를 구하는 공식은 다음과 같다 다만 위 식을 조금 간단히 하면 코드도 간단히 해결할 수 있다. n이 r보다 크므로 n!은 n x (n-1) x ... x r..

입력받은 단어에서 가장 많이 사용된 알파벳을 구하는 문제이다. 먼저 대소문자를 구분하지 않으므로 입력받은 문자열을 toUpperCase() 함수를 이용해 대문자로 바꿔준다. 이후 각 알파벳이 얼마나 쓰였는지 확인할 배열 count[] 를 생성해주고 크기를 26(알파벳 수)로 잡는다. 그리고 for문을 이용해 각 charAt() 함수로 입력받은 문자열을 하나 하나 잘라서 count[a.charAt(i)-65] 를 증가시킨다. 여기서 a.charAt(i)-65 는 입력받은 알파벳을 아스키코드로 변환하여 65를 빼면 A의 경우 0, B의 경우 1 .. 이 나온다. 즉 ABCD를 입력받았다면 a.charAt(0) - 65 는 0 a.charAt(1) - 65 는 1 a.charAt(2) - 65 는 2 a.ch..

속이 빈 트리모양의 별을 출력하는 문제이다. 2021.01.12 - [C/백준알고리즘] - [C] 백준알고리즘 #2442 #2443 별 찍기 - 5 , 6 (트리, 역트리) [C] 백준알고리즘 #2442 #2443 별 찍기 - 5 , 6 (트리, 역트리) 마치 트리모양의 별을 찍는 문제이다. 규칙을 찾아보면 빈칸은 N-1개부터 차례대로 줄어들고 *의 갯수는 1,3,5,7 ... 2n-1 개 만큼 늘어난다. 친절하게도 문제에서 N번째 줄에는 2*N-1개 라고 정의해주 sehyeok.tistory.com for문 구성은 C나 Java나 동일하므로 앞서 작성했던 트리 모양의 별 찍기를 참고해보자. 위와같은 트리 구조에서 가운데가 비어있는 공간을 만들어야 하므로 별을 하나만 찍어야 한다. 앞선 코드를 조금 수정..

반복할 횟수와 문자열을 입력 받은 후 반복할 횟수만큼 각 문자를 반복하여 출력하는 문제이다. 반복할 횟수를 r이라 입력받고 문자열을 s에 입력받는다고 하자. int r = sc.nextInt(); String s = sc.next(); ABC 라는 문자열과 3의 반복횟수를 입력받는다고 하면 먼저 A가 3회 출력되어야 한다. 이는 charAt(0) 의 문자가 3번 출력되는 것이다. 그 다음에는 charAt(1) 의 문자(B) 가 3번, charAt(2) 의 문자(C)가 3번 출력 될 것이다. 이를 위해 이중 for문을 사용해서 작성해보자 for (int j = 0; j < s.length(); j++) { for (int k = 0; k < r; k++) { System.out.print(s.charAt(..

입력한 단어의 각 알파벳들이 제일 먼저 나오는 위치를 찾는 문제이다. 먼저 비교를 위해 각 알파벳을 저장할 배열 a와 각 알파벳의 위치를 나타내 줄 b 배열을 만들어보자. char[] a = new char[26]; int[] b = new int[26]; for (int i = 0; i < 26; i++) { a[i] = (char) (97 + i); b[i] = -1; } 알파벳은 총 26자이므로 26만큼의 크기를 가진 배열 a, b 를 생성한다 그 후 배열 a에는 각 알파벳을 넣는다. 이때 소문자 a 는 아스키코드로 97에 해당하므로 97+i 를 char형으로 형변환하여 a[i] 에 담아주면 되겠다. 배열 b는 문제에서 등장하지 않는 알파벳은 -1로 표시하므로 -1로 초기화하였다. 이제 입력받은 문..

666을 포함하는 수 중 가장 작은 수 부터 순서를 매겨 N번째의 수를 구하는 문제이다. 이를 해결하기 위해서는 i라는 변수를 두고 이 수를 1부터 차례로 증가시키며 이 수가 666을 포함하는지 안하는지를 확인하면 된다. 만약 666을 포함한다면 count를 증가시켜 count 와 n이 같아질 때의 i값이 n번째 영화 제목이 될 것이다. 이를 위해 while문을 이용한다. while(count != n) { if (check(i)) { count++; if (count == n) { System.out.println(i); } } i++; } 여기서 check() 메소드는 이 수가 666을 포함하는지 아닌지를 판별해 주는 함수이다. 이 함수의 반환값이 true일 때 count를 증가시키고, count가 ..

입력받은 수들을 오름차순으로 정렬하여 출력하는 문제이다. 앞서 여러 문제들을 풀면서 사용했던 선택 정렬을 이용하면 되겠다. 2021.03.15 - [Java/백준알고리즘] - [Java] 백준알고리즘 #2798 블랙잭 [Java] 백준알고리즘 #2798 블랙잭 주어진 수들을 조합하여 3장의 카드를 골라 합이 m에 가장 근접하게 하는 문제이다. 이 문제는 선택정렬을 이용하여 풀면 간단하게 해결할 수 있다. 흔히 최소값, 최대값 또는 오름차순정렬 등을 sehyeok.tistory.com for (int i = 0; i a[j]) { int tmp = a[i]; a[i] = a[j]; a[j] = tmp; }..

임의의 n x m 크기의 보드를 8 x 8 의 보드로 잘라내어 체스판을 만들기 위해 색상을 다시 칠하는 문제이다. 조금 단순하지만 무식한 방식으로 풀어보았다. 먼저 비교할 두 체스판 (흰색이 먼저 오는 체스판 과 검은색이 먼저 오는 체스판) 을 만들어둔다. char[][] b = new char[8][8]; char[][] w = new char[8][8]; for (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { if ((i + j) % 2 == 0) { b[i][j] = 'B'; w[i][j] = 'W'; } else { b[i][j] = 'W'; w[i][j] = 'B'; } } } 그리고 n x m 크기의 보드를 이차원 배열에 입력받는다. int ..

각 사람들의 키와 몸무게를 입력받고 등수를 매기는 문제이다. 먼저 각 사람들의 키와 몸무게를 저장할 2차원 배열 a를 만들어 몸무게와 키를 입력받는다. Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[][] a = new int[n][2]; int[] b = new int[n]; for (int i = 0; i < n; i++) { a[i][0] = sc.nextInt(); a[i][1] = sc.nextInt(); b[i] = 1; } a[i][0] 은 몸무게, a[i][1]은 키를 입력받도록 했다. b 배열은 등수를 저장할 배열이므로 1로 초기화 시켜주었다. 위 조건에는 키와 몸무게가 더 많이 나간다면 덩치가 크다고 했다. 이 덩치를 이..

어떤 자연수 n이 있을 때 n과 n의 각 자리수를 더한 것을 분해합이라고 하고, 이 분해합을 A라고 할 때 n은 A의 생성자가 된다고 한다. 임의의 자연수 n, 즉 분해합 n이 주어졌을 때 생성자 m을 구하는 문제이다. 각 자리수를 더하는 방법만 알고 있다면 아주 쉽게 해결 할 수 있는 문제이다. 임의의 정수 i가 있을 때 각 자리수를 더하는 방법은 다음과 같다. while(i > 0){ sum += i % 10; i = i / 10; } 합을 저장할 sum변수에 i를 10으로 나눈 나머지를 넣은 후 다시 i에 i를 10으로 나눈 몫을 저장한다. 만약 789라면 1. 798를 10으로 나눈 나머지인 9가 sum에 저장됨 2. i에 789를 10으로 나눈 몫인 78이 저장됨 3. 78을 10으로 나눈 나머..