'분류 전체보기'에 해당되는 글 229건

컴파일 과정

Visual Studio에서 우리는 실행할때 F5(또는 Ctrl+F5)를 눌러서 우리가 만든 소스코드를 실행시켜봤죠? 우리는 너무 쉽게 프로그램을 실행시킨다고 생각할 수 있지만 의외로 몇몇 단계를 거치고 있습니다.

이번 시간에는 컴퓨터 실행파일이 어떻게 생겨나는지에 대해서 알아보도록 합시다. 

우리가 실행파일을 생성하는데까지는 아래와 같은 과정을 거치게 됩니다. 어? program.c와 program.exe는 알겠는데 나머지 파일들은 무엇일까요?

이 파일들의 정체를 알아내기 위해서 잠시 리눅스를 사용하도록 하겠습니다. 여러분들은 어떤 파일에 어떤 내용들이 기록되는지에 대해서 눈여겨 보면 될 것 같네요.

다음의 소스코드가 어떻게 실행파일로 변하는지 알아보지요.

#include <stdio.h>
#define A 10
#define B 20
int main(){
        int a=A;
        int b=B;
        int c=a+b;
        printf("%d + %d = %d\n",a,b,c);
}

전처리기(Preprocessor)

전처리기 구문(#으로 시작하는 구문)을 처리하는 것이 바로 전처리기라고 하는데요. 일반적으로 #으로 시작하는 부분을 거의 항상 사용합니다. 그것이 언제냐면 바로 #include지요. 너무나도 소중한 printf를 사용하기 위해서는 항상 #include <stdio.h>를 항상 명시해주어야 하죠.

#include를 통해서 stdio.h의 내용이 그대로 들어오게 됩니다!

또한 위의 코드에서 우리는 #define A 10 과 같은 줄을 볼 수 있는데요. 여기서 전처리기는 A라는 부분을 단순히 10으로 치환합니다.

자. 그렇다면 전처리 과정을 끝낸 program.i는 어떻게 변할까요?

위의 명령어로 program.i의 내용을 살펴봅시다.

program.i

보세요. stdio.h의 내용이 main위의 그대로 들어오지요? 또한 #define A 10과 같은 내용은 없어지고 A가 10으로 치환된것을 알 수 있습니다.

전처리기는 너무나도 단순한 역할을 하는 군요.

중요한것은 전처리기가 컴파일 단계 맨 처음 단계라는 것을 기억하셔야합니다. 그래야지 전처리를 통한 조건부 컴파일을 이해하게 됩니다.

컴파일러(Compiler)

이제 전처리기를 거쳤으니 컴파일러로 컴파일해줍니다. 컴파일러는 고수준언어를 저수준언어로 나타내는 역할을 수행합니다. 저수준언어라는 것은 기계어와 가장 가까운 언어입니다.

이제 program.i로부터 어떻게 program.s가 생겨나는지 보도록 합시다.

program.s

뭐 저도 잘 모르겠습니다. 그냥 저수준언어로 변한것 밖에는 모르겠네요. 

근데 "%d + %d = %d\n" 는 우리가 printf에 썼던 문자열이라는 것을 알 수 있네요.

이것이 컴파일러가 하는 역할입니다. 이제 파일을 오브젝트파일로 변환하는 어셈블러를 보도록 합니다.

어셈블러(Assembler)

이제 완전히 기계어로 바꾸어 주는 역할을 합니다. 우리가 읽을 수 없거든요. 다음의 명령어를 통해서 기계어 파일을 만들고 확인해보도록 하죠.

program.o

^@^(못 읽겠지?) 뭔가 비웃는것 같은 문자만 있네요. 네, 몰라요.

컴퓨터만 알고 있습니다.

hexdump로 볼까요?

그냥 보지마세요. 머리만 아픕니다. 

아 그냥 기계만 해석할 수 있는 언어구나~ 아시면 됩니다.

링커(Linker)

링커는 이름이 말해주듯 연결해주는 역할을 합니다. 여러개의 오브젝트파일을 하나로 합치거나 라이브러리를 합칠때 링커가 필요하다는 거지요.

우리는 일반적으로 개발할때 협업을 합니다. 그래서 위와 같이 오브젝트 파일(.o)라던가 라이브러리 파일이 여럿 존재할 수 있는데 하나의 소프트웨어를 만들기 위해서는 위의 파일들을 합쳐야하는 거죠. 이해되셨나요?

이제 실행파일을 만들어봅시다.

그 후 실행을 시키면 

정상적으로 실행이 되는 것을 확인할 수 있습니다.

뭔가 복잡해보이지만 이러한 과정을 아는 개발자와 모르는 개발자와는 차이가 있다는 것을 알아두세요.

끝!

함수(Function)

함수를 중학생때부터 배우죠? 그렇기 때문에 저는 중학교 시절 수학을 포기했습니다. 여러분들은 저보다 뛰어나시니 그렇지는 않았겠죠?

C언어에서 함수는 아주 필수적이라고 할 수 있습니다. 함수에 대해서 간단히 말씀을 드리면 반복되는 코드를 하나로 묶어 필요할때 가져다가 쓴다는 것입니다.

다음의 코드는 어떻게 생각하시나요?

단순히 세 입력의 펙토리얼(!)을 구하여 곱하는 프로그램이지요.

#include <stdio.h>

int main() {
	int fact_a = 1, fact_b = 1, fact_c = 1;
	int a, b, c;
	int i;
	scanf("%d %d %d", &a, &b, &c);
	
	for (i = 1; i <= a; i++)
		fact_a*=i;
	
	for (i = 1; i <= b; i++)
		fact_b *= i;

	for (i = 1; i <= c; i++)
		fact_c *= i;

	printf("%d! * %d! * %d!= %d\n", a, b, c, fact_a*fact_b*fact_c);

	return 0;
}

프로그램이 잘 동작하는지 실행해보세요!

잘 돌아가지요? 문제 없습니다.

하지만 저는 조금 불만인데요. 펙토리얼을 세번 불러오는데, 세번 다 for루프를 돌려야하기 때문에 손가락이 아픈게 그 이유인데요.

만약 10개의 입력으로 들어오고 10개의 펙토리얼의 곱을 구하게 되면 위의 코드에서 for루프를 7개 더 추가해야한다는 것이 매우 불만이지요.

우리가 팩토리얼의 기능을 하는 하나의 코드를 두고 그 코드를 원할때 마다 불러온다면 어떨까요? 그런 역할을 하는 것이 바로 함수입니다.

함수 구현 방식

함수는 어떻게 생겨먹었을까요? 꽤나 간단하게 이해할 수 있을겁니다.

함수의 형태는 이렇습니다.

우리는 위의 허접한 코드를 factorial이라는 함수를 만들어 조금 더 간편하게 바꿔볼 생각입니다.

위의 형식 그대로 사용해서 factorial을 구현한다면 이렇게 생겼겠죠?

int factorial(int n) {
	int ret = 1;
	int i;
	for (i = 1; i <= n; i++)
		ret *= i;
	return ret;
}

반환형태는 int형이면서 매개변수는 정수형 n입니다. 비교해보세요. 반환형과 반환값(ret)의 자료형이 일치하는 것을 알 수 있죠?

그 후 메인에서는 이 함수를 호출해서 쓰기만 하면 된답니다.

#include <stdio.h>
int factorial(int n) {
	int ret = 1;
	int i;
	for (i = 1; i <= n; i++)
		ret *= i;
	return ret;
}
int main() {
	int fact_a = 1, fact_b = 1, fact_c = 1;
	int a, b, c;
	int i;
	scanf("%d %d %d", &a, &b, &c);
	
	fact_a = factorial(a);
	fact_b = factorial(b);
	fact_c = factorial(c);
	
	printf("%d! * %d! * %d!= %d\n", a, b, c, fact_a*fact_b*fact_c);

	return 0;
}

어때요? 메인이 훨씬 간결해졌음을 알 수 있습니다.

호출 과정은 다음과 같습니다.

메인 함수를 실행하다가 factorial함수를 만났습니다. 그러면 factorial 함수를 실행시키고 함수가 끝나면 다시 메인함수로 돌아와서 그 전에 실행했던 것을 계속 진행하게 됩니다.

fact_a는 factorial 함수의 반환값이 저장됩니다. 나머지 fact_b, fact_c도 역시 마찬가지구요.

만약 10개의 입력이 주어진다하더라도 factorial만 10번 호출하면 되지요.

(아 물론 이 경우에는 배열과 반복문을 써야하겠지만)

함수 선언

근데 꼭 위에서만 함수를 정의하고 몸체를 구현해야할까요? 그럴필요는 없습니다. 

함수를 메인 아래에서 정의할 수도 있습니다.

하지만 꼭 위에서 함수 선언을 해주어야만 합니다. 왜 그러냐구요?

C언어는 절차지향언어이기 때문에 위에서 아래로 실행하기 때문이지요. 그래서 함수가 밑에 정의되어있는데 메인함수에서 그 함수를 호출한다고 하면 컴파일러는 그 함수를 본적이 없으니까 컴파일 에러를 토하게 됩니다.

위의 코드를 함수의 선언 방식으로 코딩해보도록 하면 다음과 같이 간단하게 바뀝니다.

#include <stdio.h>

int factorial(int);     //함수선언

int main() {
	int fact_a = 1, fact_b = 1, fact_c = 1;
	int a, b, c;
	int i;
	scanf("%d %d %d", &a, &b, &c);
	
	fact_a = factorial(a);
	fact_b = factorial(b);
	fact_c = factorial(c);
	
	printf("%d! * %d! * %d!= %d\n", a, b, c, fact_a*fact_b*fact_c);

	return 0;
}

int factorial(int n) {
	int ret = 1;
	int i;
	for (i = 1; i <= n; i++)
		ret *= i;
	return ret;
}

함수에 밑에 있군요. 메인함수 위의 선언이 있죠?

선언에서는 매개변수의 자료형만 적어주어도 상관없습니다.

재귀함수

함수에서 자신의 함수를 불러오는 것을 바로 재귀함수라고 합니다. factorial함수는 재귀함수로도 구현할 수 있습니다.

int factorial(int n) {
	if (n <= 1) return 1;
	return n*factorial(n - 1);
}

factorial함수에서 factorial함수를 호출하는 것을 볼 수 있지요? 매개변수 n과 다음 factorial(n-1)의 반환값을 곱하는 과정을 반복하고 있습니다. factorial의 매개변수 n은 하나씩 줄어들어 결국에는 1 이하가 될겁니다. 그때 1을 반환하지요.

결국 n * (n-1) * (n-2) * ... * 1이 되어 n!을 구현하는 함수죠.

그림으로 보면 더 이해가 쉽게 될겁니다.

3!을 구하는 과정을 보여줍니다. factorial(3)은 factorial(2)를 호출하고 factorial(2)는 factorial(1)을 호출하는 과정을 보여주고 있습니다.

이때 factorial(1)은 if조건문에 걸려 1을 반환하여 더이상 자신을 호출하지 않습니다. 

*** 이를 기저 사례라고 합니다.

재귀함수는 시스템의 스택을 사용하고 계속 사용할 경우 stack overflow가 발생할 수 있으므로 되도록이면 반복문을 사용하는 것이 좋습니다.

이상으로 함수에 대해서 기본적인 설명을 해봤습니다.

스트림

자바에서도 여러 입출력을 지원하지만 이번에 우리의 관심사는 바로 자바에서 제공하는 파일 입출력입니다.

그 전 우리는 스트림에 대한 이야기를 잠깐 간략하게 하고 넘어가겠습니다. 우선 파일에서 입력과 출력이라는 동작을 하려면 파일로 데이터를 전달하거나 파일로부터 전달 받는 길을 열어주어야합니다.

그러한 길을 스트림이라고 하지요.

파일로부터 입력을 받는 스트림을 입력스트림, 출력을 보내는 스트림을 출력스트림이라고 합니다.

그리고 바이너리 형태로 데이터를 입출력하는 스트림을 이진스트림, 문자형태로 입출력하는 스트림을 텍스트스트림이라고 합니다.

스트림을 알았으니 파일입출력을 알아보도록 합시다.

FileReader와 FileWriter

import java.io.*;

public class Main {
	public static void main(String[] args) throws IOException{
		File file=new File("test.txt");
		if(!file.exists())
			file.createNewFile();
		
		FileWriter fw=new FileWriter(file);
		char []buf= {'m','e','s','s','a','g','e','\r','\n'};
		for(int i=0;i<buf.length;i++)
			fw.write(buf[i]);
		fw.close();
		
		FileReader fr=new FileReader(file);
		int EOF=-1;
		int c;
		while((c=fr.read())!=EOF) {
			System.out.print((char)c);
		}
                fr.close();
	}
}

이 코드는 test.txt파일에 "message"라는 문자열을 기록하고 읽어오는 프로그램이에요. 한줄 한줄씩 보도록 하지요.

우선 File 입출력시에는 IOException이 발생할 수 있고 처리가 귀찮으니 저 멀리 보내버리도록 합시다. 가버렷!

일단 file을 열어줘야겠지요? 절대 경로로 지정하지 않는다면 현재 프로젝트 디렉토리에 파일을 엽니다.

하지만 그 파일이 없다면 새로 생성합니다. 

이것을 다음의 라인이 나타냅니다.

File file=new File("test.txt");
if(!file.exists())
	file.createNewFile();

그 후 파일에 "message"라는 문자열을 기록합니다. 그때 사용하는 클래스가 바로 FileWriter라는 클래스이지요.

FileWriter의 메소드 write를 통해서 char 배열의 문자열을 하나씩 기록한 후 스트림을 닫습니다.

FileWriter fw=new FileWriter(file);
char []buf= {'m','e','s','s','a','g','e','\r','\n'};
for(int i=0;i<buf.length;i++)
	fw.write(buf[i]);
fw.close();

이후 한문자씩 읽어오는데 그 역할을 수행하는 클래스가 바로 FileReader입니다. 파일의 끝은 int형의 -1입니다. 그래서 -1을 만날때까지 한문자 한문자 출력합니다.

int형태로 읽어왔으니 char로 바꿔줘야겠지요?

FileReader fr=new FileReader(file);
int EOF=-1;
int c;
while((c=fr.read())!=EOF) {
	System.out.print((char)c);
}
fr.close();

이제 수행을 해보도록 할게요. 어떤 변화가 있는지..

test.txt라는 파일이 생겼네요! 

이것을 까보면!

그안에 우리가 집어넣은 문자열이 존재하는 군요.

eclipse상의 결과 역시 "message"라는 문자열을 출력하는 군요.

파일에 기록한 문자열을 자바프로그램이 읽어온 것이랍니다.

한글자 한글자 읽어오는 것이 여간 불편한 것이 아니죠?

문자열을 사용해서 쓰는 것이 훨씬 더 편할텐데요.

그리고 읽어올때도 배열을 써서 읽어오는 것이 훨씬 편하구요.

그런 방법이 아래에 나와있습니다.

import java.io.*;


public class Main {
	public static void main(String[] args) throws IOException{
		File file=new File("test.txt");
		if(!file.exists())
			file.createNewFile();
		
		FileWriter fw=new FileWriter(file);
		fw.write("Hello, world!!\r\n");
		
	
		fw.close();
		
		FileReader fr=new FileReader(file);
		
		while(true) {
			char []buf=new char[4];
			int ret=fr.read(buf);
			if(ret==-1) break;
			System.out.print(String.valueOf(buf));
		}
		fr.close();
	}
}

FileWriter는 String을 받는 write메소드가 있어서 문자열로 그대로 파일에 기록할 수 있습니다.

중요한건 FileReader인데요. 우선 buf라는 char형 4개에 문자열을 계속 입력받는 거지요. 만약 파일에서 더 읽어올 것이 없다면 -1을 리턴하게 되니까 그 반환형이 -1이면 while루프를 탈출하면 됩니다.

이제 실행 후 파일을 확인해보고 이클립스에서도 확인해 봅시다.

파일에 제대로 적혀있고 이클립스 출력도 이 문자열이 나오는 것을 확인할 수 있죠?

Line 단위 입출력

아직도 불편하긴 합니다. /r/n을 통해서 개행하는 것도 별로구요. 보통 문자 입출력시에는 라인 단위로 입출력을 하기 때문에 라인별로 입력을 할 수 있었으면 좋겠습니다.

그래서 나온것이 버퍼단위의 입출력을 담당하고 있는 BufferedReader, BufferedWriter입니다.

import java.io.*;


public class Main {
	public static void main(String[] args) throws IOException{
		File file=new File("test.txt");
		if(!file.exists())
			file.createNewFile();
		
		BufferedWriter bw=new BufferedWriter(new FileWriter(file));
		
		bw.write("Hello, world!");
		bw.newLine();
		bw.write("Hello, world!!");
		bw.newLine();
		bw.write("Hello, world!!!");
		bw.newLine();
		bw.close();
		
		BufferedReader br=new BufferedReader(new FileReader(file));
		String line=null;
		while((line=br.readLine())!=null)
			System.out.println(line);
			
		br.close();
	}
}

BufferedWriter와 BufferedReader는 버퍼의 사이즈를 지정할 수도 있습니다. 그렇지 않으면 Default 사이즈로 버퍼에 담습니다.

BufferedWriter의 newLine메소드는 개행을 말합니다. 쉽죠? 별거 없어요.

여기서는 Hello, world!를 3라인에 걸쳐 출력합니다. (느낌표 갯수만 다르고요)

이제 BufferedReader를 통해서 읽어옵니다. 

readLine은 String 형태의 문자열을 반환하는데, 만약 더이상 출력할 문자열이 없으면 null을 반환하죠.

그래서 null을 만나게 되면 while루프를 탈출합니다.

이제 실행후 파일과 이클립스화면을 보면 둘의 결과는 같다는 것을 알 수 있습니다.

test.txt

이클립스 실행결과

어떻습니까?

BufferedReader와 BufferedWriter 정말 편리하죠?

이 두 클래스는 조금 빈번하게 쓰입니다. 기억해두세요.

아직 파일입출력에 대해서는 더 할 이야기가 나왔습니다. 나중에 더 이야기 해보도록 하지요.

안녕하세요. 이번 시간에는 클래스 중 조금 특별한 속성을 갖고 있는 추상 클래스(Abstract Class)와 자바에서 등장하는 인터페이스(Interface)에 대해서 알아보는 시간을 갖도록 하겠습니다.

추상클래스(Abstract Class)

이름부터가 아주 비호감입니다. 저는 추상이라는 단어를 무척이나 싫어하거든요.

뭔가 있는 듯 없는 듯하면서도.. 만질수 있을 듯 없을 듯하면서도.. 볼수 있을듯 없을 듯한 그 거시기한 거.. 그런건데

아주아주 간단히 말해서 추상메소드가 적어도 0개 있는 클래스가 추상클래스라고 합니다.

장난하냐? 그러지 마시고 일단 추상 메소드가 무엇인지 말씀 드리고 시작하겠습니다.

추상클래스는 메소드의 선언만 되어있을 뿐 정의는 되어있지 않은 것을 말합니다. 몸통이 없다는 것이죠.

몸통이 없이 메소드의 선언만 존재하는 것이 추상 메소드이며 추상 메소드를 0개 이상 갖는다면 추상클래스이다 라고 말할 수 있겠네요. 

0개 이상이라는 말은 추상메소드를 갖지 않아도 추상 클래스가 될 수 있다는  것인데, 이렇게 되면 보통의 클래스를 의미하기 때문에 보통은 한개 이상 추상 메소드를 갖는다면 추상 클래스라고 합니다.

아래와 같이 사용합니다. 우선 추상클래스를 정의하려거든 class앞에 abstract라는 키워드를 붙여줍니다.

추상메소드 역시 마찬가지입니다. abstract 키워드를 붙이고 메소드 구현부만 없으면 됩니다. 

abstract class AbstractClass{
	int x;
	public void NormalMethod() {}
	public abstract void AbstractMethod(); 
}

보통의 클래스와의 차이점은 객체를 직접생성할 수 없다는 점입니다.

그래서 이 추상 클래스를 상속받아 그 상속받은 클래스의 객체로 생성해야합니다. 또는 다형성의 성질을 이용할 수 있지요.

사용법은 아래의 코드와 같습니다.

abstract class Animal{
	public void seeFood() {
		System.out.println("내가 음식을 봤을 때");
	}
	abstract public void cry();
}

class Dog extends Animal{

	@Override
	public void cry() {
		System.out.println("왈!! 왈왈!! 왈왈~!!! 왈월워뤙왈!!! 멍멍!");
	}
	
}

class Cat extends Animal{

	@Override
	public void cry() {
		System.out.println("야옹~~ 옹옹오오오오오옹~~~~~~ 야오우오우오우옹~~~~");
	}
	
}
public class Main {

	public static void main(String[] args) {
		Animal dog=new Dog();
		dog.seeFood();
		dog.cry();
		
		System.out.println();
		
		Animal cat=new Cat();
		cat.seeFood();
		cat.cry();
	}
}

Animal을 상속받은 클래스 Dog와 Cat은 무조건 abstract의 메소드를 오버라이딩해주어야 합니다. 그렇지 않으면 Animal클래스를 상속할 수 없습니다.

결과는 어떻게 될까 예상이 되시나요?

여기서 추상클래스와 비슷한 인터페이스(Interface)를 소개합니다.

인터페이스(Interface)

인터페이스는 명세라고도 불리는데요. 추상클래스의 가장 극단적인 형태라고 보면 됩니다. 

인터페이스는 전부가 추상메소드로 이루어져 있습니다.

자신의 변수도 쓸수 없고 오로지 메소드의 선언만이 있어야합니다.

아래처럼 말이죠.

interface Interface {
	public void method1();
	public void method2();
}

마치 추상클래스로 표현하자면 이렇게 표현할 수도 있겠네요.

abstract class Interface{
	public abstract void method1(); 
	public abstract void method2(); 
}

인터페이스의 사용 예제는 아래와 같습니다.

interface Animal {
	public void cry();
	public void sleep();
}

class Dog implements Animal{

	@Override
	public void cry() {
		System.out.println("왈!! 왈왈!! 왈왈~!!! 왈월워뤙왈!!! 멍멍!");
	}
	@Override
	public void sleep() {
		System.out.println("자신의 집에서 잠을 잡니다.");
	}
	
}

class Cat implements Animal{

	@Override
	public void cry() {
		System.out.println("야옹~~ 옹옹오오오오오옹~~~~~~ 야오우오우오우옹~~~~");
	}
	@Override
	public void sleep() {
		System.out.println("집사 얼굴 위에서 잠을 잡니다.");
	}
	
}
public class Main {

	public static void main(String[] args) {
		Animal dog=new Dog();
		dog.cry();
		dog.sleep();
		
		System.out.println();
		
		Animal cat=new Cat();
		cat.cry();
		cat.sleep();
	}
}

Dog와 Cat은 Animal 인터페이스를 implements하고 있습니다. 근데, 이제까지 봐왔던 extends가 아니군요. 그 이유는 아래에서 설명하도록 하겠습니다.

결과는 이렇게 됩니다.

추상클래스 VS 인터페이스

한가지 중요한건 이 둘의 차이에 대해서 알아야합니다.

추상클래스는 역시 클래스입니다. 단독으로 객체를 생성할 수만 없지 나머지는 보통의 클래스처럼 생성자, 변수, 메소드를 갖고 있을 수 있습니다. 그렇기 때문에 자식 클래스에서는 변수나 구현된 메소드를 물려받기 때문에 상속(extends)받을 수 있는 것이죠.

인터페이스 역시 직접 객체를 생성할 수 없습니다. 구현되어야 할 메소드만 명시해 놓고 인터페이스를 받는 클래스는 그 인터페이스에 맞는 메소드를 구현해야합니다. 그렇기 때문에 implements(구현하다)라는 키워드로 인터페이스를 전달받을 수 있지요.

클래스와는 다르게 여러개의 인터페이스를 클래스가 구현할 수 있습니다. 클래스로 따지자면 다중상속과 비슷한 개념입니다.

자바는 다중상속을 지원하지 않지만 다중 인터페이스를 통한 상속은 지원하지요.

interface Calculator{
	public int sum(int a,int b);
	public int subtraction(int a,int b);
}

이제 왜 인터페이스는 implements를 써서 받고, 추상클래스는 extends를 써어 받는 지 차이점을 알겠죠?

다형성(Polymorphism)

다형성이라는 개념은 OOP에서 아주 중요한 개념이므로 모르면 OOP에 대해서 제대로 안다고 할 수 없는 개념입니다.

각 요소들이 여러 가지 자료형으로 표현될 수 있다는 것을 말하게 되는데, 반댓말로는 단형성이 있습니다. 한가지의 요소는 한가지의 형태로만 매칭된다는 것을 의미합니다.

음... 일단 모르겠어요.. 다형성이 정확히 무엇인지.

암튼 뭐.. 앞에 '다'라는 의미는 '많은 다(多)' 자가 아니겠어요?? 뭔가 여러가지 (자료)형을 말하는 것 같은데 클래스를 만들어가면서 알아보도록 하지요.

여기 People이라는 클래스가 있습니다. 아주 간단하게 정의한 클래스죠. 그 안에는 printInfo라는 멤버메소드가 있군요.

class People{
	
	public void printInfo() {
		System.out.println("나는 사람입니다.");
	}
}

People 클래스에서 printInfo를 호출하게 되면 지가 사람이라는 군요.

그 밑에 Man과 Woman 클래스는 People클래스를 상속합니다.

class Man extends People{}
class Woman extends People{}

이후 메인에서는 이 두 클래스를 객체로 만들어 printInfo를 호출합니다. 

public class Test {

	public static void main(String[] args) {
		Man man=new Man();
		Woman woman=new Woman();
		
		man.printInfo();
		System.out.println();
		woman.printInfo();
	}
}

이후 실행을 하게 되면 아래의 결과가 나오게 되겠죠.

두 클래스 Man과 Woman은 People이라는 클래스를 상속받았으므로 printInfo 호출시 People의 printInfo를 호출할 수 있다는 것, 뭐 놀랍지 않군요.

이제 이것을 토대로 다형성을 세세하게 알아보도록 합시다.

Woman, Man은 People이다

UML 다이어그램으로 본다면 위의 그림과 같을 겁니다.

Man과 Woman은 People이라는 클래스를 상속하기 때문이에요.

우리는 이 다이어그램을 이런 관점으로 한번 바라볼 수 있을까요?

현실 세계에서 이 다이어그램을 말로 풀어보아도 그 의미가 맞습니다.

그 반대는 어떨까요?

사람은 남자인가요? 아니면 사람은 여자인가요?

그렇지 않습니다. 사람은 남자인지, 여자인지 알 수가 없습니다.

그렇기 때문에 반대로 표현하면 모호해진다는 것을 알 수 있지요.

여기서 중요한 점은 Man은 People로 표현할 수 있고, Woman도 People로 표현할 수 있다는 것입니다.

이것이 다형성의 개념이 나오게 됩니다. Man과 Woman은 People이기 때문에 People이라는 자료형으로 받을 수 있습니다.

한번 확인해볼까요?

public class Test {

	public static void main(String[] args) {
		People people=new Man();
		
		people.printInfo();
		System.out.println();
		
		people=new Woman();
		people.printInfo();
		
	}
}

실행을 시켜서 확인해보면 위의 결과와 동일한 것을 알 수 있습니다. 

Man과 Woman은 People(부모클래스)로 받을 수 있다는 점을 기억하세요!

다형성과 오버라이딩

여기서 Man과 Woman은 printInfo를 물려받았고 오버라이딩(Overriding)할 수 있다는 것을 알고 있습니다.

그래서 저는 Man과 Woman의 printInfo를 그 클래스에 맞도록 오버라이딩하고 싶습니다. Man과 Woman 클래스를 다음과 같이 수정해보도록 하지요.

class Man extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 남자입니다.");
	}
	
}
class Woman extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 여자입니다.");
	}
}

