버블 정렬 버블정렬 (bubble sort)란 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간복잡도가 O(n^2)로 상당히 느리지만 코드가 단순하기 때문에 자주 사용된다. (출처 위키백과) GIF 으로 개념이해 오름차순정렬을 하게되면 첫번째 원소와 두번째 원소를 비교하여 첫번째 원소가 두번째 원소보다 크면 두 원소를 교환하고 두번째 원소와 세번째 원소를 비교하고, 세번째 원소와 네번째 원소를 비교하고 이런식으로 (마지막-1) 번째 원소와 마지막 원소를 비교하여 정렬한다. 이런식으로 1번 처음부터 끝까지 수행하게 되면(1회전 후) 배열의 가장 큰 원소가 맨 뒤로 이동하므로 2회전을 수행할때는 맨 끝에 있는 원소는 정렬에서 제외된다. 1회전을 할때 교환이 이루어지지 않으면 정렬이 된 상태라고 볼 수 있는..

선택정렬 선택정렬 (selection sort)은 제자리 정렬 알고리즘의 하나이다. 주어진 리스트 중에 최소값을 찾는다. 그 값을 맨 앞에 위치한 값과 교체한다(패스(pass)). 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 이 1,2,3을 계속 반복하는 알고리즘이다. 이런식으로 처음엔 첫번째 원소부터 마지막 원소중 최소값을 찾아 배열 맨 앞에 있는 원소와 교환하고 (정렬된 첫번째 원소를 제외한) 두번째 원소부터 마지막 원소중 최소값을 또 찾아 배열 두번쨰 원소와 교환하고 배열 마지막 원소는 자동으로 정렬되기 때문에 원소 개수 -1 만큼 반복해 주면 된다. C++ 로 구현 #include using namespace std; int a[10] = { 3,6,7,1,4,2,9,0,5,8 }..

이후에 추가로 알게된 것들을 계속 추가 할 예정이다. 인프런 강좌 내용을 참고하였습니다, 퀵 정렬 (quick sort) 퀵정렬은 분할정복 방법을 사용합니다. 분할정복방법이란 순환적(recursive)으로 문제를 푸는 하향식(top-down) 접근방법입니다. 분할: 배열을 pivot 을 기준으로 pivot보다 작은 값들과 pivot 보다 크거나 같은 값으로 두 부분으로 나눈다. 정복: 각 부분을 순환적으로 정렬한다. 합병: nothing to do (필요x) 슈도코드 A배열의 첫번째 원소를 p, 마지막 원소를 r로 설정한다. 마지막 수를 pivot으로 뒀을때 그 pivot이 어디에 위치해있는지 구하는 partition 함수를 이용한다. 검사하려는 값이 pivot보다 클때, 결국 오른쪽에 있는 원소들 값이..

문제 https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 풀이과정 & 코드 디게 간단한데 쓸데없이 허우적거렸던 문제... #include using namespace std; int main() { int tc; cin >> tc; //테스트케이스 개수 입력 int result = 0; for (int i = 0; i > num; int cnt = 0; for (int j = 1; j

문제 https://www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 문제 설명 P ? : ?라는 문자를 커서 왼쪽에 추가 L : 커서를 왼쪽으로 한칸 옮김 (커서가 문장의 맨 앞이면 무시됨) D : 커서를 오른쪽으로 한칸 옮김 (커서가 문장의 맨 뒤면 무시됨) B : 커서 왼쪽에 있는 문자를 삭제함 (커서가 문장의 맨 앞이면 무시됨) - 커서를 기준으로 스택을 두개로 나눈다. #include #include #include using namespace std;..