esuperstar   2년 전

아래 코드와 같이 구현을 시도하였지만 주석처리한 부분에서 문제가 있어서 진행이 안되고 있습니다

혹시 시간적 여유가 있으시거나... 뉴비에게 희망을 주실분이 계시다면 도움 요청드립니다. ㅜㅜ

대략적인 구현방법은 아래와 같습니다.

  1. 정점간 연결을 리스트에 저장하고
  2. 해당 데이터를 깊이우선탐색으로 시작정점과 목표정점을 넣어 두 정점이 연결되있는지 파악
  3. 연결되어 있으면 YES출력 그렇지않으면 NO출력
    ( 도구들(?) : xhash[5] 리스트에 들어있는 데이터는 x좌표가 5인 정점들의 인덱스값들

       x_hash[5] 리스트에 들어있는 데이터는 x좌표가 -5인 정점들의 인덱스값들 
       R_HP에는 HP값들을 저장하며, graph의 인덱스와 R_HP의 인덱스가 일치

jh05013   2년 전

쿼리마다 dfs를 하면 제대로 구현하더라도 시간초과가 날 수밖에 없습니다. 시간복잡도를 계산해 보세요.

꽤 어려운 문제이므로 경험을 쌓고 돌아오시는 것을 추천드립니다.

그리고 iostream밖에 안 쓰시는 것 같은데, algorithm이나 vector 등 여러 C++ 헤더를 공부하시면 큰 도움이 됩니다.

djm03178   2년 전

힘들게 이 정도로 코드를 짜셨는데 감히 말씀드리기 좀 그렇지만... 이 코드는 포기하시는 게 좋을 것 같습니다.

코드가 너무 길어서 완전히 파악하지는 못 하겠지만, 대략적으로 목표하시는 것으로 보이는 코드의 시간복잡도를 생각해보자면, 최대 (체크포인트의 수)개만큼을 (질의의 수)번 탐색해 들어가야 하고, 리스트에 체크포인트를 삽입하는 연산 또한 매번 최대 (체크포인트의 수)만큼 수행해야 하니, 대략 O(N^2 + NQ) 라고 할 수 있습니다.

N과 Q가 모두 최대 25만이니, 제곱이면 625억인 데다가, 수행해야 하는 연산들 자체가 무거운 편입니다. 채점 서버가 1초에 약 10억 번의 연산을 수행할 수 있다는 걸 생각해 보면, 8초에 해결하기에는 턱없이 부족하죠. 적어도 100초는 필요한 상황입니다.

링크드 리스트, 소트, 스택 등 배우신 많은 것들을 직접 구현하셨는데, 이들을 스스로 만들 수 있다는 건 분명 좋은 일이지만 이 문제에 테스트할 일은 아니었던 것 같습니다.

푸신 문제 목록을 보니, 이 문제는 아직은 풀기에 너무 이르지 않나 생각이 됩니다. 그래도 꼭 푸셔야겠다면, 무엇을 구현해야 하는지 힌트만 간단히 드리겠습니다.

첫째로, 체크포인트 A에서 B로 갈 수 있다면 B에서 A로도 갈 수 있습니다. A에서 B로 갈 수 있고 B에서 C로 갈 수 있다면 A에서 C로도 갈 수 있습니다. 즉, 특정 최대 HP에서 이동할 수 있는 체크포인트들은 '집합'으로 표현이 가능합니다. A, B, C 사이가 자유로이 왕래가 가능하고, D, E 사이에서 자유로이 왕래가 가능하다면, {A, B, C}, {D, E} 이런 식으로 표현이 되는 거죠. 그러면 "두 체크포인트가 같은 집합에 속한다"를 빠른 시간 내에 찾는 알고리즘이 무엇이 있을까요? 여기에 Disjoint-set을 사용하면 됩니다.

둘째로, Disjoint-set의 문제점은 한 번 합쳐놓은 집합들을 다시 분리하는 것이 어렵다는 점입니다. 그런데 만약, 질의가 점점 최대 HP가 커지는 방향으로만 들어온다고 가정해 봅시다. 그렇다면 집합을 합치는 일은 필요하지만, 분리하는 일은 필요하지 않겠죠? 문제는 질의는 HP순으로 들어오지 않는다는 점인데, 그러면 어떻게 해결하면 될까요? 바로 질의를 최대 HP 순으로 정렬해버리면 됩니다. 이를 오프라인 알고리즘이라고 부릅니다. 질의를 정렬해서 각각에 대한 답을 구한 뒤, 다시 처음의 질의 순서에 맞게 답을 재배열해서 출력하면 됩니다.

그리고 여러 기본 자료구조들을 직접 구현하신 것은 좋지만, 정말 간단한 문제에 연습용으로나 할 만하지, 이렇게 문제마다 구현해서 쓰는 것은 추천하지 않습니다. 문제 풀이의 목표는 문제를 해결하는 로직을 떠올리고 그걸 코드로 옮기는 데에 있는 것이지, 링크드 리스트, 머지 소트 같은 걸 구현하는 데에 있는 것이 아닌데, 직접 구현하기에는 시간이 너무 많이 들어갑니다. 이 정도의 기본적인 자료구조는 STL에서 기본적으로 다 제공하고 있습니다. 직접 구현한 것보다 안정성도 보장되고, 속도도 일반적으로 더 빠릅니다. 이런 부차적인 일은 라이브러리에 맡기고, 문제 해결 로직에 집중하는 것이 알고리즘 능력을 기르는 데에 더 도움이 된다고 생각합니다.

esuperstar   2년 전

 덕분에 어떤 방향으로 공부해야할지 알았습니다, 이렇게 장문의 글로 이끌어주셔서 정말 감사합니다. 해주신 말씀 상기하면서 공부하도록 하겠습니다! 항상 좋은 일만 가득하십쇼!~

esuperstar   2년 전

djm03178 님 지난 답변은 정말 많은 도움이 되었습니다! 이 문제 관련해서 질문 하나만 더 여쭙겠습니다.

알려주신 Disjoint sets와 오프라인 알고리즘에 대해 이해하고 해당 파트는 구현을 해보았습니다.
이렇게하니, 질의중에서 HP가 같은 값일 경우에는 disjoint sets 정보를 새로 갱신할 필요가 없어 
해당 case에 대해 속도가 상당히 빨라졌습니다.

하지만 HP가 커지는 방향으로 바뀔때 마다 disjoint sets를 갱신해줘야 하는데, 
어떤 방법으로 갱신해도 O(N^2) 이하로 빅오를 줄일 방법이 떠오르지 않습니다. 
이 부분에 있어서 좋은 방법이 있다면 알 수 있을까요?...!

djm03178   2년 전

지난 번에 설명을 좀 덜 드린 것 같은데, 추가적으로 해야 할 작업이 있습니다.

두 체크포인트가 왕래가 가능해지는 조건은 X 좌표의 차 또는 Y 좌표의 차가 HP 이하가 되는 것입니다.

그러면 모든 체크포인트를, X 좌표에 대해 한 번 정렬하고, Y 좌표에 대해 따로 한 번 정렬하면, 정렬된 상태에서 인접한 체크포인트끼리 왕래가 가능해지는지만 체크하면 되겠죠.

그러면 좌표의 차이가 작은 체크포인트 쌍부터 확인할 수 있게끔 인접한 쌍들 모두에 대해 우선순위 큐에 삽입합니다. 이러한 쌍이 X 좌표에 대해 N-1개, Y 좌표에 대해 N-1개 있을 테니, 이 작업은 통틀어서 O(NlogN)이면 되겠네요.

그 다음은 쿼리를 HP가 증가하는 순으로 정렬하고 처음부터 탐색하는 데에 O(QlogQ)면 되고, 매 쿼리마다 좌표 차가 현재 HP 이하인 체크포인트 쌍들을 모두 우선순위 큐에서 꺼내서 merge시킵니다. merge를 N번 하는 데에 걸리는 시간은 O(NlogN) 이하고요.

이렇게 총 O(QlogQ + NlogN) 시간에 해결이 가능해집니다.

esuperstar   2년 전


abf9d51f-7b12-4549-946a-6a2b2e23b7d3


djm03178 님께 

 

저의 경황없는 질문과 부족한 프로그래밍 경험, 난잡한 코드에도 불구하고 정말 친절하게 설명해주셔서, 완성된 코드를 구현할 수 있었습니다.

제 스스로 역량과 경험이 부족하다보니, 스스로가 어떤 부분을 몰라서 구현을 못하는지 조차 인지를 못하고 있었습니다. 그래서 그 동안 많은 문제에서 좌절감 느꼈고 프로그래밍에 대한 회의감이 많이 들었습니다. 하지만 djm03178님과 함께한 이번 경험을 통하여 자신감을 회복하고 다시 나아갈 수 있는 힘을 얻었습니다. 

한번도 뵌적도 없고, 이곳에서 처음 질문/답변을 통해 말씀을 나누었음에도 불구하고 저를 도와주신걸로 보아, 훌륭한 지식뿐 아니라 정말 멋진 품성을 지닌분임이 느껴집니다. 저도 djm03178님 처럼 멋진 사람이 되어, 사회에 도움이 될 수 있도록 하겠습니다. 여기서 멈추지 않고 더욱 정진하도록 하겠습니다. djm03178님의 지식과 품성에 다시 한번 경의를 표합니다! 감사합니다!

댓글을 작성하려면 로그인해야 합니다.