윈플


흔히들 사용하는 랜덤함수.

1~25 사이의 수를 렌덤하게 꺼내려면            ----->    rand()%25 + 1   (+1의 차이)
0~24 사이                                                ----->    rand()%25

이렇게 사용을 합니다.

그렇다면 중복되지 않게, 중복되지 않게 하려면 어떻게 해야할까요??


보통 쓰는 방법은 rand()를 통해 나온 값을 지금까지 나온 값과 비교하여 이미 있는 값이라면... 다시 돌리는 방식입니다.

[순서도] 

1. rand() 사용
2. 비교              
-->(있을 경우) 다시 1로 
-->(없을 경우) 다음 단계
3.1 완료될 경우 종류.
3.2 아니라면 저장 후 다시 1로



이와 같은 경우, 실제로 소스로 구현해보면 아시겠지만.............. 무한루프에 걸릴 때도 생깁니다.


그래서 다음 방법을 소개합니다.
1 to 50, 또는 퍼즐 게임와 같이 중복되지 않게 배열에 집어넣거나 순서를 섞어야 되는 경우! 에 편하실겁니다.


순서대로 보시면..


(그림이 짤린 것 같지만 짤린게 아닙니다.)




[필요한 것들]
같은 크기의 배열.
배열의 크기를 저장하는 변수.
그리고 swap에 필요한 변수.


[C++ 소스]

(+) "greatest"님의 지적사항입니다. 
      그림으로 설명이 된 부분으로 코드가 매칭되지 않았습니다. 추후에 수정하겠습니다(__)

int main()
{
// 배열로 초기값(정렬 안 된 상태)
int temp_arr[25]={0,}, temp, index_size=24, n;
int i;

// 임시 배열 초기화
for(i=0; i<25; i++)
{
temp_arr[i] = i+1;
}
// rand()사용 중복되지 않게 만들기
for(i=0; i<25; i++)
{
n = rand()%(index_size+1);

// 마지막 index와 나온 index swap하기
temp = temp_arr[n];
temp_arr[n] = temp_arr[index_size];
temp_arr[index_size] = temp;
}
cout << "<rand()사용, 중복되지 않게 배열 초기화>" << endl;
// 결과 확인
for(i=0; i<25; i++)
{
cout << temp_arr[i] << " ";
}
cout << endl;

return 0;
}

혹시 잘못된 부분. 궁금점. 질문은 댓글로 피드백바랍니다.



Comment +5

  • 상세한 설명과 코드까지! 좋네요~^^
    그런데 0~25사이와 1~25사이라는 것이 헷갈릴 수 있을 것 같습니다 ㅎ
    '0~24사이, 1~25사이' 로 표현하는 것은 어떨까 생각해 봅니다 ㅎ

  • 와아 2012.03.27 07:57

    좋은글 감사합니다 ㅎㅎ

  • greatest 2016.11.24 02:38

    그림으로 친절하게 설명해 주셔서 감사합니다.

    하지만 그림으로 설명한 과정과 하단의 코드 동작이 일치하지 않다고 생각하여 댓글을 남깁니다.

    코드의 두 번째 for문에서,
    index_size가 1만큼 감소되지 않으니 '난수로 생성된 위치의 요소'는 항상 '제일 마지막 요소'와 swap 되겠네요.

    그림과 같이 코드가 동작하려면, 두 번째 for문의 마지막 줄에 index_size--;를 추가해야 하는 것 아닌가요?

    • 댓글확인이 늦었습니다 ㅠ
      그렇네요; 오래전에 작성한거라 저도 왜 이렇게 했는지는 기억이 안나는데 그림과 코드가 매칭이 되지 않네요.
      지적감사드립니다!

방진 or 마방진?
영어로 Magic Square.
 

요약
1에서 n2까지의 정수를 n행 n열의 정사각형 모양으로 나열하여 가로·세로·대각선의 합이 전부 같아지도록 한 것. 

 
 홀수방진
n=3인 경우, 즉 3방진의 경우를 보기로 들면 다음과 같다. ⑴ 맨 윗줄 중앙에 1을 쓴다. ⑵ 오른쪽 위의 대각선 방향으로 2, 3, 4,…를 차례로 쓴다. ⑶ 수를 쓴 자리가 위쪽으로 가버릴 때는 그 수를 쓸 자리의 열의 맨 아래 칸에 쓴다. ⑷ 수를 쓴 자리가 오른쪽으로 나가버릴 때는 그 수를 쓸 행의 왼쪽 끝 칸에 쓴다. ⑸ 오른쪽 위의 칸에 이미 숫자가 들어 있거나 오른쪽 위의 코너에 왔을 때는 그 수의 바로 아래 칸에 쓴다.

 짝수방진
짝수방진을 만드는 일반적인 규칙은 없다. 여기서는 4방진을 만드는 방법을 소개한다. ⑴ 먼저와 같이 1~16까지를 차례로 써넣는다. ⑵ 대각선을 그어 대각선 위에 있는 수를 ∥표를 중심으로 하여 서로 점대칭의 위치에 있는 것끼리 바꾸어 놓는다.   



 
[출처 네이버 백과사전]







