가상 함수

  • 부모를 상속받은 자식 클래스에서 "재정의할 것"으로 기대하고 정해놓은 함수
  • 자식 클래스에서 가상함수를 재정의하면 이전에 정의되었던 내용들은 모두 새롭게 정의된 내용들로 교체된다.
  • 부모 클래스에서 virtual 키워드를 사용해 가상 함수를 선언하면 자식 클래스에서 재정의된 멤버함수도 자동으로 가상 함수가 된다.

 

사용법

  • 멤버함수 앞에 virtual을 붙이면 된다.

 

 

가상 함수 호출 방식

c++ 에서는 가상 함수가 아닌 일반적인 멤버 함수들의 호출은 컴파일 할 때 고정된 메모리 주소로 변환된다.  
➡️  정적 바인딩


가상 함수를 호출할 때는 컴파일러가 어떤 함수를 호출해야 하는지 미리 알 수 없다. 
왜냐하면, 가상 함수는 프로그램이 실행될 때(런타임 때) 객체를 결정하므로 컴파일 타임에 해당 객체를 특정할 수 없기 때문이다.
➡️ 동적 바인딩

 

 

가상 함수를 사용하는 이유

c++컴파일러는 virtual을 쓰지 않으면 모든 함수가 정적 바인딩으로 선언된다.

class Person;
class Man : public Person;
class Girl : public Person;

man,girl이 person클래스를 상속 받았다면 프로그램을 짜는 도중에 어쩔 수 없이
Man *gracefulMan = new Man;

Person *pMan = gracefulMan;


이런 식으로 써야 하는 경우가 많다.


예를 들어 사람 리스트를 만들었을 때 리스트는 동일 자료형을 가져야 하는데, 특정 자료형(남자 or 여자)으로 만들면
성별마다 따로 리스트를 만들어야 되지 않나?
그래서 남자, 여자 두 타입의 변수를 모두 받을 수 있는 부모 클래스 포인터를 쓴다.

 

Person *pMan = new Man;
Person *pGirl = new Girl;

List<Person*> list;

list.AddTail(pMan);
list.AddTail(pGirl);

이 때 문제가 c++에서 멤버함수를  정적 바인딩 한다는 것이다. 즉, 코드를 실행하기 전에 전에 어떤 함수가 불러질 지 결정된다.


예를 들어 Person,Man,Girl 모두 talk()라는 멤버함수를 가지고 있다고 하자.
그런데 pMan->talk()를 호출하면 Man의 talk()함수가 호출되길 바라지만, 실제로는 Person의 멤버함수가 호출되어 버린다.

 

Person *pMan = new Man;
delete pMan;

이 경우에도 우리는 Man의 소멸자 함수가 호출되기를 바라지만, delete는 Person의 소멸자를 호출해 버린다.

 

위와 같은 상황의 해결책으로 virtual을 쓰는 것이다.

 

만일 타입 변환을 쓰지 않는다면 굳이 virtual 키워드를 신경쓸 필요가 없다. 하지만 타입변환은 매우 편하다.
만약 스타크래프트에서 12부대의 유닛을 지정한다면 타입변환을 통해 marine이든 wraith든 다 하나의 배열에 담을 수 있다.

CUnit(*team)[12];

for(int i=0; i<12; i++){
	team[i]->MoveTo(마우스 클릭 위치);
}

위의 코드처럼 여러 타입의 객체를 같은 배열로 관리할 수 있다. 만일 저것을 타입 변환을 쓰지 않고 각각 처리하려고 했다면 
코드가 얼마나 복잡해 졌을까? ^^

 

 

 

사용 예시

#include<stdio.h>
#include<iostream>

class A
{
    public:
    virtual void Print(){
    	printf("A 클래스의 print() 함수\n");
    }
};

class B : public A
{
    virtual void Print(){
    	printf("B 클래스의 Print()함수\n");
    }
};

int main(){
	A obj_a;
    B obj_b;
    
    A* ptr = &obj_a;
    ptr->Print(); // A클래스의 프린트 함수 호출
    
    A* ptr2 = &obj_b;
    ptr2->Print(); // B클래스의 프린트 함수 호출
                       // 가상함수가 아닌 그냥 일반적인 멤버함수로 만들었다면 A의 프린트 함수를 호출했을 것이다.
                       // => 컴파일러는 포인터가 가리키는 객체가 아닌 "포인터 변수의 자료형을 기준"으로 결정하기 때문
                       // 하지만 가상함수를 사용하면 "포인터가 가리키는 객체를 기준"으로 호출함수를 결정하기 때문에
                       // B클래스의 프린트 함수가 호출되는 것이다.
    return 0;
}

 

 

코딩테스트 코드 작성 팁

  • 코딩테스트와 개발은 다르다.

  • 남들이 보기 편한 클린코드가 아닌 가장 빠르게 풀 수 있도록 짜는 것이 훨씬 중요하다.

  • 출력 맨 마지막 공백 or 줄바꿈이 추가로 있어도 상관이 없다.

  • 디버거는 사용하지 않는다. 차라리 중간에 변수를 확인하고 싶다면 printf나 cout으로 확인한다. 

  • endl은 죽어도 쓰지 마라!!!
    endl은 개행문자('\n')을 출력하고 출력 버퍼를 비우라는 명령어이다. 
    온라인 저지 채점은 출력값만 확인하기 때문에 버퍼를 매번 비워줄 필요가 없다. (시간낭비)

  • #include<bits/stdc++.h> 선언
    vscode에서만 쓸 수 있는 구현에 필요한 헤더들을 다 인클루드해 놓은 헤더이다.
    #include<iostream>
    #include<string>
    #include<map>
    #include<set>
    #include<stack>
    #include<vector>
    #include<functional>
    #include<algorithm>

 

