IDE 및 SCSI 장치 개념, 하드디스크 추가

    IDE 이전까지 많이 사용하던 연결 방식, 최근 디스크는 주로 SATA로 연결한다.

    SCSI  0 0~15 (0:7제외)    0~1 : 0~15 (x :7은 제외) 해서 총 60개 사용가능

    Linux에서는 하드디스크 연결을

        /dev/sd<a/b/c/ ... >    순으로 연결되어 있는 SCSI에 순서대로 지정된다.

        같은 SCSI에 연결된 하드디스크의 파티션을 나누면 /dev/sda<1/2/3/ ... > 순으로 번호를 붙여서 구분한다.

        ls -l /dev/sd*    로 현재 드라이브 공간과 파티션을 확인이 가능하다.

    f명령어

        디스크를 조작할 수 있는 다양한 명령어 파티션이다.

        fdisk    /dev/sb<X>    로 해당 디스크 조작 파티션으로 이동한다.

        n    파티션 생성

        w    변경사항 저장(쓰기)

    포맷

        mkfs.ext4    /dev/sd<X>        지정한 디스크 파티션을 포맷한다. (처음 연결시 필수)

    마운트

        디스크를 추가하면 / 이하 디렉토리에 마운트를 해줘야 접근이 가능하다.

        mount    /dev/sd<X>    /<디렉토리 이름> 

        mount    현재 마운트 된 정보 출력

        마운트 해준 디렉토리에 데이터를 저장했다가, 마운트를 해제하면 해당 디렉토리에는 저장했던 데이터가 보이지 않는다.

        (실제 저장은 디스크에 저장되어 있고, 디렉토리는 단순히 연결해주는 경로)

    부팅 설정 저장        

        지정 해준 마운트는 리부팅시 해제되기 때문에 /etc/fstab 에 마운트 설정을 저장해 놓으면 재부팅시 자동으로 마운트 된다.

        vi    /etc/fstab  

            /dev/sd<X>        /<마운트할 디렉토리명>    ext4    defaults                    0                                                    0

            마운트할 디스트        디렉토리                      타입                        덤프기능 설정(백업)                부팅시 디스크체크 설정

RAID (Linear, RAID0, RAID1)

    Linear RAID

        2개 이상, 1번부터 순차적으로 저장하고 디스크 추가가 가능.

        공간 효율이 100프로, 비용이 저렴

    RAID 0 (Stripping)

        2개이상, 복수의 디스크에 동시에 저장하고 읽기 때문에 속도가 빠르다.

        공간 효율이 100프로로 저렴하고 속도가 빠르지만 신뢰성이 낮다.

    RAID 1 (Mirroring)

        2개 동시저장, 자동 백업으로 결함이 발생해도 백업에서 가져올 수 있다.

        데이터 저장에 2배의 용량이 필요하지만 신뢰성이 높다.

    RAID 5

        결함 허용, 페리티 정보 사용, 공간 효율이 좋다.

        RAID 0의 속도, RAID 1의 안정성을 모두 충족하기 위한 모델로

        오류가 발생시 패리티 를 이용해서 데이터를 복구

        디스크 개수 - 1 의 공간효율.

        대신 패리티1개에 디스크를 많이 늘리고, 2개 이상의 디스크가 고장시 데이터가 손실된다.

    RAID 6

        RAID 5 개선, 중복 페리티 정보 사용. RAID 5 보다 훨씬 안정적이다.

        RAID 5와 비슷하지만 패리티를 2개를 사용. 신뢰도는 많이 높아지지만 속도가 약간 떨어진다.

    RAID1+0 식으로 사용하기도 한다.

RAID 구현 - 디스크 파티셔닝 설정

    디스크를 연결 후 fdisk 콘솔로 이동

    n로 파티션 지정 후 l 을 입력해보면 파티션타입 목록이 나온다.

    t 명령어로 파티션 변경 fd 로 지정 (linux raid auto)

LinearRAID 구현

    mdadm   레이드 설정 명령어

        레이드 생성 명령어

            mdadm     --create /dev/md<num>    --level=linear    --raid-devices=2    /dev/sdb1    /dev/sdc1

                        /dev/md<num> 이름으로      linear 타입의        2개의 장치를 사용    장치1        장치2

            mkfs.ext4    /dev/<raidName>    으로 포맷 

            mount    /dev/<raidName>  /<dirName>    으로 원하는 디렉토리에 마운트

            vi    /etc/fstab     에 마운트 설정 저장

        레이드 확인

            mdadm --detail    --scan

        레이드 상세 보기

            mdadm    --detail    /dev/<raid name>

        마운트 상태 확인

            df

RAID 0, 1 구현

        LinearRAID 생성과 동일하다

            mdadm    --create /dev/md<num>    --level=0    --raid-devices=2    /dev/sdd1    /dev/sde1

            mkfs.ext4    /dev/md<>

            mount    /dev/dm<>    /<dirName>

            vi    /etc/fstab    마운트 설정내용저장

        RAID 1 , RAID 5, RAID 6  설정도 동일하다.

RAID 문제 발생과 조치 방법

    Linear RAID, RAID 0    는 결함 발생시 복구가 불가능.

    RAID 1, 5, 6 는 결함을 허용하기 때문에 복구가 가능.

Linear RAID, RAID 0, 1, 5 복구

    새로운 디스크를 연결하고, fdisk로 초기화 및 RAID 모드로 설정한다.

    사용하지 않은 RAID 복구시

        mdadm     --stop    /dev/md<num>    으로 현재 있는 RAID를 정지 시킨다.

        mdadm    --create    /dev/md<num>    으로 새롭게 RAID를 지정해준다.

    사용중이던 RAID 복구시

        mdadm /dev/md<num>    --add    /dev/sd<>    기존 RAID에 새로운 디스크를 추가해주면 된다.

    vi    /etc/fstab    에서 RAID 설정 값을 저장한다.

RAID 6, RAID 1+0 개념

    RAID 6는 패리티를 2개 사용하고 최소 4개의 디스크가 필요

    RAID 1+0 

    RAID6, RIAD1+0 결함 해결

        RAID 6는 패러티2개를 사용해 디스크 2개의 결함까지 허용한다.

        RAID 1+0 도 RAID 1 두개로 RAID 0을 이루기 때문에 결함을 허용한다.

