Study/TIL(Today I Learned)

24.02.21 CSAPP, TCP/IP, 백준, C++

에린_1 2024. 2. 22. 10:18
728x90

CSAPP

12.6 병렬성을 위해서 쓰레드 이용하기

  • 모든 프로그램의 집합은 중첩되지 않도록 순차적, 동시성 프로그램으로 나눌 수 있다. 순차 프로그램은 단일 논리흐름으로 작성 할 수 있다. 동시성 프로그램은 다수의 동시성 흐름으로 작성할 수 있다. 병렬 프로그램은 다중 프로세서에서 돌아가는 동시성 프로그램이다. 그래서 병렬 프로그램의 집합은 동시성 프로그램 집합의 부분 집합이다.
  • 서로 다른 쓰레드들에 작업을 할당하는 가장 직접적인 접근방법은 이 배열을 t개의 중첩되지 않은 영역으로 나누고, 그 후에 t개의 서로 다른 쓰레드 각각을 자신의 영역에서 동작하도록 할당한다.
  • 메인 쓰레드는 고유의 쓰레드 ID를 각각 피어쓰레드로 전달한다. 각각의 피어쓰레드는 자신의 쓰레드 ID를 사용해서 자신이 작업해야 할 배열의 부분을 결정한다. 이와같이 작은 고유 쓰레드 ID를 피어쓰레드로 보내는 아이디어는 많은 병렬 응용에서 사용되는 일반적인 기술이다.
  • 동기화 오버헤드는 비싸고, 가능하면 피해야한다. 만일 피할 수 없다면, 오버헤드는 가능한 한 유용한 계산만큼 축소되어야 한다.

12.7 다른 동시성의 이슈

12.7.1 쓰레드 안정성

  • 쓰레드로 프로그램 할 때, 쓰레드 안정성이라고 부르는 특성을 가지는 함수를 작성하도록 유의해야한다.
  • 어떤 함수는 다수의 동시성 스레드로부터 반복적으로 호출될 때 항상 정확한 결과를 만드는 경우에만 쓰레드 - 안전 이라고 한다. 만일 어떤 함수가 쓰레드 - 안전하지 못하다면 이것은 쓰레드 - 위험이라고 한다.
  • 쓰레드 - 위험한 함수의 네 가지 클래스
    • 클래스1
      • 공유변수를 보호하지 않는 함수들 이 함수는 보호되지 않은 전역 카운터 변수를 증가시킨다. 이 쓰레드 - 위험한 함수의 클래스는 비교적 쓰레드 - 안전하게 만들기 쉽다 : 공유변수를 P와 V같은 동기화 연산으로 보호한다. 한 가지 장점은 호출하는 프로그램에는 아무 변경도 할 필요가 없다는 것이다. 한 가지 단점은 동기화 연산들이 이 함수를 느리게 할 것이라는 점이다.
    • 클래스2
      • 다중호출에 대해서 상태를 유지하는 함수들 rand 함수는 쓰레드 - 위험한데, 그 이유는 현재 호출의 결과가 이전 반복 실행으로부터의 중간 결과에 의존하기 때문이다.
      • rand 같은 함수를 쓰레드 안전하게 만드는 유일한 방법은 이 함수를 재작성해서 static 데이터를 전혀 사용하지 않도록 하는 것이며, 이를 위해서는 호출자가 상태정보를 인자들로 전달해야한다. 단점은 프로그래머가 이제는 호출하는 루틴에서도 코드를 변경해야 한다는 것이다. 잠재적으로 수 백개의 서로 다른 호출 위치가 존재하는 큰 규모의 프로그램에서 이와 같은 수정을 하는 것은 간단한 일이 아니며 에러가 발생하기 쉽다.
    • 클래스3
      • 정적변수를 가리키는 포인터를 리턴하는 함수. 만일 이러한 함수를 동시성 쓰레드로부터 호출한다면 재앙이 발생할 수 있으며, 그 이유는 한 개의 쓰레드가 사용하는 결과들이 다른 쓰레드에 의해 조용하게 덮어써지기 때문이다.
      • 이 클래스의 쓰레드 - 위험 함수들을 다루는데 두 가지 방법이 있다. 한 가지 옵션은 함수를 다시 작성해서 호출자가 결과를 저장하는 변수의 주소를 전달하는 것이다. 이렇게 하면 모든 공유 데이터를 없앨 수 있지만, 이를 위해서는 프로그래머가 함수의 소스 코드에 접근할 수 있어야 한다.
      • 만일 쓰레드 - 위험 함수가 수정하기 어렵거나 불가능하다면(ex : 코드가 매우 복잡하거나 소스코드가 없는 경우), 다른 옵션은 lock-and-copy 기술을 이용하는 것이다. 기본 아이디어는 뮤텍스를 쓰레드 - 위험 함수와 연계하는 것이다. 각각의 호출 위치에서 뮤텍스를 잠그고, 쓰레드 - 위험 함수를 호출하며, 함수가 리턴한 결과를 사적 메모리 위치로 복사하고, 그 후에 뮤텍스를 풀어준다. 프로그래머는 호출자의 변경을 최소화 하기 위해 lock-and-copy를 수행하는 쓰레드 안전한 래퍼함수를 정의해야 하며, 쓰레드 - 위험 함수로의 모든 호출을 이 래퍼로의 호출로 대체한다.
    • 클래스4
      • 쓰레드 - 위험 함수를 호출하는 함수들. 만일 어떤 함수 f가 쓰레드 - 위험 함수 g를 호출한다면 f는 쓰레드 - 위험한가? → 그때 그때 다르다. 만일 g가 다수의 호출에 걸쳐서 상태에 의존하는 클래스2의 함수라면 f도 쓰레드 위험이며 g를 재시작하는 것 말고는 다른 방도가 없다. 그렇지만 만일 g가 클래스1 또는 클래스3 함수고, 프로그래머가 호출 위치와 다른 결과로 생성되는 공유데이터를 뮤텍스로 보호한다면 f는 여전히 쓰레드 안전이다.

