EC2의 개념정리


EC2는 Elastic Compute Cloud의 약자.

아마존 웹 서비스(AWS)에서 가장 중요한 서비스이다.


한 대의 컴퓨터를 임대한다는 개념이며 특별한 컴퓨터도 아니다. 

우리가 흔히 사용하는 컴퓨터와 같다고 할 수 있으며, 

실제 컴퓨터로 할 수 있는 광범위한 작업들을 EC2를 통해 작업을 할 수 있다.


다만, EC2는 물리적이 아니라 아마존에서 세계 각 지역에 만들어놓은 인프라(데이터 센터)에 

만들어지는 것이기때문에 네트워크를 통해 제어를 해야한다.

(참고로 2016년. 서울에도 데이터 센터가 생겼다. 좀 더 빨라지지 않을까?)


AWS의 경우 클릭 몇 번만에 컴퓨터 1대를 설치할 수 있으므로 편리하다.

또한, 컴퓨터가 필요없게 됐을때 클릭 몇 번만에 컴퓨터를 설치할 수 있으므로 편리하다.

즉, 유연하며, 탄력이 있는 컴퓨팅이 가능하다.

EC2에 Elastic도 "탄력이 있는, 유연한" 이라는 뜻이다. 그래서 EC2로 이름을 만들은 것일수도 있겠다.

즉, 컴퓨터 생성 및 삭제가 매우 쉽다.


자신이 선호하는 OS를 설치하고, 웹 서비스를 위해 필요한 프로그램(웹 서버, DB)을 설치하면 된다.


EC2를 통한 가장 기본적인 업무는 


웹서버를 설치하고 이 웹서버를 통해서 

사용자가 웹브라우저를 통해 요청하는 웹페이지나 이미지, 동영상 등을 제공하는 것이다.


인스턴스란 1대의 컴퓨터를 의미하는 단위이다.



결론.


특징


1. 인터넷을 통해서만 접속을 할 수 있다.

2. 컴퓨터 주문 후 1분안에 생성이 가능하며 삭제 역시 즉시 제거가 가능하다.

3. 초기 구입비가 전혀 없고, 사용한만큼 비용을 지불하면 된다.

4. 컴퓨터를 사용할때 프로그램 설치, 파일 저장, 설정 변경... 이 상태 그대로 저장이 가능하다.

이를 이미지라고 한다. 이 이미지를 이용해서 새 컴퓨터를 만들면 저장된 상태와 똑같은 컴퓨터를 

생성할 수 있다. 컴퓨터를 생성할때마다 반복적으로 설치하는 작업을 하지 않아도 되는 것이다.


AWS에서 EC2 서비스 - 인스턴스를 생성하는 방법은 이미 블로그에 작성을 해놨다.


인스턴스는 AWS에서 컴퓨터 하나를 의미한다.

인스턴스를 4개 생성한다는 표현은 4개의 컴퓨터를 AWS 인프라 위에 생성한다는 뜻이다.

 



EC2와 웹 서버


다시 말하면,

EC2의 인스턴스는 한 대의 독립적인 컴퓨터이기 때문에 뭐든 일을 EC2로 할 수 있다.

하지만, AWS를 위해 고안된 인프라 서비스이고, AWS에서 제공하는 서비스 중에 웹서버 역할을 할 수 있는 서비스는 EC2밖에 없기때문에 가장 중요한 기능은 역시 웹서버라고 할 수 있다.

즉, 인스턴스에 웹서버를 설치하는 방법에 대해 알아보고, 웹서비스를 하는 방법에 대해 알아보자.


웹서버인 Apache를 설치하기위해 SSH를 통해 인스턴스에 접근을 해야한다.

이것역시 이전에 블로그에 작성해놨다.


PUTTY를 이용하여 인스턴스에 접근하는 방법



이와같은 Welcome to ubuntu  ~~~~~~

라고 나온다면 정상적으로 접속한 것!!!!



접속을 완료했다면, 다음과 같은 명령어를 입력한다.



sudo apt-get update;


뭔가 쭉쭉쭉 쫙쫙쫙 올라가면서 자동으로 뭔가가 설치된다.

설치되어있는 모둔 패키지를 새 버전으로 업데이트 시키라는 명령어다.



sudo apt-get install apache2;

아파치(Apache) 웹서버가 설치되었다.



정리.


Linux 기반의 ubuntu 환경의 인스턴스를 만들었고, 그 위에 아파치를 설치했다.

이제 접속이 되는지 테스트를 해봐야겠다.


웹브라우저에 Public DNS 주소를 쳐보자.



이런 화면이 나온다면 정상적으로 동작하고 있는것이다!!!!!!!!!!!










Posted by sungho88
,

