프로그래밍 언어/자료구조 & 알고리즘13 알고리즘의 설계 기법 - 분할정복기법/분할정복 알고리즘 알고리즘의 설계 기법 문제를 해결해 나가는 기법 알고리즘이 채택한 전략이나 관점 대표적인 알고리즘 설계 기법 분할 정복 기법 (Divide and Conquer) 욕심쟁이 기법 (Greedy method) 동적 프로그래밍 기법 (Dynamic programming) 분할 정복 기법 (Divide and Conquer) 하향식 설계 기법 문제의 크기를 작게 나누어서 좀 더 쉽게 해결할 수 있는 상태로 변환하여 문제를 해결하는 방법 하나의 문제를 여러 개의 작은 문제로 나누고, 각각에 동일한 해결 기법을 계속적으로 적용한 후 결과를 연합하여 원래의 문제를 해결하는 기법 분할된 부분의 문제들이 크기가 커서 해결이 쉽지 않을 경우, 각 부분의 문제에 ㄷ대해 다시 분할 정복 기법 적용 각 부분의 문제들이 간단히 .. 2021. 11. 26. 순서도 작성 순서도(Flowchart) 순서도 처리하고자 하는 문제의 순서와 상호 간의 관계를 일정한 기호를 사용하여 표현한 그림 순서도의 역할 프로그램 코딩의 기초 자료로 활용 문제의 이해성 증대 디버깅 용이 프로그램의 보관, 유지보수 자료로 활용 순서도의 종류 개략 순서도 프로그램의 전체 내용을 쉽게 파악할 수 있도록 중요 부분만 블록으로 간략히 표현 상세 순서도 컴퓨터가 수행할 수 있는 명령문 단위로 세부화하여 표현 상세 순서도를 프로그래밍 언어로 코딩하면 원시 프로그램(소스)가 됨 순서도 기호의 종류 기본 기호 프로그래밍 관련 기호 시스템 관련 기호 프로그래밍 관련 기호 프로그램의 논리를 나타내는 기호 기본 기호화 함께 프로그램 순서도를 작성하는 경우에 사용 순서도의 기본 유형 - 자료의 흐름에 따라 분류 직.. 2021. 11. 26. 알고리즘의 성능과 시간복잡도 알고리즘의 성능 구현된 프로그램이 실행되는 동안 얼마나 많은 공간적 자원과 시간적 자원을 요구하는 가에 따라 결정 자원을 적게 요구하는 알고리즘이 성능이 더 좋다고 표현 공간적 자원 컴파일된 프로그램을 이루는 명령어 저장 공간: 하드디스크(HDD) 프로그램이 실행되는 동안 필요한 데이터 저장 공간: 메모리 프로그램의 제어 정보와 임시 정보 저장 공간 시간적 자원 알고리즘이 구현된 프로그램의 실행이 시작되어 종료될 때까지 걸리는 시간 알고리즘의 시간 복잡도 알고리즘의 시간적 성능을 분석하기 위해 입력크기 n에 대한 기본 연산의 실행 횟수를 함수 형태로 나타낸 것 T(n) = n T(n) = n-1 T(n) = n2 T(n) =n(n-1)/2 알고리즘의 시간 복잡도 계산 예 숫자가 저장되어 있는 배열의 각 .. 2021. 11. 26. 알고리즘의 개념, 표현 방법 Algorithm 알고리즘 주어진 문제의 해결을 위해 논리 정연한 절차에 의해 계획한 해결방안을 정형적이고 체계적으로 기술한 것 어떤 문제를 해결하기 위해 나열한 계산적인 절차 절차 실행 후 주어진 문제에서 요구하는 결과 출력 어떤 구조와 방법으로 구성해갈 것인지를 생각하는 기본적인 설계 문제를 해결하기 위해 단계별로 명확히 기술하여 나열한 일련의 명령어들의 모임 왜 필요한가? 주어진 문제를 해결하기 위함 구체적인 작업에 들어가기 전에 사용 알고리즘의 유래 19세기 아랍의 유명한 수학자인 al-Khowarizmi에 의해 알고리즘으로 명명 수작업이나 좀 더 유용한 기계로 약간의 계산을 위한 간단한 규칙의 집합 숫자를 더하고, 곱하고, 나누는 것들도 알고리즘 알고리즘 종류 재귀적 알고리즘 탐색 및 정렬 알고.. 2021. 11. 26. 이전 1 2 다음