내일은 알고리즘

11. 안드로이드

리눅스 커널을 기반으로 동작하며 JAVA, Kotlin언어로 개발된 모바일 기기에 주로 사용되는 오픈소스 플랫폼 운영체제

12. SQL

13. SOAP

SOAP (Simple Object Access Protocol)

Http등의 프로토콜을 이용해 XML 기반의 메세지를 교환하는 프로토콜.

구성하는 주요 3요소 : Envelop - Header - Body

REST API로 대체 가능, 표준기술 기반이나 XML을 사용해 상대적으로 무거움.

14. SQL Injection

웹 페이지의 입력값으로 SQL명령어를 입력해 서버의 오동작을 유도하는 해킹방법.

로그인을 하거나 서버의 DB정보를 알아내거나 개인 정보를 추출함

대응법 : 입력값 검증, Prepared Statement(DBMS 드라이버에서 SQL문장을 미리 준비), 방화벽, 에러 출력 방지 등

15. 인터페이스

- 인터페이스 설계의 기본 원칙

직관성: 누구나 쉽게 이해하고 사용할 수 있어야 한다.
유효성: 사용자의 목적을 정확하게 달성하여야 한다.
학습성: 누구나 쉽게 배우고 익힐 수 있어야 한다.
유연성: 사용자의 요구사항을 최대한 수용하며, 오류를 최소화하여야 한다.

와이어프레임(Wireframe), 목업(Mockup), 스토리보드, 프로토타입(Prototype), 유스케이스(Usecase) 등으로 설계

16. 리눅스 chmod

리눅스 운영체제에서 파일에 대한 권한을 변경하는 chmod 명령어

$ chmod [권한] [파일]

- 각 권한은 읽기4, 쓰기2, 실행1 로 부여됨.

Ex) 읽기와 쓰기 권한이 있으면 4+2 = 6

- 순서대로 소유자 / 그룹 / 다른 사용자 를 의미함.

Ex) 소유자에게 읽기, 그룹에게 쓰기, 다른 사용자에게 실행 권한을 부여하려면  chmod 421

권한 확인은 ls 명령어로, 소유 그룹 변경은 chgrp 명령어로 

17. Linked Open Data

전세계 오픈된 정보를 하나로 묶는 방식
Linked data와 Open data의 합성어
URI(Uniform Resource Identifier)를 사용
RESTful 방식으로 볼 수 있으며, 링크 기능이 강조된 시멘틱 웹에 속하는 기술

18. 데이터베이스 설계

DB 설계 과정

요구사항 분석, 정의 -> 개념 설계 -> 논리 설계 -> 물리 설계 -> 데이터베이스 구현

19. JAVA

JAVA 상속(extends), super 문제

20. 형상관리

소프트웨어 개발 과정에서 산출물 등의 변경에 대비하기 위해 반드시 필요하다. 소프트웨어 리사이클 기간 동안 개발되는 제품의 무결성을 유지하고 소프트웨어의 식별, 편성 및 수정을 통제하는 프로세스를 제공한다. 실수를 최소화하고 생산성의 최대화가 궁극적인 목적이다. 관련 도구로는 CVS, SVN, Clear Case 등이 있다.

1. RPO RTO

Recovery Point Objective : 복구 시점 목표

시스템 장애, 업무 중단 시 백업수단을 통해 복구할 수 있는 기준점.

Recovery Time Objective : 복구 시간 목표

시스템 장애 발생, 업무 중단 시점으로부터 업무가 복구되어 정상가동 될 때까지의 시간.

RPO와 RTO 모두 시스템 장애 시간으로부터 가까울 수록 좋으나, 더 많은 비용 소모.

Business Impact Analysis : 업무 영향 분석

재난, 재해로부터 시스템 중단을 가정하여 중단 시간에 따른 영향도를 분석해 복구의 우선순위를 정하고 업무재개를 위해 필요한 자원을 도출해 냄.

2. 파이썬

파이썬 Set 자료구조 활용

3. AJAX

Asynchronous JavaScript And XML 

비동기적인 웹 어플리케이션 제작을 위해 사용하는 기법이다.

기존의 웹사이트들은 사용자가 어떤 요청(데이터)을 보내면 서버에서 그 요청을 가공해서 새로운 웹페이지를 응답했다. 

하지만 AJAX를 이용한 웹사이트에서는 웹페이지가 아닌 데이터만 비동기적으로 응답된다.

따라서 통신되는 코드와 데이터 양을 줄일수 있고 대기시간 없이 화면전환이 가능하다.

