입력 : 세로 크기 N, 가로 크기 M ( 2 > m >>n; for (int i = 0; i > map[i][j]; if (map[i][j] == 1) qu.push({ i,j });// 익은 토마토의 자리는 큐에 넣어준다. else if (map[i][j] == 0) tomato_count++; // 안익은 토마토의 갯수를 카운트한다. } } void bfs() { // tomato_count 가 모두 소진됐다면 토마토가 모두 익은것 // tomato_count 가 남아있다면 ( 0 이상 ) 토마토가 익지 못하는 상황 -> -1 출력 while (!qu.empty()) // 큐가 공백이 될때까지 반복한다 { int que..
1. 기본적 하드웨어 - 주 메모리와 프로세서 내장 레지스터는 CPU가 직접 접근할수 있는 저장장치이다. 모든 실행되는 명령어와 데이터는 CPU가 직접적으로 접근할 수 있는 주 메모리오 레지스터에 있어야 한다.CPU의 내장 레지스터들은 일반적으로 CPU 클록의 1 사이클내에 접근이 가능한데 , 메모리 버스를 통해서 전송되는 주 메모리의 경우에는 많은 CPU 클록 틱 사이클이 소요되고, 지면(Stall) 현상이 발생하기도 한다. 따라서 CPU와 주 메모리 사이에 캐시(Cache)메모리를 추가하여 속도의 차이를 완화시킨다. 이러한 속도 차이에 대한 고려뿐만 아니라 보호기법등 여러가지 구현방법들이 있다. 2. 메모리 보호 기법 - 프로세스가 합법적인 영역만 접근하도록 설정하는것이 필요하다. "기준(base)"..
여러개의 프로세스들이 한정된 자원을 가지고 서로 경쟁할때 생기는 문제로 대기 중인 프로세스들이 다시는 그 상태를 변경시킬 수 없을때의 상황을 "Dead Lock", 즉, 교착상태라고 한다. 일반적으로 프로세스는 1) 요청 2) 사용 3) 방출 의 과정을 따른다. 1. 교착상태 특징 교착상태는 아래의 4가지 조건을 성립할때 발생할 수 있다. 1) 상호 배제 ( Mutual Exclusion ) - 한 번에 한 프로세스만이 그 자원을 사용할 수 있고, 다른 프로세스가 자원을 요청하면, 요청 프로세스는 자원이 방출될 때까지 반드시 지연되어야 한다. 2) 점유하며 대기 ( Hold and Wait ) - 프로세스는 최소한 하나의 자원을 가지고 있는 상태에서 , 다른 프로세스에 의해 점유된 자원을 얻기 위해서는 ..
1. 유한 버퍼 문제 - 유한 버퍼 문제는 동기화 문제의 대표적인 예로서 생산자는 데이터를 만들어서 버퍼에 저장하는 프로세스를 뜻하고, 소비자는 버퍼에 있는 데이터를 꺼내서 소비하는 프로세스를 뜻한다. 버퍼는 공유자원이기 때문에 생산하고 소비하는 작업이 서로 상호배제 되어야 하는데, 이 두개를 병행하게 실행시킬 경우 올바르게 동작하지 않는다. 왜냐하면 두 개의 프로세스가 동시에 변수 counter를 조작하도록 허용하였기 때문인데, 이를 race condition 이라고 한다. 따라서 하나의 프로세스만이 변수를 조작할수 있도록 프로세스를 동기화 시켜야 한다. ( 동기화 : 순서에 있어 질서가 잘 맞게 하는것 ) 2. 임계 영역 프로세스는 코드, 데이터, 스택 영역으로 이루어져 있다. 각각의 프로세스는 임계..
리눅스 실습 시간에 배운 Run-Length Encoding 알고리즘 간단하게 복습 기본적인 개념은 "중복되는 문자를 한 문자로 치환시키는 것" 이다. 예를들면 텍스트 파일의 내용이 " AAABCDDDDDOS " 로 되어있다고 하면 " A3BCD5OS " 로 이렇게 중복되는 문자를 숫자로 치환하는것이다. 하지만 압축을 했으면 복호화의 과정이 필요한데 만약 저렇게 되어있을경우 3이 실제로 입력된 문자인지 치환된 문자인지 구별하기 어렵다는점이 있다. 따라서 치환된부분을 탈출문자 (Escape) 문자를 이용하여 나타낼 수 있다. " *3ABC*5DOS " 이렇게 *로 나타내는것이다. 그래서 탈출문자로 문자이기때문에 거의 쓰이지않는문자를 쓰는게 중요하다. 코드 예시 int f(int n) { i#include ..
1. 개요 [그림 1] 동적 계획법 ( Dyanmic Programming ) 완전검색을 좀 더 효율적으로 하는 방법Recursive + Memoization 기법을 활용 (1) 메모이제이션 (Memoization) : 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기법으로 동적계획법의 핵심이 되는 기술이다. (2) 동적계획법의 적용 요건1. 최적 부분문제 구조 (Optimal Substructure) : 최적화 원칙이란 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다는 것이다.동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이용해서 구하기 때문에 만약 큰 문제..
1. 개요 [그림 1] 깊이 우선 탐색 (Depth First Search) 깊이 우선 탐색 알고리즘은 그래프 구조에서 시작 정점의 한 방향으로 갈 수 있는 경로가 있는 곳까지 깊이 탐색해가다가 더 이상 갈 곳이 없게되면, 가장 마지막에 만났던 갈림길 간선이 있는 정점으로 되돌아와서 다른 방향의 정점으로 탐색을 계속 반복하여 결국 모든 정점을 방문하는 순회방법이다. 따라서, 가장 마지막에 만났던 갈림길의 정점으로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 후입선출 구조의 스택을 사용 하거나 재귀호출을 통해서 구현한다. 2. 깊이 우선 탐색 예제 1 - 두 색으로 칠하기 (Binary Coloring) 평면위의 지도에서 서로 인접한 다른 영역을 구분하기 위해서 다른 색으로 칠하고자 한다. 어떤 연결..
1. 개요 [그림 1] 탐욕법 ( Greedy ) 과정 탐욕법 알고리즘은 최적해를 구하는데 사용되는 근시안적인 방법이다. 일반적으로 머리속에 떠오르는 생각을 검증 없이 바로 구현하면 Greedy접근이 된다. 여러 경우 중 하나를 선택할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들어 놓고 보면 그것이 최적이라는 보장은 없다.일단 한번 선택한 것을 번복하지 않는다는 특성 때문에 대부분의 탐욕 알고리즘은 단순하며, 또한 제한적인 문제들에 적용된다. 최적화 문제 (optimization)란 가능한 해들 중에서 가장 좋은 (최대 또는 최소)해를 찾는 ..
1. 개요 [그림 1] 백 트래킹(Backtracking) 과정 백트래킹의 주요 개념은 해를 얻을 때까지 모든 가능성을 시도하는 기법이다. 모든 가능성은 하나의 트리처럼 구성할 수 있으며, 가지 중에서 해결책을 찾는다. 탐색 중에 오답을 만나면 이전 분기점으로 돌아가고 시도해보지 않은 다른 해결 방법이 있으면 시도한다. 여러 시도중 해결 방법이 더이상 없으면 더 이전의 분기점으로 돌아가고 모든 트리의 노드를 검사해도 답을 찾지 못할 경우, 이 문제의 해결책은 없는 것으로 간주한다. 1. 어떤 노드의 유망성을 점검한 후에 유망(Promising)하지 않다고 결정되면 그 노드의 부모로 돌아가 (backtracking) 다음 자식 노드로 감 2. 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 ..