아마존 웹 서비스(Amazon Web Service)는 줄여서 AWS라고 부른다.


클라우드(Cloud) & 아마존 웹 서비스(AWS)

- 인프라 제공하는 역할을 하고, 웹 서비스를 해야하는 개발자들은 이 인프라를 임대하여 사용한다.

- 즉, 서버의 구매, 구축, 운영을 대행해주는 서비스이다.(웹 호스팅과 유사함)

- 탄력적인 인프라 운영(사용자의 폭주 시 서버의 성능, 갯수를 유동적으로 빠르게 변경이 가능하다)

- 사용한만큼 과금하는 방식이다.

  

EC2 

- Elastic Compute Cloud

- 쉽게말해 1대의 독립적인 컴퓨터를 임대한다고 생각하면 된다. 평범한 컴퓨터처럼 사용할 수 있다.

- 다만 물리적인 컴퓨터가 아니라 가상의 컴퓨터이다.

- Linux, Window 운영체제 제공한다.

- 웹서버 또는 애플리케이션 서버로 사용된다.


S3

- Simple Storage Service

- 파일 서버라고 할 수 있다.(이미지나 동영상을 갖고 있다가 제공)

- EC2에도 할 수 있지만, S3의 경우 특정 변경없이 무제한 저장이 가능하기 때문에 주로 사용된다.

- 스케일은 아마존 인프라가 담당하기때문에 편리하다.

- 1바이트 ~ 5테라 바이트의 단일 파일을 저장하는 것이 가능하다.


RDS

- Relational Database Service

- MySQL, Oracle, MsSQL 등등이 존재한다.

- DB를 쉽게 운영할 수 있게해주는 서비스이다.

- 백업, 리플리케이션과 같은 것을 아마존 인프라가 자동으로 제공한다.


EDB

- Elastic Load Balancing

- EC2로 유입되는 트래픽을 여러대의 EC2로 분산하는 기능을 한다.

- 장애가 발생한 EC2를 감지해서 자동으로 배제하는 기능을 한다.

- Auto Scaling 기능을 이용해서 EC2를 자동으로 생성 및 삭제를 한다.


위와 같은 서비스들을 조합해서 웹 서비스를 만들면 되는것이다.

AWS를 제어하는 방법에는 세 가지가 존재한다.


첫 번째. AWS Management Console

두 번째. CLI

세 번째. SDK


(1)AWS Management Console

웹에서 접속하기 때문에 언제 어디서든 접속이 가능하며 다른 것들에 비해 쉽고 사용하기 편하다.

하지만, 일부 기능의 경우 CLI를 통해서만 제공되기떄문에 상호보완적인 관계라 할 수 있다.


(2)CLI

Command Line Interface의 약자로 명령어를 이용해서 서비스를 제어한다.

아이콘과 같은 GUI 환경이 컴퓨터 세계를 장악했지만, 코딩으로 해야하는 부분이 존재한다.


(3)SDK

Software Development Kit의 약자로 각 언어(Java, Python, PHP ..)별로 AWS를 프로그래밍으로 제어할 수 있는  API 묶음이다. 이를 이용해서 AWS 인프라를 제어할 수 있는 명령어라고 할 수 있다. 

Posted by sungho88
,

PuTTY을(를) 사용하여 Linux 인스턴스에 연결하려면 프라이빗 키에 대해 생성한 .ppk 파일이 필요하다. 


ppk파일 만드는 방법 


1. PuTTY을 실행한다.

2. [Category] 창에서 [Session]를 선택하고 다음 필드를 작성한다.


[Host Name] 상자에 user_name@public_dns_name을 입력한다. 

AMI에 적합한 사용자 이름을 지정해야 한다. 


예)

Amazon Linux AMI의 경우 사용자 이름은 ec2-user

RHEL5 AMI의 경우 사용자 이름은 root 또는 ec2-user 

Ubuntu AMI의 경우 사용자 이름은 ubuntu 

Fedora AMI의 경우 사용자 이름은 fedora 또는 ec2-user 

SUSE Linux의 경우 사용자 이름은 root 또는 ec2-user 


우툰부 서버를 생성한 나의 경우  ubuntu@public_dns_name

public_dns_name은 내 인스턴스 생성한 콘솔창에서 확인이 가능하다.

⑵ [Connection type] 아래에서 [SSH]를 선택해야 한다.

⑶ [Port]가 22인지 확인한다.

⑷ [Category] 창에서 [Connection], [SSH]를 차례로 열고, [Auth]를 선택한다. 


그리고 


1. [Browse]를 클릭.

2. 키 페어에 대해 생성한 .ppk 파일을 선택한 다음 [Open]을 클릭.

