cinux

입력 : 세로 크기 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..

리눅스 실습 시간에 배운 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. 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 ..

1. 개요 [그림 1] 분할 정복법 ( Divide and conquer ) 알고리즘 방법론중 하나인 분할정복 ( Divide and conqeur ) 알고리즘은 하나의 문제를 작은 문제로 분할하여 문제를 해결하는 방법이다. 분할 정복 알고리즘은 보통 재귀함수 ( Recursive function )을 이용해서 구현하는 것이 일반적이나 빠른 실행이나 부문제 해결 순서 선택을 위해 재귀호출을 사용하지 않고 스택(Stack), 큐(Queue) 등의 자료구조를 이용하여 분발 정복법을 구현하는 것도 가능하다. 분할 정복의 설계전략으로는1. 분할 (Divide) : 해결할 문제를 여러 개의 작은 부분으로 나눈다.2. 정복 (Conquer) : 나눈 작은 문제를 각각 해결한다.3. 통합 (Combine) : 해결된..

1. 개요 [그림 1] 재귀호출의 과정 재귀적 호출 함수 ( Recursive call ) 란 작업을 작은 단위로 쪼개서 재귀 호출된 함수 내에서 이 조각중에 하나를 해결하고, 나머지 조각들은 자기 자신을 또 호출해서 해결하는 방식으로 처리되는 함수로 간단히 말해서 함수 내부에서 직접 혹은 간접적으로 자기 자신을 호출하는 함수이다.재귀호출함수를 구현하려면 2가지 부분이 필요하다. 하나는 기본 부분 (Base part)와 유도 부분 (Inductive part)이다. 기본 부분은 재귀호출이 나중엔 결국 끝이 나야하므로 종결조건을 위한 부분이고 유도 부분은 새로운 집합의 원소를 생성하기 위해 재귀하는 부분이다. 재귀적 프로그래밍은 일반 반복 ( for,,while...등 ) 프로그래밍에 비해 간결하다는 점이..

1. 개요 [그림 1] 가중치배열 ( Weight Array ) 다익스트라 알고리즘 ( Dijstra Algorithm ) 은 가중치가 부여된 그래프에서 두 정점 사이의 최단 경로를 찾을 때 사용하는 알고리즘이다. 이 알고리즘에서는 어떤 시작점 S가 주어졌을 때, 그 정점에서 시작하여 다른 모든 정점으로 가는 최단 경로를 찾을 수 있기 때문에 결과적으로 어떤 최종 목적지 T로 가는 최단 경로를 구할 수 있다. 다익스트라 알고리즘에서 가장 중요하고 핵심이 되는 "가중치 배열 (Weight Array)"은 시작점 S를 기준으로 각 정점의 최단거리를 가리키는 배열이다. 2. 다익스트라 알고리즘 (Dijstra Algorithm) 코드 구현 및 설명 /*--------------------------------..