:: 게시판
:: 이전 게시판
|
- PGR21 관련된 질문 및 건의는 [건의 게시판]을 이용바랍니다.
- (2013년 3월 이전) 오래된 질문글은 [이전 질문 게시판]에 있습니다. 통합 규정을 준수해 주십시오. (2015.12.25.)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
19/10/03 22:56
지금 당장 생각나는 방법은 두 가지네요.
1. 순회 여부를 체크하는 flag를 추가해서 디폴트 값을 false로 놓고 순회 시엔 true로 바꿔서 true인 노드들은 순회를 continue로 건너뛴다. 2. 순회를 완료한 노드들을 삭제한다. 다만 2번을 하시면서 컨테이너를 순회하실거라면 for문을 이런 식으로 바꾸시는게 편할 겁니다. for(auto it = map.begin();it != map.end();) { if(삭제해야함) it = map.erase(it); else ++it; } 다만 이건 삭제만 할 때 가능한 방법이고... insert가 같이 이루어진다면 기본적으로 작동이 잘 안될 것 같네요. C++의 unordered_map 해쉬 맵인데 unordered라 순서가 없는 관계로 insert를 할 경우엔 한 번의 iteration에서 insert된 원소를 포함하는 모든 원소를 조회한다는 보장이 안 될 겁니다. https://en.cppreference.com/w/cpp/container/unordered_map/insert https://en.cppreference.com/w/cpp/container/unordered_map/erase 참조해보시길... 근데 코드보니까 제 생각엔 insert를 할 때 it를 치환했는데 for문에서 ++it가 있어서 문제가 발생하는 듯 하네요. for문에선 제거하시고 continue 들어가는 그 부분 전에 ++it 넣어보시면 아마 삽입된 원소가 조회가 안 되는 현상은 해결이 되실 듯? 다만 기존에 있던 원소 중 건너뛰어지는 원소가 있는 문제는 발생할 것 같습니다.
19/10/03 23:32
답변 감사드립니다.
지금 삽입한 원소가 조회 안되는게 아니라 기존에 원소가 조회가 안되는게 문제였는데, 그 부분은 전반적으로 다시 문제를 해결하는 방법 밖에는 없겠네요. 말씀하신 아이디어대로 생각해서, 추가한 다음에 it = map.begin()으로 다시 초기화해서 traverse하는 방법을 일단 적용시켰는데, 이렇게하는 건 문제 해결하는 속도가 더 느려지더라구요. 다시 한 번 문제를 풀 방법을 생각해봐야될 것 같네요.
19/10/03 23:05
기본적으로 iterator 무효화 문제고요, unordered_map이 해쉬를 이용해서 아무렇게나 저장하는것이기 때문에 당연히 이 문제가 생길수밖에 없습니다. 뭐 정확이 어떤 알고리즘을 구현하고 싶으신지는 모르겠지만, iterator를 다 쓰고 나서 insert를 하던지 아니면 자료구조를 바꾸던지 해야합니다.
19/10/03 23:08
세크리님 말에 첨언해서 iterating을 할 때 container의 원소를 추가하거나 삭제하는건 그리 권장되지 않는 방법이기도 합니다. 퍼포먼스를 위해서 포기할 때도 많이 있지만...
19/10/03 23:51
답변 감사드립니다.
unordered_map을 처음 써보는거라 insert가 되면서 이런식으로 순서가 바뀐다는걸 몰랐거든요. 제가 생각했던 건 새로 추가되는 원소가 있어도 기존의 iterator간의 앞뒤 관계는 유지가 될거라고 생각했습니다. 주인없는 사냥개님하고, 세크리님 말씀을 듣고 iterator를 다 쓰고 나서 insert를 하는 방법으로 추가할 부분만 따로 만들어내는 식으로 구현을 했는데도 속도가 충분히 빠르지 못하네요. 이런 거를 iterator 무효화라하는지 몰랐는데, 많이 배웠습니다.
19/10/03 23:55
사실 문제 설명만 들으면 전형적인 BFS 문제로 들리는데 제가 뭐 문제를 정확하게 아는 건 아니라 더 얘기는 못해드리겠네요... 건승하시길
19/10/04 00:03
이 문제를 보고서 왜 BFS라고 생각을 못했는지 모르겠네요-_-;;
이게 BFS 변형인거군요. 그런데 단순하게 queue에다가 이어붙이기에는 이전에 넣었던 node가 틀린 값인 경우의 수가 있어서 다른 방법을 쓰긴 해야하는 것 같네요. 굉장히 도움이 많이 됐습니다. 정말 감사드립니다.
19/10/03 23:58
순회를 할 때 map은 좋지 못한 자료구조 형태인가요?
세포가 증식하면서 필요한 공간이 계속해서 늘어나니까 늘어난 장소를 저장하기 위해 map을 사용하는 것이 좋지 않을까 생각했거든요. 기존에 있는 solution들은 아예 공간을 제약조건보다 넓게 잡고 아무것도 없는 공간도 순회하는데, map을 쓰면 세포가 존재하는 공간만 순회하니까 이게 더 효율적인 방법이 아닐까 생각했어서요.
19/10/04 00:03
왜냐면 map은 순서가 존재하는 자료구조라 삽입 삭제가 logN에 랜덤 엑세스도 불가능해서...
말씀하신 것 들으면 그냥 구조체 배열, 혹은 정말로 최대 세포 숫자를 모른다면 리스트 정도로도 충분해보이네요
19/10/04 00:17
그래서 unordered_map을 쓰면 괜찮지 않을까 생각해서, 그리고 사실 unordered_map을 여태 한 번도 안 써봤어서 한 번 연습해보는 김에 사용해봤었는데 제가 접근 방법이 잘못됐었나보네요.크크...
감사합니다.
|