Algorithm
Bubble Sort - Back
Bubble Sort
서로 인접한 두 원소를 검사하여 정렬하는 알고리즘으로 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환한다. 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를, … 이런 식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다. 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다. 이렇게 정렬을 1회전 수행할 때마다 데이터를 하나씩 제외시키고 다음 정렬을 수행하게 된다. 따라서 버블 정렬의 시간복잡도는 이다.
아래와 같은 배열을 버블 정렬로 정렬한다고 가정해 보자.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 7 | 2 | 3 | 9 | 28 | 11 |
첫 번째로 앞에 두 칸인 7과 2를 비교한다. 2가 더 작기 때문에 둘을 교환한다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 7 | 3 | 9 | 28 | 11 |
두 번째로 다음 칸인 7과 3을 비교한다. 3이 더 작기 때문에 둘을 교환한다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 3 | 7 | 9 | 28 | 11 |
세 번째로 다음 칸인 7과 9를 비교한다. 올바른 순서로 있기 때문에 교환하지 않는다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 3 | 7 | 9 | 28 | 11 |
다음으로 다음 칸인 9와 28을 비교한다. 올바른 순서로 있기 때문에 교환하지 않는다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 3 | 7 | 9 | 28 | 11 |
다음으로 28과 11을 비교한다. 11이 더 작기 때문에 둘을 교환한다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 3 | 7 | 9 | 11 | 28 |
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {1, 3, 4, 7, 2, 88, 4, 56};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
System.out.println(Arrays.toString(arr));
}
}이 코드를 Objected Oriented Programming 기법을 적용해서 리팩토링해 보면 다음과 같다. SortAround 기능과 Sort 기능을 나누는 것이다. 이렇게 main 안에 있는 기능을 밖으로 빼 method로 만드는 연습을 하는 것이 좋다.
public class BubbleSort {
public int[] sort (int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
arr = sortARound(arr, i);
}
return arr;
}
public int[] sortARound(int[] arr, int until) {
for (int j = 0; j < arr.length - 1 - until; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {1, 3, 4, 7, 2, 88, 4, 56};
BubbleSort02 bubbleSort = new BubbleSort02();
arr = bubbleSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}Bubble Sort - Front
앞선 bubble sort는 뒤부터 가장 큰 아이템이 정렬되도록 구현하는 방법이었다. 버블 정렬의 다른 방법으로는 앞에서부터 가장 작은 값을 정렬하기 시작하는 알고리즘이 있다. 이 역시 한 정렬 사이클이 돌 때마다 앞에 가장 작은 아이템의 자리를 찾기 때문에 시간복잡도는 이다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 7 | 2 | 3 | 9 | 28 | 11 |
0과 1 index를 비교했을 때 7 > 2 이기 때문에 둘을 교환한다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 7 | 3 | 9 | 28 | 11 |
0과 2 index를 비교했을 때 2 > 3 이기 때문에 그대로 둔다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 7 | 3 | 9 | 28 | 11 |
0과 3 index를 비교했을 때 2 > 9 이기 때문에 그대로 둔다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 7 | 3 | 9 | 28 | 11 |
0과 4 index를 비교했을 때 2 > 28 이기 때문에 그대로 둔다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 7 | 3 | 9 | 28 | 11 |
0과 5 index를 비교했을 때 2 > 11 이기 때문에 그대로 둔다.
| 0 | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| 2 | 7 | 3 | 9 | 28 | 11 |
public class BubbleSort {
public static void main(String[] args) {
int[] arr = {7, 2, 3, 9, 28, 11};
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
System.out.printf(Arrays.toString(arr));
}
}이 방식의 버블 정렬도 객체 지향 형식으로 바꿔 만들면 다음과 같다.
public class BubbleSort03 {
public int[] sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] > arr[j]) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
return arr;
}
public static void main(String[] args) {
int[] arr = {7, 2, 3, 9, 28, 11};
BubbleSort03 bubbleSort = new BubbleSort03();
arr = bubbleSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
}AWS
EC2
EC2
쉽게 생각해서 한대의 컴퓨터를 임대해 주는 것이다. 이 컴퓨터는 특별한 컴퓨터가 아니라 우리가 사용하는 데스크탑이나 노트북과 정확하게 똑같은 컴퓨터다. 여기에 자신이 선호하는 운영체제를 설치하고, 웹서비스를 위한 프로그램들(웹서버, 데이터베이스 등)을 설치하면 된다. AWS(아마존 웹서비스)에서는 인터넷을 통해서 이 컴퓨터에서 접속 할 수 있는 URL(Public DNS)을 제공하는데, 이 URL을 통해서 웹서비스를 하거나, 자신이 구입한 도메인을 붙여서 서비스 할 수도 있다.
물론, 여러분의 가정용 컴퓨터와 EC2는 중요한 차이가 있다. 인터넷을 통해서만 접속할 수 있고, 주문 후 1분 안에 생성되고, 삭제 즉시 제거된다. 초기 구입비가 전혀 없고, 사용한 만큼 비용을 지불하면 된다. 컴퓨터를 사용하면 프로그램도 설치하고, 파일도 저장하고, 설정도 변경하게 되는데, 이 상태 그대로 저장 할 수 있다. 이것을 이미지라고 한다. 이미지를 이용해서 새로운 컴퓨터를 만들면 이미지에 저장된 상태와 똑같은 컴퓨터를 생성할 수 있다. 컴퓨터를 장만할 때마다 반복되는 설치 작업을 하지 않게 되는 것이다.
Elastic Compute Cloud의 약자로 EC2라고 하며, 아마존 웹서비스의 심장에 해당하는 서비스다.
EC2는 Elastic Compute Cloud 의 약자이다. Linux, Window or Mac등 다양한 OS로 클라우드상에 서버를 띄울 수 있습니다.
인스턴스 시작 후 이름과 ubundu linux OS을 선택한다.
인스턴스 타입에서 무료 버전인 t3.micro을 선택한다. t2.small 정도는 돼야 안정적이지만 비용 부담을 위해 t3.micro를 사용한다.
네트워크 설정에서 밑에 두 개 허용하고 80ㅗ트 열기
spot instance 무조건 설정하기
spot instance → 종료 권한이 AWS에 있음
키페어생성
SSH 연결
맥북 유저는 권한 변경을 위해 모드를 변경해 주고 ssh 연결을 해야 한다.
sudo chmod 400 <키페어 경로>
ssh ubuntu@<EC2 주소> -i <키페어 경로>연결이 완료된 후 터미널 창은 다음과 같은 상태가 된다.
Linux
Docker
Docker
대표적인 Container 기술의 이름이면서도 회사 이름이다. Container 기술이란 서버와 애플리케이션을 분리하는 기술이다. 컨테이너 기반의 애플리케이션을 개발하고 배포하고 실행할 수 있는 오픈 소스 플랫폼이다. 개인 컴퓨터의 infrastructure과 격리시켜 앱을 실행하기 때문에 소프트웨어 실행 속도가 빠르다. infrastructure as code 개발 환경 셋팅을 코드로 진행한다. DevOps를 지향하여 코드를 쓰고 배포하기까지 시간 단축시키는 장점이 있다.
Docker를 사용하지 않으면 어플리케이션 간의 Dependency 문제나 Port 충돌 등 여러 문제가 발생할 수도 있다. docker는 image라는 파일을 container에 띄워서 명령을 실행시킨다. 가상 머신과 다르게 명령이 끝나고 할 일이 마무리되면 image는 종료 상태가 되어 마치 프로그램과 비슷하다.
- Image: 앱을 실행하기 위한 모든 것들을 포함한 하나의 단위, 특정 프로세스를 실행하기 위한 환경
- 계층화된 파일 시스템, 파일들의 집합
- code
- runtime library
- environment variables
- configuration files
- Container: 이미지를 실행하기 위해 담을 수 있는 구조로 이미지의 런타임 객체
- 이미지를 실행하여 메모리를 차지하기 시작하면 컨테이너가 됨
- 따라서 여러 개의 컨테이너가 하나의 이미지를 위해 존재할 수 있음
- command line, docker desktop 에서 실행 중인 컨테이너 목록을 볼 수 있음
root 권한으로 실행
sudo su -docker 수동 설치 방법도 있지만 강의에서는 빠른 설치를 위해 아래 git code를 clone하여 사용한다.
git clone [https://github.com/Kyeongrok/docker_minikube_kubectl_install](https://github.com/Kyeongrok/docker_minikube_kubectl_install); cd docker_minikube_kubectl_install;sh docker_install.sh;아래 사이트에서 oh my bash를 설치한다. 자동 완성 등의 기능을 편리하게 제공해 주는 프로그램이다.
Nginx
// docker에서 nginx 실행
docker run nginx
// 포트 지정하고 실행
docker run -p 80:80 nginx
// command + c : 종료MySQL
EC2 인스턴스 보안 규칙에서 mysql 포트를 열어 준다.
이후 터미널 명령을 통해 3306 번 포트로 mysql 서버를 띄우면 된다. 이때 password 자리에 비밀번호가 들어가고, -d 옵션을 통해 Docker deamon으로 실행할 수 있다.
docker run -p 3306:3306 -e MYSQL_ROOT_PASSWORD=password -d mysql