표준 입출력

scanf, printf에서 단 한가지 아쉬운 점이라면, C++ string을 처리할 수 없다는 것이다.

 

printf()로 string 출력 예시

#include<stdio.h>
#include<iostream>
using namespace std;

int main(){
    string s = "baaa";
    printf("s is %s\n", s);
}

//실행 결과 => s is ?

 

scanf, printf를 쓰면서 C++ string을 활용한 예시

  ☞ 일단 char*로 입력을 받고 string으로 형변환해서 원하는 작업을 다 끝낸 후 다시 c_str()을 이용해 출력

#include<stdio.h>

int main(){
    char a[10];
    printf("input : ");
    scanf("%s", a);
    string s(a);  // 혹은 string s = a;
    printf("a is %\n", a);
    printf("s is %s\n", s.c_str());
}

/*
실행 결과
input : test
a is test
s is test
*/

 

 

cin, cout을 쓸 때 주의사항

scanf, printf를 쓸 때는 신경쓰지 않아도 되는데 cin,cout을 쓸 때는 주의해야 할 부분이 있다.
scanf, printf와는 달리 cin, cout은 입출력으로 인한 시간초과를 막기 위해
ios::sync_with_stdio(0), cin.tie(0)이라는 두 명령을 실행시켜야 한다. 
위 두개를 실행해주지 않으면 입출력의 양이 많을 때 시간초과가 날 수 있다.

기본적으로 scanf, printf에 쓰는 C stream과 cin, cout에서 쓰는 C++ stream은 분리되어있다.

하지만 코드의 흐름과 실제 출력이 동일하도록 하기 위해 기본적으로 프로그램은 C와 C++ stream을
동기화하고 있다. 아래와 같은 코드가 순서대로 잘 출력되는 이유는 이처럼 동기화가 되어 있기 때문이다.

#include<stdio.h>
#include<iostream>
using namespace std;

int main(){
    cout << "11111\n";
    printf("22222\n");
    cout << "33333\n";
}

 

 

만약 내가 C++ stream만 쓸거라면 굳이 쓸데없는 시간을 잡아먹으면서 두 stream을 동기화 할 필요가 있을까?
=> 그래서 필요한 것이 sync_with_stdio(0)이다.

 

ios::syn_with_stdio(0)

  • C stream과 C++ stream의 동기화를 끊는다.
  • 이걸 사용하면 동기화를 끊었기 때문에 절대 cout과 printf()를 섞어쓰면 안 된다.
  • 동기화 작업이 없으므로 프로그램 수행 시간에서 이득
  • 인자를 엄밀히 하자면 bool type이라 false가 맞는데 0이 더 짧으니 0으로 써도 된다

 

스트림 버퍼

 

 

스트림은 키보드로 받은 입력을 바로 콘솔에 넘기지 않고 버퍼에서 어느 정도 모았다가 보낸다.

하지만 입력과 출력이 번갈아 가면서 나오고 그 값들이 화면에 다 보여질 경우 버퍼의 존재로 인해 화면에 출력되는
순서가 꼬일 수 있다. 
=> 그래서 필요한 것이 cin.tie(0)이다.

오른쪽 콘솔 => 출력 순서가 꼬인 경우

 

#include<iostream>
using namespace std;

int main(){
    for(int i = 0; i < 3; i++){
    	int a,b;
        cin >> a >> b;
        cout << a + b << "\n";
    }
}

위 코드를 보면 3번에 걸쳐 두 수를 입력받고 합을 출력한다. 우리는 당연히 순서대로 출력되길 바란다.
하지만 입력 두개를 받은 후 바로 출력되지 않고 버퍼에 들어있다가 다음 숫자 2개를 입력한 후에 출력이 되버리면
순서가 꼬일 것이다. 이런 현상을 막기 위해 프로그램은 기본적으로 cin 명령을 수행하기 전 cout 버퍼를 자동으로
비워준다. 하지만 온라인 저지 사이트의 채점 형태는 입력이랑 출력이 순서가 꼬이게 콘솔에 나타나더라도 출력들만
확인하기 때문에 틀리지 않는다. 그래서 cin 명령을 수행하기 전에 cout버퍼를 비울 필요가 없다. 
이 때 cout버퍼를 비우지 않도록 하는 코드가 cin.tie(0)인 것이다.

 

 

STL을 함수 인자로 넘길 때

#include<iostream>
using namespace std;

void func1(vector<int> v){
	v[10] = 7;
}

int main(){
    vector<int> v(100);
    func1(v);
    cout << v[10];
}

STL을 함수 인자로 그대로 보내면 복사본을 만들어서 보낸다. 그렇기 때문에 원본에 영향이 없다.

 

또 다른 경우를 보자.

bool cmp1(vector<int> v1, vector<int> v2, int idx){
	return v1[idx] > v2[idx];
}

