struct big_integer { char *digit; int length; char sign; struct big_integer* add(struct big_integer lhs, struct big_integer rhs); struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs); struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs); struct big_integer* divide(struct big_integer lhs, struct big_integer rhs); };


지난 시간에 이어 포스팅을 하겠다. 지난 시간에는 C 구조체를 이용해서 위와 같은 big_integer 구조체에 필요한 맴버변수들과 관련 함수들을 묶어서 캡슐화를 할 수 있다는 것 까지 진행했다. 이렇게 확장된 구조체를 C++에서는 클래스라고 부른다. 따라서 다음과 같이 나타내어질 수 있다.

class big_integer { char *digit; int length; char sign; struct big_integer* add(struct big_integer lhs, struct big_integer rhs); struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs); struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs); struct big_integer* divide(struct big_integer lhs, struct big_integer rhs); };


위 구조체와 달라진 점은, struct가 class로 바뀌었다는 것 뿐이다. 실제로 C++에서 구조체와 클래스의 문법적인 차이는 매우 미미하다. 하지만 단지 구조체에 함수를 포함시켰다는 것의 작은 의미가 아니라, 절차지향 프로그래밍에서 객체지향 프로그래밍이라는 패러다임의 변화가 함축되어 있는 그러한 부분이다. 따라서 이러한 상징성을 위해서 class라는 새로운 이름을 부여한 것이다.


게다가 실제로 객체지향 프로그래밍을 할 때, 다른 객체지향 개념이 내재된 언어에서 구조체라는 단어는 쓰지 않고 모두 클래스와 객체라고 부른다. 그러면 문법적인 부분에서 C++의 구조체와 클래스의 차이는 어떠한 것이 있을까?


이를 알기 위해선 우선 접근지정자(Access Modifier)와 정보 은닉(Data Hiding)에 대하여 알아야 한다.


객체지향 패러다임에서는 절차지향 패러다임 보다 코드의 모듈화와 재사용성에 많이 관심을 가지면서도, 사람에 의한 실수들을 줄이는 방향으로 발전했다.


객체지향 패러다임에서는 남이 작성한 클래스와 모듈들을 쉽게 재사용하도록 하면서 생산성을 늘렸다. 남이 미리 작성한 클래스들의 내부적인 복잡한 로직은 알 필요가 없도록 추상화되어 숨겨져있고, 어떠한 상황에서 어떠한 함수를 호출해야 하는지 정도만 알면 된다.


하지만 또 다른 관점으로 보면 다른 누군가가 작성한 그 클래스를 사용하는 개발자는 그 클래스의 내부 로직에 대해 잘 모를 것이고, 내부의 중요한 값들을 잘못 건드렸다가 내부적 로직이 꼬이거나 버그를 유발할 수도 있을 것이다.


예를 들어서 big_integer 클래스를 사용하는 누군가가 big_integer.length += 5; 와 같은 코드를 추가하게 된다면 어떠한 일이 발생할까? 실제 자릿수의 값들은 digit이라는 char 포인터 변수가 가리키는 곳에 문자열 형태로 있을 것이고, 이 때 문자열의 길이는 length라는 변수로 계산이 될 것이다. 따라서 허용되지 않은 메모리에 접근하게 될 수도 있다. 그러므로 big_integer 클래스를 사용하는 개발자는 length라는 변수의 값을 읽는 것은 가능하게 하되, length의 변수의 값을 마음대로 바꾸도록 하면 안된다. length의 값은 대입, 덧셈, 뺄샘, 곱셈, 나눗셈 등의 연산으로 인하여 자연스럽게 변화되는 경우에만 변해야 한다. 이럴 때 적용할 수 있는 것이 접근지정자이다.

class big_integer {
private:
	char *digit;
	int length;
	char sign;
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
};

private라는 이름의 접근 지정자를 설정함으로써, private 접근지정자 밑의 맴버변수와 메소드들은 모두 외부에서 접근이 불가능하도록 변경되었다. 하지만 이렇게 되는 경우는 메소드들도 접근할 수 없게 되므로 좀 곤란해진다. 따라서 메소드들은 외부에서 접근이 가능하도록 변경해 보았다.


class big_integer {
private:
	char *digit;
	int length;
	char sign;
public:
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
};

