Feel Coding

C++에서 우선순위 큐를 구현하려면 <queue> 라이브러리를 사용하면 된다. 따라서 #include <queue> 코드를 써줘야 한다.

우선순위 큐를 선언하는 코드는 다음과 같다.

priority_queue<int, vector<int>> q;

이렇게 큐를 선언하면 숫자가 클 수록 우선순위가 높은 우선순위 큐가 만들어진다.

priority_queue<int, vector<int>> q;에서 이 안에서 int는 큐에 들어갈 데이터의 타입을 말한다.

priority_queue<int, vector<int>> q;에서 vector<int>는 데이터들이 들어갈 컨테이너이다. 실제로는 이 곳에 int 데이터들이 저장된다. 하지만 동작을 우선순위 큐 처럼 하게 하기 위해서 priorty_queue 타입으로 감싼 것이라고 보면 된다.

이렇게 선언하고 나서 우선순위 큐에 데이터를 집어넣으려면

q.push(3);

이렇게 push() 함수를 이용하면 된다.

q.push(4);
q.push(9);
q.push(1);
q.push(7);
q.push(10);
q.push(2);
q.push(3);

이렇게 7개의 int형 숫자 데이터를 우선순위 큐에 집어넣은 다음

while (!q.empty()) {
	cout << q.top() << endl;
	q.pop();
}

큐가 빌 때까지 pop 하면서 출력해보면 결과는 다음과 같다.

전체 코드는 아래와 같다.

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

int main() {
	priority_queue<int, vector<int>> q;
	q.push(4);
	q.push(9);
	q.push(1);
	q.push(7);
	q.push(10);
	q.push(2);
	q.push(3);
	while (!q.empty()) {
		cout << q.top() << endl;
		q.pop();
	}
	return 0;
}

우선순위 큐는 내부적으로 내림차순으로 정렬되어 있는 것을 볼 수 있다. 따라서 이렇게 pop 할 때마다 가장 큰 값을 반환한다. pop 할 때마다 가장 큰 값을 반환하는 것은 최대 힙(heap)의 성질과 같다.

따라서 priority_queue만으로 힙의 구현이 가능하다.

작은 데이터일수록 우선순위가 높은 우선순위 큐를 만들고 싶다면? 최소 힙을 만들고 싶다면?

priority_queue<int, vector<int>, greater<int>> q;

<> 사이에 vector<int> 뒤에 콤마를 찍고 세 번째 인자(?)로 greater<int>를 넣어주면 된다.

greater라는 정렬 기준을 추가해준 것이다. greater는 오름차순 정렬이라는 소리이다.

최소힙인데 왜 오름차순이지? 할 수도 있는데 잘 생각해보면 큐는 front에서 원소를 빼는데 front는 인덱스가 0이므로 맨 앞에 가장 작은 값이 와야 한다. 따라서 오름차순으로 정렬해야

값이 작을 수록 우선순위가 높은 우선순위 큐 또는 최소힙을 만들 수 있다.

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

int main() {
	priority_queue<int, vector<int>, greater<int>> q;
	q.push(4);
	q.push(9);
	q.push(1);
	q.push(7);
	q.push(10);
	q.push(2);
	q.push(3);
	while (!q.empty()) {
		cout << q.top() << endl;
		q.pop();
	}
	return 0;
}

이 코드를 실행하면

이렇게 작은 값부터 나오는 것을 볼 수 있다.

최대힙을 만들 때에는 아까처럼 정렬 기준을 정해주지 않아도 디폴트가 내림차순 정렬이고

priority_queue<int, vector<int>, less<int>> q;

이렇게 정렬기준으로 less를 넣어줄 수도 있다. less는 내림차순으로 정렬하라는 것이다.

안드로이드 스튜디오로 개발을 할 때 로그캣은 디버깅을 하기 매우 유용하다.

하지만 종종 이렇게 LogCat에 필터를 적용해서 검색할 수 있는 창이 안 보일 때가 있다.

