주어진 수들을 정렬해야 하는 경우, 수들이 모두 양수이고, 최대값이 정해져 있다면. 카운팅 정렬 (계수 정렬)로 더욱 빠르게 정렬해 볼 수 있다. ■ 계수 정렬? 계수 정렬 알고리즘은 비교를 하지 않는다. 배열의 인덱스를 사용하여 숫자의 개수를 카운팅, 순서대로 출력하는 것이다. 매우 간단하다. 계수 정렬의 시간복잡도는 O(n) 으로 실행 시간은 짧지만 사용하기 위해 조건이 있다. 먼저 주어진 숫자들이 자연수이고, 최대값이 너무 크지 않아야 한다. 배열의 인덱스를 사용 할 것이기 때문에 양수만 가능하고, 최대값이 너무 커져버리면 메모리에 부담이 커진다. 이러한 조건 때문에 다른 정렬 알고리즘만큼 많이 쓰이지는 않는다. 하지만 위 조건을 충족하는 경우 다른 정렬 알고리즘보다 효율적으로 정렬할 수 있다. ■..
Data Structure
배열? 동일한 타입의 데이터들을 한번에 여러개 만드는 방법. ex. 정수를 6개 저장할 공간을 생성한다고 할 때, 기본적인 방식으로는 int i1, i2, i3, i4, i5, i6; 와 같은 형식으로 변수들을 선언한다. 하지만 배열을 사용한다면 int i[6]; 와 같이 간단하게 선언할 수 있다. 따라서 배열은 동일한 데이터 타입을 여러 개 다뤄야 할 때 유용하게 쓰인다. 배열은 [인덱스, 값] 형태의 쌍들로 이루어진 집합이라고 볼 수 있다. 인덱스가 주어지면 그 인덱스에 해당되는 요소가 대응되기 때문에 배열에서는 인덱스 번호를 통해 값을 참조한다. 인덱스 번호를 통해 값에 쉽게 접근이 가능하기 때문에 반복루프를 사용하여 여러 작업을 할 수 있다. 2차원 배열 int i[3][3]; // 2차원배열명[..
프로그램은 큰 틀에서 보았을 때 자료구조+알고리즘 의 형태이다. 자료구조란? 프로그램에서 사용되는 자료를 표현하고, 저장, 조작하는 방법 및 수단을 말한다. 대표적으로 스택, 큐, 리스트, 트리 등이 있다. 알고리즘이란? 컴퓨터로 문제를 해결하기 위한 단계적 절차를 기술하는것을 말한다. 알고리즘의 성능을 분석하고 알고리즘의 효율성을 높여서 프로그램을 최적화하고 빠르게 작동할 수 있도록 한다. 알고리즘의 성능을 분석하기 위한 두 가지 방법을 보자. 1. 수행시간을 측정하는 방법 두 개의 알고리즘을 실행하고 실제 실행시간을 측정하고 비교하여 더 효율적인 알고리즘을 선택하는 방법이다. 하지만 두 개의 알고리즘을 실제 프로그램으로 구현해야하고 동일한 하드웨어, 사용된 언어 등 동일한 조건을 갖춰야 확실하게 비교..