이렇게 해서 메소드들은 외부에서 접근이 가능하지만, 멤버변수들은 그렇지 않도록 설정되었다. 그러면 big_integer의 자릿수를 length 변수를 통해서 알아내고 싶다면 어떻게 해야할까?


length 변수에 대한 getter 함수를 지정해주면 된다. 다음과 같은 형태가 될 것이다.

class big_integer {
private:
	char *digit;
	int length;
	char sign;
public:
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
	int get_length() {
		return length;
	}
};

위와 같이 get_length 함수를 정의해주면, 외부에서 length 멤버변수의 값을 알아야 할 때, get_length 함수를 호출하면서 간단하게 값을 알아낼 수 있다.

일반적으로 클래스의 메소드들을 디자인할 때, 이러한 점에 입각해서 멤버변수들은 모두 private 접근지정자를 설정하고, 메소드들은 public 접근지정자를 설정하는 것이 일반적이다. 그리고 접근해야 할 필요가 있는 멤버변수들에 대해서는 각각 getter 함수와 setter 함수를 지정한다. 만약 setter 함수를 지정하게 된다면 다음과 같은 모습이 될 것이다.


class big_integer {
private:
	char *digit;
	int length;
	char sign;
public:
	struct big_integer* add(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs);
	struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);
	int get_length() {
		return length;
	}
	void set_length(int length) {
		this->length = length;
	}
};

하지만 이 big_integer 클래스에서는 length의 값을 임의로 바꾸면 안되므로, set_length 함수가 없는 것이 낫다. 그리고 만약 set_length 함수를 사용한다고 하더라도 저렇게 간단하게 값만 대입하는 방식이 아닌, 입력받은 값이 정당한 값인지 확인하는 과정이 필요할 것이다. 예를 들면 length의 인자에 음수가 들어올 경우 0값을 대입한다는 식으로 말이다.


이렇게 맴버변수와 같이 잘못 건드릴 수 있는 값들을 접근지정자 등을 통해서 외부에서 잘못 바꾸지 않도록 안전장치를 만드는 것을 정보 은닉(Data Hiding)이라고 한다.


이 정보 은닉을 객체지향 프로그래밍의 특징의 한 카테고리고 분류해서 넣는 경우도 있지만, 일반적으로는 저번 포스팅에서 언급했던 "캡슐화"의 특징 중 하나로 보는 경우가 많다. 따라서 "캡슐화"의 특징은 두개로 나뉜다고 볼 수 있다.

1) 관련된 데이터(멤버변수)와 동작(메소드)를 한 곳에 묶어음

2) 외부에서 몰라도 되거나, 몰라야 하는 정보들을 자유롭게 접근하지 못하도록 제한하고 은닉함 (정보 은닉)


이제 C++ 언어에서 구조체와 클래스의 문법적 차이점을 알아보자. 이 두 개의 문법상 차이는 기본 접근 지정자(Default access modifier)가 구조체의 경우 public이고, 클래스의 경우 private라는 것이다. 다시 말하면, 접근 지정자를 설정하지 않을 경우 구조체는 모두 public이고, 클래스는 모두 private이다.

------------------------------------

다음 포스팅에서 이어진다.

이번에는 객체지향 프로그래밍의 개념에 대해서 간단간단하게 설명해보는 포스팅을 올려볼까 한다. 


> 일단 객체지향 프로그래밍이라는 프로그래밍 패러다임이 새로 생겨나게 된 배경에 대해서 설명해보겠다. 

객체지향 프로그래밍 패러다임이 있기 전에는 절차지향 프로그래밍이라는 패러다임이 있었는데, 이는 문제를 해결하는 절차들, Step by Step에 포커스를 맞춘 방식의 프로그래밍 패러다임이었다. 그런데 하드웨어는 급속도로 발달하지만, 소프트웨어는 개발 속도도 늦고 버그도 많고 해서 하드웨어의 발전 속도를 못 따라가는 일이 생겼는데, 이를 간단히 이야기 해서 '소프트웨어 위기'라고 불렀다.


이를 해결하기 위해서 소프트웨어도 하드웨어 부품들을 조립하는 것 처럼, 소프트웨어도 객체라는 부품으로 나누어서 개발을 하고, 이런 객체들을 조립하는 식으로 해보자 라는 아이디어가 객체지향 프로그래밍이다.


