. '분류 전체보기' 카테고리의 글 목록 (7 Page)
본문 바로가기

분류 전체보기111

9.9.2 왜 동적 메모리 할당인가? / 9.9.3 할당기 요구사항과 목표 우선 정수를 하나씩 입력받는 함수를 만들어보자. 1 #include "csapp.h" 2 #define MAXN 15213 3 4 int array[MAXN]; 5 6 int main() 7 { 8 int i, n; 9 10 scanf("%d", &n); 11 if (n > MAXN) 12 app_error("Input file too big"); 13 for (i = 0; i < n; i++) 14 scanf("%d", &array[i]); 15 exit(0); 16 } 이 함수는 시작할 떄, 15213칸의 array를 선언한다. 만약 정수를 10개만 입력하고 싶다면 15203칸이 낭비될 것이고, 15214개의 정수를 입력하고 싶다면 성립되지 않는다. /* 이것이 stack메모리 인가? */ 그렇기에 .. 2021. 1. 15.
9.9.1 malloc과 free함수 C언어 표준 라이브러리는 malloc 이라는 명시적인 할당기를 많이 쓴다. 이 함수로 힙으로부터 블록들을 할당받는다. 우선 어떤 함수인지 보고가자. #include void *malloc(size_t size); Returns: pointer to allocated block if OK, NULL on error size_t 만큼의 포인터를 반환한다는 뜻이다. 구체적인 예는 아래와 같다. typedef struct _NODE { int cnt; bool leaf; bool root; int key[2 * t - 1]; struct _NODE *child[2 * t]; struct _DATA *dataAdress[2 * t]; struct _NODE *prevPtr; struct _NODE *nextPtr.. 2021. 1. 15.
9.9.0 동적메모리 할당 서문 가상 메모리의 영역을 저수준의 mmap과 munmap의 함수를 사용하여 생성하고 삭제할 수 있다. /* mmap과 munmap은 어떤 함수인가? 기본적이고 간단한 가상메모리 함수인가? mmap은 사용자 수준에서 커널 내부 주소 접근시 사용하고 munmap은 해제할 때 사용한다고 한다. */ 하지만 대개 추가적인 가상메모리를 런타임에 획득할 필요가 있을 때, 동적 메모리 할당기를 사용하는 것이 더 선호된다고 한다. 동적 메모리는 힙heap 이라고 하는 프로세스의 가상메모리 영역을 관리한다. /* 동적 메모리에 들어가기에 앞서 간단히 메모리의 영역을 공부하고 넘어가겠다. 메모리 구조를 알아보자 (velog.io) 메모리 구조를 알아보자 프로그램이 운영체제로부터 할당받는 대표적인 메모리 공간(RAM)은 다음과.. 2021. 1. 15.
9.1 물리 및 가상주소 방식 메인 메모리는 M개의 연속적인 바이트 크기의 셀의 배열로 구성된다. * 셀이라는 것은 메모리의 공간 기본단위인가? 각 바이트는 0, 1, 2, 3 ... 등의 물리주소(Physical Address)를 가지고, CPU는 이런 주소를 통해 메모리에 접근가능하다. 이런 방식을 물리 주소 방식이라고 부른다. 현재의 프로세스들은 다음과 같은 가상주소 방식을 사용한다. 초기의 컴퓨터들은 직접 물리주소 방식을 사용했다고 하는데, 왜 가상 주소 방식을 사용하는 것인가? 이것이 가상메모리와 연관이 있는 것일까? ( 가상 메모리 - 나무위키 (namu.wiki) ) 「현대의 CPU는 전부 MMU라는 메모리 관리 유닛을 별도로 내장하고 있다. 각 프로세스가 동립된 가상주소를가지면, A 프로세스에서 0x1000 라는 주소를.. 2021. 1. 15.
9.0 가상메모리 개략 가상 메모리는 세가지의 중요한 기능을 제공한다. 1. 메인 메모리를 디스크에 저장된 주소공간에 대한 캐시로 취급하여, 메인 메모리를 효율적으로 사용한다. 2. 각 프로세스에 통일된 주소공간을 제공함으로써 메모리 관리를 단순화한다. 3. 각 프로세스의 주소공간을 다른 프로세스에 의한 손상으로부터 보호한다. CS의 지식이 전무한 나로서는 이 세가지가 어떤 것인지 잘 모르겠다. 그렇기에 일단 추측을 해보기로 한다. 1의 경우 : 캐시는 CPU와 메인 메모리 사이에서 다시 사용할 가능성이 높은 데이터들을 임시로 보관하는 역할을 한다. 그런데 메인 메모리를 디스크에 저장된 주소 공간에 대한 캐시로 취급한다는 것은 어떠한 의미일까? 메인 메모리가 연산할 때 필요한 디스크의 데이터 중에서 많이 쓰이는 (혹은 많이 쓰.. 2021. 1. 15.
신입사원 장그래는 정규직이 될 수 없다 (백준 1946 : 신입사원) 몇 년전에 우리네의 회사 생활을 대변해주고 위로해주는 미생이라는 드라마가 세간의 화제가 되었던 적이 있었다. 나는 웹툰으로밖에 안봤지만, 당시 신입사원이었던 나에게 많은 공감이 되었고 신입사원으로서의 마음가짐을 심게해 준 미생이었는데. 신입사원 장그래는 결국에는 정규직이 되지 못하였지만 (스포인가?) 사실 청년실업자가 넘쳐나는 이 시대에는 비정규직 장그래조차 되기힘든게 현실아니겠는가 (백수가 되어버린 나를 포함하여 ㅠㅡㅠ) 그런데 심지어 이번 문제에서는 우리는 인사담당자가 되어서 실날같은 희망을 가지고 지원한 수 많은 청년들을 떨어뜨려야한다. 하지만 어쩌겠는가. 취직이 잘 되는 사회를 만들던가! (속이 뻥) 어쩔수 없다. 눈물을 머금고 칼춤을 춰 손에 피를 묻히자. 인사 담당자도 그저 한낱 월급쟁이에 불.. 2021. 1. 3.
누가 내 치즈를 옮겼을까? (백준 2638: 치즈) 2638번: 치즈 (acmicpc.net) 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net 톰과 제리같은 만화를 보면 항상 치즈는 샛노란 색깔에 치즈케이크같은 모양에 구멍이 송송 뚫려있는 모양으로 나왔다. 그걸 보고있으면 참 맛있어 보였는데, 우리가 흔히 먹는 치즈는 네모나고 얇은 치즈였다. 한번은 위 사진같은 치즈를 먹은 적이 있었는데.... 솔직히 맛은 기억 안난다. 그냥 평범했나보다. 푸른곰팡이 치즈였나 그거는 먹은 적이 있었는데, 겉보기로 음식을 판단하는 나이기 때문에 한입먹는 것이 되게 힘들.. 2020. 12. 30.
토이스토리 (백준 2637 : 장난감 조립) 2637번: 장난감조립 (acmicpc.net) 2637번: 장난감조립 첫째 줄에는 자연수 N(3 ≤ N ≤ 100)이 주어지는데, 1부터 N-1까지는 기본 부품이나 중간 부품의 번호를 나타내고, N은 완제품의 번호를 나타낸다. 그리고 그 다음 줄에는 자연수 M(3 ≤ M ≤ 100)이 주 www.acmicpc.net 이 문제를 보면서 프라모델이 생각났다. 작은 부품들로 중간 부품을 만들고, 중간 부품들로 큰 부품을 만들고, 큰 부품을 조립하여 완성시킨다. 정말 기본 부품의 경우, 중간 부품 하나를 만들기 위해 작은 부품을 모두 떼놨다가 잃어버려서 제대로 못만드는 경우도 있어서 곤혹스러웠던 기억이 있다. 그러니 프라모델만들 때에는 딱 필요한 부품만 뗀 뒤에 작업을 진행하도록 하자. 그러고보니 프라모델 안.. 2020. 12. 29.
따봉도치는 고마워! (백준 3055:탈출) 3055번: 탈출 (acmicpc.net) 3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 여러분들은 인터넷하면서 많은 낚시글을 본적이 있을 것이다. (본적없다면 당신은 상당히 건실한 삶을 살았다는 것이다. 자랑스러워해도 된다.) 이런 고전짤로부터 시작해서 소중한 머리카락으로 협박하는 놈도 있었고 같은 대 인공지능 시대에 걸맞는 낚시글도 있었고, 최근에 유행했던 킹치만이나 가슴이 웅장해지는 구미호놈까지 인터넷이 존재하는 한, 낚시글은 끊이지 않을 것이다. 물론 인터넷보면서 이런 식의 낚시글을 본게 한두개가 아니지만 (자라.. 2020. 12. 29.
미노타우르스와 함께 춤을 (백준 2178:미로탐색) 2178번: 미로 탐색 (acmicpc.net) 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 이번 시간에는 BFS 탐색을 공부해보도록 한다. 미로 탐색 문제는 BFS 탐색의 기본을 닦을 수 있는 좋은 문제이다. 즉, 어떤 맵이 있어서 1이 통로이고, 0이 벽이다. 여기서 미로를 탐색할 수 있는 최단거리를 찾는 문제이다. 이게 또 미로라고 하니 옛날에 화면보호기라는게 있던 게 기억이 난다. 요즘은 화면보호기라는 말 자체가 안들리지만, 옛날에는 모니터의 수명이 짧았는데, 한 화면만 계속 틀고 있으면 해당 색의 화소가 타버려서 모니터가 금방 .. 2020. 12. 29.
몸에도 좋고 맛도 좋은 (백준 3190 : 뱀) 3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 라떼에는 도트로 된 게임기가 있었는데, 거기에 항상 뱀 게임이 있었다. (테트리스, ㅗ 모양으로 된 자동차 게임, 핑퐁 게임도 같이 있었다... 기억나는 사람 있는가? 내 또래는 알거야...) 그 뱀 게임을 이제 만들어 볼 시간이다. 일단 입력부터 받아보자. import sys from collections import deque sys.stdin = open("input.txt", "r") # 보드의 크기 N N = int(s.. 2020. 12. 22.
땅! 땅! 땅! 빵! (백준 8983 : 사냥꾼) 8983번: 사냥꾼 (acmicpc.net) 8983번: 사냥꾼 입력의 첫 줄에는 사대의 수 M (1 ≤ M ≤ 100,000), 동물의 수 N (1 ≤ N ≤ 100,000), 사정거리 L (1 ≤ L ≤ 1,000,000,000)이 빈칸을 사이에 두고 주어진다. 두 번째 줄에는 사대의 위치를 나타내는 M개의 x-좌 www.acmicpc.net 많은 고민을 했던 문제이다. 처음에는 동물들의 좌표를 x축으로 정렬하고 각 x좌표마다 사거리를 계산해서 그 사거리 안에 있는 동물들을 탐색해봤는데, 아무리 시간을 좁혀봐도 시간초과가 났다. 그런데, 내 생각에 맹점이 있었다. 좌표값은 10억이기 때문에 x축을 기준으로 사거리를 계산하는 것은 엄청난 시간이 걸리는 반면, 동물의 수는 10만에 불과하다. (최댓값 기.. 2020. 12. 21.
힙(heap) 구조 만들기 11279번: 최대 힙 (acmicpc.net) 11279번: 최대 힙 첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 www.acmicpc.net 이번 또한 백준 문제이지만, 힙 정렬과 힙 배열에 삽입하는 코드를 구현해볼 것이기 때문에 파이썬 항목에 작성하겠다. 우선 배열을 힙 구조로 만드는 함수부터 구현해보자. 힙 정렬은 우선 제일 낮은 레벨의 leaf를 자식으로 하고, 윗 레벨의 node를 부모로 하는 최대 3개의 tree를 힙 배열로 만들고 점점 상향하는 bottom-up 방식으로 진행할 것이다. 그렇다면 힙 정렬의 함수는 최대 3인자.. 2020. 12. 21.
레이저 타워 디펜스 (백준 2493 : 탑) 2493번: 탑 (acmicpc.net) 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제를 보는 순간, 완전탐색으로 풀면 되겠네! 했지만, 고르든 등급의 백준 문제는 그런 추잡한 시도는 용납하지 않는다. 그럼 어떤 식으로 풀어야 할까. - 대전략: 탑 높이 리스트는 tower로 저장하고, 우선 체크리스트( check = [] ) 를 만들자. 또한, tower에 대해 for i in range(N)으로 왼쪽부터 ptr(포인터)가 시작하도록 하자. 또한, ptr 시작은 0 으로 하자. 왜 why. 문제를 .. 2020. 12. 21.

티스토리툴바