다른 사람들도 그런지는 모르겠지만 나는 이런 일이 자주 발생한다. 왜 그런지 이유는 모르겠다. 안드로이드 스튜디오의 버그인 것 같다.

지난 학기 안드로이드 수업 시간에 onStart, onCreate, onResume, onPause 등 생명주기 메소드가 언제 불리는지 알기 위해서 로그캣을 이용해서 실습하는 도중 로그캣 필터가 없어졌던 기억이 난다. 옆 친구들은 다 실습하는데 나만 로그캣 필터가 없어져서 매우 당황스러웠다.

그 이후에도 이런 일이 발생해서 혼자 이것저것 눌러보다가 발견한 해결법이다.

오른쪽 아래 EventLog 버튼을 누르면 이렇게 검색창이 다시 멀쩡히 보인다. 그리고 다시 EventLog를 클릭해서 이벤트 로그 창은 없애주면 된다.

LocalDate 객체로 오늘 날짜를 뽑은 다음에 그것을 문자열로 바꾸려면 이렇게 하면 된다.

LocalDate date = LocalDate.now(); //오늘 날짜 LocalDate 객체 생성
DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofPattern("yyyy-MM-dd");
String today = date.format(dateTimeFormatter); //LocalDate 객체를 String 객체로 바꿈

이렇게 LocalDate를 String으로 바꿔서 today라는 문자열을 DB에 저장했다고 하자.

나중에 DB에서 그 문자열로 된 날짜를 읽어들였는데 이 날이 무슨 요일인지 알고 싶으면 어떻게 하면 될까?

일단 문자열을 Date타입으로 바꾸자.

DateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
Date d = dateFormat.parse(today); //String이었던 today를 Date로 바꿈

이렇게 DateFormat과 parse() 메소드만 있으면 문자열을 Date 객체로 바꿀 수 있다.

그 후 이 Date 타입의 객체 d를 LocalDate 타입으로 바꿔준다.

LocalDate localDate = d.toInstant().atZone(ZoneId.systemDefault()).toLocalDate(); //Date 객체 d를 LocalDate 객체로 바꿈

Date 객체.toInstant().atZone(ZoneId.systemDefault()).toLocalDate(); 해주면 LocalDate 객체를 반환한다.

위의 두 줄을 한 줄로

LocalDate localDate = dateFormat.parse(today).toInstant().atZone(ZoneId.systemDefault()).toLocalDate();

이렇게 할 수도 있다.

그러고나면 localDate 객체에서 요일을 뽑아낼 수 있다.

DayOfWeek day = localDate.getDayOfWeek();
if(day == DayOfWeek.MONDAY) {
	System.out.println(today +"는 월요일입니다.");
}
else if (day == DayOfWeek.TUESDAY) {
	System.out.println(today +"는 화요일입니다.");
}
else if (day == DayOfWeek.WEDNESDAY) {
	System.out.println(today +"는 수요일입니다.");
}
else if (day == DayOfWeek.THURSDAY) {
	System.out.println(today +"는 목요일입니다.");
}
else if (day == DayOfWeek.FRIDAY) {
	System.out.println(today +"는 금요일입니다.");
}
else if (day == DayOfWeek.SATURDAY) {
	System.out.println(today +"는 토요일입니다.");
}
else {
	System.out.println(today +"는 일요일입니다.");
}

parse() 메소드를 사용할 때에는 ParseException이 발생하기 때문에 반드시 예외처리를 해주어야 한다.

예외처리를 해주지 않으면 이렇게 컴파일 에러가 발생한다. 이 포스팅은 예외처리에 관한 포스팅이 아니기 때문에 그냥 main 메소드에서 throw 해주었다.

전체 코드이다.

