손가든 개발일지

오늘은 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 매트릭스라면..

BaekJun - #1946 : 신입사원 (그리디 탐색법) 출처 : https://www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성 www.acmicpc.net 오늘은 신입 사원을 풀었다. 문제 이해가 조금 어려운데 풀어서 얘기해보면 실기, 필기 두개의 시험을 등수로 매기는데, 특정 A 라는 사람이 어느 누군가보다 실기도, 필기도 등수가 낮다면 그사람은 탈락된다. 문제를 이해하는데 시간이 좀 걸리긴 하지만, 문제가 이해됬다고 하면 이제 어떻게 풀어야할지 고민을 해보자..

현재 컴퓨터 시스템을 공부하고 있는 내용은 이해할 내용이기보다는 어셈블리어의 인스트럭션 기호의 정의와 해석적인 파트를 읽고 있어서, 따로 정리하지는 않겠다. 대신 DP 알고리즘을 이용한 간단(?)하지만, 코드화(규칙화)하기 힘든 문제를 통해서 DP 문제 풀이에 조금 더 익숙해져보자. BaekJun - #9084 : 동전 (DP) 동전 0 이랑 비슷해 보이지만 이문제는 DP 문제이다. 동전 단위가 주어지고 해당 값을 만들 수 있는 경우의 수를 출력하는 문제인데, 문제 아이디어를 떠올리기가 역시 아직 쉽지 않다. 처음엔 01타일 문제를 먼저 떠올렸다. 가장 최근에 푼 01타일 문제를 겪은 후에 '베이스케이스를 찾아서, 그 케이스를 통한 확장에 대한 문제가 DP구나.' 라고 생각했었는데, 이 문제를 통해서 ..

오늘은 어제 하던 Greedy를 문제에 적용하면서 경험한 서사와 컴퓨터 시스템 약간을 추가해서 작성해 보겠다. BaekJun - # 11047 : 동전 0 (그리디 탐색법) 출처 : https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 동전 0의 문제를 처음 풀려고 생각했을 때는, 굉장히 쉽다고 생각했다. 거스름돈을 계산할 줄 아는 사람이라면 코드를 짜는 건 어렵지 않다. 하지만 문제는..

오늘의 내용은 어제의 동적 프로그래밍 공부의 연장선인 Knapsack Problem에 대해 알아보고, 컴퓨터 시스템 정리를 간단히만 다뤄보겠다. Knapsack Problem 배낭 문제라고도 하는 kapsack 문제는 정해진 무게 한도가 있는 배낭에다 물건을 담는데, 가치가 가장 높게 담는 경우를 찾는 문제이다. 이는 모든 경우를 다 셀 경우 특정 물건을 담는다 vs 안담는다로 하여 2의 n(물건의 수)승의 탐색이 걸린다. 따라서 이는 효율적인 탐색법이 필요한데 접근법은 다음과 같다. 1. 만약 물건의 무게가 배낭의 한도보다 크다면 continue, 2. 한도보다 작다면 2중 배열(dp)에 세로줄은 담은 물건의 수(i), 가로줄은 배낭의 한도무게(w)로 설정하여 선언한 뒤 그 배열안에 최대의 가치를 저장..

오늘은 컴퓨터 시스템 공부한 것을 최대한 정리하고, 알고리즘 풀이를 살짝 곁들일 생각이다. CS:APP 책이 영문판을 번역한 번역본이라, 글이 너무 이상하고 낯설게 작성되있다. 최대한 이해하기 쉽게 내 말로 풀어서 작성해 보겠다. 아무튼 그렇게 3주차가 시작됬다. 이번주도 파이팅~ 컴퓨터 시스템 (CSAPP) 정리 1.5 캐시가 중요하다. 프로세서인 CPU는 컴퓨터의 뇌로 역할을 수행하고, 레지스터와 메인 메모리, 디스크 메모리는 CPU에게 수행 명령을 지시 받는데, 파일을 실행 시에 인스트럭션(수행 명령)들이 메인 메모리로부터 CPU로 복사되고, 인스트럭션을 읽고 실행을 수행하라는 명령을 내리는 것으로, 디스크 메모리에 있던 파일을 메인 메모리로 복사하고~ (이때, 바로 디스크의 메모리가 프로세서로 ..