[D-2] 정보처리기능사 실기 알고리즘 유형 총정리!

정보처리기능사 실기시험 D-2

알고리즘 유형 총정리!

Here we go again! :D

Dat smiley blue pony tho :)

유형1. 교행수열의 합 알고리즘

- 문제 : 교행 + - 가 번갈아서 일어나는것. 

- 해법 : 1과 -1을 오가는 FLAG 혹은 SW를 세움.

혹은 홀짝 판별 (MOD(N,2)) 를 통해서 필요한 연산을하게 함.

유형2. 분수수열의 합 알고리즘

- 문제 : 분모 분자가 1씩 증가하는 수열의 합을 구하라는 문제.

- 해법 : 어렵게 생각할거 없고 계산은 내가 하는게 아니므로

그냥 조건에 맞게 계속 누적시키면 된다.

유형3. 증가값이 증가하는 수열의 합 알고리즘

- 문제 : 1+2+4+7+11+22+...

- 해법 : 증가값이라는 변수 설정하고 ㄱㄱ

유형4. 팩토리얼 수열의 합 알고리즘

- 문제 : 1!+2!+3!+4!+...

- 해법 : 2! 과 3! 의 차이는 3을 곱해줬느냐 안곱해줬느냐 밖에없다.

증가값을 정하고 이를 계속 곱해주면서 다음항을 생성해 누적한다.

유형5. 피보나치 수열 알고리즘

- 문제 : 1+1+2+3+5+8+13+...

- 해법 : A,B,C 놓고 C = A+B 이후 A=B, B=C로 한칸씩 밀어줘서 구현.

* 루프아웃 통제변수-인덱스 구하는 꿀팁

- "끝 인덱스, 마지막 연산"이 결과에 포함되게 하려면 몇을 넣을지 생각한다.

만약 조건검사가 연산전에 일어나면 일반적으로 해당인덱스를 초과해야한다.

- 디버깅한다.

All these years... she has been a good friend of twi. awww, sweet pony friendship it is :3

유형6. 소수판별 알고리즘

- 문제 : 약수가 자기자신과 1밖에 없는 수인 소수를 골라내는 유형

- 해법 : 제수를 (2)부터 시작해서 (대상수-1)까지 증가시키며 MOD값이 0이 되는지 알아보거나

나누어서 떨어지는 수가 있는지 조사한다. 하나라도 있으면 탈락! 제수가 자기자신이 될때까지

무사히 통과했다면 소수!

* 약수 구하는 알고리즘?

- 나누어 떨어지면 약수이다. = 나머지가 0 이다.

유형7. 소수의 개수 구하기 알고리즘

- 문제 : 배열에 저장된 수들중 소수의 개수를 구하는 문제

- 해법 : MOD 없이 배수를 이용해서 구하는 방법이 있는데, 그냥 2부터 시작해서 배열에서 2를 제외한 2의배수를 전부 0으로 처리하고 3이면 배열에서 3을 제외한 3의 배수를 전부 0으로 만드는 방식으로 미리 소수를 거르는? 제거하고 0이 아니면 개수에 +1해서 구해낸다.

유형8. 최대공약수, 최소공배수 알고리즘

- 문제 : 입력받은 두 수의 최대공약소와 최소공배수를 구하시오.

- 해법 : 최대공약수는 큰수를 작은수로 나눠서 나누어 떨어지면 작은수가 최대공약수가 된다. 나누어 떨어지지않으면 나머지를 작은수를 큰수로 나머지를 작은수로 놓고 나누어떨어질때까지 이를 반복한다. 

최소공배수는 두수를 합한걸 최대공약수로 나눠주면 나온다.

유형9. 소인수 분해하기 알고리즘

- 문제 : 소인수를 구해서 출력하시오.

- 해법 : 소인수분해란 어떤수를 소수로만 표현하는것으로 이를 구현하려면, 제수를 2부터 시작해서 (대상수의 제곱근)까지 +1씩 하며 검사시킨다. 이때 나누어떨어지는 수를 만나면 그 수는 대상수의 소인수로