그리고 실행해본다면 

오버라이딩된 printInfo를 호출한다는 것을 알 수 있습니다. 오...

다형성에서 People은 자식클래스에서 재정의된 메소드를 호출할 수 있다는 것입니다.

그렇다면 Woman과 Man에서 단독으로 정의한 메소드는 어떻게 될까요?

Man과 Woman클래스에서 다음과 같이 메소드를 추가해보도록 합시다.

class Man extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 남자입니다.");
	}
	
	public void enlist() {
                System.out.println("내일 군대를 갑니다.");
		System.out.println("충성!");
	}
	
}
class Woman extends People{
	@Override
	public void printInfo() {
		super.printInfo();
		System.out.println("그리고 나는 여자입니다.");
	}
	
	public void makeUp() {
                System.out.println("예뻐질 거랍니다.");
		System.out.println("톡톡 촵촵!");
	}
}

그리고 people.enlist를 호출하려한다면 호출이 되지 않습니다. 왜냐하면 People 형이기 때문이죠. People 클래스는 enlist라는 메소드를 갖지 않기 때문에 호출할 수 없습니다.

이런 경우에는 데이터 형에 맞게 캐스팅해주어서 사용해야합니다.

바로 아래처럼요.

public class Test {

	public static void main(String[] args) {
		People people=new Man();
		people.printInfo();
		((Man)people).enlist();
		
		System.out.println();
		
		people=new Woman();
		people.printInfo();
		((Woman)people).makeUp();
		
	}
}