4. 애자일 방법론

소프트웨어 개발 방법론의 하나로, 처음부터 끝까지 계획을 수립하고 개발하는 폭포수(Waterfall) 방법론과는 달리 개발과 함께 즉시 피드백을 받아서 유동적으로 개발하는 방법.

특정한 방법을 말하기 보다는 방향성을 의미.

공정과 도구보다 개인과 상호작용을
포괄적인 문서보다 작동하는 소프트웨어를
계약 협상보다 고객과의 협력을
계획을 따르기보다 변화에 대응하기를

5. JAVA

JAVA 언어에서의 상속(extends) 활용

6. SQL

7. SQL-ROLLBACK

ROLLBACK : 트랜잭션이 실패했을때 작업을 취소하고 변경된 데이터를 이전 상태로 되돌리는 데이터 제어어

8. IPSec

네트워크 계층인 인터넷 프로토콜(IP)에서 '암호화', '인증', '키 관리'를 통해 보안성을 제공해 주는 표준화된 기술

보안에 취약한 구조를 가진 IP의 보안을 위하여 통신 세션의 각 IP패킷을 암호화하고 인증하는 IPS(Internet Protocol Suite)

IPv4에선 보안이 필요한 경우에만 선택적으로 사용하였지만 IPv6부턴 기본 스펙에 포함됨

9. 분석

정적 분석, 정적 테스트 (Code Inspection)

실행상의 장애 보다는 코드의 결함을 찾음. (코드 보안 취약점, 코딩 표준 위반, Dead Code, 일관성 깨짐 등)

Inspection : 공식적 검사

Peer Review : 프로젝트 과정에서 동료들이 상호교차 검토

WalkThrough : 개발 초기에 팀 내에서 수행하는 검토

동적 테스트 (Dynamic Testing)

소프트웨어의 코드를 직접 실행시키며 수행하는 테스트.

블랙박스 테스트 : 모듈 안은 보지 않고 입력과 출력을 관찰.

화이트박스 테스트 : 모듈 안의 작동을 직접 관찰, 논리적인 구조가 커버되도록 tc를 설계

10. 디자인패턴

11. OSI 7계층

네트워크 관련 지식인 OSI 7계층을 알고 있는지 묻는 문제입니다. 

헷갈릴만한 개념으로는 TCP/IP 5계층이 있습니다

(물리 - 데이터링크 - 네트워크 - 전송 - 응용)

12. LoC기법

Line of Code

코드 라인수의 낙관치, 기대치, 비관치로 예측치를 구하고 이것으로 프로그램 개발 시간을 예측하는 기법.

예측치 : (낙관치 + 4 * 기대치 + 비관치) / 6

예시 ) 프로그램의 예측된 라인수가 10000라인이고 프로그래머가 일 평균 100라인을 작성하고 프로그래머가 5명일때 개발 기간은 10000/(100*5) = 20일

13. 애플리케이션 성능측정

성능테스트(목적에 따른 구분)

성능테스트(방법에 따른 구분)

성능지표

14. 소프트웨어 모듈화

시스템의 계층을 나누고 기능별로 분해하여 성능, 유지보수성, 재사용성 등을 향상시키는 설계기법.

모듈화의 목표 -> 결합도를 낮추고 모듈 내 응집도를 높이는 것.

응집도 : 모듈의 내부기능이 얼마나 연관되어 있는가.

결합도 : 모듈간 얼마나 구분이 되어 있는가.

15. 데이터베이스 정규화 & 반정규화

정규화 : 데이터 베이스 테이블 간에 중복된 데이터를 허용하지 않아 무결성을 유지. 삽입,갱신 등에서 이상(Anomaly)을 방지하는 것.

반정규화 : 데이터베이스 성능향상을 위해 의도적으로 정규화에 어긋난 데이터 구조로 만드는 행위

테이블 합병, 중복칼럼 추가, 계산된 칼럼 추가 등등

16. 공유도(팬인 Fan-In)  제어도(팬아웃 Fan-Out)

공유도(팬인 Fan-In) : 나를 제어할 수 있는 다른 모듈의 갯수

제어도(팬아웃 Fan-Out) : 제어할 수 있는 다른 모듈의 갯수

17. C언어

c언어 반복문

18. C언어 CASE 문

case 조건문에서 break; 구문이 없을시의 특징을 묻는 문제입니다.

19. JAVA

java 반복문

20. SQL

