Feel Coding

이 문제는 그냥 내장 함수를 사용하면 된다. 괜히 내가 정렬함수를 구현하는 것보다 훨씬 빠르고 노력도 덜 든다.

그런데 문제는 그래도 시간초과가 난다는 것이다.

endl 대신 '\n'을 쓰고

cin.tie(NULL);
ios_base::sync_with_stdio(false);

이 코드를 추가해서 시간을 줄였다.

그리고 sort 함수는 <algorithm>에 있는 sort 함수를 사용했다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	int* arr = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + n);
	for (int i = 0; i < n; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}

결과는 288ms로 성공

역시 C++은 빠르다.

그래서 파이썬으로는 어디까지 해야 시간초과가 안 나고 어디서부터 시간초과가 나는지 테스트 해봤다.

일단은 가장 무난한 코드인

n = int(input())
li = []
for i in range(n):
    li.append(int(input()))
li.sort()
for i in li:
    print(i)

이렇게 내봤더니 당연히 시간초과가 떴다.

그래서 출력시간을 줄인 이 코드로 다시 제출해봤다.

n = int(input())
li = [0] * n
for i in range(n):
    li[i] = int(input())
s = ""
li.sort()
for i in li:
    s += (str(i) + '\n')
print(s)

그래도 시간초과가 났다.

그래서 이번에는 sys.stdin.readline() 함수로 입력 받는 시간도 줄여봤다.

n = int(input())
li = [0] * n
from sys import stdin
for i in range(n):
    li[i] = int(stdin.readline())

s = ""
li.sort()
for i in li:
    s += (str(i) + '\n')
print(s)

그리고 이번에는 str(i) + '\n'과 "{}\n".format(i) 중에 뭐가 더 빠른지 테스트하기 위해서 이렇게 코드를 제출해봤다.

n = int(input())
li = []
from sys import stdin
for i in range(n):
    li.append(int(stdin.readline()))
li.sort()
s = ""
for i in li:
    s += "{}\n".format(i)
print(s)

아까 str(i) + '\n'을 사용해서 출력했을 때에는 1444ms였는데 "{}\n'.format(i)를 이용해서 출력하니까 더 느렸다.

C++은 288ms가 나오는데 파이썬은 1444ms가 최선인 것을 보고 다시 한번 C++이 빠르다는 것을 새삼 느끼고 간다.

명령의 수가 많을 경우 입출력하는데에 시간이 많이 들어서 시간초과가 될 수도 있으므로

cin.tie(NULL);
ios_base::sync_with_stdio(false);

이 코드를 써서 입출력 시간을 줄였다.

코드 구현은 스택이 비었을 경우 예외처리 하는 것 말고는 내가 따로 할 것은 없었고 C++의 <stack>을 이용했다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	stack<int> stack;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		if (s == "push") {
			int operand;
			cin >> operand;
			stack.push(operand);
		}
		else if (s == "top") {
			if (!stack.empty())
				cout << stack.top() << '\n';
			else cout << -1 << '\n';
		}
		else if (s == "size") {
			cout << stack.size() << '\n';
		}
		else if (s == "empty") {
			cout << stack.empty() << '\n';
		}
		else if (s == "pop") {
			if (!stack.empty()) {
				cout << stack.top() << '\n';
				stack.pop();
			}
			else cout << -1 << '\n';
		}
	}
	return 0;
}

매번 이렇게 내가 정렬 기준을 새로 정해서 정렬하는 문제는 항상 자바로 풀었어서 이번에는 새로 정렬하는 법을 공부하고 C++로 풀어봤다.

#include <iostream>
#include <algorithm>
#include <tuple>
#include <string>
using namespace std;

bool cmp(tuple<int, string, int>& p1, tuple<int, string, int>& p2) {
	if (get<0>(p1) == get<0>(p2)) {
		return (get<2>(p1) < get<2>(p2));
	}
	else return (get<0>(p1) < get<0>(p2));
}
int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	tuple<int, string, int>* arr = new tuple<int, string, int>[n];
	for (int i = 0; i < n; i++) {
		cin >> get<0>(arr[i]);
		cin >> get<1>(arr[i]);
		get<2>(arr[i]) = i;
	}
	sort(arr, arr + n, cmp);
	for (int i = 0; i < n; i++) {
		cout << get<0>(arr[i]) << " " << get<1>(arr[i]) << "\n";
	}
	return 0;
}

자연수 n이 주어졌을 때 n이 소수인지 아닌지 알아보려면 어떻게 해야 할까?

2부터 n-1까지 n을 나눠보면 된다.

하지만 다시 잘 생각해보면 굳이 n-1까지 가지 않아도 알 수 있다.