3. (선택 사항) 이 세션을 나중에 다시 시작하려는 경우 세션 정보를 나중에 사용할 수 있게 저장할 수 있다. [Category] 트리에서 [Session]을 선택하고 [Saved Sessions]에 세션 이름을 입력한 다음 [Save]를 클릭한다.



드디어 [Open]을 클릭하여 PuTTY를 접속하게 된다.

처음에 접속이 되기 전에 PuTTY에서 연결하려는 호스트를 신뢰할 수 있는지 묻는 보안 알림 대화 상자가 표시된다. 그냥 무시하고 예를 누르면 된다.



Welcome to Ubuntu  ....


정상적으로 접근한 것이다.이상으로 PUTTY를 이용해서 리눅스 우분투 서버에 접속하는 방법을 알았다.

Posted by sungho88
,

인스턴스를 시작한 후 인스턴스에 연결을 한 후에는 

바로 앞에 있는 컴퓨터를 사용하는 것처럼 인스턴스를 사용할 수 있습니다.


인스턴스를 처음 시작한 후, 연결할 수 있도록 인스턴스가 준비될 때까지 몇 분 정도 걸릴 수 있습니다. 인스턴스가 상태 확인을 통과했는지 확인하십시오. 

[Instances] 페이지의 [Status Checks] 열에서 이 정보를 볼 수 있습니다.


PuTTY을(를) 사용하여 Linux 인스턴스에 연결하려면 아래와 같은 조건이 만족되어 있어야 한다.


1. PuTTY가 설치되어 있어야 한다.

2. 인스턴스의 ID가 어디에 있는지 확인해놔야한다.

Amazon EC2 콘솔을 사용하여 인스턴스의 ID를 볼 수 있습니다([Instance ID] 열에서). describe-instances(AWS CLI) 또는 ec2-describe-instances(Amazon EC2 CLI) 명령을 사용할 수도 있습니다.


3. 인스턴스의 퍼블릭 DNS 이름을 확인해놔야한다.

Amazon EC2 콘솔을 사용하여 인스턴스의 퍼블릭 DNS를 볼 수 있다. [Public DNS] 열을 확인. 

이 열이 숨겨져 있는 경우 [Show/Hide] 아이콘을 클릭하고 [Public DNS]를 선택합니다. 


4. 프라이빗 키를 찾아놔야한다.

인스턴스를 시작할 때 지정한 키 페어에 대한 .pem 파일의 정규화된 경로가 필요합니다.


5. IP 주소에서 인스턴스로의 인바운드 SSH 트래픽 활성화

인스턴스와 연관된 보안 그룹이 IP 주소로부터 들어오는 SSH 트래픽을 허용하는지 확인하십시오. 자세한 내용은 인스턴스에 네트워크 액세스 권한 부여를 참조하십시오.




[PuTTYgen을 사용하여 프라이빗 키 변환]


PuTTY에서는 Amazon EC2에서 생성한 프라이빗 키 형식(.pem)을 기본적으로 지원하지 않는다. 

PuTTY에는 PuTTYgen이라는 도구가 있는데, 우리가 필요한 PuTTY 형식(.ppk)으로 변환할 수 있다. 

PuTTY를 사용하여 인스턴스에 연결하기 전에 프라이빗 키를 이 형식(.ppk)으로 변환해야한다. 


PUTTY 공식 홈페이지



개인 키를 변환하는 방법은 다음과 같다.


1. PuTTYgen을 시작한다.


2. [Type of key to generate]에서 [SSH-2 RSA]를 선택한다.




3. [Load]를 클릭한다. 기본적으로 PuTTYgen에는 확장명이 .ppk인 파일만 표시된다. 

   따라서, .pem 파일을 찾으려면 모든 유형의 파일을 표시하는 옵션을 선택한다.



4. 인스턴스를 시직할 때 지정한 키 페어에 대한 .pem 파일을 선택한 다음 [Open]을 클릭한다. 

[OK]를 클릭하여 확인 대화 상자를 닫는다. 무사히 성공했다면 아래와 같은 창이 뜬다. 그냥 닫아라.


 



5. [Save private key]를 클릭하여 PuTTY에서 사용할 수 있는 형식으로 키를 저장한다. 

   PuTTYgen에서 암호 없이 키 저장에 대한 경고가 표시된다. 여기서는 예를 클릭하고 무시한다.



6. 키 페어에 사용된 키에 대해 동일한 이름을 지정한다(예: my-key-pair). 그리고 자동으로 .ppk 형식의 파일로 추가가 된다. 즉, .pem과 .ppk 두 개의 파일이 존재하게 되는 것이다.

그리고 putty에서는 ppk를 사용하게 된다.


