mojo's Blog

문제 링크 => 10986번: 나머지 합 (acmicpc.net) 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 누적합을 이용한 문제이다. i 번째에서 j 번째까지 원소들의 합이 M으로 나누어 떨어지는 모든 경우를 구해야 한다. 이해하기 쉽도록 예시를 들어보도록 하자. ex ) 원소 5개 [1, 2, 3, 4, 5] 이 있고 3 으로 나누어 떨어지는 모든 경우의 수를 구하시오. 1. 배열 A에 대한 정보는 다음과 같다. 1 2 3 4 5 2. sum[i] = (..

Bottom-up Parsing Bottom-up parsing: - Input string을 읽어가면서 reduce에 의해 start symbol을 찾아가는 방법 - Input string이 start symbol로 reduce되면 올바른 문장이라고 판단, 파스 트리 출력 - 그렇지 않으면 문법에 맞지 않은 문장으로 판단, 에러 메시지를 출력한다. reduce, handle: S ⇒* αAw ⇒ αβw의 유도 과정이 존재할 때 - reduce: sentential form αβw에서 β를 A로 대체하는 것 - handle: β. 즉 한 sentential form에서 reduce되는 부분. ex ) rightmost derivation 과정을 보이고 parse tree를 그리고 handle 을 찾기 S..

Beyond Physical Memory : Mechanisms Use part of dist as memory. Os need a place to stash away portions of address space that currently aren't in great demand. In modern systems, this role is usually served by a hard disk drive. Memory Hierarchy는 Registers, Cache, Main Memory 와 Mass Stoarage를 구분지어서 볼 수 있다. Register, Cache, Main Memory는 volatile 하여 저장했던 내용이 증발하지만 (DRAM 과 같은) Mass Stoarge 는 involat..

Paging : Linear Tables We usually have one page table for every process in the system. - Assume that 32-bit address space with 4KB pages and 4-byte page-table entry. entry size가 4Byte 이므로 Page table 에 들어갈 entry 총 갯수는 다음과 같다. Page table의 entry 총 갯수 = 2^12 / 2^2 = 2^10 = 1024 개 이다. page table total size = 2^32 / 2^12 * 4 Byte = 4 MByte 이다. 즉, Page table 이 너무 커서 memory 소비가 큰 문제점이 있다. Paging : Small..

TLB Part of the chip's memory-management unit(MMU). A hardware cache of popular virtual-to-physical address translation. TLB Basic Algorithms VPN = (VirtualAddress & VPN_MASK) >> SHIFT (Success, TlbEntry) = TLB_Lookup(VPN) if(Success == TRUE){ // TLB Hit if(CanAccess(TlbEntry.ProtectBit) == true){ offset = VirtualAddress & OFFSET_MASK PhysAddr = (TlbEntry.PFN An instruction or data item that has..

Segmentation 복습 Dynamic relocation 방법은 base + bounds register 를 통해서 virtual address를 physical address로 변환해준다. (MMU를 통해서) Process address 공간이 물리적으로 메모리에 할당될 때 contiguous 하게 할당되어야 한다. 근데 중간 중간에 Free() 가 일어나서 결국 Fragmentation 이 생겨서 contiguous 하게 할당할 수 없는 문제가 생기는데 이를 해결하기 위해 Segmentation 이 나타났다. code, heap, stack 영역이 각각 contiguous 하지만 서로 independent 하고 이를 table 로 만들 수 있다. MMU에서 base, bound register ..