실기 알고리즘 풀이법 정리

<수열>

1. 번갈아 더하기/빼기

1-2+3-4+5-6+ ... -98+99

*3가지 풀이법

1) SW 변수 이용(+1, -1, +1, -1로 변화)

2) +홀수(i) -짝수(i) 반복 - p33

3) 양수 합(홀수) + 음수 합(짝수) - p53

2. 피보나치 수열(C = A + B)

1+1+2+3+5+8+13+ ... +20항 (P48)

A, B의 위치 한 칸씩 이동(A=B, B=C)

*초기값 구하기

CNT 19 들어가면 20항까지의 합 => CNT 2 들어가면 3항까지 합

A	B	C	CNT	합	비고
1	1	2	X	4
1	2	3	X+1	7
2	3	5	X+2	12	5항까지의 합이므로 X=3 But, 작업 후 값이므로 CNT 초기값=2

<수학>

1. 소수 X 구하기

1) 2부터 X-1까지 나눠 보기 => 안 나눠지면 소수

2) 처음으로 나눠떨어졌을 때 IF(나누는 수=자신) => 그 수는 소수

3) 2부터 SQR(X)까지 나눠보기 => 안 나눠지면 소수

2. 소수의 개수 구하기(p65)

*소수(2, 3, 5, 7 ...)의 배수는 소수가 아님

2의 배수 자리 =>0

3의 배수 자리 =>0

배열값이 0이 아닌 것만 <> 통과시키면

2, 3, 5, 7 ..만 소수로 판정됨

3. 약수 구하기(p110)

1~X까지 나누어 NMG=0이 되는 것

(주의!) 1, X도 약수로 포함시킨다.

4. 최대 공약수, 최소 공배수 구하기

BIG	SMALL	NMG
15	12	3
12	3	0

BIG=SMALL, SMALL=NMG로 대체

최대공약수: NMG=0일 때 나눠주는 값(SMALL)

최소공배수: 두 숫자 서로 곱한 수를 최대공약수로 나눈 수

5. 소인수 분해(p71, p112)

1) X를 2 ~ SQR(X)로 나눈다.

2) 나머지 0이면 '소인수'

3) X = X/소인수(=MOK)

=> MOK이 1일 때(소인수가 자기자신) 종료

6. 10진수 => 2진수(p73)

2 | 6

2 | 3 ..... 0

2 | 1 ..... 1

    0 ..... 1

6 => 110(2)

피제수	MOK	NMG
6	3	0
3	1	1
1	0	1

피제수=MOK

MOK이 0일 때 종료

7. 10진수 => n진수(p75)

ex) 19를 2진수로

피제수	32	16	8	4	2	1
몫	32>19이므로 STOP	1	0	0	1	1

1) 19와 2의 제곱들을 비교

2) 19보다 큰 수 구한다(32)

3) 19에서 32보다 한 제곱 낮은 수을 뺀다(19-16)

4) 19 = 3(19를 3이 대체)

5) 똑같이 반복

8. 최대값, 최소값(굴러 들어온 돌로 박힌 돌 밀어내기)

<최대값의 경우>

초기 비교값(무지 작은 수로 설정=> 어떤 수가 와도 최대값이 되게끔)

최대값 vs 1st

1st vs 2nd

2nd vs 3rd

*7과 가장 가까운 수: |X-7|의 최소값

9. 2의 보수 구하기(p90)

A: 기본 배열

B1: 1의 보수 배열

B2: 2의 보수 배열

C: 자리올림수

1) 1의 보수 구한 후 +1

ㄱ. B1(i) = 1 - A(i)

ㄴ. B2(i) = B1(i) +C 

ㄷ. B2(i) = B2(i)*MOD(2)

*B2가 2이면 0, 1이면 1 나오게

ㄹ. C= B1(i) * C

B1(i)=0인 시점에서 C는 0가 됨('다음 항에서' 더 이상 더해주지 않음)

2) 1이 나올 때까지 그냥 쓰고, 다음 자리부터는 반전해서 쓰기

i	1	2	3	4	5
이진수	0	1	1	0	0
2의 보수	1	0	1	0	0

i:5~3

B2(i) = A(i)

i:2~1

B2(i) = 1 - A(i)

<정렬>

Q. 다음 배열을 오름차순으로 정렬하라.

5

4

7

3

6

<D(i)와 D(j)값을 맞바꾸는 법>

K=D(i)

D(i)=D(j)

D(j)=K

1. 선택 정렬(p126) -앞부터 정렬됨

i: 자리 정할 값

j: 비교할 값이라면,

i	1	2	3	4	5	j=i+1, 5, 1
1						2~5
2						3~5
3						4~5
4						5~5

i번째 값을 i+1 ~ 5까지 모두 비교

비교 대상이 하나씩 줄어든다.

2. 버블 정렬 - 뒤부터 정렬됨

i	1	2	3	4	5	반복횟수
1						i-1
2						i-2
3						i-3
4						i-4

