버블 정렬(Bubble Sort) 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법 Repeat n–1 times For i from 0 to n–2 If i'th and i+1'th elements out of order Swap them 버블 정렬은 단 두 개의 요소만 정렬해 주는 좁은 범위의 정렬에 집중한다. 이 방법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있다. 중첩 루프를 돌아야 하고, n 개의 값이 주어졌을 때 각 루프는 각각 (n-1) 번, (n-2) 번 반복되므로 버블 정렬의 실행 시간의 상한은 O(n^2) 또한 정렬이 되어 있는지 여부에 관계없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실..
덱(Deque) front와 end에서 삭제와 삽입이 모두 가능하다. 리스트의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 자료구조 (Double Ended Queue) 연속적인 메모리를 기반으로 하는 '시퀀스 컨테이너'이다. (임의 접근 반복자 제공) 여러 개의 메모리 단위로 데이터를 저장한다. 크기가 가변적이다. (선언 후에 변경 가능) 중간 요소가 삽입, 삭제될 때, 요소들을 앞/뒤로 밀수 있으므로 vector 보다는 좋은 성능을 가짐 스크롤(Scroll) : 입력 제한 덱 (입력이 한쪽에서만 발생하고, 출력은 양쪽에서 일어날 수 있음) 셸프(Shelf) : 출력 제한 덱 (입력은 양쪽에서 일어나고, 출력은 한쪽에서만 일어나도록 제한) 장점 데이터의 삽입과 삭제가 빠르다 크기가 가변적이다. 앞/..
큐(Queue) FIFO(First In First Out) 구조 : 먼저 넣은 데이터가 먼저 나오는 구조 선형 리스트의 한쪽에서는 삽입, 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조 데이터가 삽입(push)되는 곳을 front, 제거(pop)되는 곳을 back이라고 한다. front 포인터 : 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터 (삭제 작업에 사용) rear 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터 (삽입 작업에 사용) 장점 데이터의 삽입과 삭제가 빠르다. 단점 큐(Queue)의 중간에 위치한 데이터로의 접근이 어렵다. 사용 데이터를 입력된 순서대로 처리해야 할 때 BFS(너비 우선 탐색), Flood Fill ex) BFS 문제, 콜센터 대기 ..
스택(Stack) LIFO(Last In First Out) 구조 : 한쪽 끝에서만 자료를 넣고 뺄 수 있는 구조 스택에 데이터를 push 하면 항상 top에 들어가고, pop 하면 가장 최근에 push 한 데이터가 나온다. 맨 위 요소에만 접근할 수 있다. 자료가 없을 때 pop하는 오류를 stack underflow라고 한다. 스택의 크기 이상의 자료를 push 하려고 할 때의 오류를 stack overflow라고 한다. 장점 데이터의 삽입과 삭제가 빠르다. 단점 탐색을 하려면 원소 하나하나를 꺼내서 옮겨가면서 해야 한다. 맨 위의 원소에만 접근 가능하다. 사용 재귀 알고리즘 (재귀 프로그램의 순서 제어 등) 역추적을 해야 할 때 (ex) 문서 작업 시 실행 취소) ex) 괄호 검사, 역순 문자열 만..
2개의 자연수 또는 정식의 최대공약수(greatest common divisor)를 구하는 알고리즘 중 하나 입력으로 두 수 m,n(m>n)이 들어온다. n이 0이라면, m을 출력하고 알고리즘을 종료한다. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다. 재귀 함수를 이용하는 방법 int GCD(int a, int b) { if (b == 0) return a; else return GCD(b, a%b); } 반복문을 이용하는 방법 int GCD(int a, int b) { int c; while (b) { c = a%b; a = b; b = c; } return a; } 이를 이용해 ..
소수 판정법 중 하나 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 2는 소수이므로 오른쪽에 2를 쓴다. 자기 자신을 제외한 2의 배수를 모두 지운다. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. 자기 자신을 제외한 3의 배수를 모두 지운다. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. 자기 자신을 제외한 5의 배수를 모두 지운다. 남아있는 수 가운데 7은 소수이므로 오른쪽에 7을 쓴다. 자기 자신을 제외한 7의 배수를 모두 지운다. 위의 과정을 반복하면 구하는 구간의 모든 소수가 남는다. #include int number = 100000; int a[1000001]; void primeNumberSieve() { // 1. 배열을 생성하여 초기화한다. for (in..