왜 그런걸까요?

People은 자신을 상속한 클래스 중에서 어떤 매소드를 만들지, 어떤 멤버 변수를 만들어낼지 미리 알아낼 수 없기 때문이죠.

때문에 그 메소드가 있는 객체로 직접 캐스팅해주어서 매소드를 사용해야합니다.

이해를 돕기 위한 그림이 아래에 있습니다. People이라는 자료형이 사용가능한 메소드는 printInfo밖에 없습니다. 그래서 Man의 printInfo메소드를 사용할 수 있습니다. 

또한 new가 동적 메모리를 할당하는 역할을 하므로 Man이 실제 메모리에 잡히게 됩니다. 따라서 형변환을 Man으로 하는 것이 가능한 것이죠.

이와 같은 다형성은 어디에서 쓰일까요?

대표적으로 메소드에서 매개변수로 People을 상속하는 클래스를 받을때 사용할 수 있습니다. 

        public static void func(People people) {
		people.printInfo();
	}
	public static void main(String[] args) {
		Man man=new Man();
		Woman woman=new Woman();
		func(man);
		
		System.out.println();
		func(woman);
	}

func의 매개변수 people은 People의 객체이기 때문에 그것을 상속하는 모든 클래스를 받아 낼 수 있어요.

그래서 Object 객체로 모든 객체를 받을 수 있는 것도 바로 이러한 다형성의 속성때문입니다. 