위의 cmp1()의 시간 복잡도는 어떻게 될까? 바로 O(N)이다. 응? 함수 내부에서 연산이 1번 뿐인데 어떻게 O(N)이냐고
할 수 있는데, 그것은 인자를 보낼 때 원본의 복사본을 만드는 비용을 간과한 것이다.
=> 즉, 위에서 v1의 원소는 n개이고 v2의 원소도 n개라고 한다면 총 2n만큼 복사되므로 시간복잡도가 O(N)인 것이다.

 

이런 경우 STL을 참조를 사용해 함수 인자로 전달하면 시간낭비 문제가 해결된다.

bool cmp2(vector<int>& v1, vector<int>& v2, int idx){
	return vi[idx] > v2[idx];
}

 이렇게 참조로 전달하면 시간복잡도가 O(1)이 된다.

 

 

예시) 전달받은 두 수의 값을 바꾸는 함수

 

getline()

#include<iostream>
#include<vector>
using namespace std;

int main(){
  string name;
  cout << "이름 입력 : ";
  getline(cin, name);

  cout << name;
}

getline(읽을 데이터, 읽은 데이터를 저장할 변수명);

- 문자열의 길이나 띄어쓰기 여부에 상관없이 \n을 만나기 전까지 모든 문자열을 입력받음 ( \n은 입력받지 않음 )

 

'C,C++' 카테고리의 다른 글

C++ 멤버 초기화 리스트  (0) 2022.04.10
C++ 가상 함수(virtual function)  (0) 2022.04.09
배열의 크기를 넘어가서 사용할 경우  (0) 2022.02.14
c언어 문자열  (0) 2022.02.04
이중포인터  (0) 2022.02.03

시간복잡도

주어진 입력 N의 허용 시간복잡도

 

공간복잡도

  • 입력의 크기와 문제를 해결하는데 필요한 공간의 상관관계

예를 들어 크기 N짜리 2차원 배열이 필요하면 O(N²)이고, 따로 배열이 필요 없으면 O(1)이 된다.
하지만 코딩테스트에서 대부분의 경우 공간복잡도의 문제보다는 시간복잡도 때문에 문제를 많이 틀린다.
그러므로 공간복잡도는 크게 신경쓰지 않아도 된다.

 

But!! 이거 하나만 기억해두자 
메모리 제한이 512MB일 때 1.2억개의 int를 사용할 수 있다는 것

 

 

Integer Overflow

 

Integer Overflow가 발생하는 경우

#include<iostream>
using namespace std;

int main(){
    int a = 2000000000 * 2;
    cout << a; // -294967296
}

약 21억정도 까지만 표현할 수 있으므로 40억이라는 값은 a에 저장이 안 된다.
하지만 -294967296 같은 이상한 값은 어떻게 해서 나오게 된 것일까?

 

이유 : 컴퓨터는 그냥 시킨대로만 계산을 하기 때문이다.

 

integer overflow를 막는 방법은 각 자리에 맞는 값을 가지게끔 연산을 시키면 된다. 하지만 실제로 코드를
짜 보면 integer overflow는 아주 빈번하고 찾기도 정말 힘들다.

 

 

실수를 이진수로 표현하는 방법 

3을 이진수로 나타내면 11(₂) 이다. 이렇게 정수를 이진수로 바꾸는 방식을 실수에도 적용하여 실수를 이진수로 바꿀 수있다.

 

실수의 이진수 표현

예를 들어 3.75를 이진수로 나타내고 싶다. 어떻게 해야 할까?

3.75  =  2  +   1   +   0.5   +  0.25  =  2^1 + 2^0 + 2^(-1) + 2^(-2) = 11.11(₂) 
위와 같이 바꿀 수 있다. 즉, 실수는 이진수로 바꿀 때 0.5, 0.25, 0.125. . . 등의 합으로 나타낸다.

 

이진수에서도 무한소수가 나타난다.
= 2^(-2) + 2^(-4) + 2^(-6). . . = 0.010101. . .(₂) 이런식으로 끝없이 이어지는 무한소수가 발생한다.

0.1도 0.5, 0.25, 0.125. . . 등을 아무리 조합해봐야 나오지 않기 때문에 무한소수로써 끝없이 이어진다.

 

 

실수가 저장되는 방식

 

우선 이걸 확인하고 가자.

3561.234 = 3.561234 x 10³ 로 바꿀 수 있듯이
11101.001(₂) = 1.1101001(₂) x 2⁴ 로 바꿀 수 있다.

 

실수는 float와 double에 담을 수 있다. float는 32비트, double은 64비트이다.

-6.75 = -1.1011(₂) x 2² 
위 실수를 저장해보자.

sign field

  • 해당 수가 음수인지 양수인지 저장하는 필드 ( 음수면 1, 양수면 0 )

exponent field

  • 과학적 표기법에서의 지수를 저장하는 필드 ( 2²가 뒤에 붙었으므로 이 필드에는 2가 저장됨)
  • 지수값을 그대로 넣는 것이 아닌 지수값 2에 127을 더한 값을 여기에 저장한다.
    127을 더하는 이유는?  이렇게 해야 음수 지수승도 exponent 필드 안에 넣을 수 있기 때문 

fraction field

  • 유효숫자 부분을 저장하는 필드
  • -1.1011(₂) x 2²에서 유효숫자 부분은 1.1011인데 맨 앞 1은 뺀 1011이 여기에 저장된다.
    맨 왼쪽부터 2^(-1), 2^(-2) . . . 자리인 셈이라 필드에는 1011000. . . 000이 적힌다.
    즉, 맨 왼쪽부터 비트를 채운다.