12.7.2 재진입성

  • 재진입(reentrancy) .가능한 함수라고 하는 쓰레드 - 안전 함수의 중요한 클래스가 있으며, 이들은 다수의 쓰레드에 의해 호출될 때 공유데이터는 전혀 참조하지 않는 특성으로 규정된다. 비록 쓰레드 - 안전과 재진입 가능이라는 용어가 유사어로 종종 사용될지라도(부정확하게) 여기에는 준수할 가치가 있는 명확한 기술적 구분이 존재한다.
  • 모든 함수들의 집합은 쓰레드 - 안전과 쓰레드 - 위험 함수들의 중첩되지 않은 집합으로 나누어진다. 재진입가능 함수들의 집합은 쓰레드 - 안전 함수들의 적절한 부분집합이다.
  • 재 진입 가능 함수들은 대개 재진입 불가능 쓰레드 - 안전 함수들보다 더 효율적인데, 그 이유는 이들이 동기화 연산을 필요로 하지 않기 때문이다. 추가로, 클래스2 쓰레드 - 위험 함수를 쓰레드 - 안전 함수로 변환하는 유일한 방법은 이 함수를 다시 작성해서 재진입 가능하게 만드는 것이다.
  • 일부 함수의 코드를 검사하고 사전에 이것이 재진입 가능인지 선언하는 것이 가능할까? 불행하게도 상황에 따라 다르다. 만일 모든 함수 인자가 값으로 전달되고(x포인터), 모든 데이터 참조가 지역 자동 스택 변수들로 이루어진다면 이 함수는 명시적으로 재진입 가능이며, 이것이 우리가 이 함수가 재진입성을 이것이 어떻게 호출되었는지에 관계없이 선언할 수 있다는 의미에서 그렇다.
  • 하지만 만일 우리의 가정을 약간 완화하고, 그렇지 않으면 명시적으로 재진입 가능한 함수에서 일부 매개변수들을 참조 형태로 전달되게 해주며, 그 후에 만일 호출하는 쓰레드들이 포인터를 공유되지 않은 데이터로 조심스럽게 전달하려고 한다면, 이것이 유일하게 재진입 가능하다는 의미에서 간접적으로 재진입 가능 함수를 가진다. 우리는 재진입 가능이라는 용어를 명시적이고 묵시적인 재진입 가능한 함수들 모두를 포함하기 위해서 항상 사용한다. 그렇지만, 재진입성은 때로는 호출자와 피호출자 모두의 특징이며 피호출자만을 위한것은 아니다.