기본적인 SQL 쿼리문을 이해하는지 묻는 문제이다. SQL 쿼리에 대해서는 따로 정리해서 올리도록 하겠습니다. 

신청한게 엊그제 같은데 벌써 정보처리기사 실기 시험이 2주 남았다.

작년엔 코로나로 불참 + 싸피로 바빠서 공부도 별로 하지 못하고 응시료만 날렸는데 백수인 지금은 2주 전부터 미리미리(?) 준비를 해서 한 번에 통과하겠다는 각오다.

문제를 직접 올리는건 저작권에 걸릴까봐 문제에서 묻는 개념 키워드를 설명하는 식으로 작성하겠다.

1. XML

웹 관련 프로그래밍을 해본 사람이면 AJAX라던지, XMLrequest 라던지 여러모로 익숙한 친구이다.

XML은 EXtensible Markup Language의 앞글자를 따서 붙인 이름으로 HTML의 부족한 부분을 보완하기 위해 만든 마크업 언어이다. 

마크업 언어는 데이터를 표현하기 위해 사용하는 문법으로 (프로그래밍 언어가 아니다!) 익숙한 HTML도 마크업 언어의 하나이다.단순히 HTML로 표현된 정적인 웹페이지의 위주이던 초창기 인터넷 환경에서 여러 데이터가 오갈 필요가 생기게 되는데 HTML의 경우엔 서로 다른 사이트 간에 데이터의 의미를 정확히 전달하기가 어려웠다.

예를들어 내가 학생명부를 보내려고 <p> 이름:김철수 학번:1234 , 이름:박철수 학번:1111 </p> 이런 데이터를 보냈을때 상대 사이트에선 학생 데이터가 온다는건 알아도 저 정보를 파싱하기 위한 파서가 따로 필요하다. 

또 내가 실수로 데이터 순서를 바꾸어 보낸다던지 할 경우 데이터가 뒤섞일 우려가 있다.

XML의 경우엔

<학생명부>
   <학생데이터>
        <이름>김철수</이름>
        <학번>1234</학번>
   </학생데이터>
   <학생데이터>
        <이름>박철수</이름>
        <학번>5678</학번>
   </학생데이터>
</학생명부>

이런 형태로 깊이와 태그명을 사용해서 데이터를 표현할 수 있다. 

지금은 이런 XML도 복잡하다고 JSON을 많이 사용하는데... 나중에 마크업언어들을 따로 정리해야겠다.

2. JSON

호랑이도 제 말 하면 온다더니 곧바로 JSON의 개념을 묻는 문제가 나왔다.

JSON은 속성-값 으로 이루어진 포맷이다.

아까 말했던 AJAX (Asynchronous JavaScript and XML)는 이름부터 XML이 들어가 있지만 요즘은 XML대신 JSON을 사용해 데이터를 전달한다. 

JSON을 사용해 아까 XML로 나타냈던 데이터를 표현하면 이런 느낌이다.

{
	"학생명부" : [{"이름":김철수, "학번":1234}, {"이름":박철수, "학번":5678}]
}

XML이던 JSON이던 프로그래머가 작성하기 나름이지만 JSON이 상당히 간료해 보이는걸 알 수 있다.

3. 릴리즈노트

릴리즈 노트는 소프트웨어 제품과 함께 배포되는 문서들을 말하며, 제품이 개발 중이거나 테스트 상태일 때 추가되기도 한다. 고객이 이미 사용 중인 제품의 경우 릴리즈 노트는 업데이트가 출시될 때 고객에게 전달된다. (위키피디아 설명)

그렇다고 한다. 흔히 우리가 사용하는 프로그램을 업데이트 했을때

어쩌구게임 ver 2022.378831 패치내역

1. 비쥬얼 업데이트를 적용함.
2. 김철수 캐릭터의 밸런스를 조정함.
3. 특정 상황에서 채팅이 쳐지지 않던 버그를 수정함.

이런 창을 보게 되는데 그런걸 생각하면 될 것 같다. 

릴리즈노트는 표준형식이 없이 프로그램의 개발 회사나 팀에 따라 다양하게 작성되는데, 보편적인 구성 항목은 이렇다고 한다.