이제 개인 키가 PuTTY에 사용하기에 올바른 형식으로 되어 있으므로 

PuTTY의 SSH 클라이언트를 사용하여 인스턴스에 연결할 수 있다.


본격적인 연결은 ...곧










Posted by sungho88
,

EC2 = Elastic Compute Cloud의 약자.

아마존 웹 서비스(AWS)에서 심장이라고 할 정도로 중요도가 큰 핵심 서비스이다.

한 대의 컴퓨터를 EC2를 통해서 '임대한다'고 할 수 있다. 

다만, 실존하는 것이 아니라 아마존에서 만들어놓은 거대한 인프라 위에 가상으로 컴퓨터가 

만들어지는 것이다.(클라우드 컴퓨팅의 개념)

클릭 몇 번만에 생성 및 삭제가 가능하다.(유연하게 다룰 수 있다) Elastic라는 뜻이 "유연하다"


- ,EC2를 사용해서 할수 있는 가장 대표적인 일은 


1. 아마존 EC2를 통해 인스턴스(=한 대의 컴퓨터를 뜻하는 단위)를 생성하고,

2. 인스턴스를 활성화(running)시킨 뒤,

3. SSH로 putty등을 이용하여 접속을 한 뒤,

4. 웹 서버 설치하고 그 웹 서버를 통해서 사용자가 요청하는 웹페이지, 이미지, 동영상 등을 제공하는 일.


[인스턴스 생성]


인스턴스란 가상의 컴퓨터 1대를 의미한다.




아마존의 핵심 서비스인만큼 맨 위에, 맨 처음에 EC2가 뜬다.

참고로 위 화면은  AWS 개발자 콘솔로 불리며 모든 AWS 서비스들을 관리할 수 있는 화면이다.

회원가입을 하고 난 뒤, 다음과 같은 화면이 메인페이지가 된다.


1. 위에서 EC2를 클릭하고 들어가면.



위와 같이 나온다. 만든게 없으므로 아무것도 안나올것이다.

위 네모. Launch instance를 클릭한다.


2. OS를 선택하라는 화면이 나온다. 난 우분투를 선택한다. Windows OS는 대부분 유료이므로 주의! 




3. 프리를 사용할 것이므로 기본적으로 선택된 것을 확인 후 Next




4. 만들기 전 컴퓨터의 성능 조정... 뭔 소리인지 모르므로 건들지 말고 Next  



5. 저장 공간을 설정하는 부분. 



Volume Type에서 SSD는 Magnetic보다 추가 요금이 발생 할 수 있다고 한다.. 

Magnetic을 바꿔도 되지만 테스트이므로 그냥 SSD로~


 

6. 내가 만들 클라우딩 컴퓨터의 이름을 설정한다. 본인 마음대로~




7. 방화벽을 설정하는 부분. 

기본적으로 SSH 포트번호인 22가 열려있으며, 
웹 서버 구축을 하기 위해서는 Add Rule버튼을 눌러서 HTTP 80포트도 추가해준다.



여기까지 하면 NExt 버튼이 아니라 


이렇게 바뀐다. 다시 한번 클릭


그러면 리뷰. 즉, 여태까지 지정해줬던 성능과. 환경세팅들이 정리되어 보여준다.

맞다면 드디어 Launch 버튼을 누를 수 있다.



키를 만들어야한다. Create a new key pair 로 변경후 키 이름을 아래에 적고 다운로드 키 페어 클릭~

다운로드에 저장된다~

그다음에 Launch를 눌러서 정말 진짜로 드디어 마침내 서버를 생성할 수 있었다.



만들어졌다~

다음엔 

이제 접속을 해봐야하므로 PUTTY를 이용하는 방법을 찾아보도록 하겠다.

Posted by sungho88
,

아마존 웹 서비스(Amazon Web Service)는 줄여서 AWS라고 부른다.

AWS를 사용하기 위해서는 당연히 먼저 가입을 해야한다. 가입하려면 아래 사이트로 접속을 하면 된다. 


 https://aws.amazon.com/ko/


1. 가입 또는 로그인을 클릭한다.



AWS는 기업용 회사 즉, 결제와 관련된 사이트이기 때문에 일반적인 회원가입과는 차원이 다르다.

즉, 보안과 개인정보가 까다롭다.




 


다음과 같이 4가지 단계.


1. 연락처 정보

- 이름

- 주소(나라/시/동/우편번호까지..)

- 핸드폰번호


2. 결제 정보

- AWS는 돈이 나갈 수 있는 경로(신용카드)를 반드시 제공해야 한다.  

- 또는 해외에서 사용할 수 있는 MasterCard 또는 VISA가 쓰여진 카드가 등록 가능하다. 

( 유효기간 및 카드번호까지 입력해야한다)