LVM (Logical Volume Manage)

LVM개념과 구현

여러 개의 하드디스크를 합쳐서 한개의 파일시스템으로 사용하는 것. 필요에 따라서 다시 나눌수도 있다.

    Physical Volume

    Volume Group

    Logical Volume

    LVM 구현 과정은 RAID 구현과정 틀은 동일하다. 하드를 설치하고, fdisk로 파티션을 분배한 다음, 볼륨그룹을 묶어서 마운트한다.

1.    하드디스크 설치후 /dev/sd* 으로 확인

      fdisk    /dev/sd<> 으로 설치한 하드디스크 파이셔닝, 타입을 8e Linux LVM으로 설정

2.    pvcreate /dev/sd<al><num> 으로 방금 설정한 파티셔닝을 PV 생성

3.   vgcreate   /dev/<Volume Group Name>  /dev/<PartitionName1>  /dev/<Partition Name2> ..  으로 볼륨그룹을 생성한다.

4.   lvcreate  --size <num><M/G/T>  <Logical Volume Name>  <VG Name>  으로 볼륨그룹 내에 논리 볼륨을 생성한다. size대신 extents도 가능(남은용량모두)

5.   mkfs.ext4  /dev/<VG name>/<LV name> 으로 논리 볼륨을 포맷해준다.

6.   mkdir 로 마운트할 디렉토리를 생성하고, mount    /dev/<VG  name>/<LV name>     /<Dir Name>  으로 마운트해준다.

7.    vi   /etc/fstab   에 마운트내용을 저장한다.

RAID에 CentOS 설치

    OS가 설치된 디스크에 결함이 발생할 경우 부팅도 불가능할 수 있기 때문에, RAID 1으로 설치하면 결함을 허용할 수 있다.

Linux 설치시 설치목적지 - 디스크 모두 선택  후 커스텀

- 표준파티션 으로 마운트지점을 swap으로 설정하고 장치 유형을 RAID - RAID1으로 설정한다.

- 새 파티션추가로 마운트지점을 /(루트)로 설정하고 장치 유형을 RAID - RAID1으로 설정하한다.

설치를 쭉 마무리.

cmd에서 mdadm --detail --scan 으로 마운트된 디바이스를 확인해보면 RAID1으로 마운트되어있음을 확인할 수 있다.

사용자별 공간할당-쿼터 개념과 실습

쿼터 개념

다중사용자 기능으로 사용시 디스크의 사용량을 파일갯수나 용량으로 제한하는 방식이다.

클라우드에서 사용량을 제한하는 것과 같은 개념.

파일시스템을  /(root) 보다는 별도로 지정하는 것이 좋다.

1. 유저를 생성할 때 유저홈을 마운트된 디렉토리 아래에 생성한다.

2. /etc/fstab를 수정한다. fstab에서 마운트 옵션을  defaults에서  defaults,usrjquota=aquota.user,jqfmt-vfsv0 로 변경

3. mount --options remount </디렉토리명> 으로 리마운트 해준다.

4. 해당 디렉토리로 이동해서 아래의 명령어로 쿼터DB를 생성한다.

quotaoff -avug    쿼터를 끄고

quotacheck -augmn    쿼터 체크 (rm -rf aquota.* 로 체크파일 삭제 후 다시 반복)

touch aquota.user aquota.group    쿼터 DB생성

chmod 600 aquota.*    쿼터에 대한 정보를 외부 사용자는 볼 수 없고, 내부 사용자만 볼 수 있게설정

quotacheck -augmn    다시 쿼터 체크

quotaon -avug    쿼터를 다시 킨다.

1. edquota -u <사용자명> 으로 쿼터제한을 편집하고 저장한다.

2. blocks 는 용량제한으로 뒤에 soft는 경고지점(mb단위), hard는 제한지점(mb단위)

3. inodes 는 파일수 제한

할당 받은 용량을 초과하면 soft지점에선 경고가, hard지점에선 제한 메시지가 출력되고, hard지점을 초과하는 데이터는 저장되지 않는다.

CLI 기반이던 Linux에서도 사용자의 편의를 위해 GUI 환경의 X윈도 모드가 지원된다. 윈도즈에 익숙한 많은 사용자들에게 비슷한 환경을 제공하는데, 윈도즈에서 자주 사용되는 기능들에 대응하는 X윈도에서의 기능들을 살펴본다.

X윈도 모드 설치는 Linux OS를 처음 설치할 때 모드 선택만으로 간단하게 설치가 가능하다. 설치과정에서 X윈도 모드로 기본 설치를 진행했다는 가정에서 설정과 기능들을 살펴본다.

배경화면, GRUB배경 설정

    배경화면과 테마변경

        배경화면 변경은 윈도즈와 마찬가지로 마우스 우클릭 - 배경 바꾸기로 컴퓨터에 저장되어 있는 이미지를 선택해 

       간단하게 변경할 수 있다.

        테마변경을 위해서는 먼저 터미널을 열어서 dnf -y install gnome-tweak-tool 명령어로 gnome툴을 설치한다.

        gnome-tweaks 명령어로 기능개선창을 열고 원하는 모양새를 선택해 테마를 변경할 수 있다.

    GRUB 배경설정

       GRUB배경화면은 컴퓨터를 부팅시 GRUB선택 시 나오는 배경화면으로 기본은 검은 배경에 글자만 나온다.

1. 변경하길 원하는 이미지 파일을 /root/grub2/ 디렉터리로 이동시킨다. 해당 디렉터리는 root권한이 있어야 하므로 터미널에서 su -c 'command' 명령어를 이용한다.

2. /etc/default/grub 파일을 아래와 같이 수정한다. 마찬가지로 root권한이 필요하다.

        GRUB_TERMUNAL_OUTPUT="console"    앞에 # 으로 주석처리

        GRUB_BACKGROUND="/boot/grub2/<png이름>.png"    로 설정파일에 설정 후 저장

   3. su    -c    'grub-mkconfig    -o    /boot/grub2/grub.cfg'    명령어로 변경한 내용을 GRUB에 적용시킨다.

