1. 삭제가 O(1)인 list를 사용한다. 단, 원소 탐색이 불편하고 O(N)이라는 단점이 있다 2. 일반적으로 많이 사용하는 vector 혹은 deque의 경우에, pair이라는 자료형을 효과적으로 사용해보자

algorithm 헤더에 있는 함수로 n번째 요소를 기준으로 정렬을 하는 것이다 지정한 요소 위치에서만 정확한 값을 배치하고 나머지는 좌우로 구간을 분할한다. 좌우 구간은 정렬을 보장하지 않는다

총 몇번의 이동으로 정렬이 되는지를 묻는 문제다 버블소트의 성질은 각 시도마다 시도하는 배열에서 제일 큰 값이 오른쪽으로 바로 이동하고 나머지는 수는 왼쪽으로 한 칸 이동한다 결국 왼쪽으로 이동되는 횟수 중 가장 큰 값을 조사하면 된다 문제: https://www.acmicpc.net/problem/1377 깃허브주소: https://github.com/surinoel/boj/blob/master/1377.cpp

N의 제한이 10000000이라는 점에서 모든 값을 담는다면 메모리 제한(>=40MB)을 주목할 필요가 있다 하지만, 값의 제한은 10000이하로 계수로 수를 정렬할 수 있다 문제: https://www.acmicpc.net/problem/10989 https://github.com/surinoel/boj/blob/master/10989.cpp

삼성 A형테스트 상시검정에서 출제된 문제 2 삼성은 조건과 제한이 많다는 점에서 꼼꼼이 읽어야만 코딩할 수 있다 순열 + bfs + 정렬을 이용한 문제. 그리고 deque을 이용해 vector를 구성할 수 있다는 점을 유심히 살펴봐야 한다 문제: https://www.acmicpc.net/problem/17135 깃허브주소: https://github.com/surinoel/boj/blob/master/17135.cpp

삼성 A형테스트 상시검정에서 출제된 문제 N*N이 크지 않다는 점과 제한이 많다는 점을 고려해서 브루트포스 + 백트래킹으로 생각하고 풀었다 문제: https://www.acmicpc.net/problem/17136 깃허브주소: https://github.com/surinoel/boj/blob/master/17136.cpp