3. ID 확인

- 핸드폰 번호를 다시 한번 입력한다. 확인 버튼을 누르면 전화가 걸려온다. 미국/캐나다에서..;;

- 그 순간 PC 화면에 PIN 번호가 떴다. 휴대폰에 인증하라고 한다. 요금 나올까봐 급하게 입력했다.

- 그 순간 PC 화면에 인증완료라는 창이 떴다. 

- 드디어 무지 힘든 가입이 끝났다!!  고 생각했다.


4. 계획지원

- 어떻게 컨설팅을 해줄까? 이말이다.

- 개발자모드, 비즈니스 모드 등이 있다. 문제 발생 시 컨설팅 및 지원 해주겠다. 그러니까 돈을 내거라.  

- 무료로 사용할거다 하는 사람은 그냥 기본에 체크!!

(아래 캡처화면)


 

 


5. 확인

- 끝났는줄 알았는데 메일을 보냈다고 또 인증을 하란다.

- 메일 접속 후 링크를 타고 다시 돌아오면 마침내 진짜 정말로 끝!!!


참고로 AWS 계정에 로그인하는데 필요한 비밀번호는 최대한 어렵게하는것을 추천한다.

이 사이트에서는 실수를 하게 되거나 또는 해킹을 당하게되면 막대한 금액이 청구될 수 있기 때문이다.

(수천대의 서버를 간단히 만들 수 있음)

또한 이 계정으로 접속하는 PC 역시 바이러스가 있으면 안된다. 최대한 안 깔려있는 깨끗한 컴퓨터로 접속을 하는것을 추천한다.

Posted by sungho88
,

[분할 정복 알고리즘(Divide and conquer algorithm)]


-  그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법(알고리즘)

-  즉, 한번에 해결하기 어려운 문제를 작은 단위의 문제들로 나누어 해결하는 방법이다.

-  정복(conquer)이 들어가는 이유는 재밌게도 나폴레옹과 관련이 있다.1805년 12월 2일 아우스터리츠 

   전투에서 프랑스의 황제(皇帝) 나폴레옹은 숫자면에서 우세했던 연합군을 물리치기 위해서 나폴레옹은 

   연합군의 중앙으로 쳐들어가 그들의 병력을 둘로 갈라 놓았고, 둘로 나누어진 병력은 개별적으로는 

   나폴레옹의 군대보다 숫자가 적었기 때문에 전투는 나폴레옹의 승리로 끝나게 되었다. 분할정복법은 위와 

   같은 사례를 프로그램에 이용한 것이다.


분할정복법을 구현하기 위한 순서는 다음과 같다.
  1. 분할(Divide) : 분할이 가능한 경우, 큰 문제를 하나 이상의 작은 문제로 분할한다.
  2. 정복(Conquer) : 분할이 가능하다면 계속 분할한다. 분할이 불가능하다면 나눈 작은 문제를 각각 해결한다.
  3. 결합(Combine) : 정복된(해결된) 해답을 모아 큰 문제의 답이 되도록 결합(병합)한다.
분할 정복 알고리즘은 문제를 쪼개는 과정이 가장 핵심적인 기능이며 효율적인 분할을 하는 것이 중요하다.
문제 분할만 잘해도 그것을 해결(정복)한 뒤 병합하는 과정은 간단하기 때문이다. 하지만, 분할정복법의 경우 
대다수가 재귀호출을 통해 구현되기 때문에 그만큼 많은 부담을 갖게 된다.
 

[분할 정복 알고리즘을 이용한 대표적인 알고리즘]

  • 퀵 정렬 (Quick Sort)
  • 병합 정렬 (Merge Sort)
  • 피보나치 수열 (Fibonacci Sequence)
  • 거듭 제곱 (Exponentiation)
  • 고속 푸리에 변환 (Fast Fourier Transform, FFT)

참고 블로그 

http://debugnote.com/algorithm/2015/07/06/quick-sort/



Posted by sungho88
,

선택 정렬은 오히려 버블 정렬보다도 쉽고 간단한 알고리즘이다. 

1. 주어진 리스트 중에 최소값을 찾은 후, 

2. 그 값을 리스트 맨 앞에 위치한 값과 교체(교환)한다.

3. 맨 처음 위치를 제외하고(이미 최소값이므로) 나머지 리스트를 같은 방법으로 반복한다.

딱, 세가지만 생각하면 된다. 



① 주어진 리스트 중에 최소값을 찾는 방법

위와같은 배열a[]가 존재할 때, 리스트 중 가장 작은 요소의 인덱스값을 구하기 위해서는 어떻게 할까?

int[] arr = {3,5,1,7,9,2,6};

int min_index = 0;

