손가든 개발일지

이번 포스팅에는 지난 (2) 의 코드를 개선할 방안을 나열한 뒤 각각 구현한 코드를 실행해 보고 해당 결과를 확인해보겠다. 교재 코드의 할당 구동 절차 1. init()으로 런타임 heap의 틀을 구색 2. 처음에 크기가 큰 heap을 할당 (CHUNKSIZE heap) 3. 할당과 반환 작업 4. 3번 진행 중에 크기에 맞는 가용 블럭이 없다면 2번 순서에서 진행한 heap을 재 할당 개선 방안 제시 1. first fit으로 가용블럭을 탐색하고 있는 코드현재 코드는 first-fit으로 가용 블럭을 탐색하고 있다. 이 경우 heap의 초반부에 작은 블럭들이 편향되는 단점이 있으므로 next-fit과 best-fit으로 탐색하는 코드도 테스트 해 볼수 있다. 2. 즉시연결 (free 하자마자 연결탐색)..

오늘은 malloc() 함수를 실제 구현해 보는 과정을 진행하기 위한 초석이다. 더 성능 좋은 malloc으로 구현하기 위해 책에 구현된 코드의 define 문과 함수를 전부 분석하고, 책의 어떤 방식을 채택하여 구현되어 있는지 확인해본 뒤 어떻게 개선할 수 있을지 여부를 판단하겠다. CS:APP 9.9 코드 예제 해석 먼저 코드의 내부 시스템 코드인 memlib.c 와 Define 문으로 정의된 코드부터 파악해보자 - memlib.c 해당 파일은 시스템 자원인 heap의 시작 pointer , heap이 현재까지 할당된 end pointer , heap의 최대 끝 end pointer를 기억하고 있다. 해당 데이터는 각각 mem_heap , mem_brk , mem_max_addr에 저장되어 있고, 해..

5주차가 시작되었다. 근 2일 동안 CSAPP 책 독서 진도에 집중하느라 블로그 작성을 잘 못했는데, 다시 열심히 해보자. 5주차 발제 내용 일단 저번주에 9장 이론을 공부했기 때문에 무엇을 해야 될지는 대충 감이 온다. 먼저 오늘부터 구현을 시작해서 메모리 단편화를 해결하는 여러 방법의 경우의 수를 모두 구현해서 비교해보고 점수가 제일 높은 코드로 제출하려고 한다. 그후 메모리에 대한 필요한 지식이 생기면 CS 책을 통해서 공부를 더 하는 방향으로 이번주를 진행하려고 한다. declairation VS definition declariation은 아래 코드처럼 소스 파일 최 상단에 함수들의 이름들을 나열하는 선언부를 말한다. C에서 declariation을 하는 이유는 컴파일러가 코드를 위에서 아래로 ..

오늘은 작성한 내용이 많아 목차를 작성해 놓겟다. 1. 변수의 const 설정 2. Call by value / Call by reference 3. 포인터에 대한 궁금증 1. 포인터란 무엇인가? 2. 포인터는 왜 사용하는가? 3. 이중 포인터 4. 포인터를 사용할 시 주의점 변수의 const 설정 RB tree 를 구현하다보니, const를 사용한 변수에서 const를 사용한 이유가 궁금해져 const에 대해서 공부해 보았다. const는 '변함없는' 이라는 의미가 있는 constant의 약자로, 변수 앞에 붙이면 선언 이후 값을 변경하지 못하도록 하며 해당 변수를 상수로 취급하게 된다. 그럼 이 const는 왜 쓰는 걸까? 바로 변수의 선언과 동시에 그 초기 값을 변하지 못하도록 할 때 사용할 수 있..

오늘은 코알라(코딩 알고리즘 라이브) 스터디를 처음 시작한 날이다. 스터디에서 푼 문제에 대한 리뷰와 세그멘테이션 폴트를 해결한 내용을 작성하겠다. 코알라 스터디 코딩 알고리즘 공부를 계속하고 싶어서 정글 교육생들과 함께 스터디를 만들었다. 매주 일요일에 3문제씩 실제 코테처럼 응시한 뒤, 각자 본인이 문제에 대한 접근법을 설명하는 방법이다. 알고리즘 문제 푸는 능력을 빠르게 키우는 건, 잘 하는 사람들의 문제 접근 방법을 들여다 보는 것이라 생각한다. 그래서 알고리즘에 익숙한 사람들과 같이 어떻게 접근했는지 방법을 들어보면서, 내 실력도 빠르게 키울 수 있었으면 좋겠다. 그리고 또 알고리즘 실력이 부족하다고 생각되서 참여하기가 꺼려지는 분들은 점수 매기는 거 아니니까 많이 들어와서 같이 실력 키워봅시다..