이런 식으로 실수를 저장하는 방식을 IEEE-754 format이라고 한다.

 

 

실수의 성질

1. 실수의 저장/연산 과정에서 반드시 오차가 발생할 수 밖에 없다.

#include<iostream>
using namespace std;

int main(){
    if(0.1 + 0.1 + 0.1 == 0.3){
    	cout << "true";
    }
    else{
    	cout << "no no";
    }
}

실행 결과 : no no 

 

true가 아닌 no no가 출력된 이유는?

  • 유효숫자가 들어가는 fraction field는 유한하기 때문에 어쩔 수 없이 float는 앞 23bit, double은 앞 52bit까지만
    잘라서 저장할 수 밖에 없다. 0.1은 이진수로 나타내면 무한소수라서 애초에 오차가 있는 채로 저장이 됐고
    오차가 있는 상태로 3번 더하다 보니 오차가 더 커져서 위의 코드처럼 말도 안되는 일이 벌어지게 된 것이다.

float과 double의 fraction field의 유효숫자의 안전한 범위

float    : 유효숫자 6자리    =>  상대오차 10^(-6)까지 안전
double : 유효숫자 15자리  =>  상대오차 10^(-15)까지 안전

 

그렇기 때문에 실수 자료형이 필요하면 float 대신 double을 쓰자!!

 

2. double에 long long 범위의 정수를 함부로 담으면 안 된다.

- double은 유효숫자가 15자리인데 long long은 최대 19자리라서 10^18 + 1과 10^18을 구분 못하고
  같은 값이 저장된다. 
- int는 약 21억까지 저장하기 때문에 double에 담아도 오차가 발생하지 않는다.

 

3. 실수를 비교할 때는 등호를 사용하면 안 된다.
위에서 0.1 + 0.1 + 0.1 == 0.3의 결과가 이상하게 나오는 것에서 보면 알 수 있다.

 

https://www.acmicpc.net/problem/14852

 

14852번: 타일 채우기 3

첫째 줄에 경우의 수를 1,000,000,007로 나눈 나머지를 출력한다.

www.acmicpc.net

#include<iostream>
#include<stdio.h>

using namespace std;

int d[1000001];

int solution(int n){
    if(n == 0) return 1;
    if(n == 1) return 2;
    if(n == 2) return 7;
    if(d[n] != 0) return d[n];
    int result = 2 * solution(n-1) + 3 * solution(n-2);
    for(int i = 3; i <= n; i++){
        result += (2 * solution(n-i));
    }
    
    return d[n] = result % 1000000007 ;
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%d",solution(n));
}

위 코드의 시간 복잡도

solution(n)을 구할 때 시간             =>   1(상수 시간)

뒤에 for문에서 sum을 구하는 과정   =>   n

 

solution()은 재귀 호출 함수이므로 총 n-1번 호출할 것이다. 그러므로 solution(n)을 구하는데 드는 시간은
1 * n 으로 n만큼 걸린다.

 

정리하면 solution()을 구할 때 시간 * 뒤에 for문에서 sum을 구하는 과정 = n * n  = O(n^2)

 

 

처음에는 위처럼 작성해서 제출했다. 하지만 시간 초과가 나왔다.

그 이유는 문제에서 N의 범위가 1~1,000,000 이었기 때문에 위의 코드로는 1000000^2 로 매우 큰 시간이 걸려서
시간 초과가 발생하기 때문이다.

 

그래서 sum을 구해주는 부분도 dp 테이블에 저장해서 매번 n번을 더하는 것이 아닌 더한 값을 dp 테이블에 저장
해두고 사용하도록 구현한다면 O(N)의 시간복잡도로 구현할 수 있다. 

 

즉, X[i] = sum( solution(i-1) + solution(i-2) + ... solution(0) ) 을 저장해 둔다면 그 다음 번에 X[i+1]을 구할 때는
저장되어 있는 값을 한 번 가져오기만 하면 도므로 O(1)만큼밖에 안 걸리기 때문이다. 그러므로 dp 이차원 배열을
이용해 구현하면 된다.

 

이게 바로 누적합을 저장해두는 누적합 문제 유형이다. ( 최적화를 필요로하는 심화된 dp 문제에 종종 나온다 )

 

 

정답 구현 

dp를 하나 더 만들어 sum을 저장해두자.

새로 만든 dp에 넣어야 할 값은 sum이다.

점화식

위 점화식에서 뒤에 2로 묶여있는 부분인 ( DP(n-3) + ... + DP(1) + DP(0) ) 를 새로 만든 dp에 넣어주는 것이 목표다.

실제로는 저 값을 2로 묶어줬으므로 DP[n][1]에 나중에 2를 곱해줘야 한다.

 

그러기 위해서 dp 이차원 배열을 만든다면

DP[n][0] => 길이가 2 x n일 때의 타일을 채우는 경우의 수가 들어감 

DP[n][1] =>  (solution(n-3) + ... + solution(1) + solution(0) ) 의 결과 sum 값이 들어감

 

위의 DP[n][1]을 다르게 보면 밑에처럼 볼 수 있다.

solution(n-3) + solution(n-2) + ... solution(0)
= { solution(n-3) } + { solution(n-2) + ... solution(0) }

 

즉, DP[n][1] = { DP[N-3][0] } + { DP[n-1][1] } 이 된다. 

 