이제 객체지향 프로그래밍이 어떤 것인지 예제를 통해서 알아보자. 이 포스팅의 독자는 C언어에 대해서는 기본적은 다 알고 객체지향 개념은 잘 모르는 사람이라고 가정한다.


C언어에서의 문자열(String)은 char형 배열로 표현된다. 하지만 이 방식은 여러모로 불편한 점이 많다. 예를 들어서 scanf("%s");와 같은 코드로 문자열을 입력받을 때, 문자열의 크기가 얼마나 될 지 모르기 때문에 배열의 크기를 너무 작게 지정하면 버퍼 터짐(Buffer overflow) 현상이 나타날 것이고, 너무 크게 지정하면 메모리의 낭비가 될 것이다.


다음은 C언어로 문자열을 입력받는 코드이다.

#include <stdio.h> int main() { char str[100]; // 입력받을 문자열의 길이가 99보다 크다면 Buffer overflow 발생 scanf("%s", str); }


하지만 C에서 객체지향의 개념이 추가된 C++언어로 같은 동작을 하는 코드를 작성하면 다음과 같이 나타난다.


 
#include <iostream>
#include <string>
using namespace std;
int main() {
	string str;
	cin >> str;
}


위에 있는 C로 작성된 코드의 경우는 입력 받을 문자열의 길이가 99이하 라고 가정하고 100만큼의 메모리만 할당된 char 배열을 선언해서 입력을 받았다. 따라서 99보다 길이가 작은 문자열을 받으면 안쓰는 메모리가 필연적으로 생기고, 99보다 길이가 크다면 버퍼 오버플로가 발생한다.

하지만 C++로 작성한 코드의 경우 string이라는 객체를 사용하면 입력 받을 문자열의 길이에 대하여 상관할 필요가 없다. string 객체 내부적으로 알아서 입력크기에 맞게 메모리 할당을 유동적으로 해주도록 하는 코드가 이미 작성이 되어 있고 그 코드는 흔히 나타날 수 있는 버그들은 알아서 잘 수정이 되어있는 상태이다. 따라서 우리는 이전에 어떤 누군가가 작성한 string이라는 객체 클래스를 사용함으로써 문자열을 이렇게 쉽게 다룰 수 있게 된 것이다.


그리고 이 string 객체를 사용하는 개발자는 string 객체 내에 멤버변수나 메소드가 어떻게 정의되어있는지는 알 필요가 없다. 단지 해당 객체에 어떤 함수가 있고, 그 함수는 어떤 인자를 받고, 어떤 리턴값을 주는지만 알면 된다. 예를 들면 해당 문자열의 길이를 알고 싶다면 개발자는 다음 length함수를 호출하기만 하면 된다.


#include <iostream> #include <string> using namespace std; int main() { string str("Lorem ipsum"); size_t len = str.length(); cout << len << '\n'; return 0; }

단지 개발자는 string 클래스에 length라는 함수가 있고 이 함수의 원형은 size_t length(void); 이며 리턴값이, 해당 문자열의 길이라는 것만 알면 되고, 내부적으로 해당 함수가 어떻게 구현되어있는지 알 필요가 없다. 따라서 string 클래스 내부 구조에 신경을 쓸 필요도 없다.


이러한 특징을 "추상화"라고 하며 이는 객체지향 프로그래밍의 4대 특징 중 하나이다. 해당 클래스 사용자는 클래스에 대해서 '추상적'으로만 알면 된다는 것이다. length함수 -> 문자열 길이 리턴 이라고 '추상적'으로만 알면 되고 length 함수 호출 시 어떠한 내부 기작이 일어나고 메모리에서 어떤 일이 일어나는지 '구체적'으로 알 필요가 없다는 뜻이다.


여기까지가 객체지향 프로그래밍에 있는 객체를 '사용하는 입장'에서 알아본 것이다.


이제 객체라는 개념이 C언어 문법에서 C++문법으로 확장될 때 프로그래밍 언어의 문법적인 관점에서는 어떻게 해석되는지 알아보자.