머릿말: 문서 이름(예: 릴리스 노트), 제품 이름, 릴리스 번호, 출시일, 노트 날짜, 노트 버전 등.
개요: 다른 공식 문서가 없을 때 제품과 변경사항에 대한 간략한 개요.
목적: 버그 픽스와 새로운 기능을 포함한 이 릴리스의 새로운 사항의 나열과 더불어 릴리스 노트의 목적에 대한 간략한 개요.
문제 요약: 릴리스의 버그나 개선사항에 대한 짧은 설명.
재현 단계: 버그 발생을 재현하기 위한 절차.
해결책: 버그 수정을 위한 수정/개선사항의 짧은 설명.
최종 사용자 영향: 응용 프로그램의 최종 사용자에게 필요한 조치. 이 변경사항으로 인해 다른 기능이 영향을 받는지의 여부가 포함되는 것이 좋다.
지원 영향: 소프트웨어 관리의 일일 프로세스에 필요한 변경사항.
참고: 소프트웨어나 하드웨어의 설치, 업그레이드, 제품 문서화에 관한 참고사항. (문서화 업데이트 포함)
면책: 회사와 표준 제품 관련 메시지 (예: 프리웨어, 불법 복제 금지 등)
연락처: 지원 연락처 정보.

4. 살충제 패러독스

애플리케이션 테스트의 기본 원리 중, 살충제 패러독스의 의미를 묻는 문제이다.

살충제 패러독스는 이름 처럼 같은 테스트를 반복해서 실행할 시 프로그램의 장애, 버그를 찾을 수 없다는 개념을 의미한다.

예를 들어 우리가 어떤 길찾기 프로그램을 만들었다고 하자.

프로그램이 잘 작동하는지를 확인하기 위해 회사에서 근처의 편의점을 가는 경로를 찾아봤더니 오류가 발생했다!

열심히 오류를 고치고 다시 테스트 했더니 완벽하게 동작한다.

그 후 프로그램이 몇번의 업데이트를 거치고 다시 테스트의 시간이 되었다.

예전에 했던 테스트를 똑같이 반복해 근처의 편의점을 가는 경로를 검색했더니 잘 나온다. 와! 

그럼 이 프로그램은 버그가 없는걸까? 

우리가 이전의 테스트(살충제)를 통해 확인한 오류를 고쳤기 때문에 해당 버그는 사라졌지만, 다른 곳에는 어떤 버그가 남아있을지 모른다.

수천명이 동시접속하면 서버가 터질 수도 있고, 편의점 대신 병원을 검색하거나 PC가 아니라 모바일 환경에서 접속하면 버그가 발생할 수도 있다.

이렇듯 같은 방법의 테스트를 반복하면 오류를 찾을 수 없다는게 살충제 패러독스의 의미이다.

5. 데이터 마이닝

요 10년 사이에 핫해진 빅데이터 관련 용어이다. 

데이터 마이닝이란 "많은 데이터에서 데이터간의 관계를 찾아내어 유용하고 가치있는 정보를 추출해 내고 이를 의사결정에 이용하는 과정" 이라고 말할 수 있을것 같다.

참고로 데이터 마이닝과 데이터 크롤링, 웹 크롤링이 조금 혼동되는데 보통 데이터 마이닝은 모여진 데이터에서 의미를 찾는 과정. 데이터 크롤링은 그 데이터를 모으는 과정이라고 생각하면 될 것 같다.

6. 프로토콜

Protocol

컴퓨터들 간의 원활한 통신을 위해 지키기로 약속한 규약. 프로토콜에는 신호 처리법, 오류처리, 암호, 인증, 주소 등을 포함한다. 통신을 원하는 두 개체간에 무엇을 어떻게 언제 통신할 것인지 약속해 둔 규약이다.

우리가 네트워크에서 배운 TCP/IP 나 HTTP도 프로토콜이다.

프로토콜을 구성하는 세가지 요소는 이렇다.

-구문(Syntax)

   데이터의 형식(아날로그 or 디지털), 부호화(Unicode, ASCII), 신호크기를 정하는 구문

-의미(Semantics)

   전송제어 (동기화, 전송정지 및 재개, 완료, 재전송, 등등의 신호를 정함), 오류수정(데이터 무결성, 패리티비트, CRC)

-시간(Timing) :

   신호의 지속시간, 신호의 순서 등을 정하여 타이밍을 이룸

7. 해시함수

해시함수의 종류와 설명을 정확히 알고 있는지를 묻는 문제인데, 개인적으로 정말 싫어하는 유형이다.

중요한 해시함수들의 설명은 이렇다.

8. 스케쥴링

운영체제 전공 수업때 배운 스케쥴링 문제이다.

9. 데이터베이스 트랜잭션

트랜잭션 Tx, Transaction의 특성

10. 서비스 거부 공격

DoS (Denial of Service)