그러므로
DP[n][1] = DP[n-3][0] + DP[n-1][1];

DP[n][0] = 3 * DP[n-2][0] + 2 * DP[n-1][0] + 2 * DP[n][1]; 

 

 

정답 코드     

#include<iostream>
#include<stdio.h>

using namespace std;

long dp[1000001][2];

long solution(int n){
    dp[0][0] = 1;
    dp[1][0] = 2;
    dp[2][0] = 7;
    dp[2][1] = 0;
    
    if(dp[n][0] != 0) return dp[n][0];
    
    for(int i = 3; i <= n; i++){
        dp[i][1] = (dp[i-3][0] + dp[i-1][1]) % 1000000007;
        dp[i][0] = (3 * dp[i-2][0] + 2 * dp[i-1][0] + 2 * dp[i][1]) % 1000000007;
    }

    return dp[n][0];
}

int main(){
    int n;
    scanf("%d",&n);
    printf("%ld",solution(n));
}

 

 

'알고리즘 문제풀이' 카테고리의 다른 글

백준 11726번 ( 2 x N 타일링 )  (0) 2022.02.21
백준 1431번 ( 시리얼 번호 )  (0) 2022.02.14
#include <stdio.h>

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

시간복잡도 : T(n) = T(n-1) + c        ( c는 "1의 수행시간 + 2에서의 곱셈의 수행시간" )

 

위의 factorial() 함수의 시간복잡도를 반복대치를 이용해 구해보겠다.

 

반복대치

T(n) = T(n-1) + c

      = T(n-2) + 2c

      = T(n-3) + 3c

      . . .

      = T(1) + (n-1) * c

 

이때, n = 1일 때 T(1)은 1의 수행시간 밖에 들지 않으므로  1의 수행시간 + 2의 수행시간의 값을 가지는 c보다 작다.
     <= c + (n-1) * c
     <= nc

 

즉, 빅오의 정의에 의해 T(n) = O(n)이 된다.

 

=> 재귀함수의 시간복잡도 : O(n)

컴파일러

  • 전체 소스코드를 보고 명령어 수집하고 재구성
  • 고레벨 언어를 바로 기계어로 변환

 

인터프리터

  • 소스코드의 각 행을 연속적으로 분석하며 실행
  • 고레벨 언어를 바로 기계어로 번역하지 않고 중간 코드(바이트 코드)로 변환시킨 후 기계어로 변환

 

인터프리터의 특징 4가지

  1. 인터프리터는 고레벨 언어를 중간 코드로 변환하고 이를 각 행마다 실행한다.

  2. 컴파일러가 각 행마다 실행하는 특성을 가진 인터프리터보다 실행시간이 더 빠르다.

  3. 컴파일러는 전체 소스코드 변환 후 에러를 보고하지만 인터프리터는 각 행마다 실행하는 도중
    에러가 보고되면 이후 작성된 코드를 보지 않는다. => 보안적인 관점에서 도움이 된다.

  4. 파이썬은 인터프리터 언어, C,C++은 컴파일 언어, 자바는 컴파일러와 인터프리터 모두 사용한다.

 

Compiler와 Interpreter가 하는 일 ( 자바 기준 )

컴파일러가 하는 일은?

 

helloworld를 작성하고 javac 명령어를 통해 helloworld.java 파일을 helloworld.class로 변환하는 것을 수행한다.

helloworld.java -> (javac) -> helloworld.class

 

응? 컴파일러는 기계어로 변환하는 프로그램이라고 했는데 .class 파일은 바이트 코드인데 이게 기계어인가...?
컴파일러는 소스코드 -> 오브젝트코드, 고레벨 언어 -> 저레벨 언어인 기계어로 변환한다. 
여기서의 기계는 하드웨어가 아닌 JVM을 위한 기계어로 변환한다는 뜻이다.

 

 

인터프리터가 하는 일은?

자바 컴파일러에 의해 변환된 .class 파일 내의 바이트 코드를 특정 환경의 기계에서 실행될 수 있도록 변환한다.

 

 

여기서 Machine language는 JVM을 말한다.

 

 

자바는 왜 컴파일과 인터프리터를 병행할까?

바로 기계어로 변환시키는 컴파일러는 프로그램이 작성된 기계상에서 실행할 때 매우 효율적이다. 대부분의 하드웨어
제어 시스템의 프로그래밍 언어가 C언어인 이유이다. 하지만 그렇기 때문에 기계의 종류에 종속될 수밖에 없다.

 

C언어와 달리 자바는 인터프리팅과 컴파일을 둘 다 사용한다.

인터프리팅은 플랫폼에 종속되지 않는다.

자바 바이트 코드는 컴퓨터와 프로그램 사이에 별도의 버퍼 역할을 한다.
    ☞ 이는 보안적인 장점이 될 수 있다.

 

이로 인해 자바는 플랫폼에 독립적이고 안전한 환경을 제공하면서 동시에 현대 프로그래밍 추상화를 완벽히 
수용할 수 있다.

 

즉, 자바는 컴파일러로 바이트 코드를 생성해 보안적인 장점을 얻음와 동시에 인터프리터를 사용해 플랫폼에
독립적이다.

 

컴퓨터는 0과 1로만 이루어진 기계어만 이해할 수 있기 때문에 개발자가 만든 코드를
변환해 주어야 한다. 이 역할을 하는 것이 컴파일러이다.

 

