신년맞이 boj - day3

5639 이진 검색 트리

평소에 트리를 읽는 순서인 전위순회대로 주어지는 입력값으로 이진 트리를 만들고, 후회순회를 돌리면 된다

첫 값인 root를 기준(now)으로 잡고 왼쪽 오른쪽 값을 비교한다

만약 노드가 없으면 주어진 값으로 새로운 노드를 만들고, 아니면 그 노드를 now로 두고 다시 탐색 돌아간다

 

이진 탐색 트리 구현은 전에 썼던 글이 있다

AVL트리 foxtrotin.tistory.com/191

이진 탐색 트리 foxtrotin.tistory.com/190

 

그리고 입력의 끝이 주어지지 않을 때 c++에서는 while(cin>>num){} 이렇게 하면 된다

while문으로만 EOF처리가 되기 때문에 저렇게 썼는데도 런타임 에러가 난다면 배열 크기나 벡터 초기화나 다른 곳을 살펴본다

 

github.com/proqk/Algorithm/blob/master/Tree/5639%20%EC%9D%B4%EC%A7%84%20%EA%B2%80%EC%83%89%20%ED%8A%B8%EB%A6%AC.cpp

 

---

그리디->항상 최적이 아니다

그럼 언제 쓰냐? -> 항상 지금 이 순간의 최고의 선택을 하는 것이 최적인 문제에서

그걸 어케 알지? -> 이걸 문제에서 캐치하는 것이 그리디 문제의 핵심이다

 

 

1931 회의실 배정

끝나는 시간이 같으면->시작하는 시간이 짧은 순서대로 정렬한다 
끝나는 시간이 같지 않으면->끝나는 시간이 짧은 순서대로 정렬한다

 

끝나는 시간을 기준으로 정렬하고 최대한 많이 욱여넣으면 최적의 해를 구할 수 있다

 

sort 함수의 정렬 기준 바꾸는 방법: foxtrotin.tistory.com/93

쓸 때는 알고 있다가도 한동안 안 쓰면 금세 헷갈리는 이것..

 

bool cmp(const A& first, const A& second) {
	if (first.e == second.e) return first.s < second.s;
	else return first.e < second.e;
}

이렇게 쓰면

이렇게 정렬된다

 

github.com/proqk/Algorithm/blob/master/greedy/1931%20%ED%9A%8C%EC%9D%98%EC%8B%A4%20%EB%B0%B0%EC%A0%95(2).cpp

 

 

1080 행렬

처음에는 최대 50x50니까 3x3을 전부 뒤집어 보면서 원하는 결과가 나오면 출력하는 식으로 할 수 있을 거라고 생각했다

근데 강의 들어보니까 더 쉽고 간단한 방법이 있었다

생각해 보면, 네 귀퉁이 부분을 뒤집을 수 있는 3x3뒤집기 연산은 딱 하나씩밖에 없다

 

예를 들어 저곳을 0으로 뒤집고 싶다면, 3x3을 저렇게 해야만 포함이 된다

 

그래서 왼쪽 맨위를 기준으로 (0,0)을 원하는 값으로 맞추고,

3x3를 한 칸 오른쪽으로 옮겨서 (0,1)을 원하는 값으로 맞추는 식으로 가다 보면 맨 위 줄이 전부 맞춰진다

그럼 그 다음 줄도 같은 방법으로 맞춰준다

 

다만 3x3박스를 기준으로 뒤집는 연산을 하는 것이니까, 범위를 n-2, m-2로 둔다는 점을 주의한다

 

그리고 c++이라서 또 주의할 점은 c에서는 정수 한 자리씩 입력을 %1d로 하면 됐는데 c++은 그렇게 못 한다

그렇다고 cin >> a[i][j]; 로 해 버리면 입력 자체가 안 된다

문자열로 받던가, char형 변수로 입력 받고 정수 변환 후 넣어준다

 

github.com/proqk/Algorithm/blob/master/greedy/1080%20%ED%96%89%EB%A0%AC.cpp

 

 

2138 전구와 스위치

행렬 문제에서는 바꿀 수 있는 경우가 유일한 칸이 있어서 그걸 기준으로 했는데

이 문제는 범위를 벗어날 수 있기 때문에 사실상 유일한 칸은 없다(위 그림 주황색 참고)

예를 들어 예제 입력인 0 0 0을 바꿀 수 있는 경우의 수로 표현하면 2 3 2가 된다. 즉 1인 값이 없어서 행렬 문제처럼 불가능하다

 

그런데 만약 0번째 전구가 0인지 1인지 알 수 있다면?

0번째 전구는 값이 정해졌으니까 경우의 수를 1이라고 볼 수 있다

그러면 그 뒤의 값들도 변하므로 1 2 2가 되고, 1인 값이 있으므로 행렬 문제처럼 풀 수 있게 된다

 

그러면 0번째 전구가 0인지 1인지 알 수 있는 방법은 뭘까?

둘 다 탐색을 돌려보고 가능한 곳을 선택한다. 둘 다 가능하다면 둘 중에 최솟값을 선택한다

 

실버2인데 많이 어려웠던 문제..

 

github.com/proqk/Algorithm/blob/master/greedy/2138%20%EC%A0%84%EA%B5%AC%EC%99%80%20%EC%8A%A4%EC%9C%84%EC%B9%98.cpp