삽입 정렬(Insertion Sort) -배열을 정렬된 부분(앞부분)과 정렬 안 된 부분(뒷부분)으로 나누고, 뒷부분의 가장 왼쪽 원소를 앞부분의 적절한 위치에 삽입하여 정렬되도록 하는 과정을 반복 -정렬된 부분의 원소 수가 1개 늘어나고, 동시에 정렬이 안 된 부분의 원소 수는 1개 줄어듦 -반복하면, 뒷부분에는 아무 원소도 남지 않고, 입력이 정렬됨 알고리즘 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A for i=1 to n-1 CurrentElement = A[i] j =0) and (A[j] > CurrentElement) A[j+1]=A[j] A[j+1] 1+2+3+...+(n-2)+(n-1)=n(n-1)/2 루프 내부는 O(1) >> n(n-1)/2*O(1)=O(n^2) 2. 최선 경우..
선택 정렬(Selection Sort) - 입력 배열 전체에서 최솟값을 선택하여 배열의 0번 원소와 자리를 바꾸고, 다음엔 0번 원소를 제외한 나머지 원소에서 최솟값을 선택하여, 배열의 1번 원소와 자리를 바꿈 >> 마지막에 2개의 원소 중 작은 것을 선택하여 자리를 바꿈 알고리즘 입력: 크기가 n인 배열 A 출력: 정렬된 배열 A for i=0 to n-2 min = i for j=i+1 to n-1 if A[j] < A[min] min=j A[i] A[min] return A 시간 복잡도 외부 for루프는 (n-1)번 수행 -i=0일 때 내부 for루프는 (n-1)번 수행 -i=1일 때 내부 for루프는 (n-2)번 수행 ... -마지막으로 1번 수행 내부의 for루프가 수행되는 총 횟수 -(n-1)..
내부 정렬(Internal sort) -입력의 크기가 주기억 장치의 공간보다 크지 않은 경우에 수행되는 정렬 ex) 버블 정렬, 선택 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬, 쉘 정렬, 기수 정렬, 이중 피봇 퀵정렬. Tim sort 외부 정렬(External sort) -입력의 크기가 주기억 장치의 공간보다 큰 경우에 보조 기억 장치에 있는 입력을 여러 번에 나누어 주기억 장치에 읽어 들인 후, 정렬하여 보조 기억 장치에 다시 저장하는 과정을 반복 버블 정렬 -이웃하는 숫자를 비교하여 작은 수를 앞쪽(오름차순)으로 이동시키는 과정을 반복하여 정렬 -배열을 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케 함 패스: 입력을 전반적으로 1번 처리하는 것 1번..
문제 https://www.acmicpc.net/problem/25304 25304번: 영수증 준원이는 저번 주에 살면서 처음으로 코스트코를 가 봤다. 정말 멋졌다. 그런데, 몇 개 담지도 않았는데 수상하게 높은 금액이 나오는 것이다! 준원이는 영수증을 보면서 정확하게 계산된 것 www.acmicpc.net 풀이 int main(void){ int x,n,a,b; int sum=0; scanf("%d\n %d\n",&x,&n); for(int i=0; i
전공자 2학년이지만, 포트폴리오도 아무것도 준비되어 있지 않아서 우선 뭐라도 해보자라는 생각에 리눅스 마스터 2급을 따기로 마음을 먹었다. 이 자격증이 얼마나 쓸모가 있을지에 대한 여부도 고려하려고 했지만, 아직 포트폴리오가 아무것도 없어서 뭐라도 따자는 마인드로 시험을 보기로 했다 글쓴이는 23학년 1학기 리눅스라는 전공 수업을 들어서 자세히는 아니지만 어느정도 리눅스에 대한 기본적인 것들을 알고 사용도 꽤 해본 상태이다. 본격적으로 리눅스 마스터 2급 1차 합격 후기를 남겨보려고 한다. (1) 리눅스 마스터 2급 시험 범위 리눅스 마스터 2급은 리눅스 일반, 리눅스 운영 및 관리, 리눅스 활용을 시험 본다. 1차에서는 리눅스 일반, 2차에서는 리눅스 운영 및 관리(60%), 리눅스 활용(40%)를 보..
