잉여의 IT

"수의 범위가 작다면 카운팅 정렬을 사용하여 더욱 빠르게 정렬할 수 있습니다." 문제 힌트대로 카운팅 정렬을 이용해서 풀어보았다. *카운팅 정렬 : 각 항목이 몇 개씩 있는지 세어서 정렬하는 알고리즘으로 시간복잡도 O(n)으로 굉장히 빠르다. ㅎㅎ발그림으로 설명해보았다. 인자에 대응하는 배열에 인자 개수만큼 저장하고 세는 알고리즘이므로 같은 수가 중복 입력되어도 정렬이 된다. 만약 수의 범위가 정해져있고 정렬 값을 출력만 하면 된다면 다음과 같이 간단하게 코드를 사용할 수 있다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static ..

"시간 복잡도가 O(nlogn)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 병합 정렬, 힙 정렬 등이 있지만, 어려운 알고리즘이므로 지금은 언어에 내장된 정렬 함수를 쓰는 것을 추천드립니다." 문제 설명란에 힌트가 나와있다. 이번에는 O(n^2)이 아닌 O(nlogn)이어야한다. 정렬 평균 최상 최악 선택정렬 n^2 n^2 n^2 버블정렬 n^2 n^2 n^2 삽입정렬 n^2 n n^2 셸 정렬 n^1.5 n n^2 퀵 정렬 nlogn nlogn n^2 힙 정렬 nlogn nlogn nlogn 병합정렬 nlogn nlogn nlogn 병합 정렬, 힙 정렬은 나중에 공부하고 지금은 설명란의 추천대로 자바 안에 내장된 정렬 함수를 사용해보았다. *Collections.sort : 리스트 정렬로서 다중 ..

백준 정렬 문제 중 가장 기초적인 문제이다. 문제 설명란을 보면, "시간 복잡도가 O(n²)인 정렬 알고리즘으로 풀 수 있습니다. 예를 들면 삽입 정렬, 거품 정렬 등이 있습니다."라고 한다. 고민도 안하고 선택정렬을 이용했다. import java.util.Scanner; public class Main { public static void main(String[] args){ Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int arr[]=new int[N]; for(int i=0; i

숫자를 문자열로 변환하는 방법을 알면 쉽게 푸는 간단한 문제이다. 숫자를 문자열로 변환한 후 그 문자열에 "666"이 포함되어 있는지를 검사만하면 된다. 반복문은 쉽게 While(true)를 이용하였다. *자바에서 숫자를 문자열로 변환하는 방법 1) String s = Integer.toSring(i); 2) String s = String.valueOf(i); import java.util.Scanner; public class Main { int Search(int N) { int i=0; int count=0; while(true) { if(Integer.toString(i).contains("666")) { count++; } if(count==N) return i; i++; } } public ..

간단하지만 생각보다 헤매느라 시간을 잡아먹은 문제... 특히 자바는 익숙하지 않아서 scanner를 사용하지않고 받는 부분에서 약간 헷갈렸다. 요약하자면, 1. B로 시작하는 8*8체스판과 W로 시작하는 8*8체스판 두 개의 배열을 준비함. 2. 첫 시작 좌표를 (i , j)로 잡는다. 3. 시작좌표 (i , j)로부터 8*8만큼 체스판을 떼어내서 1)의 배열과 비교해서 바뀌는 부분의 개수를 센다. 4. 위 과정을 좌표를 한칸씩 이동하면서 전부 비교함(브루트 포스 알고리즘) 5. 가장 작은 값을 출력함. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Str..

브루트포스 알고리즘 문제이다. 각 사람끼리 키와 몸무게를 한번씩 다 돌아가면서 매칭하여 비교하고 자신보다 덩치가 큰 사람의 수를 세는 간단한 문제이다. import java.util.Scanner; public class Main{ void Grade(int N,int[][] arr) { int grade[]= new int[N]; int x,y,p,q; for(int i=0; i

브루트 포스 알고리즘 문제이다. 주어진 자연수 N이 최대 1000000까지이므로 이를 고려하여 각 자릿수를 구하는 함수를 작성했다. 분해합은 자신과 분해된 자릿수들의 합이므로 어차피 생성자는 주어진 분해합인 N보다 작을 수 밖에 없다. 따라서 1부터 N미만까지 차례대로 생성자가 될 수 있을지 대조했을 때, 처음으로 생성자가 되는 수가 가장 작은 생성자가 될 것이다. import java.util.Scanner; public class Main { int DisassembleSum(int N) { for(int i=0; i

브루트포스 알고리즘 문제이다. 복잡하게 생각하지 않고 최대한 단순하게 풀었다. 첫번째 i를 정하고, 그 다음부터는 j, 그 다음은 z 순으로 반복문을 이용하여 정렬하듯이 최대합을 갖는 카드 3개의 조합을 찾아나갔다. import java.util.Scanner; public class Main { int BlackJack(int M, int[] arr) { int max=0; for(int i=0; i