public class DateTest {
    public static void main(String[] args) throws ParseException{
        LocalDate date = LocalDate.now(); //오늘 날짜 LocalDate 객체 생성
        DateTimeFormatter dateTimeFormatter = DateTimeFormatter.ofPattern("yyyy-MM-dd");
        String today = date.format(dateTimeFormatter); //LocalDate 객체를 String 객체로 바꿈
        DateFormat dateFormat = new SimpleDateFormat("yyyy-MM-dd");
        Date d = dateFormat.parse(today); //String이었던 today를 Date로 바꿈
        LocalDate localDate = d.toInstant().atZone(ZoneId.systemDefault()).toLocalDate(); //Date를 LocalDate로
        DayOfWeek day = localDate.getDayOfWeek();
        if (day == DayOfWeek.MONDAY) {
            System.out.println(today + "는 월요일입니다.");
        } else if (day == DayOfWeek.TUESDAY) {
            System.out.println(today + "는 화요일입니다.");
        } else if (day == DayOfWeek.WEDNESDAY) {
            System.out.println(today + "는 수요일입니다.");
        } else if (day == DayOfWeek.THURSDAY) {
            System.out.println(today + "는 목요일입니다.");
        } else if (day == DayOfWeek.FRIDAY) {
            System.out.println(today + "는 금요일입니다.");
        } else if (day == DayOfWeek.SATURDAY) {
            System.out.println(today + "는 토요일입니다.");
        } else {
            System.out.println(today + "는 일요일입니다.");
        }
    }
}

이 코드를 실행하면 다음과 같이 오늘의 요일을 출력하는 것을 볼 수 있다.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	priority_queue<int, vector<int>, less<int>> q;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (x == 0) {
			if (q.empty()) cout << 0 << '\n';
			else {
				cout << q.top() << '\n';
				q.pop();
			}
		}
		else {
			q.push(x);
		}
	}
	return 0;
}

1은 소수가 아니라는 거 아주 잘 알면서도 코드 짤 때에는 그걸 생각을 안 하고 코드를 짠다.

소수 문제 풀 때 꼭 기억하자 1은 소수가 아니다!

1은 따로 예외로 두고 코드를 짜자.

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

int main() {
	int m, n;
	cin >> m >> n;
	vector<int> v;
	for (int i = m; i <= n; i++) {
		bool flag = false;
		for (int j = 2; j < i / 2 + 1; j++) {
			if (i % j == 0) {
				flag = true;
				break;
			}
		}
		if (i == 1) flag = true;
		if (!flag) v.push_back(i);
	}
	if (v.size() == 0) cout << -1 << endl;
	else {
		int total = 0;
		for (int i = 0; i < v.size(); i++) {
			total += v[i];
		}
		cout << total << endl;
		cout << v[0] << endl;
	}
	return 0;
}

벡터든 배열이든 정렬을 하려면 <algorithm> 라이브러리의 sort() 함수를 쓰면 된다. 따라서 <algorithm> 헤더파일을 포함해줘야 한다.
sort() 함수의 첫번째 두번째 매개변수는 iterator, 즉 포인터이다.

배열의 경우 (배열의 크기가 10인 경우)

sort(arr, arr + 10);

벡터의 경우

sort(v.begin(), v.end());

이렇게 하면 된다.

첫 번째 인자로는
정렬하고 싶은 데이터 집합이 배열이라면 배열의 이름을 넘겨주면 되고 (배열의 이름은 포인터니까)
벡터라면 v.begin()을 넘겨주면 된다. (벡터에서 v.begin()을 하면 벡터의 시작 주소를 반환한다.)
두 번째 인자로는
정렬하고 싶은 데이터 집합이 배열이라면 배열의 이름 + 배열의 크기을 넘겨주면 되고
벡터라면 v.begin()을 넘겨주면 된다. (벡터에서 v.end()을 하면 벡터의 마지막 주소를 반환한다.)
이렇게 매개변수 두 개를 모두 넣어주고 sort() 함수를 호출하면 오름차순으로 정렬된다.

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

int main() {
	vector<int> v = { 4, 7, 2, 5, 10, 8, 1, 6, 3 };
    cout << "정렬 전: "; 
    for (int i = 0; i < v.size(); i++) {
    	cout << v[i] << " "; 
    }
    cout << endl;
    sort(v.begin(), v.end());
    cout << "정렬 후: ";
    for (int i = 0; i < v.size(); i++) {
    	cout << v[i] << " ";
    } 
    cout << endl; 
    return 0; 
}

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

