반응형
1. 문제 번호 2750
2. 문제 풀이
한줄 평가
- 선택정렬 (배열중 최소값을 찾아 맨 앞자리와 스왑)
- 버블정렬 (1회의 반복이 0...부터 끝까지 옆의 수와 큰 수를 반복적으로 뒤로 보낸다.)
- 삽입정렬 (1회의 반복이 1...부터 앞의 값과 비교하여 작으면 반복적으로 앞으로 보낸다.)
문제를 먼저 정확히 파악
나의 문제풀이 방식 및 순서
* 나의 다양한 학습이 우선이기 때문에 다양한 방법을 생각 *
- 이중 for문을 활용한다. 두 번째 for문은 최소값을 찾아서 첫 번째 for문에서 스왑처리
for문의 형태 + 선택 정렬하는 로직 주의
for (int i = 0; i < numAry.length; i++) {
minValue = Integer.MAX_VALUE;
temp = Integer.MAX_VALUE;
index = Integer.MAX_VALUE;
for (int j = i; j < numAry.length; j++) {
if(minValue > numAry[j]){
minValue = numAry[j];
index = j;
}
}
temp = numAry[i];
numAry[i] = numAry[index];
numAry[index] = temp;
}
- 이중 for문을 활용한다. 첫 번째 for문은 반복횟수를 나타내고 두 번째 for문으로 버블정렬 처리
인덱스 주의 + for문의 형태 + 버블 정렬하는 로직 주의
for(int i = 0; i < numAry.length - 1 ; i++){
for(int j = 0; j < numAry.length -1 - i; j++){
if(numAry[j] > numAry[j+1]){
int temp = numAry[j];
numAry[j] = numAry[j+1];
numAry[j+1] = temp;
}
}
}
- 이중 for문을 활용한다. 첫 번째 for문은 반복횟수를 나타내고 두 번째 for문으로 버블정렬 처리
인덱스 주의 + for문의 형태 + 버블 정렬하는 로직 주의
for(int i = 1; i < numAry.length; i++){
int j = i;
int temp = numAry[j];
while(j > 0 && numAry[j-1]>numAry[j]){
temp = numAry[j-1];
numAry[j-1] = numAry[j];
numAry[j] = temp;
j--;
}
}
3. 소스 인증
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
//Integer N = Integer.valueOf(); //wrapper객체로 반환
//String str1 = Integer.toString(123);
//String str1 = String.valueOf(123);
/*
String.valueOf는 내부적으로 Integer.toString()을 사용하지만
null값의 경우 에러가 발생하지 않는다.
*/
int [] numAry = new int[N];
for (int i = 0; i < N;i++ ) {
numAry[i] = Integer.parseInt(br.readLine());
}
int index, temp, minValue;
for (int i = 0; i < numAry.length; i++) {
minValue = Integer.MAX_VALUE;
temp = Integer.MAX_VALUE;
index = Integer.MAX_VALUE;
for (int j = i; j < numAry.length; j++) {
if(minValue > numAry[j]){
minValue = numAry[j];
index = j;
}
}
temp = numAry[i];
numAry[i] = numAry[index];
numAry[index] = temp;
}
for (int i = 0; i < numAry.length; i++){
System.out.println(numAry[i]);
}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int [] numAry = new int[N];
for (int i = 0; i < N;i++ ) {
numAry[i] = Integer.parseInt(br.readLine());
}
for(int i = 0; i < numAry.length - 1; i++){ //맨 끝은 계산할 필요 없으니
for(int j = 0; j < numAry.length - 1 - i; j++){ //맨 끝은 numAry[j+1]로 계산한다 + 뒤에서 i 자리는 이미 정렬
if(numAry[j] > numAry[j+1]){
int temp = numAry[j]; //대각선 스왑
numAry[j] = numAry[j+1]; //대각선 스왑
numAry[j+1] = temp; //대각선 스왑
}
}
}
for (int i = 0; i < numAry.length; i++){
System.out.println(numAry[i]);
}
}
}
import java.util.*;
import java.lang.*;
import java.io.*;
// The main method must be in a class named "Main".
class Main {
public static void main(String[] args)throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int [] numAry = new int[N];
for(int i = 0; i < N; i++ ){
numAry[i] = Integer.parseInt(br.readLine());
}
for(int i = 1; i < numAry.length; i++){
int j = i;
/*
int j = i 는 그 앞들의 모든 값과 비교해서 작으면 맨 앞으로 보내야 하기 때문에
while 는 그 앞들의 모든 값과 비교해서 작으면 맨 앞으로 보내야 하기 때문에
j > 0 는 j-- 떄문에 필요함
*/
while(j > 0 && numAry[j] < numAry[j-1]){
int temp = numAry[j-1]; //대각선스왑
numAry[j-1] = numAry[j]; //대각선스왑
numAry[j] = temp; //대각선스왑
j--;
}
}
for(int i : numAry){
System.out.println(i);
}
}
}
- 실패 소스코드 -
4.추가 개념
1. 알고리즘 개요:
- 선택 정렬은 주어진 리스트를 순차적으로 정렬하는 비교 기반 정렬 알고리즘입니다.
- 리스트에서 최소값을 찾아 첫 번째 요소와 교환하고, 다음 최소값을 찾아 두 번째 요소와 교환하는 방식으로 진행됩니다.
2. 작동 방식:
- 첫 번째 루프: 리스트의 첫 번째 요소부터 마지막 요소까지 반복합니다.
- 두 번째 루프: 최소값을 찾기 위해 현재 위치에서 끝까지 탐색합니다.
- 교환: 최소값을 현재 위치에 있는 요소와 교환합니다.
3. 시간 복잡도:
- 평균 및 최악의 경우: O(n^2)
- 최선의 경우: O(n^2)
- 예 ) 5,4,3,2,1 의 순차로 배열되어 있는경우
- 5+4+3+2+1 첫 자리 5는 5번 , 두번째 자리는 4번, 3번째 자리는 3번, ... 이렇게 반복해서 살펴봐야 한다.
- 등차수열의 공식으로 풀어서 보면 N * ( N + 1 ) / 2 이므로 5 * ( 5 + 1 ) / 2 = 15번 이다.
- 근데 무한히 큰 수를 대입해보면 1000000*(1000000+1) / 2 에서 +1과 / 2는 큰 의미가 없다.
이미 1000000 * 1000000이 시간을 다잡아먹는다. - 그래서 결론은 O(N^2) 이다.
- N이 많아질수록 속도가 2차 함수 형태로 증가한다.
- 예 ) 5,4,3,2,1 의 순차로 배열되어 있는경우
4. 공간 복잡도:
- O(1) (제자리 정렬 알고리즘)
5. 특징:
- 간단하고 구현이 쉬움.
- 작은 데이터셋에 적합.
- 안정적이지 않음(같은 값의 원소가 순서를 유지하지 않음).
1. 알고리즘 개요:
- 버블 정렬은 인접한 두 요소를 비교하여 정렬하는 비교 기반 정렬 알고리즘입니다.
- 배열을 반복적으로 순회하며, 인접한 두 요소를 비교하고 필요에 따라 교환하여 정렬을 완료합니다.
2. 작동 방식:
- 첫 번째 루프: 배열의 끝에서 끝까지 반복합니다.
- 두 번째 루프: 각 요소를 인접한 요소와 비교하여 필요하면 교환합니다.
- 가장 큰 요소가 배열의 끝으로 ‘버블’처럼 올라옵니다.
3. 시간 복잡도:
- 평균 및 최악의 경우: O(n^2)
- 최선의 경우: O(n) (이미 정렬된 경우)
- 선택정렬과 복잡도는 동일하지만 매번 버블정렬을 해주기 때문에 가장 효율이 안좋다.
4. 공간 복잡도:
- O(1) (제자리 정렬 알고리즘)
5. 특징:
- 간단하고 이해하기 쉬움.
- 작은 데이터셋에 적합.
- 안정적인 정렬(같은 값의 원소가 순서를 유지함).
1. 알고리즘 개요:
- 삽입 정렬은 배열을 정렬된 부분과 정렬되지 않은 부분으로 나누고, 정렬되지 않은 요소를 하나씩 정렬된 부분에 삽입하여 정렬하는 알고리즘입니다.
2. 작동 방식:
- 두 번째 요소부터 시작하여, 현재 요소를 정렬된 부분과 비교하면서 올바른 위치에 삽입합니다.
- 정렬된 부분은 항상 오름차순을 유지합니다.
3. 시간 복잡도:
- 평균 및 최악의 경우: O(n^2)
- 최선의 경우: O(n) (이미 정렬된 경우)
- 선택,버블 정렬과 복잡도는 동일하지만 "거의 정렬된 상황에서는" 가장 효율이 좋다. 2,3,4,5,1 일때 ..
4. 공간 복잡도:
- O(1) (제자리 정렬 알고리즘)
5. 특징:
- 단순하고 구현이 쉬움.
- 작은 데이터셋에 적합.
- 안정적인 정렬(같은 값의 원소가 순서를 유지함).
5. 참조 블로그
불편함을 느끼실 경우 연락 주시면 곧 바로 삭제하도록 하겠습니다.
728x90
반응형
'알고리즘(BOJ) 문제풀이' 카테고리의 다른 글
| [BOJ/백준] 정렬_ 2751번_ 병합정렬(Merge Sort) (1) | 2024.06.06 |
|---|---|
| [BOJ/백준] 정렬_ 2751번_ 퀵정렬(Quick Sort) (2) | 2024.06.05 |
| [BOJ/백준] 약수, 배수와 소수_ 11653번 (2) | 2024.06.03 |
| [BOJ/백준] 약수, 배수와 소수_ 2581번 (0) | 2024.06.02 |
| [BOJ/백준] 약수, 배수와 소수_ 1978번 (2) | 2024.06.02 |