n / 2까지만 나눠보면 소수인지 아닌지 판별이 가능하다.

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

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int count = 0;
	for (int i = 0; i < n; i++) {
		if (numbers[i] == 1) {
		}
		else if (numbers[i] == 2) {
			count++;
		}
		else {
			bool flag = false;
			for (int j = 2; j <= numbers[i] / 2; j++) {
				if (numbers[i] % j == 0) {
					flag = true;
					break;
				}
			}
			if (!flag) count++;
		}
	}
	cout << count;
	return 0;
}

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

int main() {
	ios_base::sync_with_stdio(false);
	vector<int> v;
	for (int i = 1; i < 10000; i++) {
		if (i < 10) {
			v.push_back(i + i);
		}
		else if (i < 100) {
			v.push_back(i + i / 10 + i % 10);
		}
		else if (i < 1000) {
			v.push_back(i + i / 100 + i / 10 % 10 + i % 10);
		}
		else {
			v.push_back(i + i / 1000 + i / 100 % 10 + i / 10 % 10 + i % 10);
		}
	}
	for (int i = 1; i <= 10000; i++) {
		bool flag = false;
		for (int j = 0; j < v.size(); j++) {
			if (v[j] == i) {
				flag = true;
				break;
			}
		}
		if (!flag) {
			cout << i << endl;
		}
	}
	return 0;
}

set은 중복없이 저장하는 자료구조이다. 집합이라고 생각하면 된다.

set을 사용하려면 #include <set>으로 <set> 헤더파일을 포함시켜야 한다.

set은 템플릿 클래스이기 때문에 set 객체를 선언할 때에는 set에 들어갈 원소들의 타입을 적어줘야 한다.

선언 방법은 다음과 같다.

set<int> s;

<> 안에는 set 원소의 타입을 적으면 된다.

double 타입의 원소를 가지는 set을 만들고 싶다면

set<double> s;

하면 된다.

​

그리고 이 set 객체에 원소를 집어넣고 싶으면

s.insert(3);

이렇게 하면 된다.

int arr[10] = { 1, 1, 2, 3, 4, 4, 5, 5, 6, 7 };

이렇게 1, 4, 5가 각각 2개씩 중복되서 있는 배열을 set에 넣어보자.

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

int main() {
	int arr[10] = { 1, 1, 2, 3, 4, 4, 5, 5, 6, 7 };
	set<int> s;
	for (int i = 0; i < 10; i++) {
		s.insert(arr[i]);
	}
	cout << "set s의 크기: " << s.size() << endl;
	return 0;
}

이 코드의 실행 결과는 다음과 같다.

배열 arr의 원소 10개를 set에 집어넣었지만 set에는 7개의 원소 밖에 없다.

중복된 원소는 집어넣지 않기 때문이다.

set은 배열처럼 s[3] 이런 식으로 인덱스로 접근할 수 없다.

set을 순회하고 싶다면 다음과 같이 해야 한다.

for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++) {
	cout << *iter << " ";
}

iterator는 포인터이다. 포인터는 주소를 담고 있기 때문에 그 주소에 있는 값을 출력해보려면 * 연산자로 접근해야 한다. *iter 이렇게 말이다.

s.begin()은 set의 시작 주소이다. for문 헤더에서 iterator를 s.begin()으로 초기화한다. 그러면 iter는 set의 시작 주소를 가리키게(저장하게) 된다.

그리고 for문으로 진입한다.

for문에 진입해서는 역참조연산자 *를 이용해서 set의 원소의 값을 출력한다.

그리고 iter++을 통해 그 주소를 4바이트만큼(int 타입이므로) 증가한다. 이 과정을 set의 마지막 주소에 가기 전까지 반복하면 된다.

이 코드의 실행 결과는 다음과 같다.

arr의 원소가 중복 없이 들어가 있는 것을 볼 수 있다.

set에 있는 원소를 삭제하고 싶으면

s.erase(1);

이렇게 해주면 된다.

이렇게 1을 삭제하고 다시 s를 출력해보면

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

int main() {
	int arr[10] = { 1, 1, 2, 3, 4, 4, 5, 5, 6, 7 };
	set<int> s;
	for (int i = 0; i < 10; i++) {
		s.insert(arr[i]);
	}
	s.erase(1);
	for (set<int>::iterator iter = s.begin(); iter != s.end(); iter++) {
		cout << *iter << " ";
	}
	cout << endl;
	system("pause");
	return 0;
}

1이 사라진 것을 볼 수 있다.

set 객체가 비어있는지 확인하려면 s.empty()를 해보면 된다. s.size()가 0이면 비어있는 것이므로 1(true)을 리턴하고 아니라면 0(false)을 리턴한다.