sort() 함수 호출 이후에는 오름차순으로 정렬되어 있는 것을 볼 수 있다.

배열로 해도 마찬가지이다.

#include <iostream> 
#include <algorithm> 
using namespace std; 
int main() { 
	int arr[10] = { 9, 4, 7, 2, 5, 10, 8, 1, 6, 3 }; 
    cout << "정렬 전: "; 
    for (int i = 0; i < 10; i++) { 
    	cout << arr[i] << " "; 
    } 
    cout << endl; 
    sort(arr, arr + 10); 
    cout << "정렬 후: "; 
    for (int i = 0; i < 10; i++) { 
    	cout << arr[i] << " "; 
    } 
    cout << endl; 
    return 0; 
}

이 코드를 실행해도

배열의 원소들이 오름차순으로 정렬된 것을 볼 수 있다.
벡터를 정렬하려면 sort(v.begin(), v.end());이고
배열을 정렬하려면 sort(arr, arr + 10);라는 것 기억하자.

벡터를 내림차순으로 정렬하고 싶다면 sort(v.begin(), v.end()); 대신에 sort(v.rbegin(), v.rend());를 쓰면 된다.

sort(v.rbegin(), v.rend());

그런데 오름차순이 아니라 내가 원하는 정렬 기준을 세워서 정렬하고 싶다면? 정렬하고 싶은 대상이 기초 타입이 아니라면?
sort() 함수의 세 번째 인자로 비교기준이 되는 함수포인터 또는 함수 객체를 넣어주면 된다.
그 함수는 반환타입이 bool 타입이어야 하고 매개변수는 두 개이며 두 매개변수의 타입은 정렬할 데이터의 타입과 일치해야 한다.
내림차순으로 정렬하고 싶다면 compare 함수를 이렇게 만들면 된다.

bool cmp(int a, int b) { 
  return a > b; 
}

이 cmp 함수를 sort() 함수의 3번째 인자로 넣어서 아래 코드를 실행하면

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

bool cmp(int a, int b) { 
    return a > b;
} 

int main() {
    vector<int> v = { 4, 7, 2, 5, 10, 8, 1, 6, 3 };
    cout << "정렬 전: "; 
    for (int i = 0; i < v.size(); i++) { 
    	cout << v[i] << " "; 
    } 
    cout << endl; 
    sort(v.begin(), v.end(), cmp); 
    cout << "정렬 후: "; 
    for (int i = 0; i < v.size(); i++) { 
    	cout << v[i] << " "; 
    } 
    cout << endl; 
    return 0; 
}

이렇게 내림차순으로 정렬된 것을 볼 수 있다.

배열을 정렬할 때에도 똑같이 하면 된다.

#include <iostream> 
#include <algorithm> 
using namespace std; 
bool cmp(int a, int b) { 
	return a > b;
} 

int main() { 
	int arr[10] = { 9, 4, 7, 2, 5, 10, 8, 1, 6, 3 }; 
    cout << "정렬 전: "; 
    for (int i = 0; i < 10; i++) { 
    	cout << arr[i] << " "; 
    } 
    cout << endl; 
    sort(arr, arr + 10, cmp); 
    cout << "정렬 후: "; 
    for (int i = 0; i < 10; i++) { 
    	cout << arr[i] << " "; 
    } 
    cout << endl; 
    return 0; 
}

이렇게 배열과 벡터를 정렬하는 방법을 배워보았다.
만약에 정렬하고 싶은 자료들의 타입이 기초타입이 아니라 내가 정의한 클래스라고 해도 compare 함수만 구현해서 sort 함수의 인자로 넣어준다면 나만의 기준으로 정렬할 수 있다.

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