등록하고 몫을 대상수로 갱신하고 루프돌리면 된다.

유형10. 진법변환 알고리즘

-문제 : 10진수를 2진수로 또는 2진수를 10진수로..

- 해법 : 10진 -> 2진 : 2로 나눠서 나머지쭉 구하고 역순으로 출력한다.

2진 -> 10진 : (자리의 수) x (2^N-1) 을 누적시켜 합을 구한다. 이때 N은 자릿수이다.

(자릿수 같은건 특수함수로 구하게 해주거나 함수 인덱스 쓰면됨.)

* 음의 이진수의 변환

- 최상위비트를 부호로 사용해서 1이면 음수 0이면 양수 이런식인데,

음의 이진수를 십진수변환하는 방법은 아래와 같음.

1) 10진변환을 함

2) [2진 최대 십진수 - 변환한 수] 해줌.

3) * -1 해서 음수로 만들어줌.

유형11. 최대, 최소 알고리즘

- 문제 : 수들을 입력받고 최대값 또는 최소값을 구하시오.

- 해법 : MAX MIN 변수를 설정하고 반복문을 통해

전수 비교하며 크면 MAX 작으면 MIN에 넣어준다.

유형12. 배수 알고리즘

- 문제 : 일정 수범위에서 N의 배수를 전부 구하시오.

- 해법 : N의 배수이다 = N으로 나누어 떨어진다. 성질을 이용한다.

아니면 계속 N을 더해가면서 직접 배수 구해도 나쁘지않을듯.

유형13. 가까운 수 알고리즘

- 문제 : 여러 수를 입력받고 N과 가장 가까운 수를 구하시오.

- 해법 : 거리차를 구해서 최소값을 갱신하는 수를 찾아낸다!

유형14. 보수 알고리즘

- 문제 : 1의 보수 2의 보수를 구하시오

- 해법 : 1의 보수는 1 - A(N)을 통해서 구함.

2의 보수는 자리올림수 C = 1로 잡고 "1의 보수" 배열의 맨뒤부터 +C해줌.

더해진 원소는 MOD2를 해줘서 자리올림이후 0으로 비는것을 구현함.

이후 C는 해당자리수 x C 를 통해서 올릴지 내릴지 결정해줌.

* 2의 보수 쉽게 구하는 방법?

- 맨뒤(오른쪽)에서부터 앞(왼쪽)으로 진행하며 "1"이 처음 나온

시점이후부터 1의 보수를 취해주면 2의보수가 간단히 나온다.

유형15. 그레이코드 알고리즘

- 문제 : 그레이코드로 변환하거나 2진수로 변환하시오.

- 해법 :  맨앞 첫비트를 기준으로 1이면 그레이코드라서 이진수변환하고

0이면 이진수라 그레이코드변환시키고 하는 방식.

그레이코드 -> 이진수 : 맨앞자리 내리고 내린수와 XOR해서 내리기

이진수 -> 그레이코드 : 맨앞자리 내리고 이웃하는수와 XOR해서 내리기

유형16. 완전수 알고리즘

- 문제 : 수 범위에서 완전수를 모두구하시오.

- 해법 : 완전수란 자신을 제외한 약수의 총합이 자신이 나오는 수를 의미한다. 통제변수를 자신/2까지의

반복문을 이용해서 약수를 구해서 모두 누적시키고 해당 누적값 = 대상수를 만족하면 대상수는 완전수라고 갱신하면 된다.

* 약수의 성질

- 자신을 제외한 약수의 범위는 자신/2까지 이다.

My bonny pony friends ♥

유형16. 정렬 알고리즘

- 문제 : 자료를 입력받고 오름차순 정렬을 하시오.

- 해법 : 대소 비교해서 작으면 앞으로 이동시키는걸 구현해야하는데

이는, "임시저장변수"를 이용해서 "교환"한다. 

이웃끼리끼리 비교해서 교환하는건 버블정렬, 멀리뛰기점프(?)하듯 하는건 선택정렬이라고 한다.