12.7.3 쓰레드 프로그램에서 기존 라이브러리 함수 사용하기

  • 대부분 리눅스 함수들은 표준 C라이브러리에서 정의된 함수를 포함해서 일부 예외를 제외하고는 쓰레드 - 안전하다.
  • 몇 함수는 쓰레드 - 위험한데 rand와 strtok을 제외하고, 이들은 클래스3의 변형된 형태이며, 이들은 정적변수로의 포인터를 리턴한다. 만일 쓰레드를 이용하는 프로그램에서 이중 하나의 함수를 호출할 필요가 있다면, 호출자에게 가장 덜 피해를 주는 방법은 lock-and-copy 방식이다. 그렇지만 lock-and-copy 방식은 많은 단점이 있다. 첫째, 추가적인 동기화 과정 때문에 프로그램 속도가 느려진다. 둘째, 복잡한 구조체의 구조체를 가리키는 포인터를 리턴하는 함수들은 전체 구조체 계층구조를 복사하기 위해서는 구조체 가장 말단까지 복사해야한다. 셋째, lock-and-copy 방식은 호출들에 대해서 정적 상태의 의존하는 rand 같은 클래스2 쓰레드 - 위험 함수들에 대해서는 동작하지 않는다.

12.7.4 경쟁상대

  • 경쟁(race)은 프로그램의 정확성이 다른 쓰레드가 y지점에 도착하기 전에 자신의 제어흐름에서 x지점에 도착하는 하나의 쓰레드에 의존할 때 일어난다. 경쟁은 대개 프로그래머들이 쓰레드가 실행상태 공간을 지나가는 어떤 특정궤적을 따른다고 가정하며, 쓰레드 프로그램이 모든 가능한 궤적에 대해서도 정확하게 동작해야 한다는 불문율을 잊어버리기 때문에 일어난다.

12.7.5 교착상태

  • 세마포어는 교착상태(deadlock)라고 부르는 못된 종류의 잠재적인 런타임 에러를 유발하며, 이것은 다수의 쓰레드가 절대로 참이 될 수 없는 조건을 기다리면서 정지되어있는 경우를 말한다. 진행그래프는 교착상태를 이해하기 위한 소중한 도구다
    • 프로그래머가 P와 V연산을 잘못 배치해서 두 개의 세마포어를 위한 금지된 구역이 겹치게 된다. 만일 일부 실행 궤적이 교착상태 d에 도달하게 되었다면, 더 이상의 진행은 불가능한데, 그 이유는 겹치는 금지 구역이 모든 합법적인 방향으로의 진행을 막기 때문이다.
    • 겹치는 금지구역은 교착구역이라고 부르는 상태들의 집합을 만든다. 만일 어떤 궤적이 교착구역 내의 상태와 닿는다면 교착상태는 피할 수 없다. 궤적들은 교착구역에 진입할 수 는 있지만, 결코 떠날 수는 없다.
    • 교착 상태는 언제나 예측 가능한 것이 아니므로 특히 어렵다. 프로그램이 어떤 머신에서는 잘 돌다가도 다른 머신에서는 교착상태에 빠질 수 있다. 가장 나쁜경우는 서로 다른 실행들이 서로 다른 궤적을 가지기 때문에 에러가 반복되지 않는다는 점이다.

TCP/IP

네트워크 프로그래밍과 소켓의 이해

01-1 네트워크 프로그래밍과 소켓의 이해

  • 네트워크 프로그래밍 : 서로 다른 두 컴퓨터가 데이터를 주고 받을 수 있도록 하는 것.
  • 소켓(Socket) : 물리적으로 연결된 네트워크 상에서 데이터 송수신에 사용할 수 있는 소프트웨어적인 장치. 프로그래밍에서의 ‘소켓’은 네트웨크 망의 연결에 사용되는 도구다. 연결이라는 의미가 담겨있어서 ‘소켓’이라는 표현을 사용한다. 그리고 그 의미를 조금 더 확장해서 소켓은 네트워크를 통한 두 컴퓨터에 연결을 의미하기도 한다.

