notcherry

선택 정렬이란? 대상 데이터에서 최대나 최솟값을 갖는 데이터를 선택하는 정렬이다. 선택 정렬은 구현 방법이 복잡하고, 시간 복잡도가 O(㎡)으로 효율적이지 않아 많이 사용하지는 않는다. 구현 방법은 최솟값 또는 최댓값을 찾고 남은 정렬에서 가장 앞에 있는 데이터와 swap하는 것을 반복하는 것이다. 예를 들어 최솟값을 기준으로 정렬할 때, 더보기 1 3 2 5 4 -> 1과 5 비교 -> 1이 더 작음 -> 그대로 둠 : 남은 정렬 3 2 5 4 1 3 2 5 4 -> 3과 2비교 -> 2가 더 작음 -> swap : 남은 정렬 3 5 4 1 2 3 5 4 -> 3과 5비교 -> 3이 더 작음 -> 그대로 둠 : 남은 정렬 5 4 1 2 3 5 4 -> 5와 4 비교 -> 4가 더 작음 -> swap 1..

버블정렬이란? 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다. 간단하게 구현할 수 있지만 시간 복잡도는 O(㎡)으로 다른 정렬 알로그리즘보다 속도가 느린 편이다. 주로 loop를 돌면서 인접한 데이터 간의 swap 연산으로 정렬한다. 만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료해도 된다. 백준 2750번 문제를 sort를 사용할 수 있지만 n값이 작으므로 직접 정렬을 시도해서 문제를 풀어보겠다. public class 수정렬하기 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(n..

슬라이딩 윈도우는 O(n)의 시간 복잡도를 가져 쉽게 문제를 풀 수 있다. s배열(기본 배열)과 비밀 번호 체크 배열을 설정한다. 윈도우에 포함된 문자로 현재 상태 배열을 만들고 현재 상태 배열과 비밀 번호 체크 배열을 비교한다. 비교 후 답이 되지 않는다면 한 칸 이동해 다시 비교한다. 이때, 빠진 첫 번째 인덱스 값과 들어온 새 인덱스 값만 비교하여 정보를 업데이트 해준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class 슬라이딩_비밀번호 { static int myArr[]; static int ch..

배열의 기본 지식 뿐만 아니라, 수학적인 접근 방법도 필요함. 그 감각을 기르기 위해서 기초 문제부터 깊게 보는 중! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class 주몽의명령 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(..