https://www.acmicpc.net/problem/19585
문제 요약
- 색상(4000개, 1000글자), 닉네임(4000개, 1000글자)
- 팀명(20000개, 2000글자)이 색상+닉네임으로 가능한지 판단
- 시간제한 3초, 메모리제한 1024MB
접근법
- 트라이 두개 사용 : 색상(순방향), 닉네임(역방향)
- 팀명을 순방향, 역방향 판단하여 둘다 만족하는것이 있는지 판단
메모리 초과
- 메모리 제한이 1024MB인데 계속 메모리 제한에 걸렸음
실패 1
- 자주 사용하는 트라이 구조체 사용
- 26개에 대한 기본 주소 저장 공간 + 끝인지 판단하는 변수
- (주소(8) X 26 + 판단(4, 구조체 특성때문에 4바이트 단위로 끊김)) X 1001(끝 포함) X 4000 X 2 = 1,697,696,000B = 1,697MB
- 최악의 경우에는 모든 문자열에 대해 구조체가 생성되므로...
- 그런데 26개 알파벳만 사용하는데 최악이 어떻게 발생하는지 모르겠다. 하나도 안겹치고??
실패 2
- 주소(8)를 사용하지 않고 인덱스(4)를 사용하는 것으로 변경
- 구조체를 한꺼번에 생성해놓으면 좋겠으나 구조체 정의 시점에 자신이 선언된 상태를 참고하는 방법이 떠오르지 않아서 다음과 같이함
- vector<void *> 형을 만들어서 구조체 생성한 것들을 저장하고 인덱스로 접근함
- 생성할 트라이 구조체들 : (인덱스(4) X 26 + 판단(4)) X 1001 X 4000 X 2
- 주소를 저장할 vector : 8 X 1001 * 4000 X 2
- 합 : 928,928,000B = 928MB
- 그래도 메모리 초과 발생. 이유는 모르겠음
실패 3
- 순방향 트라이와 역방향 트라이를 따로 생성했는데 합침
- 합치면서 판단 변수를 쪼개서 사용함 : 순방향 = 0x01, 역방향 0x02
- 그대로 메모리 초과 발생, 이유는 모르겠음
실패 4
- 트라이 구조체를 외부에서 생성하고 인덱스로 접근하는 방식으로 변경
- 구조체 안의 함수는 밖으로 빼고 대신 접근을 function(구조체 인덱스, 파라미터...) 식으로 변경함
- (인덱스(4) * 26 + 판단(4)) X 1001 X 4000 X 2 = 864,864,000B = 864MB
- 그래도 메모리 초과 발생, 이유는 모르겠음
성공
- 다음번 인덱스 공간(26개)을 미리 만들어놓는 방식을 변경함
- vector로 정의하고 다음번 공간을 필요시 추가함
- 다음번 노드가 있는지를 순차 탐색하고, 없으면 뒤에 삽입
- 순차탐색때문에 x 26의 수행횟수가 추가됨
- add : 1000 X 4000 X 2 X 26 = 208,000,000
- search : 2000 X 20000 X 26 = 1,040,000,000
- 합 : 1,248,000,000 = 1.2억
- (인덱스(4) * (실제 사용한 개수) + 판단(4)) X 1001 X 4000 X 2 = ??
- 실제 제출 결과 525400 KB = 525MB, 1788ms 로 통과했음
후기
- 실패4의 메모리 계산에서 뭐가 틀렸을까
- ==> 찾음
- 실패2의 연장선 상으로 vector를 선언해서 트라이 구조체를 생성해서 그곳에 넣는 방식으로 접근했는데
- cpp vector 생성 특성상(아마도) 두배씩 자원을 할당할 것임
- 그래서 예상치보다 공간을 더 많이 확보했을 것임
- 해결법
- vector를 대신 배열로 미리 선언 : [1001 4000 2]
- 성공함 : 845,712KB = 844,593KB(864,864,000B)
- cpp 기본 메모리 할당을 고려하면 대략 예상과 비슷함
newbieski