socket 함수를 통해 소켓생성

  1. 소켓생성 - socket 함수 호출
  2. IP주소와 PORT번호 할당 - bind 함수호출
  3. 연결요청 가능상태로 변경 - listen 함수호출
  4. 연결요청 대한 수락 - accept 함수호출
  • 클라이언트 프로그램에서는 socket 함수 호출을 통한 소켓의 생성과 connect 함수 호출을 통한 서버로의 연결요청 과정만이 존재한다.

01-2 리눅스 기반 파일 조작하기

  • 리눅스에서의 소켓 조작은 파일 조작과 동일하게 간주된다.
  • 리눅스는 소켓을 파일의 일종으로 구분한다. 따라서 파일 입출력 함수를 소켓 입출력에, 네트워크상에서의 데이터 송수신에 사용할 수 있다.
    • 윈도우는 리눅스와 달리 파일과 소켓을 구분하고 있다.

저 수준 파일 입출력(Low-level File Access)과 파일 디스크립터(File Descriptor)

  • 파일 디스크립터란 시스템으로부터 할당받은 파일 또는 소켓에 부여된 정수를 의미한다.
  • 표준 입출력 및 표준 에러에도 리눅스에서는 파일 디스크립터를 할당하고 있다.
  • 일반적으로 파일과 소켓은 생성의 과정을 거쳐야 다일 디스크립터가 할당된다.
  • 파일 또는 소켓을 생성할 때마다, 운영체제는 해당 파일 또는 소켓에 부여된 숫자 하나를 건네준다.

파일열기

  • open(path, flag)
    • path : 대상이 되는 파일의 이름 및 경로 정보
    • flag : 파일의 오픈 모드 정보(파일의 특성 정보)
    • 데이터를 읽거나 쓰기 위해서 파일을 열 때 사용하는 함수

파일닫기

  • close(fd)
    • fd(디스크립터) : 닫고자 하는 파일
    • 파일은 사용 후 반드시 닫아줘야 한다. 파일을 닫을 때 사용하는 함수 파일 뿐만 아니라 소켓을 닫을 때도 사용한다.

파일에 데이터 쓰기

  • write(fd, buf, nbytes)
    • fd : 데이터 전송 대상을 나타내는 파일 디스크립터
    • buf : 전송할 데이터가 저장된 버퍼의 주소 값
    • nbytes : 전송할 데이터의 바이트 수 전달.
    • 프로그래머에 의해 정의되는 자료형 이름과의 구분을 위해서, 시스템(운영체제)에서 정의하는 자료형의 이름에는 _t가 붙어있다.

파일에 저장된 데이터 읽기

  • read(fd, buf, nbytes)
    • fd : 데이터 수신 대상을 나타내는 파일 디스크립터
    • buf : 수신한 데이터를 저장할 버퍼의 주소 값
    • nbytes : 수신할 최대 바이트 수
    • 데이터를 입력(수신)하는 기능의 함수다.

01-3 윈도우 기반으로 구현하기

  • 윈속(winsock)의 초기화
  • 윈속 프로그래밍을 할 때에는 반드시 WSAstartup 함수를 호출해서, 프로그램에서 요구하는 윈도우 소켓의 버전을 알리고, 해당 버전을 지원하는 라이브러리의 초기화 작업을 진행해야한다.
  • WSAstartup(WORD wversionRequested, LPWSADATA lpWSAData)
    • WORD wversionRequested : 프로그래머가 사용할 윈속의 버전 정보
    • LPWSADATA lpWSAData : WSADATA라는 구조체 변수의 주소 값
  • 윈도우 소켓에는 몇몇 버전이 존재한다. 따라서 사용할 소켓의 버전정보를 WORD 행으로 구성해서 전달한다.

백준

1018 체스판 다시 칠하기

#include <bits/stdc++.h>
using namespace std;

string WB[8] =
{
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
};

string BW[8] =
{
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
	"BWBWBWBW",
	"WBWBWBWB",
};

string board[50];
int cntWB(int x, int y);
int cntBW(int x, int y);

int main() 
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int n, m;
	cin >> n >> m;
	cin.ignore();

	for (int i = 0; i < n; ++i)
		getline(cin, board[i]);

	int min_val = 65;

	for (int i = 0; i + 8 <= n; ++i)
	{
		for (int j = 0; j + 8 <= m; ++j)
		{
			int temp = min(cntWB(i, j), cntBW(i, j));
			if (temp < min_val)
				min_val = temp;
		}
	}

	cout << min_val;
	return 0;
}

