C++13 [알고리즘] - 쉘 정렬 (Shell-sort) 1. 쉘 정렬(Shell-Sort)이란? 리스트를 일정한 간격에 따라 나누고, 각 부분 리스트를 삽입 정렬을 통해 정렬하는 방법이다. 앞선 글에서 삽입 정렬 에 대해 설명하였다. 삽입 정렬의 경우, 기존 배열이 어느정도 정렬되어있냐에 따라 수행 시간이 크게 차이난다. 현재 선택한 원소의 적절한 삽입 위치가 멀다면, 비교 & 이동해야하는 횟수가 많아지면서 수행 시간이 늘어나는 것이다. 정렬된 상태와 가까운 배열일수록 수행 시간은 단축된다. 즉, 삽입 정렬은 초기 리스트가 정렬이 된 상태일 경우 더 효율적이다. → 조금이라도 정렬이 된 상태에 가까운 배열로 만든 후에 삽입정렬을 수행하는 방법이 쉘 정렬이라고 할 수 있겠다. → 쉘 정렬은 삽입 정렬을 보완한 방법! 쉘 정렬의 시간 복잡도는 아직까지도 정확하게.. 2024. 4. 14. [알고리즘] - 삽입 정렬 (Insertion-sort) 1. 삽입 정렬(Insertion Sort)이란? 선택한 원소를 현재 정렬된 배열 범위 내의 적절한 위치에 삽입하는 방법이다. 구현하기 쉬운 알고리즘이지만, 시간 복잡도는 O(n²) 으로 다른 정렬 알고리즘들에 비해서 느린 편에 속한다. 2. 삽입 정렬의 수행 방식 삽입 정렬 과정 ① 현재 index의 원소를 선택한다. ② 정렬된 부분 내에서, 현재 선택한 원소가 들어갈 적절한 삽입 위치를 찾는다. ③ 삽입 위치부터 끝까지 데이터를 한 칸씩 뒤로 민다. ④ 삽입 위치에 현재 선택한 원소를 삽입한다. ⑤ index를 1 증가시키고, 다시 ①부터 반복한다. (index가 배열의 크기만큼 커질때까지 반복) 다시 말해, 인덱스를 증가시켜 가면서 배열의 원소를 선택하고, 선택한 원소를 정렬된 범위 내의 적절한 위.. 2024. 4. 9. [C++] - 덱(deque) 사용법 정리 (STL) 덱(deque)이란? 덱(deque)이란, double-ended-queue의 줄임말로, 큐의 양쪽에서 원소를 삽입하거나 삭제할 수 있는 자료구조이다. 덱은 C++에서 많이 쓰이는 STL 자료구조 중 하나이다. 1. 헤더파일 #include using namespace std; deque를 사용하기 위해서는 헤더파일을 include 시켜주어야 한다. STL deque는 std namespace에 있기 때문에 cin이나 cout을 사용할 때와 같이 using namespace std;를 써주면 std::를 일일이 써주지 않아도 되어 편리하다. 2. deque 선언하기 deque 이름; #include #include using namespace std; int main(){ deque dq;//D라는 이름.. 2024. 1. 16. [C++] - string → int 로 형변환하기 1. stoi() 메소드 이용하기 (string -> 모든 숫자형 가능) stoi() 메소드는 간단하게 string을 int로 바꿀 수 있는 함수이다. (string to int 에서 앞 문자를 따와서 stoi라고 부른다.) stoi(string변수명) 이라고 써주면 된다. stoi() 함수를 사용하려면 헤더파일을 include 시켜줘야 한다. -> C언어에서 사용하는 #include 가 아닌 #include 을 사용하므로 혼동하지 않도록 주의하자 int 뿐만 아니라 long, double, float 등도 변환이 가능하다. (값 손실이 있을 수 있으니 주의하자) int로 변환 stoi(); long으로 변환 stol(); double로 변환 stod(); float로 변환 stof(); #include.. 2024. 1. 12. [C++] - int → string 으로 형변환하기 1. to_string() 메소드 이용하기 to_string() 메소드는 숫자형을 string으로 변환할 수 있는 간단한 방법이다. to_string(변수 이름)이라고 써주면 된다. int뿐만 아니라 long, double, float 등도 string형으로 형 변환이 가능하다. to_string()을 사용하기 위해서는 헤더파일을 include 시켜주어야 한다. -> C언어에서 사용하는 #include 가 아닌 #include 을 사용하므로 혼동하지 않도록 주의하자. #include #include using namespace std; int main() { int i_num = 2024; long l_num = 20242024; double d_num = 1234.12; float f_num = 123.. 2024. 1. 10. [C++] - vector를 2차원으로 사용하기 (STL) vector는 동적으로 메모리를 할당한 배열이다. 기존 1차원 vector를 값을 초기화하여 선언하는 방법은 다음과 같았다. vector 이름 (크기, 초기값) ; ex) vector v; 2차원 vector를 선언하려면, vector의 데이터 타입에 vector를 또 담는다고 생각하면 된다. vectorv; → 벡터의 자료형에 또 다른 벡터가 들어간다. 2차원 벡터는 2차원 배열과 같이 대괄호를 이용한 v[i][j]로 각 원소에 접근이 가능하다. 1. 행이 m개, 열이 n개인 2차원 벡터를 0으로 초기화하여 선언 vector v(m, vector(n,0)); 벡터 v는 m개의 원소를 가지고 있으며, 이 m개의 원소들은 각각 n개의 원소를 0으로 초기화한 벡터를 담고 있다. int m, n; cin >>.. 2024. 1. 8. 이전 1 2 3 다음