i번째 값과 i+1번째 값을 비교

(1, 2), (2,3), (3,4), (4,5)

(1, 2), (2,3), (3,4)

(1, 2), (2,3)

(1, 2)

* 정렬이 이미 끝나면 STOP하는 알고리즘(p134)

교환 일어나면 SW=1

안 일어나면 SW=0

=> SW=0이면 STOP

*번갈아 정렬(p137)

LEFT, RIGHT를 변수로

비교할 영역이 L/R 번갈아가며 줄어듬

---> (R-1)

<--- (L-1)

---> (R-1)

<--- (L-1)

3. 삽입 정렬(한국 아줌마 영화관 좌석 앉기)(p140)

i	1	2	3	4	5	1 ~ i
1		KEY				1~1
2			KEY			1~2
3				KEY		1~3
4					KEY	1~4

KEY 값을 꺼내 1~i번째와 비교

적당한 자리 찾으면 KEY값을 넣어줌

4. 석차 구하기

점수	70	80	60	90	70
석차	1	1	1	1	1
증가분	+1 +1	+1	생략	생략	생략

1) 석차를 모두 1로 초기화

2) 나보다 큰 놈 발견할 때마다 석차+1을 해줌

5. 이분 검색(그물망 좁히기) (P149)

L(1) MID(5) H(10)

MID=int(L+H/2)

1) 찾는 값(J) > M

M+1 ~ H에서 수색

*L=M+1(새로운 L)

2) 찾는 값 < M

L ~ M-1에서 수색

*H=M-1(새로운 H)

6. 병합(p167)

*0은 종료 표시

A(10)	1	3	5	0
B(10)	2	3	8	9	0
C(10)	1	2	3	5	8	9	0

1) A(i)와 B(j) 비교하여 작은 쪽을 C에 넣는다.

a. A(i) > B(j)인 경우

J=J+1

C(k)=B(J)

b. A(i) <= B(j)인 경우

i=i+1

c(k)=A(i)

2) A가 먼저 끝나면 B,

   B가 먼저 끝나면 A 넣기 시작.

<배열>

#푸는 요령

1) 순서대로 다 찍어본다. (1,1) (1,2) (1,3)

2) 단순하게 표현 1, 1~3

3) 규칙성 찾기

1. 달팽이 만들기(or 소용돌이 모양)

1	2	3	4	5
16	17	18	19	6
15	24	25	20	7
14	23	22	21	8
13	12	11	10	9

단순 표현	증감	반복횟수
1, 1~5	행고정, 열증가	5
2~5, 5	행증가, 열고정	4
5, 4~1	행고정, 열감소	4
4~2, 1	행감소, 열고정	3
2, 2~4	행고정, 열증가	3
3~4, 4	행증가, 열고정	2
4, 3~2	행고정, 열감소	2
		1
		1

2. 대각선으로 채우기(대각선으로 그어보면 규칙이 보임)

1	2	4	7	11
3	5	8	12	16
6	9	13	17	20
10	14	18	21	23
15	19	22	24	25

규칙. 행과 열의 합 i: 2, 10, 1

3. 마방진

17	24	1	8	15
23	5	7	14	16
4	6	13	20	22
10	12	19	21	3
11	18	25	2	9

<규칙>

1) 시작점은 (1, M)

2) 대각선(右上)으로 이동(행-1, 열+1)

단, 행 < 1이면 행=5가 됨

열 > 5이면 열=1

3) 채울 숫자가 5의 배수 +1이면 위치는 행만 +1

4. 행렬 변환

<FROM>

1	2	3	4	5
6	7	8	9	10
11	12	13	14	15

<TO>

1	2	3
4	5	6
7	8	9
10	11	12
13	14	15

한 열(J)가 다 차면

i = i+1

j = 1로 초기화

<실무 응용>

1. 화폐 매수 계산

1만원, 5천원, 1천원, 500원, 100으로 나눠 각각의 몫을 구한다.

SW(화폐 단위 변경 스위치): 1/2, 1/5, 1/2, 1/5로 변화

제수=NMG로 대체

2. 동별, 나이별 통계

동	0~9	10~19	''''''	60이상	합
1
2
10
합

ROW = 동

COL = INT(나이/10) +1

ex) 11살 =>2, 56살 => 6

*88의 경우 9에 들어가지 않도록

60 이상은 모두 60세로 초기화

2. 역순으로 숫자 만들기

<FROM>

1

2

3

4

5

<TO>

5

4

3

2

1

1) 첫번째 풀이법(첫, 끝 교환)

1 <-> 5

2 <-> 4

3이면 종료

D(i) <-> D(J)

D(i+1) <-> D(J-1)

D(i+2) <-> D(J-2)

D(M)일 때 종료

2) 2번째 풀이법

자릿수-1 만큼 제곱해서 더하기

1 + 2*10 + 3*10^2 + 4*10^3 + 5*10^4