-
백준 3217번 malloc: C언어 풀이Programming/PS 2023. 9. 16. 21:31
백준 3217번 malloc 문제의 C 언어 풀이 해설입니다.
연결 리스트와 유사하게 동작하면서도 주소를 통한 빠른 접근이 가능하도록 배열을 이용해 메모리를 구현하는 방법을 소개합니다.
변수명과 할당된 주소를 시간복잡도 O(1)에 찾을 수 있도록 해시 테이블을 구현하여 풀이하였습니다.전략
메모리 구성
메모리를 연결 리스트와 유사한 배열로 구성한다.
이전 철도 공사 문제 풀이 와 유사한 아이디어이다.
연결 리스트 대신 이전, 다음 원소의 인덱스를 갖는 하나의 구조체를 배열에 넣어주면 배열이 가지는 빠른 접근 속도와 연결 리스트의 연결성, 두마리 토끼를 잡을 수 있다.여기서는 구조체를 같은 속성을 갖는 메모리의 구간으로 정의했다.
각 구간은 할당 여부(FREE/ALLOCATED), 구간의 크기, 이전 구간의 인덱스로 구성했다.
다음 구간의 인덱스는 구간의 크기를 더하는 것으로 간단히 구할 수 있으므로 저장하지 않는다.변수 이름 인덱싱
변수의 이름이 항상 소문자 4자리 알파벳으로 구성되어있음을 활용하면 26진법 해시 함수를 작성 가능하다.
이렇게 만든 간단한 해시 테이블을 사용해 변수가 저장된 메모리 주소를 O(1)에 찾을 수 있다.개별 명령 구현
malloc(size)
메모리를 처음부터 순회하며 적절한 메모리 구간을 찾아야 한다.
구간이 FREE 이면서 구간 크기가 할당할 크기보다 크거나 같은 구간을 찾으면 된다.남는(FREE) 구간의 크기가 할당할 크기보다 클 경우, 남는 구간이 생긴다.
malloc으로 새로 할당된 구간, 할당되고 남은 FREE 구간 이렇게 둘로 나누어준다.크기가 같다면 간단히 구간의 할당 상태, FREE를 ALLOCATED로 변경만 해주면 된다.
free(var)
var
이 저장된 메모리 구간을 FREE로 바꿔주면 된다.
변수명var
가 있는 주소를 저장하는 해시 테이블이 있으므로, 해당 주소를 찾아 FREE로 바꿔주면 된다.한 가지 주의할 점은, 구간 앞/뒤에 FREE인 구간이 있는지 확인해야 된다는 점이다.
FREE인 구간이 있다면, 구간을 합쳐줘야 한다.print(var)
변수 이름과 주소를 저장하는 해시 맵을 만들었으므로, 저장된 값을 출력하기만 하면 된다.
코드