C언어에는 구조체라는 문법이 있다. Composite Data Type의 대표격이며, Primitive Data Type들과 Composite Data Type들을 묶어서 한 덩어리로 만들 수 있다. 한 예를 들어서 C언어에서 64bit 정수형으로 나타낼 수 있는 값 보다 훨씬 큰 정수 값을 다루기 위한 big_integer라는 구조체를 만든다고 생각해보자. 아마 다음과 같이 구성할 수 있을 것이다.


struct big_integer { char *digits; int length; char sign; // 0이면 양수, 1이면 음수를 나타낸다. };


숫자의 길이를 알 수 없으므로 char 형 포인터를 이용해서 동적 메모리 할당을 통해서 배열에 자릿수별 숫자를 저장한다고 설계하자. 그리고 그 숫자의 길이는 length라는 변수에 저장되고, 양수 음수의 여부는 sign이라는 값을 통해 저장한다. 1bit의 값만 저장하면 되므로 bool 자료형을 쓰면 좋겠지만, 안타깝게도 C언어에는 bool 자료형이 없다.


이제 저렇게 구조체를 구성했으니, 해당 big_integer에 기본적인 연산능력들을 넣어주기 위한 함수들을 만들어야 한다. 일단 대충만 봐도 값 할당을 위한 함수와, big_integer간의 사칙연산을 위한 함수들과 C 문자열을 big_integer로 바꿔주는 함수, 그리고 big_integer를 C 문자열로 바꿔주는 함수도 필요할 것 같다. 일단 사칙연산 함수들의 프로토타입만 한번 생각해보자.

struct big_integer* add(struct big_integer lhs, struct big_integer rhs); struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs); struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs); struct big_integer* divide(struct big_integer lhs, struct big_integer rhs);


함수에서 각 좌항 우항을 넣어서 호출 시, 함수 내부에서 big_integer 구조체를 malloc으로 동적할당한 뒤 필요한 값들을 넣고 리턴을 해준다고 생각해보면 위와 같은 프로토타입이 나타날 수 있다.


함수 명들은 직관적으로 add, subtract, multiply, divide등으로 명명하였다. 하지만 만약에 big_integer 구조체 외에 큰 수의 부동소수점을 나타내기 위한 big_float라는 구조체가 더 있다면 어떠할까?


비슷한 방식으로 big_float라는 구조체가 선언될 것이다. 그리고 해당 구조체에서 사용할 함수들도 생겨나야 하는데 그 함수들도 모두 big_float 구조체의 사칙연산을 처리해야할 것이다. 이렇게 해당 구조체에서만 사용될만한 함수 이름이 겹치기 쉬워진다. 따라서 해당 함수들의 이름 앞에 사용될 구조체의 이름을 붙이거나, 아니면 함수 오버로딩과 같은 방식을 통해서 이러한 문제를 해결해야 한다.


그리고 만약 big_integer라는 구조채를 다른 사람들도 사용할 수 있도록 배포한다고 하면, 구조체 뿐만 아니라 해당 구조체용 함수들도 같이 배표해야 한다.


물론 그렇게 해도 된다. 그래서 C언어에서도 객체지향 프로그래밍 패러다임을 따르는 것 처럼 프로그래밍이 가능하다. 하지만 큰 소프트웨어 프로젝트를 진행할 때는 이러한 부분들을 프로그래밍 언어차원에서 지원을 해 주면 개발자들이 좀 더 직관적이고 편하게 개발을 할 수 있다. 사람이 할 수 있는 실수들과 햇갈릴 수 있는 것들을 도구 차원에서 덜 햇갈리게 하고 실수를 방지하는 장치들을 추가해주는 것이다.


그렇게 객체지향 프로그래밍 언어인 C++에서는 객체지향 프로그래밍을 위하여 C에서 사용되는 구조체들을 다음과 같이 확장해 나갔다.

struct big_integer { char *digit; int length; char sign; struct big_integer* add(struct big_integer lhs, struct big_integer rhs); struct big_integer* subtract(struct big_integer lhs, struct big_integer rhs); struct big_integer* multiply(struct big_integer lhs, struct big_integer rhs); struct big_integer* divide(struct big_integer lhs, struct big_integer rhs); };

