복습노트 복습노트

문제 2108번: 통계학 첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다. www.acmicpc.net 산술평균 : N개의 수들의 합을 N으로 나눈 값 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값 최빈값 : N개의 수들 중 가장 많이 나타나는 값 범위 : N개의 수들 중 최댓값과 최솟값의 차이 N이 주어지고 N개의 수를 입력하면 위의 4가지를 모두 구하는 것입니다. N은 무조건 홀수로 주어집니다. 1) 산술평균은 먼저 모든 N개의 수의 합을 구해야 하므로 처음에 입력 받을 때 부터 sum 이라는 int형 변수에 누적으로 더해주었습니다. 문..

문제 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B v - b 또한 우리는 하루에 (a-b) 만큼 이동할 수 있습니다. 식을 세워 보..

문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 단순히 수를 오름차순으로 정렬하는 문제입니다. 하지만 틀렸습니다... 문제의 제한사항을 보면 메모리 제한이 8 MB 입니다. 또한 숫자가 들어올 수 있는 개수는 10000000개 입니다. 따라서 int 형으로 수를 받게 되면 최악의 경우 4 byte * 10^7 = 40MB 의 크기가 됩니다. 수의 개수는 100000000이지만 수의 범위는 10000까지 입니다. 따라서 수의 범위의 해당하는 배열의 크기를 잡고 입력되는 수의 index에 다가 세어줍니다. 이제 차례대로 출력해주..

문제 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타 www.acmicpc.net 666이 들어가는 숫자중 n번째 숫자를 찾아 출력하는 문제입니다. 예를 들어 n = 1이면 666이고 n = 2이면 1666입니다. 2666 3666 4666 5666 6660 6661 6662 . . 처음에 접근했을 때는 숫자를 1부터 증가시켜 각 자리를 검사해 연속으로 6이 3번 나오면 찾게 코딩을 해보았지만 말이 안됐습니다. 그러다 다른 블로그글을 참고하여 풀게 되었습니다. 간단히 말하면 1부터 하나씩 증가하면서 해당 숫자에 666이 들어있는지 판단..

이번 학기 시스템 프로그래밍 수업을 들으면서 처음으로 개발 이라는 프로젝트에 도전하였습니다. 리눅스 환경에 있는 shell을 직접 구현하는 것입니다. 총 3개의 Phase로 구성되어 있습니다. 리눅스 환경을 다루는 것도 처음이고 리눅스 명령어도 모르며 리눅스 shell 안에서 vi 에디터로 코딩하는 것도 처음이었기에 첫걸음이 매우 오래 걸렸습니다... 구글의 도움을 받아 리눅스 명령어 부터 익히고 (ex : ls, pwd, cd, 등등) 리눅스 shell 안에서 코딩하는 법(vi 에디터) 를 배우며 점점 익숙해져갔습니다. 하지만 vi 에디터로 코딩을 하는 것은 아직 많이 익숙하지 않아 vscode를 이용해 ssh 원격 접속을 통해 코딩을 진행하였습니다. 대충 프로젝트를 진행할 환경은 구축해 놓았지만 sh..

Expilcit Free Lists implicit free list와는 달리 explicit free list는 오직 free된 block만 탐색하게 됩니다. 이러한 free block을 탐색할 수 있도록 이중 linked list로 구성되는데, 이를 통해서 앞으로만 탐색하는 것이 아니라 뒤로도 탐색하는 것이 가능해집니다. 해당 block에 전의 free block의 주소로 갈 수 있는(주소값을 담고 있는) prev와 뒤의 free block의 주소로 갈 수 있는(주소값을 담고 있는) next를 넣게 됩니다. 이를 통해 allocate된 block은 탐색하지 않아 탐색하는 시간은 빨라지지만 free block에서는 prev와 next를 위한 공간이 추가적으로 요구되므로 메모리 활용도는 낮아집니다.

메모리는 크게 3가지로 나뉘어 집니다. Secondary Memory(Disk, Storage) Main Memory Cache Memory Technology 메모리에는 ROM과 RAM이 있습니다. ROM은 Read-Only Memory의 약자로 비휘발성 메모리라는 의미입니다. 전원이 꺼져도 data가 남아있습니다. RAM은 Random Access Memory의 약자로 휘발성 메모리라는 의미입니다. 전원이 꺼지면 data가 날라갑니다. Static RAM(SRAM) 메모리에 access하는데 0.5ns ~ 2.5ns가 들고 GB당 $500 ~ $1000에 가격입니다. Dynamic RAM(DRAM) 메모리에 access하는데 50ns ~ 70ns가 들고 GB당 $3 ~ $6 가격입니다. 이상적인 형태..

Basic Concepts index는 데이터 검색을 빠르게 하기 위함입니다. Search Key : file안에 있는 record를 찾기 위한 attribute 집합입니다. index file : 아래와 같은 record들을 구성합니다. 일반적으로 index file은 일반적인 file보다 작습니다. index는 크게 Ordered index : search key들은 차례대로 정렬 Hash index : search key들이 "bucket" 이라는 곳에 hash function에 의해 분배 Ordered Index Clustering index(primary index) primary key의 성격과 같습니다. search key가 그대로 순서대로 file을 가리킵니다. clustering inde..