algorithm8 [Algorithm] 정렬 (Sort) 1. 조건 (1) 정렬 조건이 필요하다. Comparable 인터페이스를 구현해야 한다. compareTo 메소드 오버라이딩을 통해 정렬 조건을 구현한다. (2) 시간 복잡도는 약 O(N logN) 이다. N개의 원소를 정렬하는 것은 O(NlogN) 만큼의 시간 복잡도를 갖는다. (3) In-place / Stable 여부를 알아야 한다. 정렬 알고리즘이 In-place(제자리)한가? 정렬하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가? 정렬 알고리즘이 Stable(안정)한가? 동등한 위상의 원소들의 순서 관계가 보전되는가? ex) 5 3 4 5 수열의 경우 3 4 5 5 => 동등한 위상의 원소들의 순서가 보전되었다. 2. 특성 코딩테스트에서 정렬은 문제에 직접 언.. 2022. 1. 22. [BOJ] 15663번: N과 M (9) (JAVA) 1. 문제 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N개의 자연수 중에서 M개를 고른 수열 중복X, 순서O => 순열(Permutation) 단, 조건) 중복되는 수열을 여러 번 출력하면 안 된다. 중복되는 답을 제거해주어야 한다. 2. 시간복잡도 입력 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8) 순열(Permutation) 알고리즘에서는 O(N! / (N-M)!) 시간복잡도를 가진다. 시간 : O(N! / (N-M)!) = 8! / 0! = 40,320 3. 구현 (1) String.co.. 2022. 1. 22. 이전 1 2 다음 반응형