코딩을 하다가 (x, y) 이런 순서쌍이 필요할 수도 있고 세 가지 정보를 묶어서 저장해야 할 수도 있다.

이럴 때 <tuple> 라이브러리를 사용하면 편리하다.

2-tuple은 주로 pair라고 부른다. 튜플에는 2-tuple(pair), 3-tuple, 4-tuple, 5-tuple, 6-tuple 등이 있는데 튜플이란 여러가지를 묶은 거라고 보면 된다.

튜플을 사용하려면 #include <tuple>을 써서 <tuple> 헤더파일을 포함해야 한다.

pair(2-tuple)를 만들고 싶으면 make_pair(a, b) 이런 식으로 사용하면 된다.

그리고 make_pair의 반환 타입은 pair<T1, T2> 템플릿(제네릭) 클래스이다.

2-tuple인 pair 생성 및 선언 방법은 다음과 같다.

pair<int, int> p = make_pair(1, 3);

두 개의 타입이 모두 같은 타입이 아니여도 된다.

pair<int, double> p = make_pair(1, 3.5);

템플릿이 T1, T2로 다르기 때문에 이렇게 서로 다른 타입의 데이터를 하나의 pair로 묶는 것도 가능하다.

그러면 p 객체에서 첫번째 요소인 1을 읽어오거나 두 번째 요소인 3의 값을 변경하고 싶을 때에는 어떻게 할까?

저장된 pair 객체에 저장된 요소 각각에 접근하고 싶을 때에는

p.first
p.second

이렇게 사용하면 된다.

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

int main(){
	pair<int, int> p = make_pair(1, 3);
	cout << p.first << endl;
	cout << p.second << endl;
	return 0;
}

이 코드의 실행 결과는 다음과 같다.

정리하자면 pair를 만들 때에는 make_pair() 함수를 쓰면 되고 저장할 때에는 pair<T1, T2> 타입으로 저장한다.

저장한 요소에 접근할 때에는 pair 객체.first, pair 객체.second 이렇게 읽어올 수 있다.

그럼 3-tuple을 만드는 방법을 알아보자.

3-tuple 생성 및 선언 방법은 다음과 같다.

tuple<int, int, int> t = make_tuple(1, 2, 3);

pair와 마찬가지로 튜플도 3개의 타입이 모두 같지 않아도 된다.

그럼 저장한 1, 2, 3 요소 각각에 접근하고 싶을 때에는 어떻게 할까?

아까 pair는 first, second를 이용했지만 tuple은 get<>() 함수를 이용한다.

사용 방법은

get<접근할 요소의 인덱스>(튜플 객체)

이다.

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

int main(){
	tuple<int, int, int> t = make_tuple(1, 2, 3);
	cout << get<0>(t) << endl;
	cout << get<1>(t) << endl;
	cout << get<2>(t) << endl;
	return 0;
}

이 코드를 실행하면

이런 결과가 나온다.

4-tuple, 5-tuple, 6-tuple도 마찬가지로 하면 된다. make_tuple() 함수를 이용해서 만들면 되고 get<>() 함수를 통해서 요소에 접근하는 것도 똑같다.

C언어와 C++은 포인터를 사용해서 다른 언어에 비해 강력한 기능을 수행할 수 있다.

주소에 직접 접근해서 데이터를 가져오는 등의 일을 할 수 있기 때문이다.

자바나 파이썬 등 기타 언어에서는 불가능한 일이다.

이렇게 강력한 기능을 가지고 있는 장점도 있는가 하면 단점도 있다.

포인터만 있으면 그 주소에 접근해서 그 주소에 있는 값을 읽어올 수 있다.

이것이 바로 강력한 기능이기도 하면서 치명적인 오류를 발생할 수 있는 부분이다.

잘못하면 중요한 데이터가 변경될 수도 있다.

예를 들어 이런 코드를 작성했다고 하자.

#include <iostream>
using namespace std;

int main()
{
	int* p;
	{	int a;
		a = 2;
		p = &a;
		cout << *p << endl;
	}
	cout << *p << endl; //허상 참조 발생
	return 0;
}

변수 a의 범위(scope)는 변수 a가 선언된 블럭 안에서만이다.

a가 선언된 그 중괄호를 벗어나면 a는 메모리의 스택에서 사라진다. 그리고 메모리의 그 공간을 안 쓰는 공간이라고 생각하게 된다.

따라서 메모리의 그 위치에 다른 데이터를 쓸 수도 있다.

그런데 포인터 p는 a보다 한 블럭 바깥 블럭에서 선언되었다.