파일편집기 노틸러스

    노틸러스는 Windows에 파일탐색기와 비슷한 역할로 간편하게 다양한 기능을 제공한다.

    현재 활동을 눌러서 파일을 선택해보면 윈도즈의 파일탐색기와 유사한 창이 뜬다. 사용법도 거의 유사해서 마우스

    우클릭으로 기능들을 볼 수 있고 좌클릭으로 원하는 디렉터리나 폴더를 선택하면 된다.

    ctl+c, ctl+x, ctl+v 등 단축키도 윈도즈에서 사용하던 기능을 지원해서 PC를 사용해왔다면 별다른 설명이 불필요.

FireFox 업그레이드

CentOS에서는 기본적으로 FireFox 브라우저를 지원하는데 새로운 버전으로 업그레이드를 해본다.

1. 브라우저로 FireFox 최신버전을 다운로드 한다.

2. 다운받은 버전의 설치파일을 압축 해제한다. 터미널에서 실행하려면 tar xfj <설치파일 이름> 명령어로 압축해제

3. 해당 파일을 /usr/local/ 디렉터리로 옮긴다. root 권한이 필요하다.

4. chown -R root.root /usr/local/firefox/ 명령어로 새롭게 덮어쓴 firefox 관련 파일들의 소유권한을 변경한다.

5. /usr/local/bin 디렉터리로 이동해서 ln -s /usr/local/firefox/firefox . 명령어로 링크를 새롭게 생성시킨다.

이제 firefox 브라우저를 새롭게 실행시켜보면 새로운 버전의 firefox로 설정하겠냐는 질문이 나오고 새로운 버전의 firefox를 확인할 수 있다.

에볼루션

MS Outlook과 비슷한 이메일 클라이언트 프로그램. 실행시켜 보면 처음에 메일 서버와 계정을 입력하고 사용하면 되는데, 요즈음에는 웹 브라우저를 통해 이메일을 주고 받고 내부 네트워크로만 구성된 경우에도 다른 프로그램을 사용하는 경우가 많아서 사실상 잘 사용되지 않는다.

문서편집기 gedit

윈도즈의 메모장과 비슷한 기본적인 텍스트 편집기다.

현재활동에서 텍스트 편집기를 선택하거나 터미널에서도 gedit <파일명> 으로 바로 열어서 사용이 가능하다.

X윈도 모드라면 터미널에서도 vi 편집기와 함께 gedit 편집기를 사용하면 쉽게 텍스트를 편집할 수 있다.

문서 뷰어 evince

PDF , XPS, TIFF 등 여러 문서를 볼 수 있는 간편한 뷰어. 현재 활동에서 문서보기를 선택하거나

터미널에서 evince 명령어로 실행할 수 있다.

그래픽 편집 프로그램 GIMP

CentOS에서 제공하는 프로그램인 GIMP는 윈도즈에서는 별도로 설치해야 하는 포토샵과 비슷한 기능을 갖는 그래픽 편집기다.

터미널에서 dnf -y install gimp 명령어로 간단하게 설치할 수 있다. (root권한 필요)

설치 후에는 현재활동 - GIMP를 선택하거나 터미널에서 gimp 명령어로 실행할 수 있다.

LibreOffice

LibreOffice는 MSOffice와 유사한 오픈소스 문서 편집기인데 MSOffice에 뒤지지 않는 성능에 높은 호환성까지 갖춘 프로그램이다.

사용법도 MSOffice와 유사하고 워드=wirter, 엑셀=calc, 파워포인트=impress 등 MSOffice에 대응하는 프로그램을 모두 제공한다.

LibreOffice는 Linux뿐 아니라 윈도즈, 맥 모두 지원한다.

1. LibreOffice에서 설치 파일과 언어팩을 다운받는다.

2. 다운 받은 설치 파일과 언어팩 파일을 압축 해제한다. tar xfz <파일명>

3. 터미널에서 다운받은 설치 파일 내의 /RPMS/디렉터리로 이동해 dnf -y install *.rpm 으로 설치한다. (root 권한 필요)

4. 다운 받은 언어팩 파일 내의 /RPMS/ 디렉터리로 이동해 dnf -y install *.rpm 으로 언어팩을 설치한다.

설치가 완료 된 후에는 현재활동이나 터미널에서 libreoffice<버전> 으로 실행할 수 있다.

VirtualBox

현재 학습을 Winodws 안에서 VM을 이용해 CentOS를 설치해서 진행하듯이 반대로 리눅스 안에서도 VirtualBox를 이용해 Windows를 설치할 수 있다.

VirtualBox는 VMware와 거의 동일한 기능을 제공하는 가상머신 툴이다.

1. dnf -y install make perl patch kernel-devel kernel-devel-4.18.0.80.el8.x86_62 elfurils-libelf-devel 명령어로 필요한 패키지를 설치한다. (패키지 버전은 학습 중인 CentOS 8 기준)

2. 브라우저에서 VirtualBox 설치 파일을 다운받는다.

3. dnf -y install Virtual* 명령어로 설치한다. (root 권한 필요)

4. usermod -a -G vboxusers <UserID> 명령어로 현재 사용자를 vboxusers 그룹에 포함시킨다.

5. /user/lib/virtualbox/vboxdrv.sh setup, /sbin/vboxconfig 명령어를 차례로 입력해 설정을 하면 완료.

설치를 완료하고 나면 현재활동에서 VirtualBox를 선택하거나 터미널에서 virtualbox 명령어로 실행할 수 있다. 사용법은 VM과 유사.

문제 설명

데이터 처리 전문가가 되고 싶은 어피치는 문자열을 압축하는 방법에 대해 공부를 하고 있습니다. 최근에 대량의 데이터 처리를 위한 간단한 비손실 압축 방법에 대해 공부를 하고 있는데, 문자열에서 같은 값이 연속해서 나타나는 것을 그 문자의 개수와 반복되는 값으로 표현하여 더 짧은 문자열로 줄여서 표현하는 알고리즘을 공부하고 있습니다.
간단한 예로 aabbaccc의 경우 2a2ba3c(문자가 반복되지 않아 한번만 나타난 경우 1은 생략함)와 같이 표현할 수 있는데, 이러한 방식은 반복되는 문자가 적은 경우 압축률이 낮다는 단점이 있습니다. 예를 들면, abcabcdede와 같은 문자열은 전혀 압축되지 않습니다. 어피치는 이러한 단점을 해결하기 위해 문자열을 1개 이상의 단위로 잘라서 압축하여 더 짧은 문자열로 표현할 수 있는지 방법을 찾아보려고 합니다.