또한 필요에 의해서는 instanceof 연산자를 사용해서 캐스팅할 수 있습니다.

        public static void func(People people) {
		people.printInfo();
		if(people instanceof Man) 
			((Man)people).enlist();
		if(people instanceof Woman)
			((Woman)people).makeUp();
		
	}
	public static void main(String[] args) {
		Man man=new Man();
		Woman woman=new Woman();
		func(man);
		
		System.out.println();
		func(woman);
	}

다익스트라 알고리즘 (Dijkstra Algorithm)

최단거리를 구하는 데에는 꽤 여러가지 알고리즘이 존재합니다. 그 중에서 가장 유명한 알고리즘, 다익스트라 알고리즘에 대해서 알아보도록 하겠습니다.

다익스트라 알고리즘은 무엇일까요?

그래프의 한 정점에서 모든 정점까지의 최단 거리를 구하는 것이 이 알고리즘입니다. 

우선 아래와 같은 그래프가 있다고 가정해볼게요.

정점 0에서 모든 정점까지의 최단거리는 어떻게 될까요?

0번에서부터 5번 정점 중 임의의 i까지 최단 거리를 dist[i]라고 할때

가 됩니다.

이와 같이 어떤 시작점을 정해서 그 정점부터 다른 정점까지의 최단거리를 구하는 알고리즘이 바로 단일 시작점 알고리즘이고, 대표적인 알고리즘이 바로 다익스트라 알고리즘입니다.

BFS 최단거리 기반

이 알고리즘은 최단 거리를 구하는 것이기 때문에 BFS를 기반으로 움직이는데요. BFS는 자료구조에서 큐를 썼었죠? 따라서 다익스트라 알고리즘 역시 큐를 사용하여 구현할 수 있다는 사실을 알아두세요.

주의 사항은 위의 그래프가 나타내는 것처럼 음수간선이 있으면 다익스트라 알고리즘을 쓸 수가 없어요.

다익스트라 구현 (C++)

코드로 다익스트라 알고리즘을 살펴본 후 설명하도록 하겠습니다.

#include <vector>
#include <iostream>
#include <queue>

#define MAX_V 100
#define INF 99999999
using namespace std;


vector<pair<int, int> > adj[100];
vector<int> dijkstra(int start, int V) {
	vector<int> dist(V, INF);
	dist[start] = 0;
	priority_queue<pair<int, int> > q;
	q.push(make_pair(0, start));

	while (!q.empty()) {
		int cost = -q.top().first;
		int from = q.top().second;
		q.pop();

		if (dist[from] < cost) continue;

		for (int i = 0; i < adj[from].size(); i++) {
			int to = adj[from][i].first;
			int distFromTo = cost + adj[from][i].second;
			if (distFromTo < dist[to] ) {
				dist[to] = distFromTo;
				q.push(make_pair(-distFromTo, to));
			}
		}
	}
	return dist;
}

int main(int argc, char **argv)
{
	int E, V;
	printf("[input] vertex edge :");
	scanf("%d %d", &V, &E);

	
	for (int i = 0; i < E; i++) {
		printf("[input] from to cost :");
		int from, to, cost;
		scanf("%d %d %d", &from, &to, &cost);
		adj[from].push_back(make_pair(to, cost));
		adj[to].push_back(make_pair(from, cost));
	}

	printf("===dijkstra===\n");
	vector<int> dist = dijkstra(0, V);
	for (int i = 0; i < V; i++) {
		printf("from 0 to %d : %d\n", i, dist[i]);
	}
	return 0;
}

우선 입력을 받습니다. 위의 그래프 모양 그대로 입력을 받습니다. 위의 그래프를 조금 더 편하게 입력받으려면 아래의 input을 복사해서 붙여넣으세요.

이후 dijkstra가 어떻게 동작하는 지 그림을 보며 살펴보도록 합시다.

우선 우리가 반환한 dist의 벡터 사이즈를 V의 크기(정점의 개수)로 정하고 그 값을 아주 큰 값으로 설정합니다.

자기 자신과의 거리는 0이므로 dist[start]는 0으로 셋팅합니다.

여기서는 priority queue를 사용하는데요. 그 이유는 정점으로부터 가장 작은 값으로 연결되어 있는 정점을 꺼내는 것이 더 효율적이니까 그렇습니다.

또한 priority queue는 pair를 통해서 우선 순위를 정할때 첫번째 요소를 기준으로 가장 큰 값을 먼저 꺼내옵니다. 그래서 첫번째 요소를 거리, 그것도 -를 붙여서 넣어주면 값이 큰 간선으로 연결된 정점이 더 나중에 나오게 되는 것이죠.

그래서 꺼내올때 -를 붙여서 꺼내오고 -를 붙여서 집어 넣습니다.

이제 그림으로 더 쉽게 보도록 합시다.

우선 초기상태는 자기 자신의 정점을 우선순위 큐에 push하며 그 거리는 0이 됩니다. while루프를 돌기 전의 모습입니다. 

그 후 첫 while 루프를 돌면서 큐에 저장된 (0,0)을 가져옵니다. 0은 dist[0]보다 작지 않기 때문에 if문에 걸리지 않고 for루프를 돌게 됩니다. 주변에 가장 작은 값으로 연결된 정점은 2, 1, 3이지요. 그래서 그에 대응되는 거리 2, 3, 5와 함께 우선 순위 큐에 저장합니다. 

하지만 우선순위 큐는 큰 값이 먼저 선정되기 때문에 음수를 붙여서 -2,-3,-5로 바꾸어서 넣어줍니다.

** 아래 그림에서 잘못된 것이 있는데 우선순위 큐에 푸시되는 값은 (-2,2) (-3,1) (-5,3)인것으로 정정해주세요. 죄송해요.

우선순위 큐에서 2를 꺼내올때 이미 dist[2]는 2로, dist[2]보다 2가 더 작지 않으므로 if 조건문에 걸려 continue됩니다.

이 후 (-3, 1)을 꺼내옵니다. 정점 1에서 연결된 정점 중 가장 가까운 정점은 4입니다. 그렇기 때문에 dist[4]를 12로 수정하고 이 정보를 우선순위 큐에 저장합니다.

이제 (-5,3)을 꺼내올 차례이군요. dist[3]은 5이고, 큐에서 꺼내온 값 역시 5이므로 if문에 걸리지 않고 for루프를 돕니다. 이제 3에 연결되어 있는 정점은 4로 연결된 cost가 1인 간선입니다. 그래서 그전에 있던 dist[3]과 4로 연결된 간선의 cost 1을 더한 값(6)과 dist[4]와 연결된 값과 비교해보니 6이 더 작으므로 dist[4]=6으로 갱신하고 (-6,4)를 큐에 집어 넣습니다.

여기서 우선순위 큐를 사용하는 이유가 나옵니다. 만일 순서를 고려하지 않고 (-5, 3)이 큐에 맨 끝에 위치해있다면 이러한 갱신을 맨끝에 하게 되어 for루프를 돌게 되는 시간적인 낭비가 있게 되는 겁니다. 

그렇기 때문에 가장 비용이 낮은 것이 먼저 나오는 것이 유리하다는 것이죠.

다음 (-15,4)는 cost가 15이기 때문에 if조건에 걸려 continue됩니다. 

남은 (-6, 4)를 꺼내오게 되면 if조건문에 걸리지 않고 for루프를 돌아요. 4와 연결된 정점 5까지의 비용은 dist[4]와 3을 더한 9가 됩니다. 왜냐하면 dist[5]는 아주 큰 값이기 때문에 6이 더 작잖아요?

그 후 5와 연결된 간선의 정보를 큐에 저장합니다.

이제 마지막 (-9, 5)를 꺼내오는데, 이미 dist[5]=9이므로 if 조건에 걸려 continue됩니다. 이 후에는 큐가 비었으므로 while문을 탈출하게 되지요.

이제 모든 거리를 구했습니다.

코드에서는 0을 기준으로 구했는데 코드를 바꾸어서 1부터 시작해서 최단거리를 구해보세요. 그리고 비교해보세요.

시그널에 대한 더 많은 정보를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

시그널

의미전달에 사용되는 대표적인 방법은 메세지와 신호입니다. 메세지는 여러가지 의미를 갖을 수 있지만 복잡한 대신 , 신호는 1:1로 의미가 대응되기 때문에 간단합니다. 컴퓨터에서 신호, 즉 시그널은 소프트웨어적인 interrupt입니다. 컴퓨터 용어에서 인터럽트라는 것은 하던일 A를 중간이 잠시 멈추고 다른일 B를 하고 난 후 다시 A로 돌아와서 멈춘 부분부터 일을 하는 것이죠.  자, 이 의미를 명확히 아셔야할 필요가 있습니다. 신호가 왜 SW적인 인터럽트인가가 포스팅 아래에 코드와 함께 설명이 됩니다.

우선 컴퓨터에서 시그널의 종류에는 어떤 것들이 있을까요? 리눅스 상에서 kill -l 명령어를 입력하면 모든 시그널의 종류와 대응되는 번호를 알 수 있습니다.

#kill -l

 

 1) SIGHUP       2) SIGINT       3) SIGQUIT      4) SIGILL       5) SIGTRAP

 6) SIGABRT      7) SIGBUS       8) SIGFPE       9) SIGKILL     10) SIGUSR1

11) SIGSEGV     12) SIGUSR2     13) SIGPIPE     14) SIGALRM     15) SIGTERM

16) SIGSTKFLT   17) SIGCHLD     18) SIGCONT     19) SIGSTOP     20) SIGTSTP

21) SIGTTIN     22) SIGTTOU     23) SIGURG      24) SIGXCPU     25) SIGXFSZ

26) SIGVTALRM   27) SIGPROF     28) SIGWINCH    29) SIGIO       30) SIGPWR

31) SIGSYS      34) SIGRTMIN    35) SIGRTMIN+1  36) SIGRTMIN+2  37) SIGRTMIN+3