시스템이 정상적인 서비스를 할 수 없도록 하는 공격을 의미한다.

DDoS는 다수의 좀비 PC을 이용해 정상적인 요청을 막대하게 보내는 방식으로 공격하지만 DoS는 서비스의 취약점을 노리고 보내는 공격이다.

카운팅 소~트 밤 하늘의 퍼얼~ 

오늘은 여섯 번째 정렬 알고리즘이자, 시간 복잡도가 O(N+K)인 특이한 정렬 알고리즘.
계수정렬(Counting sort)에 대해 알아보겠습니다.

1. 데이터의 범위를 전부 표현가능한 자료구조(배열,리스트 whatever)를 준비한다.
2. 데이터를 한 번 순회하면서 각 값의 갯수를 세어준다.
3. 알게 된 갯수만큼 데이터를 저장하거나 출력하면 정렬이 끝!

기존의 정렬들과는 달리 딱 한 번만 데이터를 순회하면 정렬이 완료됩니다.

그림과 함께 정렬의 순서를 확인 해보겠습니다.

1~5 범위의 데이터가 무작위로 준비되어 있습니다.

데이터를 전부 표현 가능한 5 사이즈의 배열을 준비했습니다.

정렬되지 않은 첫 데이터의 값은 3입니다.

값을 셀 배열에서 3의 값을 의미하는 위치의 값을 1 증가시킵니다.

두번째 데이터의 값은 2입니다.

마찬가지로 배열에서 2의 위치의 값을 1 증가시킵니다.

이런 방법으로 데이터를 한 번 순회하면...

위 처럼 정렬되지 않은 데이터가 몇개의 값으로 이루어진지 알 수 있습니다.

이제 값을 센 결과를 통해 정렬된 데이터를 만들어 봅시다.

1의 값을 가진 데이터가 2개이니 2개를 출력(혹은 정렬 후의 배열에 저장)

2의 값을 가진 데이터의 갯수도 2개이니 똑같이 출력

같은 작업을 끝까지 해주면 짠! 하고 정렬된 데이터를 얻게 됩니다.

이해하기도 쉽고 구현도 쉽고 시간복잡도까지 빠른 정렬 알고리즘입니다.

하지만 계수정렬은 특정 상황에서만 유용하게 쓰입니다.

시간복잡도 O(N+K)에서 알 수 있듯, K값인 데이터의 범위에 따라 그 효율성이 크게 달라지기 때문입니다.

예를 들어, 100명이 100점 만점의 시험을 본 점수결과 데이터를 정렬한다고 해봅시다.

K값은 100이고 이 데이터를 정렬하는데엔 대략 200번의 연산이면 충분할겁니다.

반면 100명의 연봉 데이터를 정렬한다고 해봅시다.

100명중에 능력있는 프로그래머가 한 명 있어서 최댓값이 1억이라고 생각해보면 K값은 1억이 되고 이 데이터를 정렬하는데엔 약 1억번의 연산이 필요합니다!

같은 100개의 데이터를 정렬하는데 효율성이 엄청나게 차이가 나죠.

따라서 계수정렬은 특정 상황에서만 유용하게 쓸 수 있는 정렬알고리즘입니다. 

아래는 간단하게 계수정렬을 구현한 JAVA코드 입니다.

디버깅 해보시며 정렬의 흐름을 따라해보시길 바랍니다.

import java.util.Arrays;
import java.util.Random;

public class sort_06_counting {
	static int size = 50;
	static int bound = 10;
	static int count = 0;
	// 데이터의 갯수와 범위 설정

	public static void main(String[] args) {
		int[] data = new int[size];
		Random random = new Random();

		for (int i = 0; i < size; i++) {
			data[i] = random.nextInt(bound);
		}
		// 랜덤 값 넣어주기

		System.out.println(Arrays.toString(data));
		// 랜덤하게 들어간 데이터 확인

		//////////////// 계수정렬 구현코드는 하단으로 /////////////////
		countingSort(data, bound);
		//////////////////////////////////////////////////////

		System.out.println(Arrays.toString(data));
		System.out.println("비교횟수 : " + count);
	}

	private static void countingSort(int[] data, int bound) {
		int[] countingsort = new int[bound + 1];
		int idx = 0;

		for (int i = 0; i < data.length; i++) {
			countingsort[data[i]]++;
			count++;
		}
		
		for (int i = 0; i < bound; i++) {
			count++;
			for(int j = 0; j < countingsort[i]; j++) {
				data[idx++] = i;
			}
		}

	}
}