예를 들어, ababcdcdababcdcd의 경우 문자를 1개 단위로 자르면 전혀 압축되지 않지만, 2개 단위로 잘라서 압축한다면 2ab2cd2ab2cd로 표현할 수 있습니다. 다른 방법으로 8개 단위로 잘라서 압축한다면 2ababcdcd로 표현할 수 있으며, 이때가 가장 짧게 압축하여 표현할 수 있는 방법입니다.

다른 예로, abcabcdede와 같은 경우, 문자를 2개 단위로 잘라서 압축하면 abcabc2de가 되지만, 3개 단위로 자른다면 2abcdede가 되어 3개 단위가 가장 짧은 압축 방법이 됩니다. 이때 3개 단위로 자르고 마지막에 남는 문자열은 그대로 붙여주면 됩니다.

압축할 문자열 s가 매개변수로 주어질 때, 위에 설명한 방법으로 1개 이상 단위로 문자열을 잘라 압축하여 표현한 문자열 중 가장 짧은 것의 길이를 return 하도록 solution 함수를 완성해주세요.

제한사항

• s의 길이는 1 이상 1,000 이하입니다.
• s는 알파벳 소문자로만 이루어져 있습니다.

나의 풀이

 내가 이해한 이 문제의 핵심 요지는 축의 기준이 되는 문자열을 유닛(코드상 unit)이라 할때 이 유닛의 길이는 일정해야 한다는 것. 다시 말하자면 주어진 문자열 s에서 어떤 부분은 unit의 길이가 1이고 어떤 부분은 unit의 길이가 1이 아닌 n인 경우가 존재할 수 없다는 말이다. 예를 들자면 aabbcccabab를 2a2b3c2ab로는 압축할 수 없다. aabbccc 부분은 unit의 길이가 1인데, abab부분은 unit이 ab이므로 길이가 2가 되기 때문이다.

 때문에 unit의 길이를 몇으로 했을 때 최소길이로 문자열 압축이 가능한지를 구하면 되었다. 그런데 여기서 주의해야 할 부분이 문제 설명이 아닌 문제와 함께 포함된 예제 5에 있는 부분이었다. 아래가 그 예제인데

입출력 예 #5

문자열은 제일 앞부터 정해진 길이만큼 잘라야 합니다.
따라서 주어진 문자열을 x / ababcdcd / ababcdcd 로 자르는 것은 불가능 합니다.
이 경우 어떻게 문자열을 잘라도 압축되지 않으므로 가장 짧은 길이는 17이 됩니다.

여기서 보면 알듯이 주의해야할 제약조건으로 주어진 문자열을 정한 unit 길이로만 잘라내야 한다는 것이다.

길이를 10으로 잡았다면 주어진 문자열을 앞에서부터 10개씩 잘라내서 확인해야 한다는 것. 이 제약조건이 없다면 문제는 조금 더 복잡해졌을 것이다.

여기까지 이해를 했다면 나머지 코드는 생각보다 단순?하게 작성할 수 있었다. 코드에 이해를 돕기위해 주석으로 설명을 붙여놓았다.

코드

import java.util.*;

class Solution {
    public int solution(String s) {
        int answer = s.length();
        
        //i는 비교의 기준이 되는 단위 문자열 unit의 길이를 의미한다.
        //처음엔 1글자씩 unit을 잡고 차례로 최대 길이/2 만큼 증가시킨다.
        for(int i=1; i<=s.length()/2; i++) {
            int ptr = 0;
            
            //tempLeng은 단위 i일때 압축되는 길이를 저장할 변수, 일단 s의 길이로 초기화
            int tempLeng = s.length();
            
            //문자열 s에서 ptr위치부터 ptr+1이전까지를 잘라 unit에 저정한다.
            for(;ptr+i<=s.length();) {
                String unit = s.substring(ptr, ptr+i);
                ptr += i;
                //count는 현재 단위 문자열 unit이 몇개나 반복되는지를 저장한다.
                int count = 0;
                
                //단위 문자열인 unit부터 다음 i개 문자가 일치하는지 확인한다.
                for(;ptr+i<=s.length();) {
                    //unit과 unit다음 i개의 문자가 일치하면 count를 증가시킨다.
                    if(unit.equals(s.substring(ptr,ptr+i))) {
                        count++;
                        ptr += i;
                    } else {
                        //만약 unit과 다르다면 바로 unit을 다음 i개의 문자로 갱신하기 위해 반복문을 빠져나간다.
                        break;
                    }
                }
                
                //unit을 갱신하기 전에 이번 unit으로 몇 개나 반복되었는지 확인하고, 암축된 길이만큼 tempLeng의 값을 감소시킨다.
                if(count>0) {
                    tempLeng -= i*count;
                    
                    //반복된 글자수만큼 숫자가 들어가기 때문에 tempLeng은 삽입되는 숫자 갯수만큼 다시 증가한다.
                    //count를 1 증가시키는 이유는 count가 9라면 실제로는 unit+unit*9 이므로 10unit과 같이 표현되기 때문이다.
                    count++;
                    while(count>0) {
                        count/=10;
                        tempLeng++;
                    }
                }
            }
            
            //unit의 길이가 i일때 압축가능한 길이와 이전 answer에 저장되어 있던 이전 최소압축길이를 비교해 answer을 갱신한다.
            answer = Math.min(answer, tempLeng);
        }
        
        return answer;
    }
}

문제 설명

카카오에 신입 개발자로 입사한 콘은 선배 개발자로부터 개발역량 강화를 위해 다른 개발자가 작성한 소스 코드를 분석하여 문제점을 발견하고 수정하라는 업무 과제를 받았습니다. 소스를 컴파일하여 로그를 보니 대부분 소스 코드 내 작성된 괄호가 개수는 맞지만 짝이 맞지 않은 형태로 작성되어 오류가 나는 것을 알게 되었습니다.
수정해야 할 소스 파일이 너무 많아서 고민하던 콘은 소스 코드에 작성된 모든 괄호를 뽑아서 올바른 순서대로 배치된 괄호 문자열을 알려주는 프로그램을 다음과 같이 개발하려고 합니다.