int cntWB(int x, int y)
{
	int cnt = 0;
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			if (board[x + i][y + j] != WB[i][j])
				++cnt;
		}
	}
	return cnt;
}

int cntBW(int x, int y)
{
	int cnt = 0;
	for (int i = 0; i < 8; ++i)
	{
		for (int j = 0; j < 8; ++j)
		{
			if (board[x + i][y + j] != BW[i][j])
				++cnt;
		}
	}
	return cnt;
}
  • 브루트포스 문제
  1. 비교할 체스판 배열과 board 배열을 만들어야 한다.
    • 체스판은 맨 왼쪽 윗 칸이 흰색인 경우, 검은색인 경우 두 가지가 있다.
    • 따라서 W로 시작하는 배열과 B로 시작하는 8*8배열을 미리 만들어준다.
    • 입력받은 mn 보드는 최대 5050 크기로 만들어 준다.
  2. 새로 칠해야 할 칸의 수를 구하는 함수를 구현한다.
    • 맨 왼쪽이 B인 경우와 W인 경우 두 가지를 모두 고려해서 구해야한다.
    • 따라서 두 가지를 구한다음 min함수를 통해 최솟값을 구해야한다.

2839 설탕 배달

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n, th_sugar = 3,fi_sugar = 5,check = -1;
	cin >> n;
	int i = n / fi_sugar;
	

	while (i>=0)
	{
		if (0 == ((n - (i * fi_sugar)) % th_sugar))
		{
			cout << i + ((n - (i * fi_sugar)) / th_sugar);
			check = 1;
			break;
		}
		--i;
	}
	if(-1 == check)
		cout << "-1";
	return 0;
}
  • 브루트포스 문제
  • 5로 먼저 나누어서 계산 후, 3으로 나누어 떨어지지 않으면, 5로 나누는 값을 점점 감소시키는 형식으로 코드를 짰다.
    • ex) 11이면 처음 52 를 해서 남은 1이 3으로 나누어 떨어지지 않으니 51로 6이 나누어 떨어지는지 확인하는 방법으로 진행했다.

1427 소트인사이드

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	string n;
	vector<int> n_arr;
	cin >> n;
	for (int i = 0; i < n.length(); ++i)
	{
		n_arr.push_back(n[i]-48);
	}
	sort(n_arr.begin(), n_arr.end(),greater<int>());
	for (auto i : n_arr)
		cout << i;
	return 0;
}
  • sort함수를 사용하면 쉽게 풀 수 있다.
  • char형 문자를 int 배열에 넣을 때는 아스키 코드 변환 -48사용했다. -’0’을 사용해도 된다.

11650 좌표 정렬하기

#include <bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	vector<pair<int, int>> n_arr;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int x, y;
		cin >> x >> y;
		n_arr.push_back({x, y});
	}
	sort(n_arr.begin(), n_arr.end());
	for (auto i : n_arr)
	{
		cout << i.first <<" " << i.second << '\\n';
	}
	
	return 0;
}
  • vector<pair<int,int>> 를 몰라서 조금 애먹었다. 이 함수를 사용할 줄 안다면 훨씬 편하게 풀 수 있을것이다.

11651 좌표 정렬하기2

#include <bits/stdc++.h>
using namespace std;

bool compare(pair<int, int> a, pair<int, int> b)
{
	if (a.second == b.second)
		return a.first < b.first;
	else
		return a.second < b.second;
		
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	vector<pair<int, int>> n_arr;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int x, y;
		cin >> x >> y;
		n_arr.push_back({x, y});
	}
	sort(n_arr.begin(), n_arr.end(),compare);
	for (auto i : n_arr)
	{
		cout << i.first <<" " << i.second << '\\n';
	}
	
	return 0;
}
  • 좌표 정렬하기1과 같은 문제
  • y를 기준으로 정렬하는 부분이 달라졌다
  • sort(a,b, compare)로 함수를 만들어줘서 해결했다.

10814 나이순 정렬

#include <bits/stdc++.h>
using namespace std;

