Engineering Note

it 취업을위한알고리즘문제풀이 문제 코드1 //50. 영지(territory) 선택 : (small) #include int main() { //freopen("input.txt", "rt", stdin); int map[51][51]; int H, W, HH, HW, count = 0, maxCount = 0; //입력 scanf("%d %d", &H, &W); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { scanf("%d", &map[i][j]); } } scanf("%d %d", &HH, &HW); //알고리즘 //i,j는 누적해서 더해 갈 시작위치 값을 의미 for (int i = 0; i

it 취업을위한알고리즘문제풀이 문제 알고리즘 개선 전 소스코드 //50. 영지(territory) 선택 : (small) #include int main() { //freopen("input.txt", "rt", stdin); int map[51][51]; int H, W, HH, HW, count = 0, maxCount = 0; //입력 scanf("%d %d", &H, &W); for (int i = 0; i < H; ++i) { for (int j = 0; j < W; ++j) { scanf("%d", &map[i][j]); } } scanf("%d %d", &HH, &HW); //알고리즘 //i,j는 누적해서 더해 갈 시작위치 값을 의미 for (int i = 0; i

선택정렬 기본적인 정렬 알고리즘 오름차순을 기준으로 설명하면 0번 인덱스부터 마지막 인덱스 에서 최소값을 찾아 0번 인덱스에 위치 시키고 다시 1번 인덱스부터 마지막 인덱스에서 최소값을 찾아 1번 인덱스에 위치시킨다. 위 과정을 반복한다. 문제 해결 과정 반복문을 통한 문제해결 선택 정렬의 핵심은 최소값을 찾는 알고리즘이다. 최소값을 찾는 Min(int list[],int fn, int ln)함수 구현 배열의 주소와 첫 구간인덱스 번호와 마지막 구간 인덱스 번호를 주면 첫 구간 다음 인덱스부터 마지막 인덱스 까지 비교하면서 최소 값을 찾도록 알고리즘을 구현했다. Sort(int list[], int size)함수 구현 배열의 주소와 사이즈를 매개변수로 주면 반복문으로 Min()함수에 첫구간 값을 변경하면..

리스트 자료구조 리스트는 데이터를 순서대로 나열한(줄지어 늘어놓은) 자료구조 입니다. 이때 중복된 데이터를 허용합니다. 배열기반 선형리스트 같은 타입의 데이터를 연속된 메모리 공간에 저장하는 배열도 선형리스트로 구현이 가능하다. 장점 데이터 검색, 이동시에는 인덱스 값으로 접근이 가능하므로 -> &#39;상수&#39;시간 만큼 소요됨 단점 데이터의 삽입, 삭제에 따라 리스트에 정의에 따라 삽입, 삭제에 따라 데이터를 모두 옮겨야 하기 때문에 효율이 좋지 않습니다. 배열은 선언 이후에는 크기를 변경할 수 없기 때문에 최초 선언시 쌓이는 데이터의 크기를 알아야한다. 구조체와 포인터로 연결기반 선형리스트 배열 기반 선형리스트의 단점을 극복하기 위해 다음 노드를 가리키는 포인터를 각 노드에 포함시키는 연결리스트..

알고리즘 효율성 분석 시간의 효율성 공간의 효율성 코드의 효율성 시간의 효율성 주어진 조건에서 문제를 해결하기 위해 가능한 한 빠른 시간안에 가장 효율적으로 해결책을 찾는 것 시간복잡도 시간복잡도는 알고리즘에서 사용된 입력크기와 단위연산이 몇 번 수행되는지 함수로 표현 공간의 효율성 컴퓨터의 메모리를 얼마나 사용하는지에 따라 효율성을 결정 공간복잡도 코드의 효율성 개발자 입장 변수명과 주석 등 이해하기 쉽도록 작성되어 코드의 가독성이 좋고 유지보수가 용이하도록 모듈화를 잘해 놓은 코드 하드웨어 입장 컴퓨터와 하드웨어의 입장에서 작성된 코드 알고리즘 분석 방법 Every case analysis 입력크기에 종속 입력값과는 무관함 Worst case analysis 입력크기와 입력값 모두에 종속 단위연산이 ..

KOCW 알고리즘(명지대 이충기교수님) 알고리즘 문제 해결을 위한 단계적인 절차 알고리즘 작성법 인간의 자연어(한국어, 영어)로 작성 pseudo code(의사코드)로 작성 순서도로 작성 알고리즘에서 특정 문장의 수행 횟수를 계산하기 위해 필요한 3가지 식 1. 2. 3. 1번 식의 사용 사례 i가 1일 때 1번, 2일때 2번, 3일때 3번, 4일때 4번 수행 ... n일때 n번 수행 -> 총 (1+2+3+4+...+n) 번 수행

분할정복 알고리즘 주어진 문제의 입력을 분할하여 문제를 히결하는 방식의 알고리즘이다. 분할된 입력에 대하여 동일한 알고리즘을 적용하여 해를 계산하며, 해를 취합하여 원래 문제의 해를 얻는다. 여기서 분할된 입력에 대한 문제를 부분문제라고 하고, 부분문제의 해를 부분해라고 한다. 부분 문제는 더 이상 분할할 수 없을 때까지 계속 분할한다. 가짜동전찾기 1024개의 동전에서 하나의 가벼운 가짜 동전이 있을 때 하나를 기준으로 1023개를 비교해가며 가짜 동전을 찾을 수도 있고 2개씩 짝지어 n/2번회수로 가짜동전을 찾을 수도 있지만 분할정복기법을 적용하면 비교횟수를 줄일 수 있다. 512개씩 저울에 비교 가벼운 쪽을 다시 256개씩 비교, 가벼운쪽을 다시 128개씩, 64,32,16,8,4,2,1씩 비교해가..

퀵 정렬 퀵 정렬은 병합 정렬과 마찬가지로 &#39;분할 정복(divide and conquer&#39;)에 근거하여 만들어진 정렬 방법이다. 정렬의 대상이 되는 배열에서 하나의 원소를 고른다. 이 원소를 pivot이라고 한다. 피벗을 기준으로 앞에는 피벗보다 작은 원소를 뒤에는 큰 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다. 둘로 나누어진 배열에 대해서 재귀(recursion)적으로 반복한다. 배열의 원소의 개수가 1이 될때 까지 반복한다. 퀵 정렬 세부 동작 과정 left가 가리키는 값이 pivot이 가리키는 값보다 클 때까지 반복 pivot이 가리키는 값과 left가 가리키는 값을 비교하여 left가 가리키는 값이 작기 때문에 left 우측으로 한칸 이동, 4(pivot)와 3을 비교해서 ..