오랜만에 다섯번째 정렬 알고리즘이자, 시간 복잡도가 O(NlogN)인 정렬 알고리즘.
퀵 정렬에 대해 알아보겠습니다.

1. 데이터 중에서 피봇(pivot)을 뽑습니다.
2. 피봇을 제외한 데이터들을 피봇보다 작은 데이터, 큰 데이터로 분류합니다.
3. 이렇게 두 그룹으로 나뉜 데이터에서 같은 동작을 반복하여 정렬 될 때까지 실행합니다.

퀵 정렬은 설명만 들으면 이해가 되지만 어떻게 이 정렬이 NlogN시간에 정렬이 되는지,

그리고 코드로는 어떻게 작성할지 생각이 막막한 정렬법입니다.

그림과 함께 천천히 알아보도록 하겠습니다.

퀵정렬을 위해 피봇을 정해야합니다.

이번엔 데이터의 정렬되지 않은 그룹의 가장 앞 수를 피봇으로 정해보도록 하겠습니다.

피봇을 정하고 데이터를 순회하면서 피봇보다 작은 수와 큰 수로 나누어줍니다.

계속해서 그룹을 배치해주면...

한 번의 순회가 끝나면, 피봇은 자신의 정렬된 위치에 자리하게 됩니다.

예시 데이터에서 다섯번째로 작은 5는 자신 앞에 위치하는 자기보다 작은 수가 4개임이 당연하므로 자연스럽게 다섯번째 위치에 자리잡게 됩니다.

다음은 피봇으로 나누어진 그룹의 한 쪽에서 다시 한 번 피봇을 정해줍니다.

처음에 약속한대로 가장 앞의 데이터 3을 피봇으로 정합니다.

피봇보다 작은지 큰지에 따라 재배치하면 이런 모양이 됩니다.

5의 경우처럼, 이 그룹에서 세번째에 위치해야하는 3은 자신의 정렬된 위치에 도달한 것을 알 수 있습니다.

5보다 큰 쪽의 그룹도 피봇을 정하고 똑같이 재배치합니다.

두번째 순회가 끝났습니다.

같은 방식으로 1을 피봇으로 잡으면 현 상태 그대로 머물게 되고, 이후 2,4,6,8 하나씩이 남게 된 그룹은 그대로 정렬된 상태가 됩니다.

보시다시피 피봇을 한 번 정할때마다 데이터가 두개로 나뉘고, 전체 데이터를 한 번 순회하면 2^N-1개의 데이터가 정렬되면서 logN번의 순회를 마치면 정렬이 완료되게 됩니다.

한 번 순회할때 데이터를 N개씩 비교하므로 시간복잡도는 NlogN이 됩니다.

(실제로는 매 순회마다 일부 데이터가 완벽히 정렬되므로 비교하는 데이터는 N개보다 적습니다.)

퀵정렬이라는 이름처럼 빠르게 정렬이 완료되는것이죠.

하지만 이런 퀵 정렬에도 예외적인 상황이 있습니다.

이렇게 역순으로 정렬된 데이터를 퀵정렬한다고 생각해 봅시다.

피봇을 가장 앞의 수로 정하고, 순회해서 작은 수의 그룹을 만들었더니... 

마치 버블정렬을 돌렸을 때처럼 피봇을 제외한 모든 수가 되었습니다!

같은 방식으로 피봇을 또 뽑게 되면 또다시 하나의 데이터만 정렬되게 되고, N-1번의 순회가 필요합니다.

그럼 피봇을 다른 방식으로 뽑는다면 어떨까요?

가장 앞의 수 대신 중앙의 수를 골라 피봇으로 선택했습니다.

비교 후엔 우리가 아까 테스트했던 퀵 정렬 처럼 두개의 그룹으로 나뉘며 정렬이 진행되는것을 볼 수 있습니다.

라이브러리에 구현되어 있는 퀵 소트는 이렇듯 피봇이 불리하게 뽑히는 것을 막기 위해 무작위 수로 피봇을 정하는 식으로 예외적인 상황을 회피한다고 합니다.

이렇게 퀵정렬을 통한 정렬이 완료되었습니다!

이건 이해를 돕기 위한 예시일 뿐 실제 코드와 프로그램에선 재귀적으로 파고들어 가며 정렬이 진행되기 때문에 동작 흐름은 다릅니다.

아래는 JAVA로 구현한 간단한 퀻정렬 코드와 테스트입니다!