용어의 정의

'(' 와 ')' 로만 이루어진 문자열이 있을 경우, '(' 의 개수와 ')' 의 개수가 같다면 이를 균형잡힌 괄호 문자열이라고 부릅니다.
그리고 여기에 '('와 ')'의 괄호의 짝도 모두 맞을 경우에는 이를 올바른 괄호 문자열이라고 부릅니다.
예를 들어, "(()))("와 같은 문자열은 균형잡힌 괄호 문자열 이지만 올바른 괄호 문자열은 아닙니다.
반면에 "(())()"와 같은 문자열은 균형잡힌 괄호 문자열 이면서 동시에 올바른 괄호 문자열 입니다.

'(' 와 ')' 로만 이루어진 문자열 w가 균형잡힌 괄호 문자열 이라면 다음과 같은 과정을 통해 올바른 괄호 문자열로 변환할 수 있습니다.

 1. 입력이 빈 문자열인 경우, 빈 문자열을 반환합니다.

 2. 문자열 w를 두 "균형잡힌 괄호 문자열" u, v로 분리합니다. 단, u는 "균형잡힌 괄호 문자열"로 더 이상 분리할 수 없어야 하며, v는 빈 문자열이 될 수 있습니다.

 3. 문자열 u가 "올바른 괄호 문자열" 이라면 문자열 v에 대해 1단계부터 다시 수행합니다.

     3-1. 수행한 결과 문자열을 u에 이어 붙인 후 반환합니다.

 4. 문자열 u가 "올바른 괄호 문자열"이 아니라면 아래 과정을 수행합니다.

    4-1. 빈 문자열에 첫 번째 문자로 '('를 붙입니다.

    4-2. 문자열 v에 대해 1단계부터 재귀적으로 수행한 결과 문자열을 이어 붙입니다.

    4-3. ')'를 다시 붙입니다.

    4-4. u의 첫 번째와 마지막 문자를 제거하고, 나머지 문자열의 괄호 방향을 뒤집어서 뒤에 붙입니다.

    4-5. 생성된 문자열을 반환합니다.

균형잡힌 괄호 문자열 p가 매개변수로 주어질 때, 주어진 알고리즘을 수행해 올바른 괄호 문자열로 변환한 결과를 return 하도록 solution 함수를 완성해 주세요.

매개변수 설명

• p는 '(' 와 ')' 로만 이루어진 문자열이며 길이는 2 이상 1,000 이하인 짝수입니다.
• 문자열 p를 이루는 '(' 와 ')' 의 개수는 항상 같습니다.
• 만약 p가 이미 올바른 괄호 문자열이라면 그대로 return 하면 됩니다.

나의 풀이

 처음에는 문제가 잘 이해되지 않았다. '용어의 정의' 중에서 1-4 과정이 사실상 알고리즘을 이미 알려주고 있는 상태이고 코드로 만들기만 하면 되었는데. 3,4 과정이 무엇을 말하는지 파악이 잘 되지 않아서 애를 먹었다. 결과적으로는 3,4 모두 재귀적으로 풀면 되었는데 단지 u의 값에 따라 처리과정이 추가되냐 마냐의 차이. 상세한 풀이는 가능한 코드에 주석으로 달면서 풀어놨다. 풀고나서 든 생각은 주어진 solution메서드를 재귀형으로 호출하는게 아니라 별도로 재귀메서드를 작성해서 실행해도 좋았을거 같다.

코드

import java.util.*;

class Solution {
    int pointer = 0;
    
    //주어진 문자열 w가 올바른 괄호 문자열인지 체크
    public boolean solve(String w) {
        boolean flag = true;
        Stack<Character> stack = new Stack<Character>();
        int left = 0, right = 0;
        
        //주어진 문자열에서 문자를 하나씩 꺼내서 여는괄호인지 닫는괄호인지 확인
        for(int i=0; i<w.length(); i++) {
            if(w.charAt(i) == '(') {
                left++;
                stack.push('(');
            } else {
                right++;
                //만약 여는 괄호가 없었는데 닫는 괄호가 나온다면 올바른 괄호 문자열이 아님
                if(stack.isEmpty())
                    flag = false;
                else
                    stack.pop();
            }
            
            //여는괄호와 닫는괄호 갯수가 같을때를 pointer에 저장해서 u,v의 경계를 구함
            //u,v경계가 구해지면 u가 올바른 괄호 문자열인지 결과를 가지고 리턴
            if(left == right) {
                pointer = i+1;
                return flag;
            }
        }
        
        //매개변수로 주어진 w가 균형잡힌 괄호 문자열이기 때문에 실제로 for밖으로 나올일은 없다.
        return true;
    }
    
    public String solution(String p) {
        if(p.isEmpty())
            return p;
        
        boolean check = solve(p);
        String u = p.substring(0, pointer);
        String v = p.substring(pointer, p.length());
        
        //u가 올바른 괄호 문자열이라면 나머지 v를 가지고 위 과정을 반복한다.
        if(check) {
            return u + solution(v);
        }
        
        //u가 올바른 괄호 문자열이 아니라면 과정 4를 수행한다.
        StringBuilder answer = new StringBuilder();
        
        answer.append("(").append(solution(v)).append(")");
        for(int i=1; i<u.length()-1; i++) {
            if(u.charAt(i)=='(')
                answer.append(")");
            else
                answer.append("(");
        }
        
        return answer.toString();
    }
}

가장 긴 증가하는 부분 수열 성공분류

시간 제한메모리 제한제출정답맞은 사람정답 비율

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

나의 풀이

주여진 요소마다 가질 수 있는 최대 길이값이 있을거라 생각하고 접근을 시작. 주어진 배열과 같은 길이의 dp[] 배열을 만들어서 최대 길이값을 저장하기로 하고, 자기 자신보다 작으면서 증가하는 요소가 앞에 몇개나 있나 카운트해서 dp[]배열에 저장했다. DP의 특성이 자연스럽게 드러났는데 주어진 arr[] 배열에서 자기보다 앞에 있으면서 값이 작은 요소를 찾고, 해당 요소가 dp[] 배열에 저장중인 값에 1을 더해주는 식으로 처리했다. 단 현재 요소의 dp[]의 값보다 앞의 요소의 dp[]값이 작다면 넘어가고 크거나 같을 때만 1을 증가시켜 주는 조건을 만족할때만 실행했다. 

