malloc·free·realloc이 하는 일을 직접 흉내 낸다.
힙은 주소 0부터 H − 1까지 이어진 H바이트이고, 처음에는 전체가 빈 블록 하나다.
첫 줄에 H와 명령 수 q가, 다음 q줄에 명령이 한 줄에 하나씩 주어진다.
어느 명령이든 요청한 크기 n은 8의 배수로 올려서 쓴다(이미 8의 배수이면 그대로).
빈 블록은 빌려주지 않은 바이트가 끊기지 않고 이어진 가장 긴 구간이다. 곧, 이웃한 빈 곳은 언제나 한 블록으로 합쳐져 있다.
"malloc n"은 올린 크기 이상인 빈 블록 가운데 주소가 가장 낮은 것을 골라, 그 블록의 맨 앞에서 올린 크기만큼을 빌려주고 그 시작 주소를 출력한다.
그런 빈 블록이 없으면 "null"을 출력하고 아무것도 바꾸지 않는다.
"free a"는 a가 지금 빌려준 블록의 시작 주소이면 그 블록을 돌려받고 "ok"를 출력한다.
아니면(이미 돌려받은 주소, 블록 한가운데의 주소, 빌려준 적 없는 주소) "error"를 출력하고 아무것도 바꾸지 않는다.
"realloc a n"은 a가 지금 빌려준 블록의 시작 주소가 아니면 "error"를 출력하고 아무것도 바꾸지 않는다.
올린 크기가 지금 블록의 크기 이하이면 블록의 앞쪽 그만큼만 남기고 뒤쪽을 돌려받은 뒤 a를 출력한다.
더 크면, 블록 바로 뒤에 빈 블록이 붙어 있고 둘을 더한 크기가 올린 크기 이상일 때 블록을 제자리에서 뒤로 늘리고 a를 출력한다.
그렇게 늘릴 수 없으면 옛 블록을 그대로 둔 채 malloc과 같은 방법으로 새 블록을 찾는다.
찾았으면 새 블록을 빌려주고 옛 블록을 돌려받은 뒤 새 주소를 출력하고, 못 찾았으면 "null"을 출력하고 아무것도 바꾸지 않는다.
모든 명령을 처리한 뒤 마지막 줄에 빌려준 블록 수, 빈 블록 수, 가장 큰 빈 블록의 크기(빈 블록이 없으면 0)를 빈칸 하나씩 띄워 출력하라.
입력
H는 8의 배수, 8 ≤ H ≤ 1,000,000. 1 ≤ q ≤ 2,000. 1 ≤ n ≤ 1,000,000. 0 ≤ a ≤ 1,000,000
출력
명령마다 한 줄(주소, null, ok, error), 마지막 줄에 빌려준 블록 수, 빈 블록 수, 가장 큰 빈 블록의 크기
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
C의 malloc·free·realloc 뒤에서 벌어지는 일을 블록 목록으로 흉내 내는 문제예요. 블록(시작 주소, 크기, 쓰는 중인가)을 주소 순서로 늘어놓고 앞에서부터 훑어요. 쪼갤 때는 목록 가운데에 끼우고 합칠 때는 가운데에서 빼요. Python insert·del, JS·TS splice, Java add(i, x)·remove(i), C# Insert·RemoveAt, C++ vector의 insert·erase, 크레이콘 끼우기·자리빼기예요. C는 배열의 뒤쪽을 한 칸씩 직접 밀고 당겨요. 실제 C에서는 메모리를 빌리고 돌려주는 일을 프로그램이 직접 하고, C++은 new·delete나 std::vector가, Python·JS·TS·Java·C#·크레이콘은 쓰레기 수거기가 대신 해요. 그래서 이 문제의 error 같은 잘못은 C와, new·delete를 직접 쓰는 C++에서만 생겨요. 실제 C는 두 번 free하거나 블록 한가운데 주소를 free해도 error를 알려 주지 않고, 무슨 일이 일어날지 정해져 있지 않아요. 또 이 문제의 주소 0은 힙의 첫 바이트일 뿐이라, 아무 일도 하지 않는 실제 C의 free(NULL)과는 달라요. 함정 하나: 크기를 8의 배수로 올려요. (n + 7) / 8 * 8이에요. 올리지 않으면 첫 예시의 셋째 malloc이 32가 아니라 26을 받아요. (n / 8 + 1) * 8처럼 쓰면 이미 8의 배수인 16이 24가 돼요. JS·TS는 /가 소수를 내므로 Math.floor, Python은 //, 크레이콘은 수학.몫을 써요. 함정 둘: 돌려받은 블록은 뒤의 빈 블록뿐 아니라 앞의 빈 블록과도 합쳐요. 둘째 예시에서 가운데 블록을 마지막에 돌려받으면 셋이 48바이트 하나가 되어야 malloc 41이 성공해요. realloc으로 줄여서 남은 뒤쪽도 그 뒤의 빈 블록과 합쳐요. 함정 셋: 이미 돌려받은 주소를 또 돌려받으면 안 돼요(둘째 예시의 둘째 free 16). 시작 주소가 같은 블록이 있는지만 보지 말고 쓰는 중인지도 봐요. 블록 한가운데 주소도 error예요(첫 예시의 free 16은 주소 0 블록이 늘어난 뒤라 한가운데예요). 함정 넷: realloc은 'free한 다음 malloc'이 아니에요. 새 자리를 찾는 동안 옛 블록은 아직 쓰는 중이에요. 첫 예시의 realloc 32 40은 앞의 빈 32바이트와 옛 블록 8바이트를 더하면 40이지만 null이에요. 실제 realloc도 내용을 새 자리로 복사한 뒤에야 옛 블록을 돌려줘요. 함정 다섯: realloc이 실패하면 옛 블록은 그대로 남아요. 그래서 C에서 p = realloc(p, n);이라고 쓰면 실패했을 때 p가 NULL로 덮여 옛 블록의 주소를 잃어요. 다른 변수에 받아 확인한 뒤에 옮겨요. 함정 여섯: 제자리에서 늘릴 때 뒤의 빈 블록이 꼭 맞아도 돼요(첫 예시의 realloc 0 30은 16 + 16 = 32). 이때 빈 블록은 사라져요. 함정 일곱: 고르는 것은 주소가 가장 낮은 빈 블록(first fit)이지 크기가 가장 꼭 맞는 빈 블록(best fit)이 아니에요.
Pythonmain.py · 97 줄
import sysdef main(): lines = sys.stdin.read().split("\n") heap, q = map(int, lines[0].split()) # 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가 start, size, used = [0], [heap], [False] def find(addr): # 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for i in range(len(start)): if start[i] == addr: return i if used[i] else -1 return -1 def first_fit(need): # 주소가 가장 낮은, 충분히 큰 빈 블록 for i in range(len(start)): if not used[i] and size[i] >= need: return i return -1 def take(i, need): # 빈 블록 i의 앞쪽 need 바이트를 빌려준다. 남는 뒤쪽은 빈 블록으로 쪼갠다 if size[i] > need: start.insert(i + 1, start[i] + need) size.insert(i + 1, size[i] - need) used.insert(i + 1, False) size[i] = need used[i] = True def merge_next(i): # 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if i + 1 < len(start) and not used[i + 1]: size[i] += size[i + 1] del start[i + 1], size[i + 1], used[i + 1] def release(i): used[i] = False merge_next(i) if i > 0 and not used[i - 1]: merge_next(i - 1) out = [] for line in lines[1:1 + q]: p = line.split() if p[0] == "malloc": need = (int(p[1]) + 7) // 8 * 8 # 8의 배수로 올림 i = first_fit(need) if i < 0: out.append("null") else: take(i, need) out.append(str(start[i])) elif p[0] == "free": i = find(int(p[1])) if i < 0: out.append("error") else: release(i) out.append("ok") else: i = find(int(p[1])) need = (int(p[2]) + 7) // 8 * 8 if i < 0: out.append("error") elif need <= size[i]: # 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if need < size[i]: start.insert(i + 1, start[i] + need) size.insert(i + 1, size[i] - need) used.insert(i + 1, False) size[i] = need merge_next(i + 1) out.append(str(start[i])) elif i + 1 < len(start) and not used[i + 1] and size[i] + size[i + 1] >= need: # 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 rest = size[i] + size[i + 1] - need size[i] = need if rest > 0: start[i + 1] = start[i] + need size[i + 1] = rest else: del start[i + 1], size[i + 1], used[i + 1] out.append(str(start[i])) else: j = first_fit(need) # 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if j < 0: out.append("null") # 옛 블록은 그대로 남는다 else: old = start[i] take(j, need) out.append(str(start[j])) release(find(old)) # take가 자리를 밀었을 수 있으니 다시 찾는다 busy = sum(used) free_sizes = [size[i] for i in range(len(start)) if not used[i]] out.append(f"{busy} {len(free_sizes)} {max(free_sizes, default=0)}") print("\n".join(out))main()
JavaScriptmain.js · 110 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [heap, q] = lines[0].split(" ").map(Number);// 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가const start = [0], size = [heap], used = [false];function find(addr) { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (let i = 0; i < start.length; i++) { if (start[i] === addr) return used[i] ? i : -1; } return -1;}function firstFit(need) { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (let i = 0; i < start.length; i++) { if (!used[i] && size[i] >= need) return i; } return -1;}function split(i, need) { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 start.splice(i + 1, 0, start[i] + need); size.splice(i + 1, 0, size[i] - need); used.splice(i + 1, 0, false); size[i] = need;}function take(i, need) { if (size[i] > need) split(i, need); used[i] = true;}function removeAt(i) { start.splice(i, 1); size.splice(i, 1); used.splice(i, 1);}function mergeNext(i) { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < start.length && !used[i + 1]) { size[i] += size[i + 1]; removeAt(i + 1); }}function release(i) { used[i] = false; mergeNext(i); if (i > 0 && !used[i - 1]) mergeNext(i - 1);}const round8 = (n) => Math.floor((n + 7) / 8) * 8; // 8의 배수로 올림const out = [];for (let t = 1; t <= q; t++) { const p = lines[t].trim().split(" "); if (p[0] === "malloc") { const need = round8(Number(p[1])); const i = firstFit(need); if (i < 0) { out.push("null"); } else { take(i, need); out.push(String(start[i])); } } else if (p[0] === "free") { const i = find(Number(p[1])); if (i < 0) { out.push("error"); } else { release(i); out.push("ok"); } } else { const i = find(Number(p[1])); const need = round8(Number(p[2])); if (i < 0) { out.push("error"); } else if (need <= size[i]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < size[i]) { split(i, need); mergeNext(i + 1); } out.push(String(start[i])); } else if (i + 1 < start.length && !used[i + 1] && size[i] + size[i + 1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 const rest = size[i] + size[i + 1] - need; size[i] = need; if (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } else { removeAt(i + 1); } out.push(String(start[i])); } else { const j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { out.push("null"); // 옛 블록은 그대로 남는다 } else { const old = start[i]; take(j, need); out.push(String(start[j])); release(find(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } }}let busy = 0, holes = 0, largest = 0;for (let i = 0; i < start.length; i++) { if (used[i]) busy++; else { holes++; if (size[i] > largest) largest = size[i]; }}out.push(busy + " " + holes + " " + largest);console.log(out.join("\n"));
TypeScriptmain.ts · 112 줄
import * as fs from "fs";const lines: string[] = fs.readFileSync(0, "utf8").split("\n");const [heap, q] = lines[0].split(" ").map(Number);// 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가const start: number[] = [0], size: number[] = [heap], used: boolean[] = [false];function find(addr: number): number { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (let i = 0; i < start.length; i++) { if (start[i] === addr) return used[i] ? i : -1; } return -1;}function firstFit(need: number): number { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (let i = 0; i < start.length; i++) { if (!used[i] && size[i] >= need) return i; } return -1;}function split(i: number, need: number): void { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 start.splice(i + 1, 0, start[i] + need); size.splice(i + 1, 0, size[i] - need); used.splice(i + 1, 0, false); size[i] = need;}function take(i: number, need: number): void { if (size[i] > need) split(i, need); used[i] = true;}function removeAt(i: number): void { start.splice(i, 1); size.splice(i, 1); used.splice(i, 1);}function mergeNext(i: number): void { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < start.length && !used[i + 1]) { size[i] += size[i + 1]; removeAt(i + 1); }}function release(i: number): void { used[i] = false; mergeNext(i); if (i > 0 && !used[i - 1]) mergeNext(i - 1);}const round8 = (n: number): number => Math.floor((n + 7) / 8) * 8; // 8의 배수로 올림const out: string[] = [];for (let t = 1; t <= q; t++) { const p = lines[t].trim().split(" "); if (p[0] === "malloc") { const need = round8(Number(p[1])); const i = firstFit(need); if (i < 0) { out.push("null"); } else { take(i, need); out.push(String(start[i])); } } else if (p[0] === "free") { const i = find(Number(p[1])); if (i < 0) { out.push("error"); } else { release(i); out.push("ok"); } } else { const i = find(Number(p[1])); const need = round8(Number(p[2])); if (i < 0) { out.push("error"); } else if (need <= size[i]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < size[i]) { split(i, need); mergeNext(i + 1); } out.push(String(start[i])); } else if (i + 1 < start.length && !used[i + 1] && size[i] + size[i + 1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 const rest = size[i] + size[i + 1] - need; size[i] = need; if (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } else { removeAt(i + 1); } out.push(String(start[i])); } else { const j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { out.push("null"); // 옛 블록은 그대로 남는다 } else { const old = start[i]; take(j, need); out.push(String(start[j])); release(find(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } }}let busy = 0, holes = 0, largest = 0;for (let i = 0; i < start.length; i++) { if (used[i]) busy++; else { holes++; if (size[i] > largest) largest = size[i]; }}out.push(busy + " " + holes + " " + largest);console.log(out.join("\n"));
JavaMain.java · 128 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;public class Main { // 블록을 주소 순서로 늘어놓는다: {시작 주소, 크기, 쓰는 중이면 1} static ArrayList<int[]> blocks = new ArrayList<>(); static int find(int addr) { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (int i = 0; i < blocks.size(); i++) { if (blocks.get(i)[0] == addr) return blocks.get(i)[2] == 1 ? i : -1; } return -1; } static int firstFit(int need) { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (int i = 0; i < blocks.size(); i++) { int[] b = blocks.get(i); if (b[2] == 0 && b[1] >= need) return i; } return -1; } static void split(int i, int need) { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 int[] b = blocks.get(i); blocks.add(i + 1, new int[] {b[0] + need, b[1] - need, 0}); b[1] = need; } static void take(int i, int need) { if (blocks.get(i)[1] > need) split(i, need); blocks.get(i)[2] = 1; } static void mergeNext(int i) { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < blocks.size() && blocks.get(i + 1)[2] == 0) { blocks.get(i)[1] += blocks.get(i + 1)[1]; blocks.remove(i + 1); // int 자리 번호로 지운다 } } static void release(int i) { blocks.get(i)[2] = 0; mergeNext(i); if (i > 0 && blocks.get(i - 1)[2] == 0) mergeNext(i - 1); } static int round8(int n) { // 8의 배수로 올림 return (n + 7) / 8 * 8; } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] first = br.readLine().trim().split(" "); int heap = Integer.parseInt(first[0]); int q = Integer.parseInt(first[1]); blocks.add(new int[] {0, heap, 0}); StringBuilder sb = new StringBuilder(); for (int t = 0; t < q; t++) { String[] p = br.readLine().trim().split(" "); if (p[0].equals("malloc")) { int need = round8(Integer.parseInt(p[1])); int i = firstFit(need); if (i < 0) { sb.append("null\n"); } else { take(i, need); sb.append(blocks.get(i)[0]).append('\n'); } } else if (p[0].equals("free")) { int i = find(Integer.parseInt(p[1])); if (i < 0) { sb.append("error\n"); } else { release(i); sb.append("ok\n"); } } else { int i = find(Integer.parseInt(p[1])); int need = round8(Integer.parseInt(p[2])); if (i < 0) { sb.append("error\n"); continue; } int[] b = blocks.get(i); if (need <= b[1]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < b[1]) { split(i, need); mergeNext(i + 1); } sb.append(b[0]).append('\n'); } else if (i + 1 < blocks.size() && blocks.get(i + 1)[2] == 0 && b[1] + blocks.get(i + 1)[1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 int[] next = blocks.get(i + 1); int rest = b[1] + next[1] - need; b[1] = need; if (rest > 0) { next[0] = b[0] + need; next[1] = rest; } else { blocks.remove(i + 1); } sb.append(b[0]).append('\n'); } else { int j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { sb.append("null\n"); // 옛 블록은 그대로 남는다 } else { take(j, need); sb.append(blocks.get(j)[0]).append('\n'); release(find(b[0])); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } } } int busy = 0, holes = 0, largest = 0; for (int[] b : blocks) { if (b[2] == 1) busy++; else { holes++; largest = Math.max(largest, b[1]); } } sb.append(busy).append(' ').append(holes).append(' ').append(largest).append('\n'); System.out.print(sb); }}
C#Main.cs · 167 줄
using System;using System.Collections.Generic;using System.Text;class Block{ public int Start, Size; public bool Used;}class Program{ // 블록을 주소 순서로 늘어놓는다 static List<Block> blocks = new List<Block>(); static int Find(int addr) // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 { for (int i = 0; i < blocks.Count; i++) { if (blocks[i].Start == addr) return blocks[i].Used ? i : -1; } return -1; } static int FirstFit(int need) // 주소가 가장 낮은, 충분히 큰 빈 블록 { for (int i = 0; i < blocks.Count; i++) { if (!blocks[i].Used && blocks[i].Size >= need) return i; } return -1; } static void Split(int i, int need) // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 { Block b = blocks[i]; blocks.Insert(i + 1, new Block { Start = b.Start + need, Size = b.Size - need, Used = false }); b.Size = need; } static void Take(int i, int need) { if (blocks[i].Size > need) Split(i, need); blocks[i].Used = true; } static void MergeNext(int i) // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 { if (i + 1 < blocks.Count && !blocks[i + 1].Used) { blocks[i].Size += blocks[i + 1].Size; blocks.RemoveAt(i + 1); } } static void Release(int i) { blocks[i].Used = false; MergeNext(i); if (i > 0 && !blocks[i - 1].Used) MergeNext(i - 1); } static int Round8(int n) => (n + 7) / 8 * 8; // 8의 배수로 올림 static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int heap = int.Parse(first[0]); int q = int.Parse(first[1]); blocks.Add(new Block { Start = 0, Size = heap, Used = false }); var sb = new StringBuilder(); for (int t = 0; t < q; t++) { string[] p = Console.ReadLine().Trim().Split(' '); if (p[0] == "malloc") { int need = Round8(int.Parse(p[1])); int i = FirstFit(need); if (i < 0) { sb.Append("null\n"); } else { Take(i, need); sb.Append(blocks[i].Start).Append('\n'); } } else if (p[0] == "free") { int i = Find(int.Parse(p[1])); if (i < 0) { sb.Append("error\n"); } else { Release(i); sb.Append("ok\n"); } } else { int i = Find(int.Parse(p[1])); int need = Round8(int.Parse(p[2])); if (i < 0) { sb.Append("error\n"); continue; } Block b = blocks[i]; if (need <= b.Size) // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 { if (need < b.Size) { Split(i, need); MergeNext(i + 1); } sb.Append(b.Start).Append('\n'); } else if (i + 1 < blocks.Count && !blocks[i + 1].Used && b.Size + blocks[i + 1].Size >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 Block next = blocks[i + 1]; int rest = b.Size + next.Size - need; b.Size = need; if (rest > 0) { next.Start = b.Start + need; next.Size = rest; } else { blocks.RemoveAt(i + 1); } sb.Append(b.Start).Append('\n'); } else { int j = FirstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { sb.Append("null\n"); // 옛 블록은 그대로 남는다 } else { Take(j, need); sb.Append(blocks[j].Start).Append('\n'); Release(Find(b.Start)); // Take가 자리를 밀었을 수 있으니 다시 찾는다 } } } } int busy = 0, holes = 0, largest = 0; foreach (Block b in blocks) { if (b.Used) busy++; else { holes++; largest = Math.Max(largest, b.Size); } } sb.Append(busy).Append(' ').Append(holes).Append(' ').Append(largest).Append('\n'); Console.Write(sb); }}
C++main.cpp · 131 줄
#include <iostream>#include <string>#include <vector>using namespace std;struct Block { int start, size; bool used;};// 블록을 주소 순서로 늘어놓는다static vector<Block> blocks;static int findBlock(int addr) { // 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 for (int i = 0; i < (int)blocks.size(); i++) { if (blocks[i].start == addr) return blocks[i].used ? i : -1; } return -1;}static int firstFit(int need) { // 주소가 가장 낮은, 충분히 큰 빈 블록 for (int i = 0; i < (int)blocks.size(); i++) { if (!blocks[i].used && blocks[i].size >= need) return i; } return -1;}static void split(int i, int need) { // 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 Block rest{blocks[i].start + need, blocks[i].size - need, false}; blocks[i].size = need; blocks.insert(blocks.begin() + i + 1, rest);}static void take(int i, int need) { if (blocks[i].size > need) split(i, need); blocks[i].used = true;}static void mergeNext(int i) { // 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 if (i + 1 < (int)blocks.size() && !blocks[i + 1].used) { blocks[i].size += blocks[i + 1].size; blocks.erase(blocks.begin() + i + 1); }}static void release(int i) { blocks[i].used = false; mergeNext(i); if (i > 0 && !blocks[i - 1].used) mergeNext(i - 1);}static int round8(int n) { return (n + 7) / 8 * 8; } // 8의 배수로 올림int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int heap, q; if (!(cin >> heap >> q)) return 0; blocks.push_back({0, heap, false}); for (int t = 0; t < q; t++) { string cmd; cin >> cmd; if (cmd == "malloc") { int n; cin >> n; int need = round8(n); int i = firstFit(need); if (i < 0) { cout << "null\n"; } else { take(i, need); cout << blocks[i].start << "\n"; } } else if (cmd == "free") { int a; cin >> a; int i = findBlock(a); if (i < 0) { cout << "error\n"; } else { release(i); cout << "ok\n"; } } else { int a, n; cin >> a >> n; int i = findBlock(a); int need = round8(n); if (i < 0) { cout << "error\n"; } else if (need <= blocks[i].size) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 if (need < blocks[i].size) { split(i, need); mergeNext(i + 1); } cout << blocks[i].start << "\n"; } else if (i + 1 < (int)blocks.size() && !blocks[i + 1].used && blocks[i].size + blocks[i + 1].size >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 int rest = blocks[i].size + blocks[i + 1].size - need; blocks[i].size = need; if (rest > 0) { blocks[i + 1].start = blocks[i].start + need; blocks[i + 1].size = rest; } else { blocks.erase(blocks.begin() + i + 1); } cout << blocks[i].start << "\n"; } else { int j = firstFit(need); // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 if (j < 0) { cout << "null\n"; // 옛 블록은 그대로 남는다 } else { int old = blocks[i].start; take(j, need); cout << blocks[j].start << "\n"; release(findBlock(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } } } int busy = 0, holes = 0, largest = 0; for (const Block& b : blocks) { if (b.used) busy++; else { holes++; if (b.size > largest) largest = b.size; } } cout << busy << " " << holes << " " << largest << "\n"; return 0;}
Cmain.c · 141 줄
#include <stdio.h>#include <string.h>#define MAXB 4096 /* 명령 하나가 블록을 많아야 1개 늘린다 *//* 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가 */static int start[MAXB], size[MAXB], used[MAXB];static int count = 1;static int find(int addr) { /* 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1 */ for (int i = 0; i < count; i++) { if (start[i] == addr) return used[i] ? i : -1; } return -1;}static int first_fit(int need) { /* 주소가 가장 낮은, 충분히 큰 빈 블록 */ for (int i = 0; i < count; i++) { if (!used[i] && size[i] >= need) return i; } return -1;}static void split(int i, int need) { /* 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다 */ for (int k = count; k > i + 1; k--) { start[k] = start[k - 1]; size[k] = size[k - 1]; used[k] = used[k - 1]; } count++; start[i + 1] = start[i] + need; size[i + 1] = size[i] - need; used[i + 1] = 0; size[i] = need;}static void take(int i, int need) { if (size[i] > need) split(i, need); used[i] = 1;}static void remove_at(int i) { for (int k = i; k + 1 < count; k++) { start[k] = start[k + 1]; size[k] = size[k + 1]; used[k] = used[k + 1]; } count--;}static void merge_next(int i) { /* 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다 */ if (i + 1 < count && !used[i + 1]) { size[i] += size[i + 1]; remove_at(i + 1); }}static void release(int i) { used[i] = 0; merge_next(i); if (i > 0 && !used[i - 1]) merge_next(i - 1);}static int round8(int n) { return (n + 7) / 8 * 8; } /* 8의 배수로 올림 */int main(void) { int heap, q; if (scanf("%d %d", &heap, &q) != 2) return 0; start[0] = 0; size[0] = heap; used[0] = 0; for (int t = 0; t < q; t++) { char cmd[16]; int a, n; if (scanf("%15s", cmd) != 1) return 0; if (strcmp(cmd, "malloc") == 0) { if (scanf("%d", &n) != 1) return 0; int need = round8(n); int i = first_fit(need); if (i < 0) { printf("null\n"); } else { take(i, need); printf("%d\n", start[i]); } } else if (strcmp(cmd, "free") == 0) { if (scanf("%d", &a) != 1) return 0; int i = find(a); if (i < 0) { printf("error\n"); } else { release(i); printf("ok\n"); } } else { if (scanf("%d %d", &a, &n) != 2) return 0; int i = find(a); int need = round8(n); if (i < 0) { printf("error\n"); } else if (need <= size[i]) { /* 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 */ if (need < size[i]) { split(i, need); merge_next(i + 1); } printf("%d\n", start[i]); } else if (i + 1 < count && !used[i + 1] && size[i] + size[i + 1] >= need) { /* 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 */ int rest = size[i] + size[i + 1] - need; size[i] = need; if (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } else { remove_at(i + 1); } printf("%d\n", start[i]); } else { int j = first_fit(need); /* 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 */ if (j < 0) { printf("null\n"); /* 옛 블록은 그대로 남는다 */ } else { int old = start[i]; take(j, need); printf("%d\n", start[j]); release(find(old)); /* take가 자리를 밀었을 수 있으니 다시 찾는다 */ } } } } int busy = 0, holes = 0, largest = 0; for (int i = 0; i < count; i++) { if (used[i]) busy++; else { holes++; if (size[i] > largest) largest = size[i]; } } printf("%d %d %d\n", busy, holes, largest); return 0;}
Craykonmain.cray · 190 줄
// 블록을 주소 순서로 늘어놓는다: 시작 주소, 크기, 쓰는 중인가first = 콘솔.줄읽기().공백제거().나누기(" ");heap = first[0].수로변환();q = first[1].수로변환();start = [0];size = [heap];used = [거짓];// 쓰는 중인 블록의 시작 주소일 때만 그 자리, 아니면 -1find(addr){ 반복 (i = 0; i < start.개수; i++) { 만약 (start[i] == addr) { 만약 (used[i]) { 돌려주기 i; } 돌려주기 -1; } } 돌려주기 -1;}// 주소가 가장 낮은, 충분히 큰 빈 블록firstFit(need){ 반복 (i = 0; i < start.개수; i++) { 만약 (!used[i] && size[i] >= need) { 돌려주기 i; } } 돌려주기 -1;}// 블록 i를 앞쪽 need 바이트와 빈 뒤쪽으로 쪼갠다split(i, need){ start.끼우기(i + 1, start[i] + need); size.끼우기(i + 1, size[i] - need); used.끼우기(i + 1, 거짓); size[i] = need;}take(i, need){ 만약 (size[i] > need) { split(i, need); } used[i] = 참;}removeAt(i){ start.자리빼기(i); size.자리빼기(i); used.자리빼기(i);}// 빈 블록 i 바로 뒤가 빈 블록이면 하나로 합친다mergeNext(i){ 만약 (i + 1 < start.개수 && !used[i + 1]) { size[i] = size[i] + size[i + 1]; removeAt(i + 1); }}release(i){ used[i] = 거짓; mergeNext(i); 만약 (i > 0 && !used[i - 1]) { mergeNext(i - 1); }}// 8의 배수로 올림round8(n){ 돌려주기 수학.몫(n + 7, 8) * 8;}반복 (t = 0; t < q; t++){ p = 콘솔.줄읽기().공백제거().나누기(" "); 만약 (p[0] == "malloc") { need = round8(p[1].수로변환()); i = firstFit(need); 만약 (i < 0) { 콘솔.쓰기("null"); } 아니면 { take(i, need); 콘솔.쓰기(start[i]); } } 아니면 만약 (p[0] == "free") { i = find(p[1].수로변환()); 만약 (i < 0) { 콘솔.쓰기("error"); } 아니면 { release(i); 콘솔.쓰기("ok"); } } 아니면 { i = find(p[1].수로변환()); need = round8(p[2].수로변환()); 만약 (i < 0) { 콘솔.쓰기("error"); } 아니면 만약 (need <= size[i]) { // 줄이기(또는 그대로): 제자리, 남는 뒤쪽을 돌려준다 만약 (need < size[i]) { split(i, need); mergeNext(i + 1); } 콘솔.쓰기(start[i]); } 아니면 만약 (i + 1 < start.개수 && !used[i + 1] && size[i] + size[i + 1] >= need) { // 늘리기: 바로 뒤 빈 블록까지 합치면 되므로 제자리에서 rest = size[i] + size[i + 1] - need; size[i] = need; 만약 (rest > 0) { start[i + 1] = start[i] + need; size[i + 1] = rest; } 아니면 { removeAt(i + 1); } 콘솔.쓰기(start[i]); } 아니면 { // 옛 블록은 아직 쓰는 중인 채로 새 자리를 찾는다 j = firstFit(need); 만약 (j < 0) { 콘솔.쓰기("null"); // 옛 블록은 그대로 남는다 } 아니면 { old = start[i]; take(j, need); 콘솔.쓰기(start[j]); release(find(old)); // take가 자리를 밀었을 수 있으니 다시 찾는다 } } }}busy = 0;holes = 0;largest = 0;반복 (i = 0; i < start.개수; i++){ 만약 (used[i]) { busy = busy + 1; } 아니면 { holes = holes + 1; 만약 (size[i] > largest) { largest = size[i]; } }}콘솔.쓰기("" + busy + " " + holes + " " + largest);