int main() {
	int n;
	cin >> n;
	vector<int> arr;
	while (true) {
		if (n == 0) break;
		arr.push_back(n % 10);
		n /= 10;
	}
	sort(arr.begin(), arr.end());
	for (int i = arr.size() - 1; i >= 0; i--) {
		cout << arr[i];
	}
	return 0;
}

비주얼 스튜디오에서 돌릴 때에는 문제 없었지만 제출할 때에는 algorithm 헤더파일을 include 하지 않으니 컴파일 에러가 났다. 오늘도 잊지말자. find() 함수를 쓰려면 <algorithm> 헤더파일을 포함하자.

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int n, m;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	cin >> m;
	for (int i = 0; i < m; i++) {
		int temp;
		cin >> temp;
		vector<int>::iterator iter;
		iter = find(arr.begin(), arr.end(), temp);
		if (iter != arr.end()) {
			cout << 1 << '\n';
		}
		else cout << 0 << '\n';
	}
	return 0;
}

앞에 cin.tie(NULL);과 ios_base::sync_with_stdio(false);는 입출력 속도 향상을 위함이다. 이 글을 참고하면 된다.

줄바꿈을 할 때에 endl을 쓰지 않고 '\n'을 써준 것도 시간초과가 나지 않도록 하기 위함이다.

#include <iostream>
using namespace std;

int main() {
	int a, b, v;
	cin >> a >> b >> v;
	v -= a;
	int day = 1;
	day += (v / (a - b));
	if (v % (b - a) != 0)
		day++;
	cout << day;
	return 0;
}

데이터의 집합(컬렉션)을 다룰 때 배열을 사용하면 중간에 끼워넣기에도 불편하고 크기를 늘릴 수도 없어 여러 가지로 불편한 점이 많다. 그래서 더 편리한 자료구조를 만든 것이 컬렉션이다. 컬렉션과 컬렉션 프레임워크는 혼용해서 많이 쓰기 때문에 용어에 집착할 필요는 없다.

컬렉션 프레임워크는 우리가 자료구조 시간에 배운 그 자료구조들을 쉽게 이용할 수 있도록 제공해준다.

JDK 1.2까지는 제네릭 타입이 없었는데 JDK 5부터는 제네릭을 지원하므로 더 안전하게 사용 가능하다. (JDK 1.5를 JDK 5라고도 함)

컬렉션은 데이터의 집합을 말하는데 특징에 따라 두 가지 종류로 나눌 수 있다.

하나는 동일한 데이터의 집합인 Collection

또 하나는 두 가지 종류(key, value)의 데이터로 이루어진 Map이다.

이렇게 Map은 Collection과 특징이 좀 다르지만 일반적으로 넓은 의미의 컬렉션인 Collection+Map의 의미로 많이 쓴다.

Collection은 인터페이스이다. Collection 인터페이스의 자식 인터페이스로 List, Queue, Set이 있다.

일단 List, Queue, Set의 간단한 특징부터 말하자면 List는 선형적인 자료구조, Queue는 선입선출 자료구조, Set은 순서가 없고 중복이 없는 자료구조이다.

이렇게 List, Queue, Set은 Collection의 자식 인터페이스이고 Map은 Collection의 자식 인터페이스가 아니다.

Map은 key와 value를 하나의 쌍으로 저장하는 자료구조로, key 값은 중복될 수 없다. 따라서 key 값은 유일하다.

이 인터페이스 5개 (Collection, List, Queue, Set, Map)는 꼭 알아두자.

일단 컬렉션 인터페이스와 클래스의 구조부터 살펴보자. 분홍색은 인터페이스, 하늘색은 클래스이다.

List의 구현 클래스 중에서 가장 자주 쓰이는 것은 ArrayList이다. Vector는 ArrayList와 동일한데 동기화를 지원한다. 따라서 멀티스레딩, 다중화에서 사용한다. 멀티스레딩을 하는게 아니라면 굳이 더 느린 Vector를 쓸 필요는 없다.