38) SIGRTMIN+4  39) SIGRTMIN+5  40) SIGRTMIN+6  41) SIGRTMIN+7  42) SIGRTMIN+8

43) SIGRTMIN+9  44) SIGRTMIN+10 45) SIGRTMIN+11 46) SIGRTMIN+12 47) SIGRTMIN+13

48) SIGRTMIN+14 49) SIGRTMIN+15 50) SIGRTMAX-14 51) SIGRTMAX-13 52) SIGRTMAX-12

53) SIGRTMAX-11 54) SIGRTMAX-10 55) SIGRTMAX-9  56) SIGRTMAX-8  57) SIGRTMAX-7

58) SIGRTMAX-6  59) SIGRTMAX-5  60) SIGRTMAX-4  61) SIGRTMAX-3  62) SIGRTMAX-2

63) SIGRTMAX-1  64) SIGRTMAX

1. SIGHUP : 터미널과 연결이 끊겼을 때 발생합니다. 기본적인 처리는 프로세스가 종료되는 것입니다.

2. SIGINT : 인터럽트가 발생했을때 발생합니다. 기본으로 프로세스가 종료됩니다.

9. SIGKILL : 프로세스를 무조건 종료합니다. 절대 무시할 수 없으며 제어될 수도 없습니다.

11. SIGSEGV : 프로세스가 잘못된 메모리를 참조했을 때 발생합니다. 기본 동작은 코어덤프를 남기고 종료합니다.

19 SIGSTOP : 프로세스를 중단시킵니다. 종료한 상태는 아닙니다. 이 신호 역시 제어될 수 없습니다.

#include <signal.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
int main(){
        printf("give signal...\n");
        sleep(30);
        exit(0);
}

이후 컴파일을 하여 실행파일로 만들어줍니다. 이후 실행하면 30초간 프로그램이 실행될 겁니다.

이 상태에서 Ctrl+C를 누르게 되면 SIGINT 신호를 보내게 됩니다. 기본동작은 종료이므로 프로세스가 종료하게 됩니다.

또는 kill -시그널번호 프로세스 id 를 통해서 시그널을 보낼 수 있습니다. 그러니까 SIGINT를 보내려면 kill -2 pid 또는 kill -SIGINT pid를 통해서 SIGINT보낼 수 있습니다.

# ./a.out

give signal...

^C

#

void (*signal(int signum, void (*handler)(int)))(int);

signum은 시그널을 발생시키는 번호입니다. 아까 SIGINT는 2번이었죠?? 아니면 매크로를 쓸수도 있습니다. SIGINT 그대로가 매크로로 정의되어 있습니다.

두번째 인자로 handler라는 함수포인터가 보이네요. 여기에 함수를 인자를 주게 되면 시그널을 받았을때 그 함수가 호출됩니다.

직접 코드로 짜고 확인해보지요.

#include <signal.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void interruptHandler(int sig){
        printf("this program will be exited in 3 seconds..\n");
        sleep(3);
        exit(0);
}

int main(){
        signal(SIGINT, interruptHandler);
        printf("input Ctrl+C\n");
        while(1);
}

컴파일하고 실행 후에 Ctrl+C를 입력하면 메시지와 함께 3초 후 프로그램이 종료됩니다.

# ./a.out 
input Ctrl+C
^Cthis program will be exited in 3 seconds..

이번엔 SIGTSTP이라는 시그널을 보내보도록 할게요. 위 코드에서 단지 SIGINT를 SIGTSTP이라고 바꿔주기만 하면 됩니다. (아, 물론 printf안에 문자열도 바꾸면 이쁘장하겠죠?)

#include <signal.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
void stopHandler(int sig){
        printf("this program will stop in 3 seconds..\n");
        sleep(3);
        exit(0);
}

int main(){
        signal(SIGTSTP, stopHandler);
        printf("input Ctrl+Z\n");
        while(1);
}

그후 Ctrl+Z를 입력하여 SIGTSTP을 보내면 적절히 핸들링이 되는 것을 확인할 수 있습니다. 

# ./a.out 
input Ctrl+Z
^Zthis program will stop in 3 seconds..

그렇다면 SIGSTOP은 어떨까요? 아래의 코드는 SIGSTOP을 핸들링하기 위한 코드입니다. 

#include <signal.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

void stopHandler(int sig){
        printf("this program will stop in 3 seconds..\n");
        sleep(3);
        exit(0);
}

int main(){
        signal(SIGSTOP, stopHandler);
        printf("wait\n");
        pause();
}

a.out에 kill을 통해서 SIGSTOP을 보내기 위해서 잠시 백그라운드로 돌립니다. /proc/92089/status에는 92089에 대한 프로세스 정보들이 나와있습니다. 현재 State는 Speeping, 즉, 우리가 pause를 했기 때문에 이러한 상태가 되는 것입니다. Kill 명령으로 SIGSTOP(19)를 그 PID로 보내게 되면 어떻게 될까요?

# ./a.out &
[2] 92089
# wait <-- a.out 프로그램에 의한 출력
# cat /proc/92089/status | head -5
Name:   a.out
Umask:  0022
State:  S (sleeping)
Tgid:   92089
Ngid:   0
# kill -19 92089
# cat /proc/92089/status | head -5
Name:   a.out
Umask:  0022
State:  T (stopped)
Tgid:   92089
Ngid:   0

[2]+  Stopped                 ./a.out

시그널을 보내고 다시 상태를 확인해보면State가 T인 stop 상태인 것을 확인할 수 있습니다. 여기서 알 수 있는 것은 SIGSTOP은 제어할 수 없다는 것을 보여줍니다.

위에서 SIGSTOP 설명을 보고 오세요. 제어할 수 없다는 설명이 있습니다. SIGKILL과 SIGSTOP은 사용자가 절대 제어할 수 없다는 점을 알고 있으세요~! 그 이유는 어떤 이유로 인해 프로세스를 무조건 죽여야하는 경우가 있습니다. 만약 좀비프로세스를 계속해서 생성하는 프로세스가 있는데, 이 프로세스를 죽이지 못하면 안되겠죠. 그래서 2개는 핸들링을 하지 못합니다.

또한 핸들러에 전달인자 sig는 시그널의 종류를 나타냅니다. 그렇기 때문에 시그널의 종류에 따라 처리할 수 있죠.

#include <signal.h>
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>

void signalHandler(int sig){
        if(sig==SIGINT){
                printf("this program will stop in 3 seconds..\n");
                sleep(3);
                exit(0);
        }
        if(sig==SIGQUIT){
                printf("signal SIGQUIT\n");
        }
}

int main(){
        signal(SIGINT, signalHandler);
        signal(SIGQUIT, signalHandler);
        printf("input Ctrl+C or Ctrl+\\ \n");
        while(1);
}

프로그램을 실행하여 Ctrl+\를 입력해서 SIGQUIT신호를 보내도 종료하지 않고, Ctrl+C를 입력하여 SIGINT를 보냈을 때 3초안에 종료합니다.

# ./a.out

input Ctrl+C or Ctrl+\

^\signal SIGQUIT

^\signal SIGQUIT

^\signal SIGQUIT

^\signal SIGQUIT

^Cthis program will stop in 3 seconds..

SW적인 Interrupt

중간에 멈추고 다른일을 하고 다시 돌아와 아까 했던일을 처리하는것이 인터럽트라고 하였습니다. 아래의 코드가 있습니다. SIGINT와 SIGQUIT을 처리하는 함수 2개가 있죠.

#include <stdio.h>
#include <unistd.h>
#include <signal.h>
#include <setjmp.h>
#include <stdlib.h>

void sig_int(int signo){
        volatile int k=0;
        int i,j;
        printf("sig_int start\n");

        for(i=0;i<300;i++)
                for(j=0;j<600000;j++)
                        k+=i*j;

        printf("sig_int end\n");
}

void sig_quit(int signo){
        volatile int k=0;
        int i,j;
        printf("sig_quit start\n");

        for(i=0;i<300;i++)
                for(j=0;j<600000;j++)
                        k+=i*j;

        printf("sig_quit end\n");
}
int main(){
        signal(SIGINT, sig_int);
        signal(SIGQUIT, sig_quit);
        //pause는 신호가 생기고 처리될때까지 대기하는 함수
        pause();
        printf("process end\n");
}

저는 SIGINT와 SIGQUIT 순서대로 시그널을 줄겁니다. for문을 도는 이유는 SIGINT가 끝나기 전에 SIGQUIT을 수행하기 위해서 시간 지연을 하는 역할을 합니다. 그럴때 결과를 여러분들이 예측해보세요.

아래와 같은 결과일까요? SIGINT를 처리하고 나서 SIGQUIT을 처리하니까요. 

^Csig_int start
^\sig_quit start
sig_int end
sig_quit end
process end

땡! 아래의 결과처럼 나오게 됩니다. 

^Csig_int start
^\sig_quit start
sig_quit end
sig_int end
process end

SIGINT신호가 발생되어 신호 처리부인 sig_int 수행합니다. for문을 도는 도중에 SIGQUIT 신호가 발생해서 sig_quit을 수행하러 갑니다. 그럼 sig_int는 sig_quit가 처리가 다 되고 나면 나중에 멈췄던 부분부터 다시 수행한다는 겁니다. 이런 사실을 망각하게 되면 아주 어려운 버그를 만날수가 있지요. 

느린 시스템 콜에서의 시그널

여기서부터는 라이브러리 함수가 아닌 시스템 콜과 시그널에 대해서 이야기합니다. 그 중에서도 반환이 느린 시스템 콜에 대해서 이야기합니다. 만약 read하는 동안 signal이 발생했다면 어떻게 될까요?

#include <signal.h>
#include <stdio.h>
#include <unistd.h>

void sig_int(int signo){
        printf("SIGINT 발생!\n");
}
int main(){
        char buf[32];
        int n;

        signal(SIGINT, sig_int);
        //읽는 중 SIGINT를 발생 시키면 오류? 아니면 성공?
        if((n = read(STDIN_FILENO, buf,32)) < 0){
                printf("read error\n");
        }else{
                buf[n]='\0';
                printf("%s\n",buf);
        }
}