이것저것 바꿔보고 디버깅하면서 흐름이 이해되시길 바랍니다.

import java.util.Arrays;
import java.util.Random;

public class sort_05_quick {
	static int size = 10;
	static int bound = 1000;
	static int count = 0;
	// 데이터의 갯수와 범위 설정

	public static void main(String[] args) {
		int[] data = new int[size];
		Random random = new Random();

		for (int i = 0; i < size; i++) {
			data[i] = random.nextInt(bound);
		}
		// 랜덤 값 넣어주기

		System.out.println(Arrays.toString(data));
		// 랜덤하게 들어간 데이터 확인

		//////////////// 퀵정렬 구현코드는 하단으로 /////////////////
		quickSort(data, 0, data.length - 1);
		//////////////////////////////////////////////////////

		System.out.println(Arrays.toString(data));
		System.out.println("비교횟수 : " + count);
	}

	private static void quickSort(int[] data, int left, int right) {

		if (left < right) {
			int i = left;
			int j = right;
			int pivot = data[(left + right) / 2];

			while (i < j) {
				while (j >= 0 && data[j] > pivot) {
					j--;
				}
				while (i < j && data[i] < pivot) {
					i++;
				}

				int tmp = data[i];
				data[i] = data[j];
				data[j] = tmp;
				count++;
			}
			// 정렬 과정
			quickSort(data, left, i - 1);
			quickSort(data, i + 1, right);
		}

	}
}

2월 말에 누나랑 같이 목감기 기운이 있다가 누나가 먼저 확진 받고, 저도 확진 받았습니다.

확진받은 전 후로 3,4일 정도는 열,몸살,기침,콧물,가래... 

기침이 너무 심해서 가습기를 틀고 자도 두세시간마다 기침때문에 깨면서 버텼고 격리 해제 이후에도 일주일정도 기침으로 고생하다가 겨우 회복했습니다.

한창 취준 시즌에 코로나에 걸려버려서... 영어시험도 못 보러 가고 난리가 났지만...

다음 주 부터는 포스팅도 하고 코테와 포트폴리오 준비도 다시 시작해야겠네요... 

오늘은 네 번째 정렬 알고리즘이자, 시간 복잡도가 O(NlogN)인 첫 번째 정렬 알고리즘.

병합정렬에 대해 알아보겠습니다.

1. 데이터들이 한 개씩 쪼개어질 때까지 주어진 데이터를 두 개의 그룹으로 나누는 작업을 반복한다.

2. 하나씩 쪼개어진 데이터는 정렬된 상태가 된다.

3. 정렬된 데이터들을 쪼갠 역순으로 병합하면서 정렬하면 정렬된 상태의 전체 데이터를 구할 수 있다.

처음 병합정렬의 설명을 말로만 들으면 머릿속으로 정렬 과정을 그리기 쉽지 않을 텐데요.

그림을 통해 실제로 정렬이 이루어지는 과정을 보면서 설명하고 정리해드리도록 하겠습니다.

언제나처럼 정렬되지 않은 데이터가 있습니다.

3, 5, 7, 4, 2, 6, 8, 1의 여덟 데이터를 정렬해보도록 하겠습니다.

우선 데이터들을 두 개의 그룹으로 나누는 과정을 반복하여, 하나씩 쪼개어줍니다.

이번 예시의 경우엔 데이터의 개수가 2^3인 8개이므로 3번의 단계를 거쳐서 쪼개어집니다.

이렇게 최종적으로 쪼개어진 밑단의 데이터들은 자연스럽게 정렬된 상태가 됩니다!

(데이터가 하나이기 때문에 당연히 정렬된 상태입니다.)

이제 부분적으로 정렬된 데이터들을 병합하는 첫번째 단계가 시작됩니다.

각각 정렬된 상태인 3과 5를 비교하여 병합합니다.

(두 데이터 그룹이 부분적으로 정렬된 상태이기때문에 앞에서부터 읽어들이면 됩니다.)

같은 방법으로 7과 4를 병합합니다.

이렇게 첫번째 병합이 완료되었습니다.

두번째 단계부턴 두개의 그룹이 병합되는 과정을 설명해보겠습니다.

우리는 이미 부분적으로 정렬된 3,5 그리고 4,7의 그룹을 가지고 있습니다.

각 그룹이 이미 정렬된 상태기 때문에 전체를 탐색할 필요 없이 두 그룹의 가장 앞의 수를 보고 더 작은 수를 고르면 됩니다.