big_integer라는 구조체에 해당 구조체를 위해 필요한 함수들을 구조체에 포함시켜버렸다. 언어차원에서 C절차지향 -> C++객체지향으로 발전한 것은 간단하게 생각하면 구조체에 함수도 같이 포함시킬 수 있다는 점인 것이다.


이렇게 관련있는 데이터(구조체 맴버변수)에 함수들도 묶어버린 것을 "캡슐화"라고 한다. 이 특징 역시 추상화와 같이 객체지향 프로그래밍 4대 특징 중 하나이다. 데이터와 동작을 묶어서 하나의 캡슐로 묶어버린 것이라고 생각하면 이해하기 쉽다.


이렇게 해서 이 하나의 big_integer라는 구조체에 함수를 포함시키는 확장을 함으로써, 이 구조체가 소프트웨어의 부품으로서 동작할 수 있게 된 것이다.

-----------------------------------------

다음 포스팅에서 이어진다.

한국정보올림피아드(정올) 2014년도 초등부 문제 풀이 포스팅입니다.


문제들은 백준저지에서 참고하고 풀이했습니다.

https://www.acmicpc.net/category/detail/1274


총 4문제가 있습니다.


1번 전자레인지 문제입니다. (백준 10162)

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


나눗셈 연산과 모듈러 연산을 이용하면 간단하게 해결할 수 있습니다.



 

#include <iostream>

using namespace std;

int main() {
	int t;
	cin >> t;
	if (t % 10 != 0) {
		cout << -1 << endl;
		return 0;
	}
	int m300, m60, m10;
	m300 = m60 = m10 = 0;
	
	m300 = t/300;
	t %= 300;
	m60 = t/60;
	t %= 60;
	m10 = t/10;
	cout << m300 << ' ' << m60 << ' ' << m10 << endl;
	return 0;
}


2번 색종이 문제입니다. (백준 10163)

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


N값이 작으므로, 2차원 배열로 종이 그리드를 모두 나타내고 시뮬레이션 한 뒤 개수를 세면 됩니다.



 

#include <iostream>

using namespace std;

int map[102][102];
int sz[101];
int n;
int main() {
	cin >> n;
	int sx, sy, dx, dy;
	for (int i=1; i <= n; i++) {
		cin >> sx >> sy >> dx >> dy;
		dx += sx;
		dy += sy;
		for (int x=sx; x < dx; x++) {
			for (int y=sy; y <dy; y++) {
				map[x][y] = i;
			}
		}
	}
	
	for (int i=0; i < 101; i++) {
		for (int j=0; j < 101; j++) {
			if (map[i][j]) {
				sz[ map[i][j] ]++;
			}
		}
	}
	for (int i=1; i <= n; i++) {
		cout << sz[i] << endl;
	}
}


3번 격자상의 경로 문제입니다. (백준 10164)

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


다이나믹 프로그래밍으로 문제를 해결할 수 있습니다. K값이 하나 뿐이므로, (시작점 -> K까지 경로)와 (K지점 -> 도착점까지 경로)를 나누어서 구해주면 된다. 숫자를 1부터 세므로 이에 따른 오류를 조심해야 한다.


get함수를 쓸 때 dp[x][y]는 시작 지점에서 (x, y)까지 도달 할 수 있는 경로의 개수를 뜻한다.

get2 함수를 쓸 때에는, (limitx, limity)에서 (x, y)로 도달할 수 있는 경로의 개수를 뜻한다.

get함수가 호출되었을 때에는 K지점을 기점으로 왼쪽과 위쪽부분의 부분 사각형에만 값이 들어가 있으며 또한 get2함수에서 (limitx, limity)보다 위쪽이나 왼쪽은 0으로 예외처리가 되어있게 처리되어있다.


 

#include <iostream>

using namespace std;
int dp[16][16];

int n, m, k;

int get(int x, int y) {
	if (x < 0 || y < 0) return 0;
	if (x == 0 && y == 0) return 1;
	if (dp[x][y]) return dp[x][y];
	
	return dp[x][y] = get(x-1, y) + get(x, y-1);
}

