[탑기공] 알고리즘(Algorithm)

 

---

멘토링

 

기출 문제를 분석하다 보니 생각 외로 알고리즘 관련 문제들이 많네요.
출제된 기출 문제 토픽에 대해서 
최소한 개념 정도는 꼭 한 번쯤은 정리하고 넘어가시길 권고합니다.

 

알고리즘 관련 주요 키워드

 

백트래킹(Backtracking), 분할정복, 탐욕법, 동적계획법
선택 정렬, 삽입 정렬, 퀵 정렬, 버블 정렬
시간 복잡도, 공간 복잡도
최소 신장 트리, 크루스컬 알고리즘, 프림 알고리즘
최단 경로 알고리즘(다익스트라, 벨만-포드, 플로이드 와샬, A* 알고리즘)
그리디(Greedy) 알고리즘
재귀 호출, B 트리 / B+ 트리

 

알고리즘의 개념

 

주어진 문제를 해결하기 위한 일련의 처리 절차를 단계적으로 기술한 것으로
문제 해결 방법을 추상화하여 단계적 절차를 논리적으로 기술해 놓은 명세서

 

알고리즘의 목표

 

단순히 원하는 결과를 얻을 수 있는 알고리즘이 아닌, 
처리시간이나 기억장소 사용 측면에서 효율적인 알고리즘을 개발하는 것
→ 시간 복잡도, 공간 복잡도 최적화

 

알고리즘의 조건

[두음] 입출명유효

 

입력, 출력, 명확성, 유한성, 효과성

 

출처 : 탑싯 에센스

 

좋은 알고리즘의 특징

 

정밀성, 유일성, 타당성, 입력, 출력, 유한성, 일반성

 

알고리즘 분석 기준

 

[두음] 정작기최단

정확성, 작업량, 기억 장소 사용량, 최적성, 단순성

 

정확성 - 타당한 입력에 대해서 유한 시간 내에 올바른 결과를 산출하는가를 판단
작업량 - 알고리즘을 수행하는데 걸리는 수행 횟수
기억 장소 사용량 - 알고리즘이 수행되는 동안 데이터와 정보 등을 저장하기 위해 필요한 컴퓨터 메모리의 용량
최적성 - 알고리즘을 적용할 시스템의 사용 환경(수행량, 메모리 사용량 등)을 고려할 때 

  그 알고리즘보다 더 적합한 알고리즘이 없다는 것
단순성 - 알고리즘 표현이 얼마나 이해하기 쉽게 명확하게 작성되었는지를 의미

 

알고리즘 성능 분석

알고리즘의 성능 분석은 실행에 필요한 공간 측면에서 분석하는 공간 복잡도와
실행에 소요되는 시간 측면에서 분석하는 시간 복잡도를 추정하여 일반적인 평가를 한다.

 

공간 복잡도 = 고정 공간량 + 가변 공간량

 

시간 복잡도 = 컴파일 시간 + 실행 시간

알고리즘 간의 비교 시에는 주로 실행 시간을 사용하며
시간 복잡도로 나타낼 빅-오(Big Oh) 표기법을 사용하여 O(n)로 표기하여
알고리즘에 따라 logn, n, nlogn, n^2, n^3, 2^n 등의 실행 시간 함수가 있다.

 

출처: 탑싯 에센스

 

기출 문제

 

(응용 122-1-9)
백트래킹(Backtracking), 분할정복, 탐욕법, 동적계획법의 개념 및 알고리즘 사례

 

(응용 116-1-1)
알고리즘의 시간복잡도(Time Complexity) O(1), O(n), O(n2)에 대하여 설명하시오

 

(관리 108-3-1)
1. 그리디(Greedy) 알고리즘에 대하여 다음 질문에 답하시오. 
230원어치를 구매함, 손님이 이때

가. 지폐 1000원을 받고 동전으로 770원을 돌려줄 때 최소 동전수를 찾는 그리디 알고리즘을 설명하시오.
(단, 동전의 액면은 500원, 100원, 50원, 10원임)
나. 위 알고리즘을 C 또는 Java 언어로 구현하시오.

 

(관리 101-3-4)
B트리와 B+트리와 관련하여 다음을 설명하시오.

1) B트리와 B+트리의 정의와 차이점
2) B트리의 삽입 알고리즘
3) B트리의 삭제 알고리즘
4) 26, 57, 5, 33, 72, 45를 순서대로 삽입하고, 72, 33, 45를 순서대로 삭제하는 모든 과정의 B트리를 그리시오. (단, 차수는 3)

 

(관리 90-1-8)
“Factorial n"을 구하는 재귀(Recursive) 알고리즘을 작성하시오.
(단, 프로그래밍 언어에는 제한이 없음, Factorial n(n!): n * (n-1) * (n-2) * ... * 1)

 

(관리 89-4-1)
알고리즘의 평가 방법인 Time Complexity와 Space Complexity에 대해 설명하시오

 

(관리 87-1-13)
알고리즘 설계 기법 중 동적 계획법(Dynamic Programming)에 대해 설명하시오

 

참고 자료

탑싯 에센스 - 소프트웨어 개발

시간 복잡도에 대한 설명 및 활용 예에 대해 참고할 수 있습니다.

https://ko.wikipedia.org/wiki/알고리즘

알고리즘 - 위키백과, 우리 모두의 백과사전

알고리즘의 조건 및 종류에 대해 참고할 수 있습니다.

https://namu.wiki/w/알고리즘

알고리즘 - 나무위키

 

알고리즘 분석 기준에 대해 참고할 수 있습니다.
https://m.blog.naver.com/zenix4078/10455703

알고리즘의 분석 기준