for (int i = 1; i < arr.length; i++) {

if(arr[min_index]>arr[i]) min_index = i;

System.out.println(arr[min_index] +" "+arr[i]);

}

요런식으로 하면 인덱스 0(값6)이후의 값부터 비교해가며 최소값의 인덱스를 찾을 수 있다. 

min_index = 2일 것이다.


② 리스트 맨 앞 요소와 위치를 교환한다.

for (int i = 1; i < arr.length; i++) {

if(arr[min_index]>arr[i]) min_index = i;

System.out.println(arr[min_index] +" "+arr[i]);

//아래 부분이 추가됨.

temp = arr[0];

arr[0] = arr[min_index];

arr[min_index]= temp;

}


이러면 될까? 되긴 한다. 그렇지만 어떻게 나올까? 

1 5 3 7 9 2 6 

뭐야 이게? 뭐가 되긴 됐는데? 그렇다. 최소값 1이 맨 앞 3과 자리가 바꼈다....

근데. ㅡ_ㅡ;;;다른건 움직이지 않았다. 위 그림에서 보면 두번째 그림과 같다는 것을 알수 있다.

그래서 우리는 반복을 해주어 계속 정렬을 해야한다.


③ 리스트 맨 앞 요소를 제외한 리스트 전체를 위 과정을 반복실행 한다.

맨 앞 즉, 0번째 인덱스 정렬은. 끝났다. 1번째 인덱스부터 새롭게 시작한다. 그러면

min_index값은 어떻게 될까? 당연히.. 1부터다. 

즉, (배열의 크기-1)만큼 돌려야 모든 요소들이 비교를 해가면서 정렬이 완성될 것이다.(그림 참조)

for (int i = 0; i < arr.length; i++) {

for (int j = i+1; j < arr.length; j++) {

if(arr[min_index]>arr[j]) min_index = j;

temp = arr[i];

arr[i] = arr[min_index];

arr[min_index]= temp;

}

}


일단, 에 나오는 for문을 감싸는 for문을 하나 더 삽입해서 이중for문이 되도록 해야 한다.

기존에 i변수를 j로 바꾸고 0번째 인덱스를 의미하는 0을 지우고 j를 넣는다.

왜냐하면 j가 하나하나 증가되면서 값을 저장하기 때문이다. 따라서,다음과 같이 정렬이 된다.

1 2 3 5 6 7 9 




선택 정렬의 성능평가 

버블 정렬과 성능상 큰 차이가 없다. 선택 정렬의 빅-오 역시 O(n^2) 

이 둘을 비교하는 것은 도토리 키재기..라고 할 수 있다.


Posted by sungho88
,

버블 정렬은 정렬하면 가장 먼저 떠오르는 간단한 정렬방법이다.

버블 정렬은 이름 그대로 앞에서부터 순서대로 비교하고 교환하는 과정이 마치 거품이 일어나는 모습에

비유되어 버블 정렬이라는 이름이 지어진 것이다.

그만큼 이해하기도, 구현하기도 쉽고 간단하다. 물론 구현이 쉬운만큼 성능적으로는 매우 떨어진다.

만약, 오름차순으로 정렬을 하려고 한다. 아래와 같은  배열 6 1 2 3 4 5이 있다면, 

위 그림에서 보듯, 버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.

두 개의 데이터를 비교하여, 정렬순서상 위치가 바뀌어야 할 경우에는 두 데이터의 위치를 바꿔나간다.

즉, 정렬의 우선순위가 가장 낮은, 제일 큰 값을 맨 뒤로 보내는 것을 반복하는게 바로 이 정렬의 핵심이다.

위 사진의 경우에는 6만 보내면 해결됐지만, 만약 6 5 4 3 2 1이라면 모든 값을 비교 후 이동함으로 최악이다.

먼저, 하나의 요소와 그 뒷 요소를 비교해서 앞이 뒤보다 크다면 앞.뒤의 위치를 변경하는 코드를 구현하면,