dp[] 배열의 모든 값이 저장되고 나서 가장 큰 값을 찾으면 가장 긴 증가하는 부분수열의 길이가 된다.

코드

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int num = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int[] arr = new int[num];
        for(int i=0; i<num; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        
        int[] dp = new int[num];
        dp[0] = 1;
        
        for(int i=1; i<num; i++) {
            dp[i] = 1;
            for(int j=0; j<i; j++) {
                if(arr[j] < arr[i] && dp[i]<=dp[j]) {
                    dp[i] = dp[j]+1;
                }
            }
        }
        
        int max = 0;
        for(int i=0; i<num; i++) {
            max = Math.max(max, dp[i]);
        }
        
        bw.write(max+"\n");
        bw.flush();
    }
}

LIS (Longest Increasing Subsequence) 최장 증가 부분 수열은 주어진 수열 중에서 각 요소가 증가하는 형태의 부분수열 중 가장 긴 수열을 의미한다. 말로 설명하니 복잡한데 아래 예를 보면 간단하다. 예시는 백준 알고리즘의 11053번 문제이다.

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 이런 최장 증가 부분 수열을 찾는 방식은 가장 간단하게는 DP테이블을 이용하는 문제해결이다. 

주어진 수열이 arr[n] 라 할대 dp[n]의 배열을 만들고, 각 요소마다 가질수 있는 최대 길이값을 저장하는 방식이다.

이 방식으로 문제를 푼것이 아래 포스팅.

coder9084.tistory.com/109

헌데 이와같이 구현하면 이중 for문을 돌면서 시간복잡도는 O(n^2)이 된다. 더 시간복잡도를 줄일 수 있는 다른 방법으로는 이분탐색을 이용한 방법이다.

List를 하나 만들고 주어진 수열에서 매 요소를 꺼내면서 List에 같거나 더 큰 요소 중 최소인 요소 자리에 삽입하는 방식이다. 과정을 보면

 1. 주어진 수열에서 요소를 차례로 꺼낸다.

 2. List에서 꺼낸 요소와 같거나 더 큰 값을 갖는 요소 중 최소 요소를 이분탐색 방식으로 찾아서 교체한다.

 3. 1-2. 작업을 반복한다.

이를 예시로 들어서 보면  주어진 수열이 A = {10, 20, 10, 30, 25, 50} 일때, LIS는 {10, 20, 25(30), 50} 이 된다.

 10을 꺼내서 list에 크거나 같은 값 중 최소를 찾아서 넣으면 처음에는 비어있기 때문에 {10}

 20을 꺼내서 위 작업을 반복하면 {10, 20}

 10을 꺼내서 위 작업을 반복하면 {10, 20}

 30을 꺼내서 위 작업을 반복하면 {10, 20, 30}

 25를 꺼내서 위 작업을 반복하면 {10, 20, 25}

 50을 꺼내서 위 작업을 반복하면 {10, 20, 25, 50}

 결과적으로 list에 남아있는 요소들이 LIS가 되는것을 확인 할 수 있다. 매번 크거나 같은 값 중 최소를 찾는 작업이 이분탐색으로 실행되기 때문에 log n의 시간복잡도를 갖고, 모든 요소로 작업을 수행하기 때문에 결과적으로 O(nlogn)의 시간복잡도를 갖게된다.

 하지만 주의해야 할 점은 LIS의 길이는 보장이 되지만 같은 길이의 부분함수가 여럿이라면 요소들의 조합을 보장하진 않는다는 점이다. 위의 문제에서도 볼 수 있지만 결과는 {10, 20, 25, 50} 으로 30이 포함되지 않는다.

이 블로그 카테고리에 포함되어 있지 않은 모든 코드도 저장되어 있는 git주소.
해당 깃에 있는 모든 내용은 직접 작성한 것이고, 단계별 풀어보기를 모두 완료할때까지 계속 갱신된다.

깃은 자격증이나 급한 다른 공부를 하고 있을때가 아니고서는 매일 푸쉬하려 하는데...

github.com/programo90/BackJoon-Algorithm

 정렬(Sorting)이란 데이터 집합을 일정한 순서대로 정렬하는 작업을 말하는데, 알고리즘 구현에 있어서 데이터 집합이 정렬되어있어야 빠른 검색이 가능한것은 당연하다. 정렬 방식에 따라서 안정성과 비용의 차이가 있기 때문에 적절한 방식으로 정렬을 수행할 필요가 있다. 정렬의 기본은 교환, 선택, 삽입이고 여기에 정리할 정렬 알고리즘들도 앞에 세 가지 요소를 응용한 것이라 할 수 있다.

선택 정렬

선택 정렬은 데이터 집합 중에서 가장 작은 값부터 차례로 선택해 적합한 자리에 요소와 교환하는 방식을 반복하는 기법이다. 과정을 보면

 1. 데이터 집합 중 가장 작은 값을 찾는다.

 2. 첫번째 요소와 가장 작은 값의 요소를 교환다.

 3. 1-2 를 반복하면서 차례로 두번째로 작은 값과 두번째요소, 세번째로 작은 값과 세번째요소와 같이 진행한다.

과정이 단순하고 (n^2 -n)/2 의 복잡도를 갖는데 동일값이 있을 경우 안정적이지 않은 문제점이 있다.

동일한 가중치를 갖는 값의 순서가 정렬 이전과 달라질수 있는 경우를 안정적이지 않다고 하는데, 서로 멀리 떨어져있는 요소를 교환하는 알고리즘의 경우 이와같이 안정적이지 않을 수 있다.

예시 코드

public class SelectionSort {
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}
	
	static void selectionSort(int[] a, int n) {
		for(int i=0; i<n; i++) {
			int min = i;
			for(int j=i+1;j<n; j++) {
				if(a[j]<a[min]) {
					min = j;
				}
			}//for selection pass
			swap(a,i,min);
		}// for
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
	}

}

버블 정렬