List의 구현 클래스들을 보다보면 특이한 것을 발견했을 것이다. LinkedList는 List의 구현 클래스이자 Queue의 구현 클래스이다. 클래스를 다중 상속하는 것은 안 되지만 여러 인터페이스를 구현하는 것은 가능하다. LinkedList는 List 인터페이스도 구현하고 Queue 인터페이스도 구현한 것이다. LinkedList의 자식 클래스로 Stack이 있다.

Set의 구현 클래스로는 HashSet과 TreeMap이 있는데 TreeMap은 Map이 아니라 Set이라는 거 기억하자. 헷갈리기 쉽다.

Map에는 HashMap을 자주 사용한다. Hashtable도 종종 쓰는데 t가 소문자라는 거 기억하자. (교수님께서는 아마 만든 사람이 실수한 것 같다고 하셨다)

이제 정말 메소드들을 배워보자.

다음은 Collection 인터페이스가 제공하는 메소드이다.

헷갈리지 말아야 할 것은 컬렉션 객체의 크기(길이)를 알고 싶다면 length()가 아니라 size()라는 것이다.

문자열은 length(), 배열은 length, 컬렉션은 size()라는 거 잊지 말자.

Collection이 최상위 인터페이스이므로 이 메소드들은 하위 인터페이스, 클래스도 모두 가지고 있는 공통의 메소드이다.

굳이 컬렉션을 더 불편한 배열로 바꿀 일은 거의 없지만 그래도 배열로 바꾸는 방법은 알아야 하므로 toArray 메소드는 알아두자.

다음은 Map 인터페이스가 제공하는 메소드이다.

Map 인터페이스는 키와 값을 쌍으로 저장한다. 메소드만 봐도 containsKey(), containsValue()라는 메소드가 있다.

Map에 저장된 객체 중에 해당 key 또는 value를 가지고 있는지를 알아낼 수 있다.

get 메소드는 key를 주면 value가 나오는 메소드이다. key가 유일하기 때문에 key로 접근해서 value를 얻어올 수 있다.

isEmpty()는 굳이 외우지 않아도 당연히 알테고 put 메소드는 Collection으로 따지면 add와 같은 메소드이다. Map 객체가 <String, Integer> 타입이고 맵 객체 이름이 map이라면 map.put("one", 1); 이렇게 하면 one을 key로, 1을 value로 하는 하나의 쌍이 Map에 추가된다.

여기에서 keySet()과 values() 메소드는 꼭 알아둬야 한다. Map에 있는 데이터들을 Collection 타입으로 바꾸어야 하는 상황이 있을 수도 있다. 그런데key와 value로 이루어져있는데 Map에는 데이터 한 개에 2개의 값이 들어있으므로 key와 value를 따로 따로 가져와야 한다. key들을 가져와서 Collection으로 만드는 게 keySet() 메소드이고 value들을 가져와서 Collection으로 만드는 것은 values() 메소드이다.

그런데 key들을 모아서 컬렉션으로 만드는데 keySet() 메소드의 반환타입은 왜 하필 Set일까?

Map의 특징 중 하나, key값들끼리는 중복이 없으므로 Set의 특징인 중복이 없는 것과 일치한다. 따라서 key값들을 모으면 저장할 자료구조는 Set이 딱이다. keySet() 메소드의 반환타입은 Set<K>인데 K는 key를 말한다. Map 원소들 중 key의 타입이었던 그 타입이 Set의 원소들의 타입이 되는 것이다.

반면 values() 메소드는 반환 타입이 Collection<V>이다. value 값들을 모아서 컬렉션으로 만드는데 value는 중복되어도 되기 때문에 중복 데이터가 있을 수 있다. 따라서 Set으로는 못 바꾸고 Collection으로 바꾸는 것이다. 물론 Set도 Collection이다. (Collection의 자식인터페이스)

사실 여기까지 봤을 때에는 무슨 소리인지 잘 모를 수도 있지만 이에 해당하는 예제 코드들을 보면 이해가 갈 것이다. 예제는 다음 글에 이어가겠다.