bool compare(tuple<int, string, int> a, tuple<int, string, int> b)
{
	if (get<0>(a) == get<0>(b))
		return get<2>(a) < get<2>(b);
	else
		return get<0>(a) < get<0>(b);
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int n;
	vector<tuple<int, string, int>> n_arr;
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		int x;
		string y;
		cin >> x >> y;
		n_arr.push_back(make_tuple(x,y,i));
	}
	sort(n_arr.begin(), n_arr.end(),compare);
	
	for (int i = 0; i < n; ++i)
	{
		cout << get<0>(n_arr[i]) << " " << get<1>(n_arr[i]) << "\\n";
	}
	
	return 0;
}
  • vector<tuple>형태로 3개를 쌍으로 받아올 수 있다.
  • 가져올 때는 get을 통해서 받아와야한다.
    • get<인덱스>(어레이)

C++

입력함수 : cin(), getline() and cin.ignore()

  • C++의 입력 함수
  • 입력버퍼를 비우는데 사용하는 cin.ignore()

cin()

  • <iostream> 헤더에 정의되어 있다.
  • 표준 입력 버퍼에서 공백 혹은 개행 문자(\n) 이전 까지의 값만을 받아들인다.
  • 연산자를 사용하여 공백이 포함된 문자열을 입력 받을 경우, 공백 전의 문자만 입력된다는 단점이 존재한다.

    • 공백이 포함된 문자열을 입력받으려면 getline() 함수를 사용해야한다.

getline()

  • 다음과 같은 2가지로 나누어진다.
    • <istream>라이브러리에 속하는 cin.getline()
    • <string> 라이브러리에 속하는 getline()

<istream> cin.getline()

cin.getline(변수 주소, 최대 입력 수, 제한자);
  • C 형식 문자열 방식인 마지막 글자에 ‘NULL(\0)’ 문자가 포함된 문자 배열을 받는데 사용한다.
  • N-1개의 문자를 읽어와서 문자형 배열에 저장하고, 마지막 문자는 자동으로 NULL로 바꾼다.
  • 세 번째 인자 delim(제한자) 직전까지 읽어서 문자형 배열에 저장한다.
    • 제한자를 별도로 지정하지 않으면 개행문자(\n)로 인식한다.

<string> getline()

getline(입력 스트림, string 객체, 구분자);
  • 지정한 구분자(Delimiter)를 만날 때까지 문자열을 입력받아 string객체에 저장한다.
  • 구분자는 따로 지정해주지 않아도 된다.

cin.ignore() 함수 사용하기 전 참고사항

  • cin으로 입력받을 경우, 버퍼에 ‘\n’이 남는다.
  • cin 다음 입력을 cin으로 받을 경우, 전 버퍼에 있던 공백 및 개행문자를 무시하기 때문에 없다.
  • cin 다음 입력을 getline 으로 받을경우, 전 버퍼에 있던 공백 및 개행문자를 포함해서 입력받기 때문에 버퍼를 지워주는 작업이 필요하다.
  • getline 다음 입력을 getline 으로 받을경우, getline은 ‘\n’ 문자를 버퍼에 포함시키기 않기 때문에 버퍼를 비워줄 필요가 없다.

Sort()

  • sort 알고리즘은 <algorithm> 헤더파일에 속해있다.
  • sort(start,end)를 이용해서 범위에 있는 인자 (element)를 오름차순으로 정렬해준다.
  • quick sort(퀵 정렬)을 기반으로 함수가 구현되어있어, 평균 시간복잡도는 nlogn이다.
sort(arr,arr+n);
sort(v.begin(), v.end())
sort(v.begin(), v.end(), compare());         // 사용자 정의 함수
sort(v.begin(), v.end(), greater<자료형>()); //  내림차순
sort(v.begin(), v.end(), less<자료형>());    //  오름차순
728x90

'Study > TIL(Today I Learned)' 카테고리의 다른 글

24.02.23 CSAPP, 백준, KEYWORD  (0) 2024.02.24
24.02.22 백준,KEYWORD  (1) 2024.02.23
24.02.20 퀴즈, CSAPP, 백준  (1) 2024.02.20
24.02.19 CSAPP, 백준, Keyword  (1) 2024.02.19
24.02.18 CSAPP 11, Keyword  (0) 2024.02.18