위의 코드를 리눅스 상에서 실행을 시키고 난 후 아래와 같이 실행시켜보았습니다. 

# ./a.out
^CSIGINT 발생!
^CSIGINT 발생!
hello^CSIGINT 발생!
reakwon
reakwon

read를 하는 와중에 SIGINT를 발생시켰는데 오류가 발생하지 않고 처음부터 다시 read를 하는 것처럼 보이는데요. 이렇게 리눅스에서는 read와 같은 대기 시간이 길어가 수행시간이 긴 시스템 콜이 발생할때 자동으로 그 시스템 콜을 재시작하게 됩니다. 그러므로 hello는 출력이 되지 않고, reakwon만 출력이 되는거죠. 재시작한다는 것이 중요한 포인트입니다. 

read뿐만 아니라, 느린 호출에 해당되는 ioctl, read, readv, write, writev, wait, waitpid가 있습니다. 

이런 재시작 처리 방식은 시스템마다 다른데요. SVR2, SVR3, Solaris 등의 시스템은 자동 재시작하지 않고 errno를 EINTR로 설정한 후 반환시킵니다. 그래서 프로그래머는 아래와 같이 errno를 검사하며 프로그래밍해야됩니다. 하지만 우리는 리눅스를 만지는 중이니까 이런 처리를 할 필요는 없죠. 

retry :
        if ((n = read(fd, buf, BUF_SIZE)) < 0){
                if(errno == EINTR){
                        goto retry:
                }
        }else{
                printf("%s\n",buf);
        }

이처럼 리눅스 신호의 대한 개념과 시그널을 어떻게 잡아서 다룰 수 있는지에 대해서 알아보는 시간을 가졌습니다.

더 많은 정보를 담은 리눅스 교재를 배포했습니다. 아래의 페이지에서 리눅스 교재를 받아가세요.

https://reakwon.tistory.com/233

프로세스(process)

프로세스는 간단히 말하자면 실행 중인 프로그램을 의미합니다. 아마 여러분들은 컴퓨터를 하면서 아주 빈번하게 듣는 용어이기도 합니다.

실행 중인 프로그램이라??

컴퓨터에서 말하는 실행 중인 프로그램이라는 건 저장공간에 있는 실행 파일이 메모리를 할당받아 명령어를 수행한다는 것을 의미합니다.

우리가 예를 들어 한글이라는 프로그램을 설치했다고 가정합시다. 아직은 더블클릭으로 프로그램을 실행하지 않았으므로 프로세스가 아닙니다. 설치 후 보고서를 작성하기 위해 프로그램을 실행한다면 그 순한 한글이라는 프로세스가 생성되는 것입니다.

프로세스에서 프로세스를 생성할 수도 있습니다. 이 경우 생성한 프로세스는 부모 프로세스, 생성당한 프로세스를 자식프로세스라고 합니다.

코드 영역(혹은 텍스트 영역이라고도 함) : 프로세스의 명령어가 존재합니다. CPU는 이 영역에서 명령을 실행합니다. 위 그림에서는 부모 자식 프로세스간 별개로 텍스트 영역이 존재하는 것처럼 보이지만 실제로 코드영역은 프로 자식 프로세스간 공유가 됩니다.

 

데이터 영역 : 전역 변수와 정적 변수가 존재합니다. 프로그램이 실행하는 동시에 할당되고 종료시 소멸됩니다.

 

힙 영역 : 동적할당에 필요한 메모리입니다. 프로그램 종료시 해제되지 않고 직접 해제해 주어야 합니다. C언어에서는 free를 사용해서 해제하게 됩니다. 

 

스택 영역 : 함수 호출 시 매개변수, 지역변수가 이 곳에 자리잡게 됩니다. 함수가 종료하게 되면 해제됩니다.

자식 프로세스를 생성하는 시스템 콜이 fork라고 합니다. fork는 자기 자신을 복사합니다만 결국 다른 별도의 메모리를 갖게 됩니다. 그래서 자식 프로세스에서 변수의 값을 바꾸어도 부모 프로세스에 영향을 주지 않게 되죠.

자식 프로세스 생성(fork)

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>

int g_var = 1; 
char buf[] = "a write to stdout\n"; 

int main(){ 
        int l_var; 
        pid_t pid; 
        l_var = 10; 

        if(write(STDOUT_FILENO,buf,sizeof(buf)-1) != sizeof(buf)-1){ 
                printf("write error\n"); exit(0); 
        } 

        printf("fork start!\n"); 

        //fflush(stdout); 
        if((pid = fork())<0){ 
                printf("fork error\n"); 
                exit(0); 
        } else if(pid == 0){ 
                //child 
                g_var++; 
                l_var++; 
        } else { 
                //parent sleep(3); 

        } 

        printf("pid = %ld, g_var = %d, l_var = %d\n",
                        (long)getpid(),g_var,l_var); 

        exit(0); 
}

 # gcc fork.c 
 # ./a.out
 a write to stdout
 fork start!
 pid = 83929, g_var = 2, l_var = 11
 pid = 83928, g_var = 1, l_var = 10

 # ./a.out > fork.out
 # cat fork.out
 a write to stdout
 fork start!
 pid = 83960, glob = 2, var = 11
 fork start!
 pid = 83959, glob = 1, var = 10

고아 프로세스

프로세스를 생성하기만 하면 다가 아닙니다. 왜 그런지 실행과 결과를 보면서 이야기 하도록 하지요.

#include <stdio.h> 
#include <unistd.h> 
#include <stdlib.h> 

int main(){ 
        int pid; 

        if((pid=fork()) == 0){ 
                sleep(1); 
                printf("\t [child process %d] created from %d\n", getpid(),getppid());
                exit(0); 
        } 

        printf("[parent process %d] create %d process, ppid:%d\n", getpid(),pid,getppid()); 

}

getpid : 현재 프로세스의 pid를 반환합니다. 

getppid : 부모의 프로세스 id를 반환하지요.

이 코드의 결과를 예상해보세요.

자식 프로세스에서는 부모의 프로세스 ID를 출력하니까 부모의 getpid와 같을 겁니다. 그럴까요??

[parent process 21162] create 21163 process, ppid:20819

[child process 21163] created from 1

????

우리의 예상과는 다른데요??

분명 부모프로세스의 pid는 21162인데 자식 프로세스의 부모프로세스 pid가 쌩뚱맞은 1입니다.

왜 그럴까요??

우선 이 코드는 문제가 좀 있는 코드입니다. 부모프로세스가 먼저 종료되었기 때문입니다.  자식이 먼저 종료된다는 사실을 확보하기 위해 1초를 기다리는 이유가 바로 이 사실을 확인하기 위해서 입니다.  자식 프로세스는 부모 프로세스를 잃어 다른 부모를 찾게 됩니다. 바로 init 프로세스라고 하는데요. init프로세스의 pid가 바로 1입니다.

그러니까 모든 프로세스의 선조가 init프로세스라는 이야기죠.

이런 프로세스를 부모를 잃었다고 하여 고아프로세스가 됩니다.

그렇기 때문에 모든 부모님이 그렇듯 자식을 기다려주어야합니다. 그렇기 때문에 wait이라는 시스템 콜이 있지요.

코드를 수정해서 다시 확인합시다.

#include <stdio.h> 
#include <unistd.h> 
#include <stdlib.h>
#include <sys/wait.h> 
#include <sys/types.h>    

int main(){         
        int pid;         
        int status;         
        int terminatedPid;         

        if((pid=fork()) == 0){  
                printf("\t [child process %d] created from %d\n", 
                                getpid(),getppid()); 

                sleep(1);       
                exit(0);     
        }      
        printf("[parent process %d] create %d process, ppid:%d\n",  
                        getpid(),pid,getppid()); 
        terminatedPid = wait(&status);      
        printf("[parent process ] process wait process %d, status %d\n",  
                        terminatedPid,status); 
}

wait : wait의 첫번째 인자는 상태를 나타냅니다. 종료 상태를 받아올 수 있는 거죠. 반환값은 종료된 자식의 pid를 반환합니다.

[parent process 21803] create 21804 process, ppid:20819

         [child process 21804] created from 21803

[parent process ] process wait process 21804, status 0

하지만 반대로 부모프로세스는 종료하지 않았지만 자식 프로세스가 먼저 종료하게 되면 어떨까요? 단, wait 호출을 하지 않고 말입니다.

#include <stdio.h> 
#include <unistd.h> 
#include <stdlib.h> 

int main(){   
        if(fork()==0){    
                printf("\t child process created and exit\n");  
                exit(0);   
        }      
     
        printf("parent process sleep\n"); 

        sleep(10);  
        sleep(10);
        printf("process exit\n"); 
}

# gcc process.c
# ./a.out &
[1] 22111
parent process sleep
child process created and exit
process exit

# ps -ef | grep 22111

...

root     22112 22111  0 10:26 pts/2    00:00:00 [a.out] <defunct>

...

코드를 다음과 같이 수정해보세요. 

#include <stdio.h> 
#include <stdlib.h> 
#include <sys/types.h> 
#include <sys/wait.h> 
#include <unistd.h> 

int main(){     
        if(fork() == 0){     
                printf("\tchild process created and exit\n");  
                exit(0);   
        }       
      
        printf("parent process sleep\n");   
  
        wait(NULL); 

        sleep(10);
        sleep(10);
        printf("process exit\n"); 
}

부모 프로세스에서 바로 wait 콜을 호출합니다. 그러니까 종료상태를 알게 되죠. 결과도 그럴까요?

# gcc process.c

# ./a.out &

[1] 23839

parent process sleep

        child process created and exit





# ps -ef | grep 23839

root     23839 20819  0 11:31 pts/2    00:00:00 ./a.out

root     23842 20819  0 11:31 pts/2    00:00:00 grep --color=auto 23839

process exit

오.. 좀비프로세스가 없어졌어요. 

또는 시그널을 이용한 방법도 있습니다.

#include <stdio.h> 
#include <sys/types.h> 
#include <sys/wait.h> 
#include <signal.h>
#include <unistd.h> 
#include <stdlib.h> 

void childSignal(int sig){        
        printf("signal:%d\n",sig); 
        wait(NULL);
} 