int get2(int x, int y, int limitx, int limity) {
	if (x < limitx || y < limity) return 0;
	if (dp[x][y]) return dp[x][y];
	
	return dp[x][y] = get2(x-1, y, limitx, limity) + get2(x, y-1, limitx, limity);
}
int main() {
	cin >> n >> m >> k;
	
	if (!k) {
		cout << get(n-1, m-1) << endl;
	} else {
		int xpos = (k-1) / m;
		int ypos = (k-1) % m;
		get(xpos, ypos);
		cout << get2(n-1, m-1, xpos, ypos) << endl;
	}
}


4번 버스 노선 문제입니다. (백준 10165)

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


케이스를 잘 나누어야 한다. 일단 노선이 직선일 경우에 대하여 생각을 해 보자. 비교 연산자를 재정의해서 소팅해서, 시작위치는 오름차순으로, 끝 위치는 내림차순으로 정렬한다.    

그러면 소팅을 하고 나서 선형탐색을 앞에서 뒤로 할 때, 뒤에 나타난 녀석이 앞에 있는 녀석을 포함하는 경우는 없다. 

시작위치는 뒤로 갈 수록 앞으로 가기 때문에 시작 범위는 줄어들기 마련이다.    

그리고 시작 위치가 고정인 상태에서는 끝나는 위치는 계속해서 작아지게 되어있으므로, 시작 위치가 다음 값이 되었을 때 끝 위치가 가장 큰놈 일 것이다. 이러한 점을 이용해서 끝놈 위치만 저장해 놓고, 끝놈보다 작으면 포함시켜버리고, 끝놈보다 크면, 그 끝놈 위치를 새 끝놈 위치로 저장해서 끝만 비교하면서 선형 탐색을 하면 된다.    


그러면 또 노선이 원형일 경우를 체크를 해야 하는데, 시작점<끝점 의 경우 A그룹으로 정의하고 시작점>끝점 의 경우를 B그룹으로 정의를 하자. B그룹의 경우는 0번위치를 무조건 통과하고 A그룹은 0번 위치를 지나갈 수는 없다. 따라서 A그룹이 B그룹을 포함할 수는 없다. 

B그룹에서 시작 부분의 최대값을 구하고, 끝 부분의 최소값을 구해서 A그룹의 (?~시작부분 최대값) 의 경우와 (끝부분 최소값~?)을 모두    

포함할 수 있다. 이러한 경우를 체크해 주고(B가 A를 포함하는 경우) A그룹이 A를 포함하는 경우와 B그룹이 B를 포함하는 경우는 직선에서 비교하는 것과 똑같은 방법으로 체크하면 된다.

#include <bits/stdc++.h> using namespace std; int n, m; struct Route { int src, dst, num; }; bool cmp(const struct Route& lhs, const struct Route& rhs) { if (lhs.src != rhs.src) return lhs.src < rhs.src; return lhs.dst > rhs.dst; } vector<Route> small, large; //인덱스 숫자가 작을수록 범위가 큰놈이다. vector<bool> ans; int main() { cin >> n >> m; ans.reserve(m+1); int large_over = -1; int large_below = n+1; int over = 0; for (int i=1; i<=m; i++) { Route tmp; scanf("%d %d", &tmp.src, &tmp.dst); tmp.num = i; if (tmp.src < tmp.dst) { small.push_back(tmp); } else { large_over = max(large_over, tmp.dst); large_below = min(large_below, tmp.src); large.push_back(tmp); } } sort(small.begin(), small.end(), cmp); sort(large.begin(), large.end(), cmp); //초기 large_over값은 large가 small 덮어쓰는 경우(0~over 범위로 덮는 경우임) //초기 large_below값은 large가 small 덮어쓰는 경우(below~N) 범위로 덮는 경우 //진행하다보면 small이 small 덮어쓰는 경우도 있음 for (size_t i=0; i < small.size(); i++) { if (small[i].dst <= large_over) ans[small[i].num] = true; else if (small[i].src >= large_below) ans[small[i].num] = true; if (small[i].dst <= over) { ans[small[i].num] = true; } else { over = small[i].dst; } } over = -1; //large가 large 덮어쓰는 경우 for (size_t i=0; i < large.size(); i++) { if (large[i].dst <= over) ans[large[i].num] = true; else over = large[i].dst; } for (int i=1; i <= m; i++) { if (!ans[i]) { cout << i << '\n'; } } return 0; }


+ Recent posts