[백준,BOJ 10989] 수 정렬하기 3( JAVA 구현)

-풀이 이 문제에 대한 설명으로 계수 정렬을 사용하라고 나와있다. 계수 정렬은 O(n + k)의 시간 복잡도를 가지며, 여기서 k는 정렬을 해야하는 데이터 중 가장 큰 값을 의미한다. 만약 k가 n보다 작은 수이면 O(n)이 되지만, k가 n보다 매우 큰 수이면 O(무한)이 될 수도 있다. 예를 들어 10개의 숫자를 정렬하는 데, 가장 큰 숫자가 100일 경우, O(n^2)이 된다. 100(k)은 10(n)의 제곱이므로. 1000이면 O(n^3)이 된다. 즉 정렬할 수들의 최댓값에 영향을 받는 알고리즘이라고 볼 수 있다. 즉, 정렬해야 하는 데이터의 범위가 적을수록 효율적인 성능을 보여주는 알고리즘이라 할 수 있다. 그리고 실제로 이 문제에서는 이전 수 정렬하기2 문제의 데이터 범위인 1,000,000과..

→2020.11.10

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2751] 수 정렬하기 2( JAVA 구현, 재풀이)

-내 생각 이전에 퀵 소트를 이용한 풀이를 작성한 적이 있는데, 문제가 수정된 건지 아니면 테스트 케이스가 바뀐 것인지 모르겠지만, 다시 제출해보니 오답처리를 받았다. 따라서 문제 설명에서 제시하는 O(nlogn) 시간 복잡도를 가지고 있는 정렬들을 이용해 다시 풀어보고자 했다. -해법 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main{ static int sorted[]; // i: 정렬된 왼쪽 리스트에 대한 인덱스 // j: 정렬된 오른쪽..

→2020.10.21

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2750] 수 정렬하기(JAVA 구현)