버블 정렬의 기본은 인접요소 두 개를 비교해서 원하는 순서와 다르다면 교환하는 기법이다. 버블 정렬의 실행 순서를 아래에 정리해 보면

 1. 젤 끝(앞)에 있는 요소를 시작으로 인접 요소와 비교-교환을 하며 젤 앞(뒤) 요소까지 진행한다.

 2. 1. 과정을 다시 수행하는데, 이번엔 젤 앞(뒤)에 요소는 제외한다.

 3. 1-2 과정을 반복할때마다 앞(뒤)의 요소가 하나씩 제외되도록 반복한다. 모든 요소가 제외되고나면 정렬이 끝난다.

오름 차순으로 예를 들어보면, 데이터 집합 중에 젤 작은 값은 1-2 과정을 한번 끝내면 젤 앞에 오게된다.

다시 한번 1-2 과정을 실행하면 두 번째로 작은 요소가 데이터 집합 중 두 번째에 위치한다.

버블 정렬은 안정적인 알고리즘이지만 요소의 갯수가 n일때 n(n-1)/2 의 복잡도를 갖는다.

예시 코드

import java.util.Scanner;

public class BubbleSort {
	static void swap(int[] a, int idx1, int idx2) {
		int temp = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = temp;
	}
	
	static void bubbleSort(int[] a, int n) {
		for(int i=0; i<n-1; i++) {
			for(int j=n-1; j>i; j--) {
				if(a[j]<a[j-1]) {
					swap(a,j,j-1);
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);
		
		System.out.println("버블정렬 1.");
		System.out.print("요소수 : ");
		int n = Integer.parseInt(sc.nextLine());
		int[] x = new int[n];
		
		for(int i=0; i<n; i++) {
			System.out.print("arr["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		bubbleSort(x, n);
		
		System.out.println("오름차순 버블 정렬 완료.");
		for(int i=0; i<n; i++) {
			System.out.println("x["+i+"] : "+x[i]);
		}
		
		sc.close();
	}

}

삽입 정렬

삽입 정렬은 요소를 하나씩 선택해서 정렬된 부분 중에 알맞는 위치에 삽입하는 작업을 반복해서 정렬한다. 이 과정을 보면 매번 요소를 선택해서 삽입할 때마다 데이터 집합의 순서가 갱신되는 방식. 과정을 정리해보면

 1. 젤 앞(뒤) 요소부터 시작해 요소 하나를 선택하고, 자신보다 앞에 있는 요소들 중 들어갈 자리를 찾아서 삽입한다.

 2. 1. 를 데이터 집합의 끝(앞)까지 반복한다.

 1-2 과정을 반복하는 것으로 정렬이 끝나게 되는데 원리는 간단하지만 삽입과정이 실제 구현에서 많은 비용이 소모된다. 왜냐하면 삽입을 위해서는 '현재 선택된 요소 - 들어가야할 자리' 사이에 있는 모든 요소들을 한칸씩 뒤로 배치해야 하기 때문이다. 만약 자료구조가 LinkedList와 같이 삽입비용이 적다면 모르지만, 배열과 같은 구조라면 결국 요소들을 일일이 한 칸 뒤로 배치하는 작업을 반복되야 하기 때문이다. 때문에 삽입 정렬은 요소의 갯수가 n개일때, 최대 n^2의 복잡도를 갖게 된다.

예시 코드

import java.util.Scanner;

public class InsertionSort {
	static void insertionSort(int[] a, int n) {
		for(int i=1; i<n; i++) {
			int j;
			int temp = a[i];
			for(j=i;j>0&&a[j-1]>temp;j--) {
				a[j] = a[j-1];
			}
			a[j] = temp;
		}
	}
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.println("단순 삽입 정렬");
		System.out.print("요소수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("x["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		insertionSort(x,num);
		
		System.out.println("정렬 완료");
		for(int i = 0; i<num; i++) {
			System.out.println("x["+i+"] : " + x[i]);
		}
		
		sc.close();
		
	}

}

퀵 정렬

이름 대로 빠른 정렬인데 자료들을 반으로 나눠가며 정렬을 반복하는 방식. 여기서 자료를 나누는 기준을 피벗(pivot)이라 부른다. 나뉘어진 자료의 그룹이 한 개의 요소만 갖게 되면 정렬이 종료된다. 오름차순 퀵 정렬의 순서를 보면

 1. 피벗을 정하고 그룹의 양 끝 요소부터 하나씩 전진하며 피벗과 값을 비교한다.

 2. 앞쪽부터 진행하던 요소가 피벗보다 값이 크다면 정지한다.

 3. 뒤쪽부터 진행하던 요소가 피벗보다 값이 작다면 정지한다.

 4. 앞쪽에서 선택중인 요소가 뒤쪽에서 선택중인 요소보다 크다면 두 값을 교환하고 1-3을 다시 반복한다.

 5. 앞쪽에서 선택중인 요소가 뒤쪽에서 선택중인 요소보다 작다면 1-3반복을 멈추고 피벗을 기준으로 그룹을 두개로 나누어 1-4를 반복한다.

 6. 그룹의 요소가 한 개만 남으면 정렬을 종료한다.

위에 작업 순서를 보면 복잡해 보일지 모르지만 이를 표로 보면 한눈에 들어온다. 쉽게 다시 설명하면 기준을 정해서 기준보다 큰그룹, 작은그룹을 나누고 각 그룹으로 다시 기준을 잡고 그룹나누기를 반복하는 기법. 복잡도는 평균 n log n의 복잡도를 갖기에 상술한 버블 정렬, 삽입 정렬보다 빠르지만 데이터의 분포에 따라 최대 n^2의 복잡도를 갖게 된다.

예시 코드

import java.util.Scanner;

public class QuickSort {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	static void quickSort(int[] a, int left, int right) {
		int pl = left;
		int pr = right;
		int x= a[(pr+pl)/2];
		
		System.out.printf("x[%d]~x[%d] : {",left,right);
		for(int i = left; i<right; i++) {
			System.out.printf("%d, ",a[i]);
		}
		System.out.printf("%d}\n",a[right]);
		
		
		do {
			while(x>a[pl]) pl++;
			while(x<a[pr]) pr--;
			if(pl<=pr) {
				swap(a, pl++, pr--);
			}
		} while(pl<=pr);
		
		if(left<pr) quickSort(a,left, pr);
		if(right>pl) quickSort(a,pl,right);
		
			
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.print("요소수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("x["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		quickSort(x, 0, num-1);
		
		System.out.println("퀵정렬 수행");
		for(int i =0; i<num; i++) {
			System.out.print(x[i]+" ");
		}
		
		sc.close();
	}

}

병합 정렬

 병합 정렬은 배열을 나누어 각각 정렬한 다음 병합하는 작업을 반복하는 방식의 정렬. 병합 정렬의 전체 과정을 보기전에 정렬되어 있는 두 그룹의 데이터 집합을 병합하며 정렬하는 과정을 알아야 한다. 그 과정을 아래에서 보면

 1. 나뉘어진 두 그룹이 정렬이 되었다는 가정(혹은 요소가 1개)하에 각 그룹의 젤 앞에 요소부터 차례로 값을 읽는다.

 2. 두 그룹에서 현재 읽은 값이 더 작은 순서대로 새로운 그룹에 넣는다. 두 그룹의 모든 요소가 새로운 그룹에 들어가면 병합 정렬이 종료된다.

 정렬된 두 그룹을 병합정렬하는 과정이 위와 같음을 이해하고 병합 정렬의 전체 과정을 아래에서 보자

 1. 데이터 집합을 둘로 나눈다. 나누어진 그룹의 요소가 2개 이상이면 다시 그룹을 둘로 나누기를 반복한다.

 2. 요소가 1개인 그룹이 되면 상술한 정렬된 두 그룹간 병합 정렬을 하면서 나뉘어졌던 모든 그룹들을 병합 정렬로 거슬러 올라간다.

 3. 2.를 반복하여 나뉘어졌던 모든 그룹이 하나의 데이터 집합으로 병합 정렬된다.

병합 정렬은 안정한 정렬기법에 복잡도가 n log n을 보장하는데 단점으로는 위의 과정에서 새로운 그룹이 계속해서 생겨나기 때문에 별도의 메모리 공간이 필요하다.

예제 코드

import java.util.Scanner;

public class MergeSort {
	static int[] buff;
	
	static void __mergeSort(int[] a, int left, int right) {
		if(left<right) {
			int i;
			int j = 0;
			int p = 0;
			int k = left;
			int center = (left+right)/2;
			__mergeSort(a,left, center);
			__mergeSort(a,center+1, right);
			
			for(i=left; i<=center; i++) {
				buff[p++] = a[i];
			}
			
			while(i<=right&&j<p) {
				a[k++] = (buff[j]<a[i])? buff[j++] : a[i++];
			}
			
			while(j<p) a[k++] = buff[j++];
			
			
		}
	}
	
	static void mergeSort(int[] a, int n) {
		buff = new int[n];
		__mergeSort(a, 0, n-1);
		buff = null;
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.println("병합정렬");
		System.out.print("요솟수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i =0; i<num; i++) {
			System.out.print("x["+i+"] :");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		mergeSort(x, num);
		
		System.out.println("정렬 완료");
		for(int i =0; i<num; i++) {
			System.out.println("x["+i+"] : "+x[i]);
			
		}
		
		sc.close();
	}

}

힙 정렬

 힙정렬은 선택 정렬을 힙과 함께 사용해 정렬하는 알고리즘이다. 힙은 부모의 값이 자식의 값보단 큰 완전이진트리를 말한다.(반대로 늘 자식이 더 크더라도 규칙성이 유지되면 힙이라 한다.) 힙의 특성에 따라 완전이진트리의 루트가 늘 최대값이므로, 루트를 꺼내고 남은 값들을 다시 힙으로 구성하는 작업을 반복하므로서 데이터집합을 정렬할 수 있다.

 과정을 보자면

 1. 데이터 집합을 힙으로 구성한다.

 2. 루트값을 꺼내고, 마지막 요소를 루트로 보낸다.

 3. 남은 데이터들을 다시 힙이 되도록 한다.

 4. 2-3 작업을 반복하면서 꺼낸 루트값들을 나열하면 힙 정렬이 완료된다.

 위 과정들을 배열로 구현해 보면

 1. 배열을 힙구조로 정렬하고

 2. 루트가 되는 인덱스 0의 요소를 꺼내서 배열의 젤 뒤 요소와 교환한다.

 3. 젤 뒤요소를 제외하고 나머지 요소들로 다시 힙을 만든다.

 4. 2-3을 반복할때마다 뒤의 요소를 하나씩 추가로 제외하면서 실행하면 배열이 오름차순으로 정렬된다.

힙정렬은 정렬 자체는 선택정렬과 동일하기 때문에 매우 간단한데 힙에 대한 이해와 힙을 구현할줄 알아야 한다. 시간복잡도는 선택정렬이 n^2 인데 반해 힙 정렬은 n log n의 복잡도를 갖는다.

예시 코드

import java.util.Scanner;

public class HeapSort {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}
	
	static void downHeap(int[] a, int left, int right) {
		int t = a[left];
		int child;
		int parent;
		
		for(parent = left;parent<(right+1)/2; parent=child) {
			int cl = parent*2+1;
			int cr = cl+1;
			child = (cr<=right&&a[cr]>a[cl])?cr:cl;
			if(t >=a[child]) break;
			
			a[parent] = a[child];
		}
		a[parent] = t;
	}
	
	static void heapSort(int[] a, int n) {
		for(int i=(n-1)/2; i>=0; i--) {
			System.out.println(i);
			downHeap(a, i, n-1);
		}
		
		for(int i=n-1;i>0; i--) {
			swap(a,0,i);
			downHeap(a,0,i-1);
		}
	}
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		System.out.println("힙 정렬");
		System.out.println("요솟수 : ");
		int num = Integer.parseInt(sc.nextLine());
		int[] x = new int[num];
		
		for(int i=0; i<num; i++) {
			System.out.print("x["+i+"] : ");
			x[i] = Integer.parseInt(sc.nextLine());
		}
		
		heapSort(x,num);
		
		System.out.println("오름차순 힙정렬 완료");
		for(int i =0; i<num; i++) {
			System.out.println("x["+i+"] : "+x[i]);
		}
		
		sc.close();
	}

}