CordCat

문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 난 이 문제를 처음에 수가 100만 개나 입력되기 때문에 시간복잡도가 효율적인 정렬을 사용하기 위해 Quick Sort를 이용해서 풀려고 했었다. Quick Sort import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; impo..

Selection Sort 선택 정렬(Selection Sort)은 가장 간단한 정렬 알고리즘 중 하나입니다. 이 알고리즘은 주어진 리스트에서 가장 작은 값을 선택하여 맨 앞으로 이동시키는 과정을 반복하여 리스트를 정렬하는 방식입니다. 동작 과정 주어진 리스트에서 가장 작은 값을 찾습니다. 가장 작은 값과 리스트의 맨 앞의 원소를 교환합니다 정렬된 영역을 제외하고 나머지 리스트에서 가장 작은 값을 찾습니다. 다시 가장 작은 값과 정렬되지 않은 부분의 맨 앞 원소를 교환합니다. 이러한 과정을 리스트의 모든 원소가 정렬될 때까지 반복합니다. 예시 코드 public class SelectionSort { /** * i 와 j의 위치에 있는 값을 바꿉니다. (가장 작은 값인 array[j]와 array[i]의 ..

시간 복잡도 위에 그래프의 모습에서 보이는 것처럼 간단한 출력과 같은 O(1) 혹은 단순한 증가함수인 O(n), O(log n ) 들과 O(n^2), O(2^n)의 그래프의 기울기가 큰 차이가 나타나는 걸 볼 수 있습니다. 컴퓨터가 계산할 때 사용하는 알고리즘,함수에 따라 값에 증가에 따른 결괏값을 구하는 시간이 달라지는데 이를 시간 복잡도라고 얘기합니다. 시간 복잡도를 고려해야 하는 이유 우리가 프로그램을 만들 때 구현하려는 값을 어떤 알고리즘을 이용해 구현하느냐에 따라 그 프로그램의 최적화에 영향이 가기에 항상 어떻게 하면 더 효율적으로 구현할 수 있는지 고민해야 하며 알고리즘 문제를 풀 때도 문제에서 원하는 시간을 초과하면 문제를 풀 수 없는 경우도 있기에 어떠한 방식으로 알고리즘을 구현할지 생각할..