11월 1주차

10월 31일 (월)

 

내가 학교를 안가서 안했다.

밤에 후배가 저번주에 못풀고 끝났던걸 푸려고 노력하는 영상을 보내줬다.

세그트리나 이런것도 알길래 스위핑은 알 줄 알았더니 몰라서 의외였다. 그래서 이번주?는 스위핑을 조금 집중적으로 해볼거다.

좌표압축도 모를 것 같아서 같이 연습하려고 한다.

그리고 영상을 보니, 문제를 읽고 시간복잡도나 공간복잡도를 따지지 않고 바로 구현으로 들어가는 것 같다. 쉬운 문제들은 이래도 됐었지만 어려워지면 풀이를 계속 개선시켜서 시간복잡도를 줄이거나 이래야 되므로 고쳐야 할 습관으로 보인다.

사소한 구현미스도 자주 있는 것 같아 어떻게 해결할 수 있을지 고민이다. 그냥 구현 연습시키는게 답인가..

---

11월 1일 (화)

 

A. 놀이공원 2594

N도 작고 입력이 시간이라 스위핑이나 이런거 없이도 그냥 구현해서 풀 수도 있다.

하지만 스위핑 연습을 하기로 했으니 스위핑으로 풀어보자.

시작과 끝나는 시각을 모두 종합해 정렬하고 처리해주면 된다.

사실 이 문제는 그냥 시간 정보를 어떻게 처리하는게 좋을지 알려주기 위해 넣은 문제다.

 

B. 여러 직사각형의 전체 면적 구하기 2672

이제 스위핑을 대충 감 잡았을테니 저번주의 그 문제로 돌아가보자.

 

정석적인 스위핑으로 푼다면

커다란 판 위에 문제에서 주어진 직사각형들을 배치하고, 가로로 긴 칼로 위에서부터 자르면서 내려온다고 볼 수 있다.

각각의 행을 처리한 후, 그 값들을 모두 더해주면 전체의 넓이가 된다. (적분처럼 생각할 수 있다)

 

그럼 각각의 행에서는 어떻게 처리하냐

직사각형이 시작하는 열에서 +1을 해주고 끝나는 열에서 -1을 해주면 각 칸마다 그 칸을 덮는 직사각형이 몇개인지 셀 수 있다. (누적합)

그리고 이를 '몇 개'에 집중하지 않고 '있다/없다'에 집중하면(즉, 0개인지 아닌지) 어느 부분의 넓이를 계산해야하는지 알 수 있다.

 

근데 이 작업들을 행번호와 열번호를 1씩 증가시키면서 해야할까?

아니다. 그러면 시간초과가 날 것이다.

우리가 관찰해야 할 부분은 직사각형의 둘레 부분이 아닌 곳에서는 어떠한 변화가 생기지 않는다는 점이다.

단위가 되던 '칸'을 꼭 1*1로 볼 게 아니라 n*m의 직사각형으로 생각하면 시간을 줄일 수 있는 것이다.

(이 문제에서는 시간이 여유있기 때문에 이렇게 풀기 헷갈린다면, 행만 스위핑해주고 열은 1씩 움직여도 제한시간 내에 통과한다.)

 

C. 물고기의 서식 범위 5536

이번에는 3차원이다!

좌표압축 비슷하게 어떤 좌표들만 꼭 필요한 좌표인지 구해준다.

직육면체의 경계(모서리) 부분에서만 어떤 상태가 변한다는 것에 집중하면 꼭 필요한 x값, y값, z값이 각 직육면체마다 2개씩 나오게 된다.

이 좌표들을 이용해 입력으로 주어진 직육면체들을 쪼개어 계산해주면 된다.

 

D. 수상 택시 2836

머리를 좀 굴려줘야 된다.

문제를 꼼꼼히 읽고, 문제의 특성을 이용해 해결해야 한다.

 

우선 승객을 두 부류로 나누어 생각할 수 있다.

1. s(타는 위치) < e(목적지)인 경우

2. s > e

 

1번의 경우에는 아무런 문제가 되지 않는다. 어차피 이 택시는 0번에서 M번까지 가야되고, 이 과정에서 모든 집을 순서대로 지나게 될 것이다. 그냥 아무도 모르게 탔다가 아무도 모르게 내리면 된다.

2번의 경우를 잘 생각해보자. 2번 승객을 위해 택시는 역행하게 될 것이다. 그리고 역행하기 전의 위치로 돌아오면 왕복하는 비용으로 소리소문없이 승객 한명을 처리한 것이 된다. 하지만 이게 최선일까?

여러 2번 승객의 동선이 겹치면 최적이 아니다. 이렇게 겹칠 때를 잘 생각해보면 겹치는 사람 중 최대인 지점에서 최소인 지점까지 역행하고, 다시 돌아가면 처리 끝.

이제 최적이다. 증명하고 싶다면 귀류법을 이용하면 간단하다.

 

겹치는 사람은 어떻게 찾는가?

2번 승객들을 s와 e를 정렬을 하면 쉽게 해결할 수 있다. s와 e를 각각 닫는 괄호와 여는 괄호라고(s>e이기 때문) 생각하면 이해가 쉽다.

 

이 다음에는 사이클도 연습시키려고 한다. 저번주에 사이클을 이용하는 문제 한 문제를 풀게했는데 구현을 조금 힘들어하는 것 같았다.

 

A번만 풀었다. 시간이 너무 빨리간다..

---

11월 2일 (수)

 

B번을 풀었다.

일단 행을 1씩 움직이면서 열을 스위핑하는 방식으로 했는데 시간이 다돼서 끝났다.

행을 스위핑하면서 열은 배열에 마킹하는 방법도 쉬운데, 이렇게 한번 풀어보도록 해야겠다.

좌표압축도 알려줘야 한다.

---

11월 3일 (목)

 

내가 면접보느라 학교를 안가서 안했다.

---

11월 4일 (금)

 

한동안 중요한 면접은 없어서 학교에서 문제 쭉 봤다.

스위핑이 세그나 레이지랑 같이 쓰니까 개쩔긴 하더라. 대회에서도 이런 방법으로 푸는 문제가 많았던 기억이 난다.

레이지는 아직 가르치기에는 이른 것 같고, 다음주쯤에 스위핑 + 세그/펜윅으로 몇문제 넣어놔야겠다.

이번주는 좌표압축 끝내고.....D번이 그리디하게 접근한 후에 스위핑으로 계산해주는 거라 문제가 되게 재밌어보여서 꼭 하고 싶은데 이번주에 가능할지 모르겠다.