유형17. 석차 알고리즘

- 문제 : 점수 배열을 주고 석차(등수) 구하기

- 해법 : 모두가 1등이 될수있다고 셋팅하고 비교후 패배시(작으면) +1해서 뒷등수로 밀리게한다.

유형18. 이분검색 알고리즘

- 문제 : 주워진 배열에서 특정 수 찾는 알고리즘

- 해법 : 중간수찾아서 중간수보다 큰지 작은지 물어보며 "범위를 좁혀가며" 해당 자료를 찾는 방식.

유형19. 병합 알고리즘

- 문제 : 두 오름차순으로 정리된 배열을 병합해서 또 다른 오름차순 배열을 만드시오.

- 해법 : 비교후 작으면 등록, 작은쪽 인덱스 증가후 재비교후 등록. 만약 한쪽이 최대치 도달시,

남은쪽 전수등록.

twi will never give up on any friends!

유형20. 배열 알고리즘

- TIP1 : 이중반복문

- TIP2 : 진행방향 파악

- TIP3 : 행인덱스i, 열인덱스J 그리고 들어가는 수의 관계 파악.

- TIP4 : "빈 칸"의 구현은 반복문의 통제변수에서 해당 인덱스 까지 진행되지않게 함으로 구현할 수 있다.

- TIP4 : 대칭인 경우 중간행까지 반복문 중간행 이후 반복문 둘로나누어 알고리즘을 짠다.

유형21. 달팽이 배열 알고리즘

- 문제 : 달팽이 모양으로 진행되는 배열 알고리즘

- 해법 : 행의 진행이 끝날때마다 최대 이동 칸수가 -1씩 깎이며

행이후 열을 끝내면 방향변수를 -1 을 곱해줘서 바꿔줘야 한다.

유형22. 밀리는 배열 알고리즘

- 문제 : 행이 바뀔때마다 왼쪽으로 밀리는 형태의 배열의 알고리즘

- 해법 : 시작 인덱스를 행과 일치시키고 최대치에 도달시 다시시작하게해서 밀리는것 처럼 보이게함.

Aw twi, so cute :3

유형23. 화폐 매수 계산

- 문제 : 입력받은 금액을 50000, 10000, 5000, 1000 ... 단위로 표시하시오.

- 해법 : 스위치 변수를 이용해서 나누기5, 나누기2를 교차반복한다.

유형24. 큰 수 더하기 알고리즘

- 문제 : 정수범위를 넘어서는 큰 금액의 수를 오차없이 계산하려고한다.

- 해법 : 배열에 저장된 각 자리수를 더하고 나누기10을 해서 몫(올림수)와 나머지를 구한다.

(주의점은 올림수 구할때는 맨뒤배열인덱스부터 시작하고 더한결과가 있을 배열은 일반 배열보다 크기가

+2크다는 것이다.)

유형25. 부서별 통계, 표작성 알고리즘

- 해법 : 문제에서 제시한 <출력 형식>에 완벽히 기인해서 풀면 된다.

유형26. 구구단 알고리즘

- 문제 : 구구단을 출력하는 알고리즘은?

- 해법 : 변수 2개 사용 "단" 변수, "곱해지는 수" 변수를 적절히 이용한다.

유형27. 변환 알고리즘

- 문제 : 수를 받아서 문자열 배열로 변환하시오. 4자리마다 "," 로 구분하시오.

- 해법 : "%10" 연산 즉 10으로 나눈 나머지를 구하는 연산으로 자릿수를 구해서 배열에 저장하고

/10 을해줌으로 수를 줄여가며 반복한다.

유형28. 주차요금 알고리즘

- 해법 : 남은 시간에서 "단위시간"을 빼주면서 루프 돌리며 요금을 추가하고

단위시간이 마이너스가 되면 루프에서 나오게 한다.

유형29. 항공기 운항일 알고리즘

  - 해법 : 항공기 출발일은 도착일 + 대기일이다. 7초과시 MOD7 연산을

해주면 일주일 범위안으로 어떻게든 다시 집어넣을 수 있다.