뿌리깊은 나무에서는 세종(이도)께서 빈 참합을 보고 풀이 법을 제시하였다는데... 

알고보면 간단한 마방진 풀이법.

홀수방진.

1.  n방진에 +1칸을 추가
2.  가운데부터 순서대로 방향은 상관없이 나열.
3.  칸 이외의 칸에 있는 숫자를 반대쪽으로 넣으면 끝.


or




짝수방진.

1.  n방진에 차례대로 나열.
2.  대각선으로 뒤바꾸면 끝.






뿌리깊은 나무라는 드라마를 통해 많은 사람들이 방진과 한글의 위대함에 알게 된 것 같습니다.



마방진 알고리즘.

1.  만들 n방진의 n 입력.

2.  if( n%2 ) 짝수 인지 홀수인지 따라 다른 방법

2.1 홀수
(1)  n배열의 + 2 크기로 생성
(2)  2n-1 , 즉 1,3,5 ... 순으로 시작지점 달리 나열
(3)  원래 칸 이외의 수 체워넣기.

2.2 짝수 
(1)  순서대로 숫자 체우기
(2)  대각선으로 뒤바꾸기
(3)  반대 대각선 뒤바꾸기 
 
3.  끝. 

Comment +0

백트랙킹 (Backtracking)
: 뒤에서 추적한다? 라는 의미의 이 알고리즘은 간단하게 모든 경우의 수를 확인하여 최적의 해를 찾는 방법입니다.

( 보통 재귀함수를 이용해 구현하며, N-Queens, 외판원 문제 등이 있다.)

 
  


위 질문에 확실하게 답을 줄 수 있습니다. 

하지만 일단 모든 경우의 수를 확인하는 데 걸리는 시간, 또한 재귀 호출을 이용하는 방법 등 많은 시간이 걸리는 방법입니다.





욕심쟁이, 탐욕적 (Greedy)
:  이름 그 자체에 핵심을 많이 내포하고 있는데요. 선택한 시점에서의 가장 최고인 것 처럼 보이는 것을 선택하는 방법입니다.

최적의 해는 아니지만 근접한 해와 빠른 처리 시간의 장점을 가지고 있습니다.



 
하지만 ...

[ 동전 교환 문제 ] 
1, 5, 12, 50 단위의 동전을 최소 갯수 조합으로 거스름돈을 돌려주기. ( 단위는 외국 동전이라 그럼 -_- )

거스름돈 : 15 일 경우.

그리디 알고리즘의 경우 
[ 12 :  1개  , 1   :  3개 ] 가 나오게 된다.

하지만 정답은 [ 5 : 3개 ] 

( 이렇게 그 상황에서 최선을 고르지만 그 답은 최적해가 아닐 수가 있습니다. )

 



구현과 이해는 사람마다 다를 수 있습니다.

Comment +0

selection sort

 

bubble sort

 

merge sort

 

quick sort

 

insertion sort

 

topological sort

 

sequential search

 

interpolation search

 

binary search

 

DFS


Gaussian Elimination
 

BFS

 

LU Decomposition

 

Horner's Rule


binary exponential

 

 

Brute force

 

Divide and conquer

 

Decrease and conquer
 

decrease by a constant
 

decrease by a constant factor
 

virable size decrease

 

Transform and conquer

 

Representation change
 

convex-hull(quick-hull)

 

closet - pair

 

TSP

 

knapsack problem

 

assignment problem

 

a' la Russe

 

fake coin problem

 

josephus problem

 

selection problem(quick sort의 반쪽)

 

Nim game

Comment +0

Algorithm 

정의
: 어떠한 문제를 풀기 위한 절차나 방법
: 알고리즘이란 특정 작업을 수행하는 명령어들의 유한 집합이다. 또한 모든 알고리즘은 다음과 같은 조건들을 만족시켜야 한다. 

1. 입력 : 외부에서 제공되는 데이타가 0개 이상 있다.
2. 출력 : 적어도 한 가지 이상의 결과를 생성한다.
3. 명확성 : 각 명령은 명확하고 모호하지 않아야 한다.
4. 유한성 : 알고리즘의 명령대로 수행하면 어떤 경우에도 한정된 수의 단계 뒤에는 반드시 종료된다.
5. 유효성 : 원칙적으로 모든 명령들은 종이와 연필만으로 수해알 수 있도록 기본적인 것이어야 한다.
   ( 각 연산이 3.에서처럼 명확하기만 해서는 안 되고 반드시 실행 가능해야 한다. )



뭐 단순히 우리과에 맞추면 
어떠한 기능을 컴퓨터가 수행할 수 있도록, 명령어의 순서를 정해주는 정도??
요즘은 컴퓨터의 성능이 워낙 좋아서... 

작은 프로그램 같은 경우엔 중요치 않다고 보지만
(예를 들면 빛이 지구를 1바뀌 돌고 오던  7바퀴를 돌고 오던 내가 느끼는 속도는 같은 것과 같다.)

위 예는 너무 극단적인 경우일 뿐이고 실상은 그렇지 않기에 알고리즘은 중요하다.


Comment +0