[Java] 컴파일 과정

자바는 OS에 독립적인 특징을 가지고 있다. 그게 가능한 이유는 JVM(Java Virtual Machine) 덕분이다.

 

자바 컴파일 순서

1. 개발자가 자바 소스코드(.java)를 작성한다.

 

2. 자바 컴파일러(Javac)가 자바 소스파일을 컴파일한다. 이 때 나오는 파일은 자바 바이트 코드(.class) 파일로
    아직 컴퓨터가 읽을 수 없고 JVM이 이해할 수 있는 코드이다.
    ( 바이트 코드의 각 명령어는 1바이트 크기의 Opcode와 추가 피연산자로 이루어져 있다. )

 

3. 컴파일된 바이트 코드를 JVM의 클래스로더(Class Loader)에게 전달한다.

 

4. 클래스 로더는 동적로딩(Dynamic Loading)을 통해 필요한 클래스들을 로딩 및 링크하여
   런타임 데이터 영역(Runtime Data area), 즉 JVM의 메모리에 올린다.

   ※ 클래스 로더 세부 동작
      ① 로드 : 클래스 파일을 가져와서 JVM의 메모리에 로드
      ① 검증 : 자바 언어 명세(Java Language Specification) 및 JVM 명세에 명시된 대로 구성되어 있는지 검사
      ① 준비 : 클래스가 필요로 하는 메모리를 할당 ( 필드, 메서드, 인터페이스 등등 )
      ① 분석 : 클래스의 상수 풀 내 모든 심볼릭 레퍼런스를 다이렉트 레퍼런스로 변경
      ① 초기화 : 클래스 변수들을 적절한 값으로 초기화 ( static 필드 )

5. 실행엔진(Execution Engine)은 JVM 메모리에 올라온 바이트 코드들을 명령어 단위로 하나씩 가져와서 실행한다.
   
   이때 실행 엔진은 두 가지 방식으로 변경한다.
   ① Interpreter
        - 바이트 코드 명령어를 하나씩 읽어서 해석하고 실행한다. 하나하나의 번역속도는 빠르나,
          전체적인 실행 속도는 느린 단점이 있다.


   ② JIT Compiler ( Just-In-Time Compiler )
        - 인터프리터의 단점을 보완하기 위해 도입된 방식
        - 바이트 코드 전체를 컴파일하여 바이너리 코드로 변경하고 이후에는 해당 메서드를 더이상 인터프리팅 하지
          않고, 바이너리 코드로 직접 실행하는 방식
        - 하나씩 인터프리팅하여 실행하는 것이 아닌 바이트 코드 전체가 컴파일된 바이너리 코드를 실행하는 것이기
          때문에 전체적인 실행속도는 인터프리팅 방식보다 빠르다.
    
    자바는 javac로 컴파일하고 java로 실행 시 바이트 언어를 한 줄씩 자바 인터프리터가 번역하기에 컴파일 언어이면서
    인터프리터 언어이다.

 

[C++] 컴파일 과정

GCC의 컴파일 과정

  1.  전처리기가 cpp 파일과 header파일을 읽어와 인라인시키고 전처리된 .i 파일로 만든다.

  2.  컴파일러는 이 .i 파일을 컴파일해서 기계어와 가장 유사한 상태인 어셈블리어로 변환된 .s 파일을 생성한다.

  3.  어셈블러는 .s파일을 어셈블해서 2진수로 이루어진 기계어로 된 .o 파일을 생성한다.

  4.  링커는 만들어진 .o 파일을 실행 파일로 변환한다. 링크 과정에서 각 .o 파일의 관계가 서로 연결되고
     필요로 하는 라이브러리도 함께 코드화되어 실행 가능한 파일이 만들어진다.

 

Java보다 C,C++의 수행속도가 빠른 이유

일괄 컴파일 방식 언어인 C,C++의 코드는 컴파일만 하면 바로 CPU에서 실행이 가능한 코드인 기계어로 변환된다.
그렇기 때문에 수행속도가 빠르다.

 

Java의 코드는 컴파일을 해서 byte code를 생성하고, 그 byte code를 기계어로 변환하는 시간을 필요로 하기 때문에
수행 속도가 더 오래 걸린다. 

 

PUSH 기법

  • 인터넷 상에서의 어떠한 전송 요청이 중앙 서버에서 시작되는 정보 전달 방식
  • 전송 요청이 클라이언트에서 시작되는 풀 기법과 대비되는 방식
  • 사용자가 원하든 원하지 않든 방송처럼 뉴스를 제공하는 기술
  • 푸시 방법으로 정보를 제공하던 기존의 TV나 라디오와 다른 점은 사용자가 미리 원하는 범위를 지정할 수 
    있다는 점이다.
  • 사용자가 일일이 요청하지 않아도 사용자에게 자동으로 뉴스나 사용자가 원하는 특별한 정보, 예를 들면
    증권시장의 주기적인 정보 같은 것을 제공한다.

 

PUSH 기법의 가장 큰 이점

  • 정보의 맞춤화(Customization)가 가능하다.
    => 사용자가 이미 등록되어 있기 때문에 등록된 사용자 정보에 의해 타겟을 정확히 선정할 수 있다.

 

카카오톡 등의 웹 기반 실시간 채팅 어플리케이션은 서버가 클라이언트(ex 스마트폰)에게 알려줄 정보(ex 메시지 등)
가 있을 경우 실시간으로 알려주어야 할 필요가 있다. 

 