-내 생각 단순한 정렬 문제로, Arrays.sort() 메서드를 사용하면 손쉽게 풀 수 있지만 개인적으로 정렬 알고리즘에 대한 공부도 할 겸 문제의 설명에 나와있는 삽입 정렬, 거품 정렬을 이용해 풀어보고자 했다. -해법 import java.util.Scanner; public class Main{ static void insertion_sort(int[] arr) { // 삽입 정렬 메소드 int key; // 정렬할 키 값 for(int i =1;i=0;j--) { // key값 이전의 인덱스들과 크기 비교 if(arr[j]>key) { // key값 보다 크다면, arr[j+1] = arr[j]; // 뒤로 한 칸 이동. arr[j] = key; // key 값을 앞선 인덱스 자리에 삽입. } ..

→2020.10.20

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1018] 체스판 다시 칠하기(JAVA 구현, 재풀이)

-내 생각 저번에 풀 때도 어려워서 제대로 풀지 못했던 경험이 있는 문제다. 다시 풀기 위해 이전에 풀었던 풀이를 보았는데, 너무 복잡하다고 생각이 들어서 더 간단하게 푸는 방법이 없을까 생각하며 다른 블로거분들이 작성한 풀이를 참고해보았는데, 아래의 블로그에서 잘 설명하고 있다고 생각해서 따로 링크를 남겨둔다. 방문해서 참고하면 도움이 될 것 같다. [백준] 1018번 : 체스판 다시 칠하기 - JAVA [자바] www.acmicpc.net/problem/1018 1018번: 체스판 다시 칠하기 첫째 줄에 N과 M이 주어진다. N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어�� st-lab.tistory.com -해법 import..

→2020.10.20

코테/백준 온라인 저지(BOJ)

[백준,BOJ 11729] 하노이 탑 이동 순서(JAVA 구현, 재풀이)

-내 생각 별 찍기 - 10 문제와 마찬가지로 이전에 풀어봤던 문제로, 당시에는 이해가 불가능해 그냥 공식처럼 외우고자 했었는데, 이번에는 그나마 그 때보다는 좀 더 이해할 수 있었다고 생각되는 문제이다.. -해법 우선 하노이탑의 조건은 탑의 가장 상단에 있는 작은 원판부터 움직일 수 밖에 없게 되어있다. 즉 원판에 번호를 붙혀 생각해본다면, 1번 원판을 우선으로 고려해야 하기 때문에 n이 몇이던지 작은 부분으로 쪼개기 위해 재귀함수를 사용해야 한다. n이 3일 때, 3을 움직일 수 없으므로 -> 2를 고려, 2도 움직일 수 없으므로 -> 1을 고려, 1이 가장 작은 원판이기에 1부터 시작한다. import java.util.Scanner; public class Main{ static int k = 0..

→2020.10.19

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2447] 별 찍기 - 10(JAVA 구현, 재풀이)

-내 생각 이번에 한 번 풀어봤던 문제여서 조금만 고민하면 풀 수 있을 줄 알았는데, 풀이 방법의 감이 잡히질 않았다. n을 3으로 가정하고 작성하면 잘 출력이 되는데 n이 9일 때 안되거나, 반대로 n이 9일 때를 가정하고 작성하면 n이 3일 때가 잘 출력되지 않았다... ㅋㅋㅋ 그래도 처음 풀 때는 거의 다른 분들의 블로그에서 풀이를 보고 베끼다시피 했는데, 이번엔 참고 정도만 하면서 풀 수 있어서 좋았다. -해법 다른 분의 블로그에서 얻은 힌트는 하나의 분할에서 4번 째는 고려하지 않는다는 점이었다. 아래의 블로그를 참고하기를 바란다. 다른 문제들도 이해하기 쉽게 올려주셔서 보기 편하다. [백준] 2447번 : 별 찍기 - 10 - JAVA [자바] www.acmicpc.net/problem/244..

→2020.10.19

코테/백준 온라인 저지(BOJ)

[백준,BOJ 10870] 피보나치 수 5(JAVA 구현)

-해법 import java.util.Scanner; public class Main{ static int fibonacci(int n) { // 피보나치 메소드 if(n == 0) return 0; // 0이면 0을 반환 else if(n == 1) return 1; // 1이면 1을 반환 else { return fibonacci(n-1)+fibonacci(n-2); // 나머진 자신-1 + 자신-2 후 리턴 } } public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(fibonacci(n)); in.close() } } 팩토리얼과 마찬가지로 4..

→2020.10.09

코테/백준 온라인 저지(BOJ)

[백준,BOJ 10872] 팩토리얼(JAVA 구현)

-해법 import java.util.Scanner; public class Main{ static int factorial(int n) { if(n == 0) return 1; // n이 0이면 1이므로 리턴하여 무한 루프 방지 else { // 나머지의 경우 return n*factorial(n-1); // 자신 * 자신-1의 팩토리얼 값을 지속적으로 호출, 리턴해준다. } } public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); System.out.println(factorial(n)); // 출력! } } 재귀 알고리즘의 첫 문제이자 대표 문제라 할 수 있는 팩토리얼이다. 재..

→2020.10.09

코테/백준 온라인 저지(BOJ)

[백준,BOJ 1316] 그룹 단어 체커(JAVA 구현)

-해법 import java.util.Arrays; import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); int n = in.nextInt(); // 입력 될 문자열의 개수 int cnt = 0; // 그룹 단어의 수 String alph[] = new String[n]; // n개의 문자열 배열 생성 boolean alph_check[] = new boolean[26]; // 알파벳의 재등장 여부를 판단할 변수 for(int i=0;i 방문한적이 없으므로 그대로 반복문 종료 6. 결국 happy는 그룹 단어이다. 이와 같은 방식으로 하나의 ..

→2020.10.09

코테/백준 온라인 저지(BOJ)

[백준,BOJ 2941] 크로아티아 알파벳(JAVA 구현)

-해법 import java.util.Scanner; public class Main{ public static void main(String[] args){ Scanner in = new Scanner(System.in); String cro[] = {"c=", "c-", "dz=", "d-", "lj", "nj","s=", "z="}; String alph = in.next(); for(int i=0;i

→2020.10.09

티스토리툴바