연결 리스트
-
백준 3217번 malloc: C언어 풀이Programming/PS 2023. 9. 16. 21:31
백준 3217번 malloc 문제의 C 언어 풀이 해설입니다.연결 리스트와 유사하게 동작하면서도 주소를 통한 빠른 접근이 가능하도록 배열을 이용해 메모리를 구현하는 방법을 소개합니다.변수명과 할당된 주소를 시간복잡도 O(1)에 찾을 수 있도록 해시 테이블을 구현하여 풀이하였습니다.전략메모리 구성메모리를 연결 리스트와 유사한 배열로 구성한다. 이전 철도 공사 문제 풀이 와 유사한 아이디어이다.연결 리스트 대신 이전, 다음 원소의 인덱스를 갖는 하나의 구조체를 배열에 넣어주면 배열이 가지는 빠른 접근 속도와 연결 리스트의 연결성, 두마리 토끼를 잡을 수 있다.여기서는 구조체를 같은 속성을 갖는 메모리의 구간으로 정의했다. 각 구간은 할당 여부(FREE/ALLOCATED), 구간의 크기, 이전 구간의 인덱..