알고리즘 기초

대전 멤버십 회원인 박태현씨의 알고리즘 기초 강좌에서 기억하고자 하는 내용들을 정리해본다.

1. for 문의 1억번은 1초이다.

2. 알고리즘 문제는 100줄 이하로 풀 수 있다.

3. 제한조건을 꼭 확인하라

4. 전역변수는 배열크기 약 천만개까지 가능하다.

5. 동적 메모리 할당은 시간을 잡아먹는다.

6. cout보다 printf 가 훨씬빠르다.

에라토스테네스체

: 1보다 큰 자연수 n 에 대하여 루트n 보다 작거나 같은 모든 소수가 n을 나누지 못하면 n은 소수이다.

다음은 윤필립씨의 피티 강의를 따라 가보겠다~

1. 알고리즘이라는 것 무엇일까?

=> 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것

2. 좋은 알고리즘이란?

=> 빠르다.

=> 메모리를 적게 먹는다.

=> 알고리즘의 각 과정이 알아보기 쉽다. ( 이거 좋은 것 같다 )

=> 구현이 쉽다

다음은 삼각형의 최대길이 문제이다.

다음의 문제가 있다고 한다면.

가장 긴 봉의 길이는 다른 2개의 봉 길이의 합보다 작아야한다.

A < B + C

해결방안 중 하나이다.

O(n3): 3중루프로선택할수있는모든봉을조사하고위의식을이용해삼각형을만들수있는지를 판단한 후에 가장 긴 둘레를 찾는다. 

아래는 그 유명한 하노이탑 문제이다.

Base Condition : 디스크가 1개일 때, 1

n번째 디스크를 옮기기 위해서는 위에 있는 n-1개의 디스크를 다른 곳에 옮긴 후에 옮겨야 한다. 그럼 문제는 n-1개의 디스크를 옮기는 문제로 작아지게 된다.

Recursive Formula : f(n) = f(n-1) + 1 + f(n-1) = 2 * f(n-1) + 1 

그래프 

GRAPH _ 인접행렬 , 가중치 표현방법 

배열의 인덱스가 노드간 연결 상태를 표현한다.

ex) : array[1][2] = 7 , array[2][4] = 3

DFS 깊이 우선 탐색 - [스택 + 재귀]

출처 : http://en.wikipedia.org/wiki/Depth-first_search

BFS 넓이 우선 탐색 - [큐]

출처 :  http://en.wikipedia.org/wiki/Breadth-first_search