코테 준비... 먼 훗날의 이야기라고 생각했었다
영원히 신입생일 거라 생각했지만 어느새 졸작을 준비하며 취업시장에 뛰어들 때가 왔다(나만 늙었어...)
그래서 코테준비를 위해 프로그래머스와 백준의 문제를 조금씩 풀기로 했다.
뭔가 재정비하는 시간이 온 것 같아 약간 설레기도~
처음은 무난한 것부터! 정렬문제로 시작해보자.
이번 문제같은 경우에 대략 윤곽이 나왔지만 문제에서 vector를 이용했기 때문에 해당 문법에 관련된 오류가 많았다.(보면 프로그래머스는 배열은 대부분 vector로 던져주는 듯...) 여기서는 vector과 정렬에 대한 부분을 정리하면 될 것 같다.
What is Vector?
Vector란 C++ 표준 라이브러리(Standard Template Library)에 있는 컨테이너로 사용자가 손쉽게 사용하기 위해 정의된 class이다. 배열은 크게 정적배열과 동적배열로 구분할 수 있다. 정적배열은 실행 전 배열의 크기를 명확히 해야하지만 동적배열의 경우 실행시간에 배열 크기 변경이 가능하다. C에서는 이런 동적배열을 malloc과 free를 사용해서 해결했다. 이것의 C++ 버전이 Vector라고 생각하면 된다.
Vector은 시퀀스 컨테이너에 속한다. 시퀀스 컨테이너란 배열처럼 객체들을 순차적으로 보관하는 컨테이너이다.
한마디로 정의하면 Vector란 C++에서 원소들을 메모리 상에 순차적으로 저장하는 '가변길이 배열'이라고 생각하면 된다.
How to use Vector?
vector 사용법에 대해 알아보자.
vector의 헤더파일
#include <vector>
using namespace std;*using namespace std; 를 작성하지 않을 시 vector를 사용할 때 항상 std:: 를 붙여야 한다!
vector 초기화
| Format | Description |
| vector<자료형> 변수명 | vector 변수 생성 |
| vector<자료형> 변수명(숫자) | vector 변수 생성 및 숫자만큼 size, 초기값 0 설정 |
| vector<자료형> 변수명 ={x, y, z, ...} | vector 생성 후 x, y, z 등의 값으로 초기화 |
| vector<vector<자료형>> 변수명 | 2차원 벡터 생성(열과 행 모두 가변 길이) |
| vector.assign(범위, 초기값) | 해당 범위(크기)만큼 초기값으로 초기화 |
vector 요소 접근
| Format | Description |
| vector.front() | vector의 첫번째 요소 접근 |
| vector.back() | vector의 마지막 요소 접근(size-1) |
| vector.at(i) | vector의 i번째 요소 접근(0부터 시작) |
| vector[i] | vector의 i번째 요소 접근(0부터 시작) |
vector 요소 삽입, 제거
| Format | Description |
| vector.push_back(A) | vector 마지막 요소에 A 추가 |
| vector.pop_back() | vector 마지막 요소 제거 |
| vector.insert(삽입할 주소, A) | 원하는 위치에 요소 A 삽입 |
| vector.erase(삭제할 주소) vector.erase(삭제 시작 주소, 삭제 끝 주소) |
원하는 위치의 요소 제거 |
| vector.clear() | vector의 모든 요소 제거(size=0) |
| vector.resize(X) | vector size를 X로 변경(기존 size 초과 시 자동으로 0으로 초기화) |
vector iterator
| Format | Description |
| vector.begin() | vector의 시작점 주소값 반환 |
| vector.end() | vector의 끝점+1 주소 반환(끝 요소 아님) |
| vector.rbegin() | vector의 끝점 반환 |
| vector.rend() | vector의 (시작-1) 점을 반환(시작 요소 아님) |
*iterator 변수 itr은 주소값이기 때문에 *itr을 이용해 값을 가져온다.
vector size, capacity
| Format | Description |
| vector.empty() | vector가 비어있으면 true, 아니면 false 반환 |
| vector.size() | vector size 반환 |
| vector.capacity() | 현재 heap에 할당된 vector capacity 반환 |
| vector.reserve(X) | vector size를 X로 예약 |
| vector.shrink_to_fit() | vector capacity를 size에 맞춤 |
*size는 흔히 알고있는 길이이고, capacity는 vector의 용량이다.
선택정렬(Selection sorting)
선택 정렬의 알고리즘 순서는 다음과 같다.
1. 주어진 리스트 중에 최소값을 찾는다.
2. 그 값을 맨 앞의 위치한 값과 교체한다.(Swap)
3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
시간복잡도
1. 비교횟수 : 2개의 for문 실행
- 외부 for문 : list의 가장 왼쪽에 접근 -> (n-1)번
- 내부 for문 : 최솟값 찾기 -> (n-1), (n-2), ... , 2 , 1 번
2. 교체횟수 : 외부 루프의 실행 횟수와 동일, 즉 상수 시간 작업
- 한번 교환하기 위해 3번의 이동(Swap함수의 작업)이 필요하기 때문에 3(n-1)번
=> T(n) = (n-1) + (n-2) + ... + 2 + 1 = n(n-1)/2 = O(n^2)
CODE
#include <string>
#include <vector>
#include <iostream>
using namespace std;
void Swap(int &a, int &b){
int temp;
temp = a;
a = b;
b = temp;
}
void selection_sort(vector<int> &list, int n){
int i, j, least, temp;
//마지막 숫자는 자동으로 정렬되기에 (숫자개수-1)만큼 반복
for(i=0; i<n-1; i++){
least = i;
//i부터 끝까지 중 최솟값 찾기
for(j=i+1; j<n; j++){
if(list.at(j)<list.at(least))
least = j;
}
//찾은 최솟값이 i가 아니라면 최솟값을 가장 왼쪽으로 Swap
if(i!=least){
Swap(list[i], list[least]);
}
}
}
vector<int> solution(vector<int> array, vector<vector<int>> commands){
vector<int> answer;
for(int i=0; i<commands.size(); i++){
vector<int> arr;
int start, end, num, a;
start = commands[i][0]-1;
end = commands[i][1]-1;
num = commands[i][2]-1;
a = start;
for(int k=0; k<end-start+1; k++){
arr.push_back(array.at(a));
a++;
}
selection_sort(arr, end-start+1);
answer.push_back(arr.at(num));
}
return answer;
}