mojo's Blog

문제 링크 : 25189번: 시니컬한 개구리 (acmicpc.net) 25189번: 시니컬한 개구리 개구리는 $N \times M$ 격자 모양의 청정한 서식지에 살고 있다. 가장 왼쪽 위 칸의 좌표는 $(1,1)$이고 가장 오른쪽 아래 칸의 좌표는 $(N,M)$이다. 각 격자 칸에는 개구리밥이 있는데, 개구리는 자신이 www.acmicpc.net 2022 서강대학교 청정수컵 Round G번 문제이다. 문제 유형은 전형적인 BFS 로 보이지만, 인풋 사이즈로 인해 난이도가 급상승한 느낌이다. N, M 값의 최대값이 100 이였다면 navie 하게 \(O(N^{3})\) 으로 해결이 가능했을 것이다. 그러나, N, M 값의 최댓값이 1000 이므로 navie 한 접근이 불가능하므로 약간의 생각이 필요했다. ..

※ Implicit Memory Management : Garbage Collection Garbage Collection : 힙이 할당된 storage 를 자동으로 회수한다. 많은 dynamic langauges 에서 공통적으로 : Python, Ruby, Java, Perl, ML, Lisp, Mathematica C 및 C++ 에 대한 Variants ("conservative" 가비지 수집기)가 있다. 그러나 모든 가비지를 반드시 수집할 수는 없다. void foo() { int *p = malloc(128); return ; /* p block is now garbage */ } 위 코드는 memory leak 을 유발하는 함수이다. 이러한 상황은 다음과 같이 나타낼 수 있다. stack에 fo..

※ Keeping Track of Free Blocks Method 1: 길이를 사용한 implicit list 으로 모든 블록을 연결한다. Method 2: 포인터를 사용하는 free blocks 중에 explicit list 이다. Method 3: Segregated free list 다양한 크기 클래스에 대한 서로 다른 free lists Method 4: 크기별로 정렬된 Blocks 각 free 블록 내에 포인터가 있는 균형 잡힌 트리(Red-Black tree)와 key로 사용된 길이를 사용할 수 있다. 1번 방법 같은 경우는 포인트된 모든 영역을 전부 스캔해야하는 점에서 시간적인 문제가 존재한다. 2번 방법 같은 경우는 free 된 영역만을 scan 하기 때문에 시간적인 문제는 줄지만 fre..

문제 링크 : 24526번: 전화 돌리기 (acmicpc.net) 24526번: 전화 돌리기 첫 줄에 부원의 수 $N$과 관계의 수 $M$이 공백을 사이에 두고 정수로 주어진다. ($2 \le N \le 100,000$ , $1 \le M \le $ $500,000$) 둘째 줄부터 $M+1$번째 줄까지 어떤 부원 $U_{i}$가 전화를 받았을 때 다른 부원 www.acmicpc.net 사이클을 어떻게 처리해야 할지 고민을 했던 문제이다. 우선 방문배열을 2차원 배열 형태(visited[100001][2])로 선언하여 다음과 같이 처리하도록 하였다. visited[x][0] : 노드 x가 최초로 방문되었는지 판단하기 위한 용도이며 true로 마킹된 경우 방문한 경우다. visited[x][1] : DFS를..

※ Dynamic Memory Allocation 프로그래머는 malloc 와 같은 dynamic memory allocator 를 사용하여 런타임때 VM 을 획득한다. 크기가 런타임에만 알려진 데이터 구조용이다. Dynamic memory allocator 는 힙으로 알려진 프로세스 가상 메모리 영역을 관리한다. Allocator 는 힙을 할당되거나 free 할 수 있는 가변 크기 블록의 모음으로 유지 관리한다. Allocator 의 종류로는 다음과 같다. Explicit allocator : 응용프로그램이 공간을 할당하고 free 가능 예: malloc 및 free in C Implicit allocator : 응용 프로그램이 공간을 할당하지만 free 는 하지 않음 예: Java, ML 및 Lisp..

※ Exploiting parallel execution 지금까지는 스레드를 사용하여 I/O 지연을 처리했다. 예를 들어, 클라이언트당 하나의 스레드를 사용하여 다른 스레드를 지연시키는 것을 방지한다. Multi-core/Hyperthreaded CPU는 또 다른 기능을 제공한다. 병렬로 실행되는 스레드에 작업 분산 독립적인 작업이 많은 경우 자동으로 발생 예를 들어, 많은 응용 프로그램을 실행하거나 많은 고객에게 서비스를 제공한다. 또한 코드를 작성하여 하나의 큰 작업을 더 빨리 진행할 수 있다. 다중 병렬 하위 그룹으로 구성함으로써 Hyperthreading 이란? 하이퍼스레딩은 Intel 이 동시 멀티스레딩을 구현한 기술이다. 물리상 실행 장치 한 개에 가상 실행 장치(virtual 또는 logic..