머리쓰기/알고리즘 5

rand()사용, 그리고 중복되지 않게 뽑기(소스포함)

흔히들 사용하는 랜덤함수. 1~25 사이의 수를 렌덤하게 꺼내려면 -----> rand()%25 + 1 (+1의 차이) 0~24 사이 -----> rand()%25 이렇게 사용을 합니다. 그렇다면 중복되지 않게, 중복되지 않게 하려면 어떻게 해야할까요?? 보통 쓰는 방법은 rand()를 통해 나온 값을 지금까지 나온 값과 비교하여 이미 있는 값이라면... 다시 돌리는 방식입니다. [순서도] 1. rand() 사용 2. 비교 -->(있을 경우) 다시 1로 -->(없을 경우) 다음 단계 3.1 완료될 경우 종류. 3.2 아니라면 저장 후 다시 1로 이와 같은 경우, 실제로 소스로 구현해보면 아시겠지만.............. 무한루프에 걸릴 때도 생깁니다. 그래서 다음 방법을 소개합니다. 1 to 50, 또..

마방진.

방진 or 마방진? 영어로 Magic Square. 요약 : 1에서 n2까지의 정수를 n행 n열의 정사각형 모양으로 나열하여 가로·세로·대각선의 합이 전부 같아지도록 한 것. 홀수방진 n=3인 경우, 즉 3방진의 경우를 보기로 들면 다음과 같다. ⑴ 맨 윗줄 중앙에 1을 쓴다. ⑵ 오른쪽 위의 대각선 방향으로 2, 3, 4,…를 차례로 쓴다. ⑶ 수를 쓴 자리가 위쪽으로 가버릴 때는 그 수를 쓸 자리의 열의 맨 아래 칸에 쓴다. ⑷ 수를 쓴 자리가 오른쪽으로 나가버릴 때는 그 수를 쓸 행의 왼쪽 끝 칸에 쓴다. ⑸ 오른쪽 위의 칸에 이미 숫자가 들어 있거나 오른쪽 위의 코너에 왔을 때는 그 수의 바로 아래 칸에 쓴다. 짝수방진 짝수방진을 만드는 일반적인 규칙은 없다. 여기서는 4방진을 만드는 방법을 소개..

백트랙킹(Backtracking) vs 욕심쟁이(Greedy)

백트랙킹 (Backtracking) : 뒤에서 추적한다? 라는 의미의 이 알고리즘은 간단하게 모든 경우의 수를 확인하여 최적의 해를 찾는 방법입니다. ( 보통 재귀함수를 이용해 구현하며, N-Queens, 외판원 문제 등이 있다.) 위 질문에 확실하게 답을 줄 수 있습니다. 하지만 일단 모든 경우의 수를 확인하는 데 걸리는 시간, 또한 재귀 호출을 이용하는 방법 등 많은 시간이 걸리는 방법입니다. 욕심쟁이, 탐욕적 (Greedy) : 이름 그 자체에 핵심을 많이 내포하고 있는데요. 선택한 시점에서의 가장 최고인 것 처럼 보이는 것을 선택하는 방법입니다. 최적의 해는 아니지만 근접한 해와 빠른 처리 시간의 장점을 가지고 있습니다. 하지만 ... [ 동전 교환 문제 ] 1, 5, 12, 50 단위의 동전을 ..

알고리즘.

Algorithm 정의 : 어떠한 문제를 풀기 위한 절차나 방법 : 알고리즘이란 특정 작업을 수행하는 명령어들의 유한 집합이다. 또한 모든 알고리즘은 다음과 같은 조건들을 만족시켜야 한다. 1. 입력 : 외부에서 제공되는 데이타가 0개 이상 있다. 2. 출력 : 적어도 한 가지 이상의 결과를 생성한다. 3. 명확성 : 각 명령은 명확하고 모호하지 않아야 한다. 4. 유한성 : 알고리즘의 명령대로 수행하면 어떤 경우에도 한정된 수의 단계 뒤에는 반드시 종료된다. 5. 유효성 : 원칙적으로 모든 명령들은 종이와 연필만으로 수해알 수 있도록 기본적인 것이어야 한다. ( 각 연산이 3.에서처럼 명확하기만 해서는 안 되고 반드시 실행 가능해야 한다. ) 뭐 단순히 우리과에 맞추면 어떠한 기능을 컴퓨터가 수행할 수..