thexl   2년 전

안녕하세요.

Competitive Programming 할 때 Linked list가 Array보다 속도면에서 유리할 때가 있나요?? 

물론 크기가 큰 구조체 Array는 쓰지 않는 다는 가정 하에서요..

(복사, 이동량이 많아지므로 이럴 경우 pointer array 사용)

링크드 리스트로 푼 문제가 속도 1위인 문제가 있다면 알려주세요.

baekjoon   2년 전

링크드 리스트와 배열은 용도가 다르다고 생각합니다.

portableangel   2년 전

링크드 리스트의 특수성 (삽입/삭제가 O(1)) 을 이용한 문제를 풀 때 씁니다.

https://www.acmicpc.net/proble...

이 문제에서 곰곰히 생각해 보시면, 뱀의 각 마디를 이어 링크드 리스트로 만들면 관리가 한결 수월하지 않을까 싶지 않나요? (물론 다른 풀이가 있겠지만)

http://codeforces.com/problems...

n*m 배열에서 두 직사각형을 잡고 내용을 통째로 스왑하는 쿼리가 1만 개인 문제입니다.

이동시켜야 할 원소의 개수는 한 개의 쿼리당 O(n*m)개지만,

행 단위로, 열 단위로 링크드 리스트로 묶어 관리하면 한 개의 쿼리당 O(n+m)번의 포인터 교체 연산으로 직사각형 내부의 내용을 통째로 스왑하는 연산이 가능합니다.

이처럼 '문제에서 요구하는 연산을 빠르게 처리할 수 있는 자료구조' 가 어쩌다 보니 링크드 리스트인 경우에 쓴다고 보시면 됩니다.

보통은 그런 일이 드물어서 잘 쓰지 않는 것처럼 보일 뿐입니다.

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