정보를 가지고 있는 사이트에서 사용자에게 원하는 정보를 밀어내 준다(PUSH).

 

푸시 시스템은 매일 아침 우유나 신문이 집 앞에 배달되듯이, 이미 등록이 되어 있는 서버에서 원하는 시간에
원하는 내용을 자신의 컴퓨터로 정기적으로 배달되도록 하는 방식의 기술을 말한다.

 

 

PUSH 시스템의 작동 과정

 

이용자가 PUSH 정보를 받아오는 과정은 다음과 같다.

  1. 사용자는 일단 정보 생산자의 사이트나 채널에 자신이 원하는 정보와 자신의 인적 사항을 담은 정보 파일을
    생산자에게 보내어 등록한다. 또한 사용자는 정보가 전송되어야 할 예정시간을 정해야 한다.

  2. 사용자의 예정 시간에 맞추어 pc는 인터넷에 연결되고 클라이언트의 소프트웨어는 정보 생산자의 서버를
    인식하여야 다운로드가 가능해진다. 서버는 해당 사용자의 프로필에 적합한 정보를 모으고 사용자의 컴퓨터에
    해당 정보를 다운로드한다.

  3. 서버에서 다운로드가 끝나면 클라이언트 쪽에서는 언제든지 하드디스크에 저장된 정보를 이용하면 된다.

 

PUSH 클라이언트 쪽에서의 동작 과정은 다음과 같다.

  1. 환경 설정하기
    - 우선 사용자는 일정 주기에 한 번씩 데이터를 갱신하라고 환경을 설정한다. 이때 실제로 자신이 원하는 정확한
       뉴스와 정보들만 자신에게 가져오라는 설정도 함께 하게 된다.

  2. 클라이언트 <-> 서버 교환
    - 이러한 환경 설정에 따라 PUSH 클라이언트는 실제로 정해진 시간에 서버에 접속하여 사용자가 원하는 정보만
      가지고 온다.

  3. 뉴스 전달
    - 사용자는 이미 PUSH 클라이언트가 가져와서 로컬 파일 시스템(하드디스크)에 저장한 정보를 언제든지 읽으면 
       된다.

 

 

polling과 call-back

일반적으로 상태를 알아오기 위한 방법에는 크게 두가지 방법이 있다.

 

1. polling

  • 상태를 주기적으로 조사해서 알아오는 방식
  • 궁금한 사람이 바쁘게 일하는 방식

일을 계속해야 한다는 문제점이 있다. => 일을 하는 것 자체가 부하 발생

 

예를 들어 집에 중요한 택배를 시켜놓고 왔다. 다행히 집에 동생이 있어서 전화로 물어보니 아직 안 왔다고 한다.
폴링의 경우라면 1시간마다 집에 전화를 걸어 택배가 왔는지 물어보는 방법을 취할 수 있다. 그렇게 한다면 
3시간 후 쯤에는 동생이 짜증을 낼 수도 있다. ( 부하 발생 )

 

2. call-back

  • 상태를 알고 있는 주체(listener)에게 알려 달라고 이야기(등록)한 후 리스너가 알려주는 방식
  • 콜백을 비동기적인 방법이라고 한다

 

위에서의 예를 콜백 방법을 취해보겠다.


콜백 방식이라면 한번 집에 전화를 걸어 동생에게 혹시 택배가 오면 나한테 전화를 해달라고 요청을 하기만 하면 된다.
그러면 일을 하다가 전화를 받아서 택배가 온 상황을 통보받기만 하면 되는 것이다.

 

pull 과 push의 차이점

pull과 push의 차이점은 정보의 흐름을 누가 통제하느냐 하는 점에 있다고 할 수 있다.

 

PUSH

  • 정보를 전달하는 쪽(즉 광고주) 정보의 흐름을 직접 통제할 수 있다.

PULL

  • 사용자(즉 소비자)들이 정보 취득 및 정보의 접촉을 마음대로 통제할 수 있다.

 

게임 서버에서 가장 중요한 것

  • 안정성
  • 성능

성능을 높이려면?

  • 프로그램 최적화
  • 멀티코어 활용

멀티코어를 활용하려면

  • 멀티쓰레드 프로그래밍이 필요

온라인 게임을 만들려면?

  • 소켓 프로그래밍 필요

다중 접속 서버를 만들려면?

  • 서버에서 동접과 같은 수의 소켓을 관리하여야 한다

효율적인 다중 접속 관리는?

  • IOCP가 필수  -> IOCP는 멀티쓰레드 프로그래밍을 요구한다.

 

프로세스와 쓰레드

프로세스 :  실행 중인 프로그램

쓰레드    :  프로그램(프로세스) 실행의 흐름 -> 프로세스 실행 중 프로그램이 쓰레드 생성 명령 실행 

 

 

프로세스는 실행 중인 프로그램을 프로세스라고 한다. 스레드는 프로세스의 안에 있는 것이다. 멀티스레드 프로그래밍을
하지 않아도 스레드 1개는 있다(메인부터 해서 끝날때까지의 흐름). 

 

병렬처리

  • 하나의 작업을 여러 개의 context에서 수행하는 것( context == CPU의 실행 상태 )