(당연히 선언과 초기화를 따로 할 수도 있다.)

포인터 변수도 일반 변수와 마찬가지로

int* pa = &a;

이렇게 한 줄로 선언과 초기화를 동시에 할 수도 있는거고

int* pa;
pa = &a;

이렇게 선언과 초기화를 따로 두 문장으로 할 수도 있는 것이다.

아무튼 p가 존재하는 범위는 a보다 범위가 한 블럭 바깥 범위이다. 따라서 중괄호가 끝나 a는 메모리에서 사라졌지만 p는 아직도 살아있고 a가 저장되어 있었던 그 주소를 아직도 가리키고 있다. 

이렇게 a의 scope은 끝났지만 p의 scope은 끝나지 않았을 때 p가 간접참조연산자 *을 이용해서 *p 이렇게 접근해서 출력하면 2가 아니라 다른 이상한 값을 출력할 수도 있다.

메모리의 그 주소에 마침 다른 데이터가 아직 써지지 않았다면 2를 출력할 것이고 아니라면 이상한 값을 출력할 것이다.

그런데 이렇게 읽어만 와서 출력하는는 것은 그나마 다행이지 만약에 *p = 100; 이런 코드를 a의 scope 바깥에서 쓴다면 정말 치명적인 오류가 발생할 수도 있다. 그 주소에 중요한 데이터가 있었을 지도 모르는데 그 데이터를 100으로 덮어쓰는 것이기 때문이다.

이렇게 scope이 끝난 변수에 접근하는 것을 허상 참조(dangling pointer)라고 한다.

이처럼 포인터는 주소를 가지고 메모리의 그 위치에 접근할 수 있다는 강력한 기능을 가지고 있으면서도

그 장점으로 인한 치명적인 오류가 발생할 수도 있다.

그러한 오류를 막기 위해서 포인터를 이용한 코드를 짤 때에는 이러한 습관을 들이는 것이 좋다.

포인터 변수를 선언하고 바로 초기화해주지 않을 때에는 NULL로 초기화해주는 것이 좋다.

int* pa = NULL;

이렇게 NULL로 초기화를 해준다면 적어도 아까와 같은 치명적인 오류는 발생하지 않는다.

(참고로 NULL은 포인터 변수에만 사용할 수 있다.)

예를 들어 int* pa; 이렇게 선언해놓고 '나중에 pa에 a의 주소를 담아야지' 하고 생각하고 있었는데 깜빡하고 pa = &a; 이 코드를 쓰지 않고 pa에는 a의 주소가 있겠거니 하고 *pa 이렇게 역참조하면 아까와 같은 치명적인 오류가 발생할 것이다. pa를 초기화하지 않았기 때문에 pa가 선언된 메모리의 주소에 있던 쓰레기 값 32비트를 주소라고 생각하고 억지로 읽어와서 그 32비트 주소 메모리 위치에 접근해서 그 곳의 데이터를 바꿀 수가 있다.

하지만 NULL로 초기화해놨다면

널포인터라며 예외(런타임에러)가 발생한다. 이것은 치명적인 오류가 아니라 이것을 보고 '아 내가 널 포인터를 썼구나' 하고 코드를 짠 사람이 알게 되고 코드를 고칠 것이다.

따라서 처음에는 포인터를 NULL로 초기화 하는 것이 좋다.

LIS 문제에서 부등호 하나만 반대 부등호로 바꿔주면 된다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* numbers = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> numbers[i];
	}
	int* lds = new int[n];
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int longestLength = 0;
		for (int j = 0; j < i; j++) {
			if (numbers[i] < numbers[j]) {
				if (lds[j] > longestLength)
					longestLength = lds[j];
			}
		}
		lds[i] = longestLength + 1;
		if (lds[i] > maxLength)
			maxLength = lds[i];
	}
	cout << maxLength;
	return 0;
}

11053번 문제와 정확하게 일치하는 LIS(Longest Increasing Subsequence) 문제이다.

#include <iostream>
using namespace std;

int main() {
	int n;
	cin >> n;
	int* card = new int[n];
	for (int i = 0; i < n; i++) {
		cin >> card[i];
	}
	int* lis = new int[n];
	lis[0] = 0;
	int maxLength = 0;
	for (int i = 0; i < n; i++) {
		int longestLengthBeforeI = 0;
		for (int j = 0; j < i; j++) {
			if (card[i] > card[j]) {
				if (lis[j] > longestLengthBeforeI)
					longestLengthBeforeI = lis[j];
			}
		}
		lis[i] = longestLengthBeforeI + 1;
		if (lis[i] > maxLength)
			maxLength = lis[i];
	}
	cout << maxLength << endl;
	return 0;
}