마방진 배열 채우기 알고리즘
5행 5열의 2차원 배열에 대해 5개의 행, 5개의 열, 2개의 대각선에 각각 위치한 5개 원소들의 합이 모두 65로 일정하도록 1부터 25까지의 일련번호를 할당한 알고리즘을 마방진 알고리즘이라부른다.
1 2 3 4 5 밑에보다 작은값
6 7 8 9 10
-> 대각선방향으로 가야됨
1~25까지 배정하는데 13이 가운데 45도 위로 올라가게함.
알고리즘은 어떻게?
규칙 생각
1. 시작지점은 1행의 3열부터 시작, 45도 오른쪽 위로, 1~25까지.
행도 1~5 열도 1~5 이안에 들어가지 않는 것은 6열은 1열로 바꿔주는 규칙 0열이면 5열로
1. 1행 중간 열에 위치한 1행의 3열에 1을 할당
2. 위치에서 45도 대각선 방향으로 이동하기 위해 행번호는 1씩 감솜시키고 열번호는 1씩 증가시킨다.
이동하기 위해서, 행 번호는 1씩 감소시키고 열번호는 1씩 증가시킨다.
* 감소시킨 행 번호가 1행보다 작으면 마지막 행인 5행으로 재설정하며, 증가시킨 열번호가 마지막 열인 5열보다 크면 1열로 재설정하여 다음숫자를 할당
3. 배정하려는 위치에서 이미 숫자가 배정되어 있으면, 현재 위치보다 행 번호만을 1만큼 증가시켜서 행을 재설정한 후 다음숫자를 할당한다.
순서도
+ 배열 회전시키기
배열 A(5,5)를 시계방향으로 90도 회전시켜 B(5,5)생성하는 알고리즘
A(1,1) -> B(1,5)
A(1,2) -> B(2,5)
A(1,3) -> B(3,5)
규칙이 보인다. A는 열이 1,2,3... B는 행이 1,2,3...
석차구하기 알고리즘
응용 알고리즘 -자료구조
매출액과 석차를 순서대로 출력하는 알고리즘
첫번째 대리점부터 마지막 25번째 대리점까지 각 대리점 i 에 대해 매출액 A(i)을 일볅하고 현재까지는 전체에서 1등이라고 A(i)를 초기화 한다
대리점 i의 매출액 A(i)를 전체 25개 대리점 매출액 A(i)과 25번 비교하여 자신의 매출액보다 큰 경우에만 자신의 석차 R(i)의 값을 1씩 증가시켜 석차를 하나씩 낮추도록 한다.
1, 동점자를 자신보다 상위자로 보지 않고 석차를 낮추는 방식
2. 동점자를 자신보다 상위자로 보아 석차를 낮추는 방식
+반복기소 사용하여 간단하게 표현
선택정렬 알고리즘
학생 100명의 영어 성적을 오름차순으로 선택정렬하는 알고리즘
(오름차순, 내림차순)
1. 전체 데이터 n개 가장 작은수 선택해서 왼쪽 1번째 자리에 오도록한다.
2. 가장 왼쪽 데이터 1개를 제외한 데이터 n-1개를 빅하여 그 가장 작은 수를 선태갛여 왼쪽에서 2번쨰 자리에 오도록한다.
3. 가장 왼쪽 데이터 2개를 제외한 데이터 n-2개를 빅하여 그 가장 작은 수를 선태갛여 왼쪽에서 3번째 자리에 오도록 한다.
4. 더이상 비교할 필요가 없을 때 까지 이런 과정을 반복한다
-예를들어, 5개의 영어 점수가 주어졌을떄 오름차순
순서도
버블정렬 알고리즘
학생 100명의 영어성적을 오름차순으로 버블정렬하는 알고리즘
순서도
+ 버블정렬에서 중첩 반복 구조와 스와핑 서브루틴을 활용
삽입정렬 알고리즘
학생 100명의 성적 오름차순으로 삽입정렬하는 알고리즘
오름차순 삽입정렬
- 삽입 정렬은 알고리즘이 진행되는 동안 1정렬이 이미 이루어진 데이터그룹 a와 2정렬이 아직 이루어지지 않은 데이터 그룹 b등 총 2개의 그룹을 나누어 진행한다.
- 정렬이 아직 이루어지지 않은 그룹 b에 한개의 데이터 꺼내 정령이 이미 이루어진 그룹 a의 적절한 위치에 삽입하여 진행한다. 이것 때문에 삽입 정렬이다.
- 그룹 b에서 그룹 a로 이동하는 데이터를 키라고 부른다. 키는 그룹 b에 남아있는 데이터들 중에 가장 좌측 데이ㅣ터를 뽑는다. 뽑은 키가 존재하지 않으면 삽입정렬은 종료된다.
병렬정렬 알고리즘
오름차순으로 정렬된 배열 A(M)과 내림차순으로 정렬된 배열 B(N)을 병합정렬이라 하여 오름차눗ㄴ의 배열 C(M+N)을 생성하는 알고리즘을 제시해라. 단 배열 A(M)과 배열 B(N)에는 900000이하의 정수가 저장되어 있으며 모든 배열의 첨자는 1부터 시작
문제 문제 공략
- A(M)은 오름차순으로 이미 정렬되어 있고 B(N)은 내림차순으로 이미 정렬되어 있으므로, 각 배열에서 가장 작은 원소인 A(1)과 B(N)부터 병합정렬 실시
퀵정렬 알고리즘
학생 100명 성적 오름차순으로 퀵정렬하는 알고리즘
정렬중 가장 빠른시간안에 할수있는 퀵정렬, recursion을 사용한다. 자기자신을 부르는
pibot number 축이 퀵정렬에서 중요한 용어이다. 어떤 숫자들을 정렬했는데
순서도
이분검색과 순차검색
이분검색 bs 순차검색 ss
제일 가운데랑 찾고자 하는 숫자랑비교, 같지않으면 왼쪽이나 오른쪽에 있음. 다시 서치
이분검색은 배열 변수 e에 대해 데이터 k가 있는 위치를 찾아주는 알고리즘