if( arr[j] > arr[j+1){ tmp = arr[j]; arr[i] = arr[j+1]; arr[j+1] = tmp; }

import java.util.Scanner;

public class Main {
 public static void main(String[] args) {

  int bubbleSort[] = {6,3,4,5,2,1};

  for (int i = 0; i < bubbleSort.length; i++) {
   System.out.print (bubbleSort[i]+" ");
  }  // 6 3 4 5 2 1 출력
  

BubbleSort(bubbleSort,bubbleSort.length); 


  System.out.println();
  for (int i = 0; i < bubbleSort.length; i++) {
   System.out.print (bubbleSort[i]+" ");
  }  // 1 2 3 4 5 6 출력
 }

 private static void BubbleSort(int[] bubbleSort, int length) {
  
  int temp;
  
  for (int i = 0; i < length-1; i++) {
   for (int j = 0; j < (length-i)-1; j++) {
    if(bubbleSort[j] > bubbleSort[j+1]){
         temp = bubbleSort[j];
         bubbleSort[j] = bubbleSort[j+1];
         bubbleSort[j+1] = temp;
    }
   }
  }
 }
}

위에서 BubbleSort()메소드가 바로 버블 정렬 알고리즘을 구현한 코드이다.

++추가적으로 다른 방법으로 버블 정렬을 구현하였다. 이것이 더욱 간단하지 않을까싶다.

import java.util.Scanner;


public class Main {


public static void main(String[] args) {


Scanner scanner = new Scanner(System.in);

int num1 = scanner.nextInt();

int[] arr = new int[num1];

int flag = 0, temp = 0;

for (int i = 0; i < arr.length; i++) {

arr[i] = scanner.nextInt();

}


for (int i = num1 - 2; i >= 0; i--) {

for (int j = 0; j <= i; j++) {

if (arr[j] > arr[j + 1]) {

temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

}

}

}

for (int j = 0; j < arr.length; j++) {

System.out.print(arr[j]);

}

}

}

입력 :

7

2 5 11 24 8 1 9

출력 :

1 2 5 8 9 11 24 


성능

정렬 알고리즘의 성능은 두 가지를 근거로 판단한다.  

1. 비교 횟수  : 두 데이터간의 비교연산의 횟수

2. 이동 횟수  : 위치의 변경을 위한 데이터의 이동 횟수.

최선의 경우는 배열이 이미 완벽하게 정렬되어 있는 상태 - 데이터의 이동이 한 번도 일어나지 않음

최악의 경우에는 내림차순.. 즉, 역순으로 정렬되어 있을 경우 비교횟수 = 이동횟수.. 

버블 정렬은 빅오 오브 n^2 (= O(n^2))이므로 매우 좋지 않은, 실제로 사용하지 부담스러운 성능을 보인다.

하지만, 코드가 간단하게 구현할 수 있기 때문에 간단한 배열의 정렬의 경우에는 이 방식을 사용해도 무방하다..

이상으로 버블 정렬에 대한 정리를 마치도록 하겠다. 다음번에는 선택 정렬!!!

 

Posted by sungho88
,

1. 배열(Array)

[배열(Array)이란 무엇인가]

- 거의 모든 언어에서 지원하는 문법이다.

- 배열은 가장 기본적인 자료구조다. 즉, 앞으로 배울 많은 자료구조들이 배열을 부품으로 사용된다.

- 데이터가 적다면 물론 일반 변수를 사용하여 값을 저장하여 사용하면 문제없다.

- 하지만, 데이터가 많아질수록 그룹 관리에 대한 필요성이 생긴다. 이럴 때 배열을 사용하게 된다.

- 즉, 배열은 여러 데이터를 하나의 이름으로 그룹핑해서 관리하기 위한 목적으로 사용하는 자료구조이다.

- element = value + index (value = 저장된 실제 데이터, index는 데이터를 저장 및 조회를 위한 위치 식별자(Index))

- 배열은 반복문과 조합하면 훨씬 더 효율적으로 사용할 수 있다. 

 


 

[배열의 생성 방법]

int[] number = new int[5];

number[0] = 10;

number[1] = 20;

number[2] = 30;

number[3] = 40;

number[4] = 50;

위 코드가 바로 배열을 생성하고, 인덱스에 값을 대입하는 코드이다. 또한 더 간단하게 생성을 하고 싶다면 

int[] number2 = {10,20,30,40,50};

또는 int[] number3 = new int[]{10,20,30,40,50};

모두 같은 의미이다.


[배열 안에 저장된 값을 가져오는 방법(하나의 데이터를 가져올때)]

이를 위해서 인덱스(Index)가 필요하다. 

number[0];   을 호출하면 0번째 인덱스의 값(value)를 가져오게 된다


[배열 안에 저장된 값을 가져오는 방법(하나의 데이터를 가져올때)]

이를 위해서 반복문이 필요하다. while 또는 for문을 통해 0부터 0!부!터! 배열의 크기만큼(number.length) 반복한다.

[배열 안에 저장된 길이를 구하는 방법]

number.length를 작성하여 number라는 배열에 저장된 데이터 길이를 가져올 수 있다. 

[배열의 장점]

작고 가볍다. 또한 단순하다. 그래서 다른 자료구조에서 배열을 부품으로 사용하게 될 것이다.

[배열의 단점 --> 이 단점때문에 ArrayList를 사용한다]

크기가 정해져있기 때문에 데이터 저장이 크기를 초과되면 자동으로 늘어나지 않고 에러를 발생한다.
또한 기능이 없어 단순하다.


2. 리스트(List)

리스트의 특징1. 데이터가 순서대로 저장된다.            2. 중복 데이터를 허용된다.

배열과 리스트의 차이점
(삽입 시)
1. 배열 중간에 데이터를 삽입 시에 덮어쓰기가 되기 때문에 기존의 데이터값은 사라진다!! 
2. 리스트 중간에 데이터를 삽입 시 해당 인덱스 이후 데이터들이 한칸씩 뒤로 이동 후 그 위치에 값 저장                   (데이터 손실이 없다)
(삭제 시)
1. 배열내에 중간에 데이터를 삭제 시 값(value)은 지워지지만 element는 그대로 남아있다(이 경우 null이 나옴..) 
2. 리스트에서 중간에 데이터를 삽입 시 해당 인덱스 삭제 후 데이터들이 한칸씩 앞로 이동하여 빈 공간을 메꿈       (데이터 손실이 없다)
 
즉, 배열은 빈공간이 생길 수 있지만, 리스트는 빈틈(빈공간)을 허용하지 않는다.  

리스트의 기능
- 처음, 끝, 중간에 엘리먼트를 추가/삭제하는 기능
- 리스트에 데이터가 있는지를 체크하는 기능
C언어의 경우 리스트가 없어서 구현해야 하지만, 최근의 언어는 리스트를 기본적으로 지원한다.  

리스트의 생성 방법
ArrayList number = new ArrayList();
number.add(10);
number.add(20);
number.add(30);
number.add(40);
number.add(50);

자바는 리스트와 배열을 모두 지원하며, 둘을 엄격히 구분하여 직접 적절히 선택하여 사용해야한다.
C언어의 경우는 배열만 있고, 리스트는 직접 구현하거나 남의 구현한 리스트를 사용해야한다.
반면, 파이썬. PHP의 경우는 배열과 리스트를그냥 동일한 것으로 간주하여 사용한다. 즉, 리스트를 몰라도 배열을   쓰면 리스트 기능도 묻혀서 사용된다.

자바는 리스트를 두 가지 지원한다. 똑같은 사용방법(메소드) 가지고 있다.

ArrayList의 경우 추가/삭제시 느리지만, 인덱스를 알고 있다면 매우 빠르게 조회할 수 있다.
LinkedList의 경우 추가/삭제 시 빠르지만, 인덱스를 통해 조회하는 속도는 상당히 느리다.
이런 차이를 'Trade-off가 존재한다'
즉, 자기가 구현하고자 하는 것이 무엇이냐에 따라서 배열을쓸지, ArrayList를 쓸지, LinkedList를 쓸지 개발자의 선택에 달렸다....자바는 파이썬. PHP들보다 개발자가 알고 있어야 할것이 더욱더 많지만, 자유도 역시 매우 높다고 할 수 있다. 다시한번 말하지만, 자료구조는 언어마다 다르다. 

 

추가/ 삭제               

 인덱스 조회

 ArrayList

 느림  

빠름 

 LinkedList

빠름 

느림 


리스트 = 완제품 / 배열 = 부품 --> 대비되는 사이가 아니라, 서로서로 비슷비슷 사용된다고 하 수 있다.
자바에서 ArrayList를 사용하는 방법
자바의 경우 컬렉션 프레임워크이라는 곳 안에 ArrayList 자료구조를 기본적으로 내장하고 있기때문에, C언어와 같이 직접 구현을 하지 않아도 된다. 그렇기 때문에 ArrayList 사용방법을 익힌 후 어떻게 구현되는가를 살펴보도록 한다.

[ArrayList 사용방법 - 생성(Create)]
ArrayList<Integer> number = new ArrayList<>();

[ArrayList 사용방법 - 추가(Insert)]

number.add(10);

number.add(20);

number.add(30);

number.add(10);

//ArrayList안에 데이터를 차례대로 저장

또는

number.add(1,10);

//ArrayList안에 인덱스1 위치에 데이터를 끼워서 저장(그 이후 값들은 뒤로 한 칸씩 밀려)



[ArrayList 사용방법 - 삭제(Remove)]

number.remove(2,10);


[ArrayList 사용방법 - 가져오기(Get)]

number.get(2);


[ArrayList 사용방법 - 크기 가져오기(Size)]

number.size();

[ArrayList 사용방법 - 반복(Iteration)]

Iterator it = number.iterator();

// it변수에 iterator 인터페이스 객체를 리턴함.


hasNext() --> 리턴값이 boolean. 해당 엘리먼트 다음 엘리먼트가 존재하는가를 판별

 

Posted by sungho88
,