오늘은 RB 트리의 삭제 연산과 구현을 실제로 진행해보겠다. 그전에 make 파일에서 발생한 오류부터 해결해 보자. Segmentation fault 세그멘테이션 폴트(Segmentation fault)는 프로그램이 잘못된 메모리 주소에 접근하려고 할 때 발생하는 오류이다. 이는 일반적으로 배열의 범위를 초과하거나 널 포인터를 참조하는 등의 상황에서 발생할 수 있다. 현재 RB 트리의 선언, 단일 노드의 삽입과 탐색, 삭제까지 구현을 마치고 올바르게 작동 된다는 것을 확인했다. 근데 test_find_erase() 함수에서 for문으로 arr[i]의 값들을 각각 insert하는 상황에서 Segmentation fault가 발생한 상황이다. 문제는 이 함수를 진입하지도 못하고 있는 상황이라는 것이다. 아마..

C컴파일/디버깅/make 사용법 학습 make 사용법을 학습하라는데, make가 뭔지 모른다.. 그래서 찾아봤다. make는 C언어 프로젝트를 빌드하고 컴파일하는 빌드 자동화 도구이다. 여러 파일간의 종속성을 관리하면서, 특정 소스 코드만 변경될 경우 필요한 파일만 다시 컴파일하면서 빠르게 재빌드 할 수 있게 해준다. 다음은 간단한 C 프로젝트를 위한 Makefile의 예시이다. CC = gcc CFLAGS = -Wall -O2 TARGET = myprogram SOURCES = main.c helper.c OBJECTS = $(SOURCES:.c=.o) $(TARGET): $(OBJECTS) $(CC) $(CFLAGS) -o $(TARGET) $(OBJECTS) %.o: %.c $(CC) $(CFLAG..

금일은 새로운 발제 내용이 나오는 목요일이다. 새로운 조가 형성되고 새로운 과제가 주어지는데, 항상 설레는 날인 것 같다. 오전에 시험을 봤는데 어제 공부한 알고리즘과 비슷한 문제가 나와서 시간이 부족해 다 풀진 못했지만, 나름 목표 만큼은 맞춰서 뿌듯했다. 아무튼 이번주는 C언어로 돌입한다. 이번주 과제는 알고리즘 문제 풀이가 아닌, Python에서 쉽게 가져다 쓴 자료구조를 직접 C 코드로 구현하는 것이다. 구현 자료구조는 블랙레드 트리 (BR tree). 먼저 이 자료구조가 어떻게 생겨먹은 놈인지 뜯어보고, 어떻게 구현할지를 생각해봐야 하기 때문에 코어타임 때 이론 내용 공부를 통해 부족한 부분을 채워나가기로 했다. 그리고 환경 설치를 위해서 터미널을 다뤘는데, 터미널 관련 명령어들에 대한 자료가 ..

3주차 마지막 날이 다가왔다. 남은 문제를 오늘 전부 풀겠다. (도전빼고.) BaekJun - #11053 : 가장 긴 증가하는 부분 수열 (DP) 출처 : https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 이 문제를 처음 접했을 때, DP적 접근이 아니라 문제를 해결하는 방식을 생각하다가 뒤에서부터 result에 append하고 만약에 다음에 append할 수의 값이..

오늘은 컴퓨터 시스템과 관련된 CS 정리를 퀴즈 문제와 같이 정리하겠다. 그전에 DP의 행렬 체인 알고리즘을 공부하고 해당 문제를 푸는 과정을 정리하겠다. DP : 행렬 체인 알고리즘 행렬 체인의 연산은 몇번째의 행렬을 먼저 계산하는가에 따라 연산의 횟수가 달라진다. 따라서 주어진 행렬의 체인을 최소로 연산하는 횟수를 구하는 알고리즘을 공부해보자. `Introduction to Algorithm` 책에 해당 로직에 대한 설명이 나와있다. 매우 이해하기 힘들지만, 간단히 정리해 보겠다. 행렬을 쭉 나열하고 그 행렬의 열이 체인형태로 (NxM , MxP) 나열되어 있어서 곱을 순서대로 할 수 있다. Ai = pi-1 x pi 의 차원을 가진다. (이부분이 어려울 수 있는데, A의 i번째가 3x6 매트릭스라면..