int main(){     
        signal(SIGCHLD,childSignal);     
        if(fork() == 0){ 
                printf("\tchild process created and exit\n"); 
                exit(0);   
        }    
   
        printf("parent process sleep\n"); 
        
        sleep(10);  
        sleep(10);

        printf("process exit\n"); 
}

(시그널을 알아야 코드를 이해하는 데 도움이 됩니다.)

그리고 컴파일하고 실행해보도록 합시다. 그리고 재빠르게 ps 명령어를 쳐서 확인해보세요.

# gcc process.c

# ./a.out &

[1] 23451

parent process sleep

        child process created and exit

signal:17



# ps -ef | grep 23451

root     23451 20819  0 11:09 pts/2    00:00:00 ./a.out

root     23461 20819  0 11:10 pts/2    00:00:00 grep --color=auto 23451

process exit

이제 좀비프로세스가 없어졌군요!

왜 그럴까요??

우선 부모프로세스는 시그널을 등록합니다. 핸들러는 childSignal입니다.

자식 프로세스가 종료가 되면 시그널 번호 SIGCHLD로 부모프로세스에 시그널을 보냅니다. 

그렇다면 그 순간 시그널 핸들러가 동작하죠. 그렇다면 부모프로세스는 childSignal함수안에 wait을 호출합니다.

그러므로 종료상태를 받을 수 있게 되고 자식 프로세스는 좀비프로세스가 되지 않습니다.

아차, sleep함수는 일정 시간 동안 시그널을 기다립니다. 그 시간안에 시그널을 받는 다면 sleep은 동작을 멈추게 됩니다. 

왜 2번 sleep을 호출하는지 알겠죠? 바로 ps를 입력할 시간을 확보하기 위해서 입니다.

자식 프로세스의 종료 상태 알아오기

이번에는 wait에 인자를 이용하여 자식 프로세스의 종지 상태를 알아보도록 합시다. 종지상태를 조사하는 매크로는 표에 나와있습니다.

다음은 위의 매크로를 사용한 예제입니다.

#include <sys/wait.h> 
#include <unistd.h>
#include <stdio.h> 
#include <stdlib.h>  
#include <errno.h>
#include <string.h>

void pr_exit(int status){  
        if(WIFEXITED(status))      
                printf("normal termination, exit status = %d\n",WEXITSTATUS(status));    
        else if(WIFSIGNALED(status))      
                printf("abnormal termination, signal number =%d%s\n",
                                WTERMSIG(status),
#ifdef WCOREDUMP           
                                WCOREDUMP(status) ? " (core file generated)": ""); 
#else                
        ""); 
#endif          
        else if(WIFSTOPPED(status))     
                printf("child stopped, signal number = %d\n", 
                                WSTOPSIG(status)); 
}  

int main(void){     
        pid_t pid;     
        int status;    

        if((pid = fork()) < 0){       
                printf("[1] fork error\n");       
                exit(0);      
        } else if(pid == 0) {
                // 자식프로세스 곧장 7 반환하며 종료
                exit(7);       
        }
        //부모 프로세스에서 자식 상태 점검
        if(wait(&status) != pid){      
                printf("[1] wait error\n");       
                exit(0);       
        }     
    
        //자식의 종료 상태 출력
        pr_exit(status);       


        if((pid = fork()) < 0){     
                printf("[2] fork error\n");       
                exit(0);      
        } else if(pid == 0) {
                //자식 abort signal 발생하며 종료, 신호번호 6   
                abort();
        }        

        //부모 프로세스에서 자식 상태 점검
        if(wait(&status) != pid){       
                printf("[2] wait error\n");      
                exit(0); 
        }        
       
        //자식의 종료 상태 출력
        pr_exit(status);      

        return 0;
}

컴파일 후 실행해보면 자식 프로세스가 어떻게 종료가 되었는지 알 수 있습니다.

 # ./a.out
normal termination, exit status = 7
abnormal termination, signal number =6 (core file generated)

자식 프로세스가 exit(7)로 종료되었음을 부모 프로세스는 WEXITSTATUS매크로로 알 수 가 있네요.

이제 fork와 wait을 사용하는 방법을 아시겠나요?

하지만 wait에는 문제점이 존재하는데요. 그 문제점을 보완하는 함수 waitpid가 존재합니다. 

아래의 포스팅을 참고하세요.

https://reakwon.tistory.com/99

구간트리(Segment Tree)

구간트리는 특정 구간에서 특정한 값을 뽑아올때 유용하게 사용됩니다. 세그먼트트리라고도 하지요. 한 가지 예를 들어보도록 할게요. 어떤 배열이 아래와 같이 있다고 치구요.

int arr[] = {7, 4, 5, 1, 9, 5, 2, 11, 10};

0번 요소부터 5번째 요소까지의 가장 작은 값은 얼마인가요? 1이네요. 그쵸?

그렇다면 2번 요소부터 7번째 요소까지 가장 큰 값은 얼마일까요? 11이 됩니다. 

어떻게 찾을 수 있죠? 구간트리를 배우지 않았다면 for루프를 통해서 가장 작은 값이나 가장 큰 값을 구할겁니다.

for (i = from; i <= to; i++) {
	minVal = min(arr[i], minVal);
}

이렇게 말이죠. 아주 쉽네요!! 시간 복잡도는 O(n)입니다. 

하지만 구간에서 가장 작은 값을 계속해서 뽑아내야하는 상황이라면 구간트리를 사용해야합니다. 구간트리를 사용한다면 최소, 최대값을 찾는데 O(log n)이면 충분합니다.

구간트리의 노드는 특정 구간에서 가장 작은 값을 가지고 있습니다. 아래 트리가 구간 트리를 보여줍니다. 위의 배열을 구간트리로 표현한 모습이죠.

파란색 원 안의 숫자는 노드의 번호, 사각형 안의 숫자는 배열의 범위를 나타냅니다. 우리는 트리를 배열로 표현하기 위해서 가장 첫번째(root)는 1번 인덱스를 갖습니다. 자식 노드의 번호는 2와 3이 됩니다.

그렇다면 어떤 노드 i의 왼쪽 자식은 i*2, 오른쪽 자식은 i*2+1이 되는 것이죠.

우리가 3번 요소부터 7번 요소까지 가장 작은 값을 갖는 값을 뽑아오려면 5번, 6번, 14번 노드를 통해서 구할 수 있습니다.

이제 본격적으로 구현해보도록 합시다. 

구현(C++)

구간 트리에서 특정 구간에서 최소값을 찾는 것을 구간 최소 트리(Range Minimum Query, RMQ) 라고 합니다. 그래서 이 구조체를 만드는 것에서부터 시작합니다.

struct RMQ {
	int size;
	vector<int> minValues;
	RMQ(int *arr,int arrSize) {
		size = arrSize;
		minValues.resize(size * 4);
		init(arr, 0, size - 1,1);
	}
}

size는 배열의 size를 의미합니다. minValues는 해당 노드에서 가장 작은 값을 저장하는 벡터입니다.

이제 이 구조체를 초기화하는 함수 init을 불러서 구간트리의 모양을 잡아보도록 합시다.

init

잘 생각해보면 간단합니다. 왼쪽 자식, 오른쪽 자식의 값을 비교해서 가장 작은 값이 지금 이 노드의 값이 됩니다.

만약 leaf노드까지 도달했다면 그 값만을 반환해주면 되죠.

그리고 구간트리의 인덱스 node라는 값도 함께 넘겨주어 현재 노드에 가장 작은 값을 저장할 수 있게끔 하면 됩니다.

int init(int *arr, int left, int right,int node) {
	if (left == right) return minValues[node] = arr[left];

	int mid = (left + right) / 2;
	int leftMinValue = init(arr, left, mid, node * 2);
	int rightMinValue = init(arr, mid + 1, right, node * 2 + 1);

	return minValues[node] = min(leftMinValue, rightMinValue);
}

query

이 함수는 질의, 즉 물어보는 함수입니다. 특정 구간에 가장 작은 값을 반환하여라! 라고 질문을 던져 답을 받습니다. 이 함수도 역시 잘 생각해보면 별 어려움은 없습니다. 

질의하는 범위가 노드가 커버할 수 있는 범위를 완전히 포함한다면 그 값을 내주면 됩니다.

그것이 아니라면 아주 큰 값을 리턴하면 되지요.

만약 위의 배열에서 3-7 구간에 대해 질의를 한다면 5번, 6번, 14번 노드가 3-7구간에 완전히 포함되므로 그 세개의 노드만이 자신의 값을 반환합니다. 그 후 가장 작은 값이 답이 되겠죠?

헷갈릴 수 있습니다. 노드가 커버하는 범위가 질의하는 범위에 완전히! 속해있어야합니다. 

int query(int left, int right, int node, int nodeLeft, int nodeRight) {
	if (right < nodeLeft || nodeRight < left) return INF;
	if (left <= nodeLeft&&nodeRight <= right)
		return minValues[node];

	int mid = (nodeLeft + nodeRight) / 2;
	int leftMinValue = query(left, right, node * 2, nodeLeft, mid);
	int rightMinValue = query(left, right, node * 2 + 1, mid + 1, nodeRight);

	return min(leftMinValue, rightMinValue);
}

너무 함수가 섹시하지가 않군요. 인자가 너무 많습니다. C++에 지원되는 오버로딩을 사용하여 좀 더 간편하게 부를 수 있도록 하죠.

int query(int left, int right) {
	return query(left, right, 1, 0, size - 1);
}

update

구간 트리에서 값이 바뀌면 구간의 최소값도 바뀌어여합니다. 특정 index와 새로운 value를 받게되면 구간트리의 해당 노드의 값을 바꾸고 차례대로 값을 갱신해주어야합니다. 여기서 노드의 값이 바뀌는 순서는 해당 leaf노드부터 루트까지 올라오게 됩니다.

만약 5번 인덱스가 새로운 값으로 바뀌게 되었다면 해당하는 노드의 번호 12번노드부터 6번 노드, 3번 노드, 1번 노드가 갱신되어야 하죠.

int update(int index, int value, int node, int nodeLeft, int nodeRight) {
	if (index < nodeLeft || nodeRight < index) return minValues[node];

	if (nodeLeft == nodeRight) return minValues[node] = value;
	int mid = (nodeLeft + nodeRight) / 2;
	int leftMinValue = update(index, value, node * 2, nodeLeft, mid);
	int rightMinValue = update(index, value, node * 2 + 1, mid + 1, nodeRight);
	return minValues[node]=min(leftMinValue, rightMinValue);
}