하나의 프로그램이 병렬로 실행된다. 그 단위를 context라고 정의한다. context가 여러개 있다는 것은
여러 개의 cpu가 동시에 실행한다는 뜻이다. cpu의 실행 상태는 context이고, cpu가 한 개 있을 때 여러 개의
프로세스를 실행한다는 것은 하나의 cpu가 옮겨가면서 프로세스들을 실행한다는 뜻이다. 그렇기 때문에
실행 상태를 저장해야 하고 그걸 context라고 한다. 이 저장은 PCB에 저장된다. 프로세스에 여러개의 context가
있는 게 병렬 컴퓨터이다.

 

병렬처리를 하는 이유는?

  • 한 개의 CPU의 처리 속도가 너무 느리기 때문

예전에는 1G CPU 팔다가 2G CPU 팔면서 2배 빠른 컴퓨터를 사라고 홍보했지만 이제는 안된다. 지금 나오는 CPU
클럭은 3G 정도다. 2002년에 CPU가 2.4G가 있었으니까 지금 CPU와 클럭 속도의 차이가 얼마 안 난다. 그렇기 때문에
싱글코어 CPU의 성능 차이는 거의 없다. 그러면 CPU 만드는 회사들이 망할까? 아니다. 그래서 나온게 바로 멀티코어다.
싱글 코어 팔다가 듀얼 코어 팔면서 2배 빠르다고, 그리고 쿼드코어 팔면서 4배 빠르다고, 이제는 코어 개수로 승부한다.

 

프로세스

프로세스는 PCB라는 자료구조가 있다. 이건 커널이 관리하는 자료구조로 우리가 읽고 쓸 수 없는데, 여기엔 프로세스
실행에 필요한 여러 데이터가 있는데 그 중 context가 있다. 스택 포인터(SP)가 어디까지 와 있는가는 레지스터에 있고,
지금 코드에 어느 명령어가 실행 되는가는 프로그램 카운터(PC)에 들어 있다.

 

그래서 실행 중인 프로세스는 context가 CPU 안에 들어 있다. CPU 안에 있는 레지스터가 쭉 사용되다가 프로그램이
스위칭 되면 CPU 안에 있는 레지스터 내용을 context에 저장하고 다른 프로세스를 실행한다.

 

 

멀티스레드

  • 하나의 프로그램의 여러 곳이 동시 다발적으로 실행되는 프로그래밍 기법
  • 최근에 가장 많이 사용되는 병렬처리 프로그래밍 기법
  • 하나의 프로세스에서 여러개의 실행 흐름을 만들어주는 것
  • 하나의 쓰레드는 한번에 하나의 일만 할 수 있다. 멀티쓰레드란 여러 개의 쓰레드로 동시에
    여러개의 쓰레드를 사용해
    여러 개의 일을 하는 것이다.

프로세스 안에 스레드가 여러 개 존재할 수 있다. 그리고 스레드마다 TCB를 가진다. 각자 컨트롤 블록마다 context를
따로 가지고 있다. 

 

 

멀티쓰레드의 장단점

장점

  • 성능 향상
  • 빠른 응답속도
  • 더 나은 자원 활용 ( CPU Core )
  • 프로세스보다 효율적인 통신 ( 메모리 읽고 쓰기, context switching )

멀티스레드 프로그래밍을 하지 않으면 쿼드 코어인 경우 3개의 코어는 놀고 있다. 
데이터를 주고받을 때도 프로세스끼리 데이터를 주고받는 것보다 스레드끼리 주고받는게 훨씬 빠르다.
context switching을 프로세스간에 하는 것보다 스레드간에 하는 것이 더 오버헤드가 적다.

 

단점

  • 프로그램 복잡도 증가
  • 디버깅의 어려움 ( data race, deadlock )

 

게임 서버에서 멀티 쓰레드를 사용하는 이유

게임 서버에서의 성능은 동접이다. 한 프로그램에서 동접을 최대한 많이 받기 위해 멀티쓰레드를 쓰는 것이다.
게임 서버는 많은 처리를 해야 하는데 해야할 일의 길이가 차이가 있다. 어떤 일은 1초, 어떤 일은 1/10000초만에
작업을 한다. 작업들이 쌓이면 cpu가 처리해야 하는데, 싱글스레드 프로그램일 때 1초짜리 일이 날라오면 1초동안
다른 동작들은 다 멈춰버린다. 1초의 딜레이가 생기는 것이다. 하지만 멀티스레드는 어떤 스레드가 1초동안 어떤 작업을
하느라 묶여 있더라도, 다른 스레드가 다른 작업을 처리하면 된다. 그래서 응답 속도를 높일 수 있다.

 

 

멀티스레드 프로그래밍 주의할 점

  • 쓰레드의 개수가 많다고 좋은 것은 아니다.
  • 코어의 개수에 맞추어라
  • 운영체제 및 하드웨어에 부담

쓰레드의 개수가 多 -> 스택에 차지하는 메모리 多 -> PCB 안에 TCB가 多
-> context 일어날 때 비교할 게 多 -> 운영체제 부담 ↑

 

아무리 개수가 많아도 코어의 개수만큼만 돌아가고 나머지는 waiting하고 있다. -> 코어의 개수에 맞춰서 돌려야 함!!

예를 들어 쿼드코어라면 스레드를 4개 만드는게 제일 성능에 좋다. 8개 만들면 오히려 context switch overhead 때문에
느려진다.

 

 

 

+ Recent posts