3과 4를 비교해 3을, 5와 4를 비교해 4를, 5와 7을 비교해 5, 마지막으로 남은 7을 골라줍니다.

자연스럽게 두개의 그룹이 정렬된 상태로 합쳐집니다.

그리고 두개의 그룹을 합칠 때 비교횟수는 전체 데이터의 갯수만큼이면 충분합니다!

(한 번의 비교에서 한개의 데이터가 골라집니다.)

같은 방법으로 나머지 그룹도 병합을 진행시켜줍니다.

이제 마지막, 세번째 병합을 똑같이 진행해줍니다.

두개의 그룹이 각각 부분적으로 정렬된 상태이기 때문에 앞에서부터 비교해가면서 합쳐주면 됩니다.

이렇게 병합정렬을 통한 정렬이 완료되었습니다!

이건 이해를 돕기 위한 예시일 뿐 실제 코드와 프로그램에선 재귀적으로 파고들어 가며 정렬이 진행되기 때문에 동작 흐름은 다릅니다.

병합정렬의 시간 복잡도가 왜 NlogN인지 간단하게 설명해보겠습니다.

앞서 배운 정렬들에서 우리는 각 단계마다 비교를 N, N-1, N-2... 번씩 수행하였고 N^2번의 비교가 필요함을 알았습니다.

병합정렬의 경우에는 각 단계별로 N번의 비교가 이루어집니다. 

하지만 이 단계는 N번 반복되는 것이 아니라, N의 Log2값을 취한 만큼 이루어집니다.

데이터가 2^10개인 1024개라고 생각해봅시다.

처음 분할 단계에서 데이터는 2개의 그룹으로 나뉘는 일을 10번 반복하여 1개씩 1024개로 쪼개집니다.

그리고 이 데이터들은 10번의 단계를 거쳐 정렬된 1024개의 데이터가 됩니다.

10 * 1024 = 10,240번의 비교를 통해 정렬이 완료되는 겁니다.

버블정렬의 경우 같은 데이터에 대해 523,776번의 비교가 필요한 걸 생각하면, 또 데이터의 개수가 늘어날수록 이 차이가 더 커질 거란 걸 생각하면 NlogN정렬 알고리즘들이 더 효율적인걸 알 수 있습니다.

아래는 JAVA로 구현한 간단한 병합정렬 코드와 테스트입니다!

ArrayList 자료구조를 이용해 만들어봤는데요, 제가 적당히 작성한 코드라 실제 효율적인 부분에선 좋지 않을 것 같습니다!

병합정렬의 작동원리를 이해한다 정도로만 봐주시면 감사하겠습니다!

이것저것 바꿔보고 디버깅하면서 흐름이 이해되시길 바랍니다.

import java.util.ArrayList;
import java.util.Random;

public class sort_04_merge {
	static int size = 10;
	static int bound = 1000;
	static int count = 0;
	// 데이터의 갯수와 범위 설정

	public static void main(String[] args) {
		ArrayList<Integer> data = new ArrayList<Integer>();
		Random random = new Random();

		for (int i = 0; i < size; i++) {
			data.add(random.nextInt(bound));
		}
		// 랜덤 값 넣어주기

		System.out.println(data.toString());
		// 랜덤하게 들어간 데이터 확인

		//////////////// 병합정렬 구현코드는 하단으로 /////////////////
		data = mergeSort(data);
		//////////////////////////////////////////////////////

		System.out.println(data.toString());
		System.out.println("비교횟수 : " + count);
	}

	private static ArrayList<Integer> mergeSort(ArrayList<Integer> list) {
		int size = list.size();
		ArrayList<Integer> mergeList = new ArrayList<>();

		if (size <= 1) {
			return list;
		} else {
			ArrayList<Integer> left = new ArrayList<>();
			ArrayList<Integer> right = new ArrayList<>();

			for (int i = 0; i < (size / 2); i++) {
				left.add(list.get(i));
			}
			for (int i = (size / 2); i < size; i++) {
				right.add(list.get(i));
			}

			left = mergeSort(left);
			right = mergeSort(right);

			//System.out.println("left : " + left.toString());
			//System.out.println("right : " + right.toString());

			for (int i = 0, l = 0, r = 0; i < size; i++) {
				if (r == right.size() || (l != left.size() && left.get(l) <= right.get(r))) {
					mergeList.add(left.get(l));
					l++;
				} else {
					mergeList.add(right.get(r));
					r++;
				}
				count++;
			}
			//System.out.println("merge : " + mergeList.toString());
			return mergeList;
		}
	}
}