CS STUDY

Counting Cells in a Blob - Binary 이미지 - 각 픽셀은 background pixel이거나 혹은 image pixel - 서로 연결된 image pixel들의 집합을 blob이라고 부름 - 상하좌우 및 대각방향으로도 연결된 것으로 간주 - 입력: - N*N 크기의 2차원 그리드(grid) - 하나의 좌표(x, y) - 출력: - 픽셀 (x, y)가 포함된 blob의 크기 - (x, y)가 어떤 blob에도 속하지 않는 경우에는 0 Recursive Thinking 현재 픽셀이 속한 blob의 크기를 카운트 하려면 현재 픽셀이 image color가 아니라면 0을 반환한다. 현재 픽셀이 image color라면 먼저 현재 픽셀을 카운트한다 (count - 1). 현재 픽셀이 중복..

Maze 미로찾기 현재 위치에서 출구까지 가는 경로가 있으려면 1) 현재 위치가 출구이거나 혹은 2) 이웃한 셀들 중 하나에서 현재 위치를 지나지 않고 출구까지 가는 경로가 있거나 boolean findPath(x,y) if (x,y) is the exit return true: else for each eighbouring cell (x', y') of (x, y) do if (x', y') is on the pathway if findPath(x', y') return true; else false; } boolean findPath(x,y) if (x,y) is the exit return true: else mark (x, y) as a visited cell; for each eighbourin..

Designing Recursion(순환 알고리즘의 설계) - 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함. - 모든case는 결국 base case로 수렴해야 함. - 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라. 순차 탐색 int search(int [] data, int n, int target) { for(int i=0; iend) return -1; else if (target == items[begin]) return begin; else return search(data, begin+1, end, target); } 이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색..

Recursive Thinking : 순환적으로 사고하기 Recursion은 수학함수 계산에만 유용한가? -> 수학 함수 뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다. 문자열의 길이 계산 if the string is empty return 0; else return 1 plus the length of the string that excludes the first character; 문자열의 길이 계산 public static int length(String str){ if (str.equals("")) return 0; else return 1+length(str.substring(1)); } 문자열의 프린트 public static void printChars(String s..

Recursion : 자기 자신을 호출하는 함수 void func(...){ func(...); } What will happen? > 무한루프에 빠진다. public class Code01{ public static void main(String [] args){ func(); } public static void func(){ System.out.println("Hello..."); func(); } } recursion은 항상 무한 루프에 빠질까? > No. recursion이 항상 무한 루프에 빠지는 것은 아니다. public class Code02{ public static void main(String [] args){ int n = 4; func(n); } public static void ..

Swap-Space Management Disk를 사용하는 두 가지 이유 memory의 volatile한 특성 -> file system 프로그램 실행을 위한 memory 공간 부족 -> swap space(swap area) Swap-space Virtual memory system에서는 디스크를 memory의 연장 공간으로 사용 파일시스템 내부에 둘 수도 있으나 별도 partition 사용이 일반적 공간효율성보다는 속도 효율성이 우선 일반 파일보다 훨씬 짧은 시간만 존재하고 자주 참조됨 따라서, block의 크기 및 저장 방식이 일반 파일 시스템과 다름 RAID(Redundant Array of Independent Disks) 여러 개의 디스크를 묶어서 사용 RAID의 사용 목적 디스크 처리 속도 ..