int update(int index, int value) {
	return update(index, value, 1, 0, size - 1);
}

깔끔하게 함수를 호출할 수 있도록 오버로딩했구요.

전체코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 99999999
using namespace std;
struct RMQ {
	int size;
	vector<int> minValues;

	RMQ(int *arr,int arrSize) {
		size = arrSize;
		minValues.resize(size * 4);
		init(arr, 0, size - 1,1);
	}

	int init(int *arr, int left, int right,int node) {
		if (left == right) return minValues[node] = arr[left];

		int mid = (left + right) / 2;
		int leftMinValue = init(arr, left, mid, node * 2);
		int rightMinValue = init(arr, mid + 1, right, node * 2 + 1);

		return minValues[node] = min(leftMinValue, rightMinValue);
	}

	int query(int left, int right, int node, int nodeLeft, int nodeRight) {
		if (right < nodeLeft || nodeRight < left) return INF;
		if (left <= nodeLeft&&nodeRight <= right)
			return minValues[node];

		int mid = (nodeLeft + nodeRight) / 2;
		int leftMinValue = query(left, right, node * 2, nodeLeft, mid);
		int rightMinValue = query(left, right, node * 2 + 1, mid + 1, nodeRight);

		return min(leftMinValue, rightMinValue);
	}

	int query(int left, int right) {
		return query(left, right, 1, 0, size - 1);
	}

	int update(int index, int value, int node, int nodeLeft, int nodeRight) {
		if (index < nodeLeft || nodeRight < index) return minValues[node];

		if (nodeLeft == nodeRight) return minValues[node] = value;
		int mid = (nodeLeft + nodeRight) / 2;
		int leftMinValue = update(index, value, node * 2, nodeLeft, mid);
		int rightMinValue = update(index, value, node * 2 + 1, mid + 1, nodeRight);
		return minValues[node]=min(leftMinValue, rightMinValue);
	}

	int update(int index, int value) {
		return update(index, value, 1, 0, size - 1);
	}
};

int main() {

	int arr[] = { 7, 4, 5, 1, 9, 5, 2, 11, 10 };
	RMQ rmq(arr, sizeof(arr) / sizeof(int));

	printf("query(0-8) : %d\n", rmq.query(0, 8));
	printf("query(1-6) : %d\n", rmq.query(1, 6));
	printf("query(7-8) : %d\n", rmq.query(7, 8));
	printf("query(3-7) : %d\n", rmq.query(3, 7));
	printf("query(0-2) : %d\n", rmq.query(0, 2));
	printf("query(0-2) : %d\n", rmq.query(4, 8));
	printf("update(index 4, value 0)) : %d\n", rmq.update(4,0));
	
}

-- 내용과 코드는 구종만의 알고리즘 문제해결 전략을 참고했습니다 

힙 정렬(Heap Sort)

정렬 시리즈 중 고급 정렬 알고리즘에 속하는 힙정렬은 힙이라는 자료구조를 토대로 정렬합니다. 그러니까 힙에 대해서 알고 와야겠죠??

힙에 대해서 모르는 분들은 아래 url를 참고하시기 바랄게요.

https://reakwon.tistory.com/42

힙에 대해서 아셨다면 이제 어떻게 정렬을 하는지 알아보도록 하지요.

정렬

위의 url의 코드를 통해서 힙정렬을 한다고 하면 의외로 쉽습니다. 메인 함수를 이렇게 바꾸어서 실행해보세요. 정렬이 아주아주 잘됩니다.

int main() {
	heap hp;
	initHeap(&hp);
	int i;
	int arr[] = { 5,3,4,1,6,10 };
	int size = sizeof(arr) / sizeof(int);
	for (i = 0; i < size; i++)
		insert(&hp, arr[i]);

	for (i = 0; i < size; i++)
		arr[i] = deleteData(&hp);

	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}

근데 문제점이 있죠. arr이라는 배열 공간과 heap이라는 배열 공간 두개를 쓰니까 메모리의 낭비가 있습니다.

그리고 insert함수를 부르는 시간 nlog(n), deleteData함수를 부르는 시간 nlog(n)입니다.

우리는 더 잘할 수 있다

이것도 훌륭하지만 우리는 더 나아갈 수 있습니다. 더 잘할 수 있습니다.

아래의 그림은 방금 위의 배열을 단지 트리 형태로 표현한 것입니다.

최대힙을 구현할 것인데, 힙의 조건을 만족하지 않지요. 왜냐면 5가 가장 큰 원소가 아니거든요. 

아차, heap을 구현할때는 1부터 인덱스가 시작되는데 힙정렬할땐 0부터 시작한답니다. 왜냐면 공간을 아끼기 위해 그 배열 자체를 정렬할 것이기 때문이에요. 배열의 인덱스는 0부터 시작하는 것이니까요.

heapify

우리는 이것을 힙의 모양으로 고치는 것, 그 함수를 heapify라고 정의해보겠습니다.

코드와 함께 heapify가 어떻게 동작하는 지 보도록 합시다.

void heapify(int arr[], int here, int size) {
	int left = here * 2 + 1;
	int right = here * 2 + 2;
	int max=here;
	if (left<size&&arr[left]>arr[max])
		max = left;
	if (right < size&&arr[right]>arr[max])
		max = right;

	if (max != here) {
		swap(&arr[here], &arr[max]);
		heapify(arr, max, size);
	}
}

이 함수 하나로 힙의 모양을 만들수는 없습니다. 

아래 왼쪽의 트리에서 우리가 heapify(arr, 0, size)를 호출한다고 치면 오른쪽의 트리로 만들어지게 됩니다.

가장 작은 1이 맨 끝에 이동함을 알 수 있죠. 하지만 최대힙은 아닙니다. 4가 가장 큰 값이 아니잖아요. 

우리는 이렇게 생각해볼 수 있습니다. 만약 자식을 갖고 있는 노드가 있다면 그 위치에서부터 heapify를  역순으로 호출하는 방식이죠. 그러니까 자식노드를 갖고 있는 노드는 0, 1, 2의 인덱스인데, heapify(arr, 2, size), heapify(arr, 1, size), heapify(arr, 0, size) 이렇게 호출하면 되지 않을까요?

그런 함수가 buildHeap이라는 함수입니다.

buildHeap

우선 우리는 자식을 갖고 있는 노드가 어떤 인덱스를 갖고 있어야하는지 알아야합니다. 어떻게 알 수 있을까요??

가장 마지막 노드는 size-1의 노드인것을 알 수 있습니다. 하지만 우리는 그 부모님 성함을 알 수 있죠. 바로 size/2 -1이 그 부모노드의 인덱스라는 것을 알 수 있습니다.

그러니까 맨 마지막의 인덱스는 5, 그 부모노드는 5/2 -1로 2가 됩니다. 

이제부터 우리는 

{ 5,3,4,1,6,10 }

이 배열을 heap으로 만드는 과정을 살펴봅니다.

초기는 아래와 같죠.

자식을 갖고 있는 노드를 알았으니 heapify(arr, 2, size)를 호출해봅시다. 그러면 위의 트리는 이렇게 바뀝니다.

10이 더 크니까 4와 자리를 바꾸죠.

이제 heapify(arr, 1, size)를 호출하면 다음과 같이 바뀝니다.

6이 더 크니까 3과 자리를 바꿉니다.

이제 heapify(arr,  0, size)를 호출합시다.

5의 자식 중 10이 5보다 크네요. 자리 바꿔줍니다.

루트까지 호출이 되었으니까 heapify는 종료됩니다.

어때요? 최대힙 모양이 완성되었죠? 

이것을 for루프로 돌리면 아래와 같은 코드가 됩니다.

void buildHeap(int arr[], int size) {
	int i,j;
	for (i = size / 2 - 1; i >= 0; i--) {
		heapify(arr, i, size);
		for (j = 0; j < size; j++)
			printf("%d ", arr[j]);
		printf("\n\n");
	}
}

이제 정렬 좀 하자..

여기까지 됐으면 거의 끝났습니다. 루트원소를 맨끝에 옮기고 다시 heapify를 호출하면 됩니다. 단, 트리의 사이즈는 하나씩 줄어듭니다.

이제 정렬과정만 보이면 되겠군요.

void heapSort(int arr[],int size) {
	int treeSize;
	buildHeap(arr, size);
	for (treeSize = size - 1; treeSize >= 0; treeSize--) {
		swap(&arr[0], &arr[treeSize]);
		heapify(arr, 0,treeSize);
	}
}

#include <stdio.h>

void swap(int *a, int *b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}
void heapify(int arr[], int here, int size) {
	int left = here * 2 + 1;
	int right = here * 2 + 2;
	int max=here;
	if (left < size&&arr[left]>arr[max])
		max = left;
	if (right < size&&arr[right]>arr[max])
		max = right;

	if (max != here) {
		swap(&arr[here], &arr[max]);
		heapify(arr, max, size);
	}
}

void buildHeap(int arr[], int size) {
	int i,j;
	for (i = size / 2 - 1; i >= 0; i--) {
		heapify(arr, i, size);
		for (j = 0; j < size; j++)
			printf("%d ", arr[j]);
		printf("\n\n");
	}
}

void heapSort(int arr[],int size) {
	int treeSize;
	buildHeap(arr, size);
	for (treeSize = size - 1; treeSize >= 0; treeSize--) {
		swap(&arr[0], &arr[treeSize]);
		heapify(arr, 0,treeSize);
	}
}
void printArray(int arr[], int size) {
	int i;
	for (i = 0; i < size; i++)
		printf("%d ", arr[i]);
	printf("\n");
}
int main() {
	int arr[] = { 5,3,4,1,6,10 };
	int size = sizeof(arr) / sizeof(int);
	
	heapSort(arr, size);
	printArray(arr, size);
}

시간복잡도

힙 정렬에서 시간 복잡도는 O(nlogn)입니다. 완전 이진 트리이기때문에 높이가 균등합니다. 그래서 heapify는 logn으로 보장할 수 있습니다. 그리고 heapify를 n번 호출하기 때문에 nlogn이라는 것을 알 수 있지요. 

도움이 되셨나요??