반응형 [Public] 컴퓨터공학/알고리즘13 [알고리즘] 시간 복잡도 알고리즘 책을 넘기다 보면 시간 복잡도 란 개념으로 1장 ~ 2장 사이에 위치하고 있어 설명하는 내용도 뭐이리 어렵게 설명하는지 처음으로 알고리즘을 공부해 보겠다는 사람들에게 이런 뷁 ~~ 이란 말이 나오도록 알고리즘이란 어려운 것이야 하는 느낌을 준다 . 시간복잡도 너 뭐니? 한번 시간 복잡도에 대해서 알아보자 먼저 시간복잡도를 알기 전에 알고리즘을 짠다면 가장 중요한게 뭘가 ? 생각 해보아라 . . . 먼저 시간은 적게 걸려야 하고 메모리 사용은 적어야 한다 . . 이정도 만 생각했다면 당신은 이제 시간 복잡도와 공간복잡도에 대해 다 안것이다. 말 그대로 알고리즘을 구현하는데 있어 얼마나 속도가 걸리는지 얼마나 적은 메모리 사용하는지 이자체가 시간복잡도 공간복잡도 라 생각하면된다. 예전 286 시대만.. 2010. 4. 28. [알고리즘] 카프-라빈 알고리즘 (문자열 검색 #1) 카프-라빈 알고리즘에 대해서 설명해보려고 한다. 먼저 새로운 다짐을 하고 새해 처음 쓰는 글이다. 이미 20일이지만.. ㅋㅋ 내글을 한방에 읽고 카프-라빈 알고리즘이 머리에 꽉 박히면 좋겟다. 박혔으면 리플은 남겨주는 센스... ㅎㅎㅎ 리플을 남겨주면 이 글을 써놓은 보람이 생겨서 재미를 느끼고 글을 쓰게 되는거 같다. 말이 길었다. 카프 라빈 알고리즘에 대해 알아보자 오늘 나는 읽고 싶은 책이 생겨서 학교 도서관을 갔다. 읽고 싶은 책은 "카프-라빈 이 들려주는 이야기 " 어라 이 책이 어디 있을가? 앞에 컴퓨터가 있다. 음 여기서 찾으면 되겠군 ㅋㅋㅋ 검색란을 사용해야 겠다. 카프-라빈 검색 클릭! 짠 A열 135번에 있단다. 자 여기서 우리는 한번 짚어 보자 검색하는 과정을 보자 우리는 여기서 카프.. 2010. 1. 23. [알고리즘] 4배수 마방진 2009. 05. 13 (水) 4배수의 마방진이란 n의 값이 4 8 12 같이 4의 배수로 구성된 마방진을 뜻 합니다. 1. 4배수 마방진 풀이 ① 1:2:2 의 비율로 가로 세로를 3등분하여 9개 구역으로 나눕니다. ② 대각선 방향은 정방향으로 1부터 숫자를 차례대로 대입합니다 ③ 나머지 영역은 끝에서부터 역방향으로 차례대로 기록 합니다. 2. 소스 #include "stdafx.h" #include #define MAXSIZE 10 int g_nSquare[MAXSIZE][MAXSIZE] ={0, }; bool IsInBlock(int n, int row, int col); void GetQuaterSquare(int n); void InitSquare(); void PrintSquare(int n).. 2009. 5. 13. [알고리즘] 홀수 마방진 2009. 05. 11 (月) 중국 전설의 주인공인 한나라 우임금은 홍수를 다스리려고 황하강의 지류에서 물길을 고치다가 거북 등껍질에 새겨진 이상한 그림을 얻었다고 합니다. 낙서라 불려지는 이 그림은 1부터 9까지의 숫자가 3X3의 정사각형에 배열돼 있었다고 한다. 신기한 것은 늘어선 숫자들이 가로, 세로, 대각선 어느 방향으로 더해도 그 합이 15가 되는 것이었습니다. 그래서 고대 중국에서는 이 낙서가 우주의 원리를 포함 하고 있다고 여기고 신비한 힘을 가지고 있다고 생각되었습니다. 이처럼 1부터 연이은 숫자로 사각형 모양으로 배열해 가로 세로 대각선 방향의 합이 모두 같도록 배열한 것을 마방진 이라고 합니다. 1. 홀수 마방진 풀이 ① 첫 번째 숫자를 1행의 중앙열에 넣는다. ② 대각선 방향(한 칸 .. 2009. 5. 11. [알고리즘] 소수를 구하자 (소수#1) 2009. 05. 08 (金) 수학시간에 배운 소수(prime number)의 사전적인 의미는 1보다 큰 정수 p가 1과 p자신 이외의 양의 약수를 가지지 않을 때의 p를 소수라 정의합니다. 반대로 다른 숫자의 곱으로 이루어진 소수가 아닌 자연수를 합성수라 합니다. 참고로 1은 소수도 합성수도 아닙니다. 1. 자연수 n 의 소수 판단법 ① 1부터 n까지 반복해서 n의 약수인지 확인한다. ② 만약 새로운 약수를 찾으면 count 변수를 +1한다 ③ 모든 확인이 끝난 뒤 약수의 개수가 2이면 소수이고 그렇지 않으면 소수가 아니다 2. 소스 #include "stdafx.h" #include bool IsPrimeNumber(int n); int _tmain(int argc, _TCHAR* argv[]) { .. 2009. 5. 8. [알고리즘] 하노이의 탑 2009. 05. 06 (水) 883년 프랑스 수학자 루카스(Lucas. E.)는 하노이 탑이라고 불려지게 된 유명한 문제를 고안해냈습니다. 전설에 따르면 천지 창조 시에 가장 가운데 작은 구멍이 뚫린 64개의 금으로 된 원판이 하노이의 한 사원에 보관되어 있었다고 합니다. 이들 원판은 어느 것도 크기가 같지 않으며 그림과 같이 작은 원판이 큰 원판 위에 오도록 포개어져, 세 개의 기둥가운데 한 개에 끼워져 있었다고 합니다. 이러한 모양이 탑과 비슷하다 하여 하노이탑(Hanoi Tower) 이라고 부릅니다 1. 하노이 탑 정의 - 원판을 세 번째로 모두 옮겨놓아야 한다. 이때도 작은 원판이 큰 원판 위에 있어야 한다. - 원판을 옮길 때는 반드시 한 번에 한 개씩 옮길 수 있고 두 번째 막대기를 이용할 .. 2009. 5. 6. 이전 1 2 3 다음 반응형
