* 문제
n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 숫자는 한 개 이상 선택해야 한다.
예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

* 풀이
수열의 원소중 연속된 숫자를 선택해 가장 큰 합을 구하기 위해서 동적계획법(Dynamic Programming)을 사용합니다. 첫번째 원소부터 별도의 배열(dp배열)에 수열값과 그전까지 합한 값 중 큰값을 저장합니다. 그중 최댓값을 구하면 정답입니다. 이해가 안가시면 아래 코드를 주석과 함께 한 줄 씩 해석해 보시기 바랍니다.

* 소스코드

#include <iostream> 
#define MAX(a,b) ((a) > (b) ? (a) : (b)) 
using namespace std; 

int main(){ 
     int input_value = 0; 
     cin >> input_value; 
     int *data = new int[input_value]; 
     int *dp = new int[input_value];  // 배열 동적 할당
     int max = -1001; // max는 입력 값 중 가장 작은값보다 작은값

     for (int i = 0; i < input_value; i++)  
          cin >> data[i]; // 데이터 입력

     dp[0] = data[0]; // 첫번째 원소는 그대로 대입(그 자체로 최대값)

     for (int i = 1; i < input_value; i++) 
          dp[i] = MAX(data[i], data[i] + dp[i - 1]); 
          // dp배열에 원소 값과 그전 dp값을 합한 값 중 큰 값 대입

     for (int i = 0; i < input_value; i++) 
          if (max < dp[i]) max = dp[i]; // 최댓값 검색

     cout << max; 

     delete[] dp; 
     delete[] data; // 배열 동적 할당 메모리 해제

     return 0; 
}

질문 및 오류사항은 댓글로 달아주세요.


'자료구조, 알고리즘' 카테고리의 다른 글

정렬 알고리즘 종류  (0) 2018.09.12
검색 알고리즘 종류  (2) 2018.09.11
자료구조 그래프(Graph)  (1) 2018.09.06
자료구조 힙(Heap)  (0) 2018.09.05
자료구조 이진 탐색 트리(Binary Search Tree)  (0) 2018.09.01
자료구조 트리(Tree)  (0) 2018.08.30
[자료구조] 큐 QUEUE  (0) 2018.08.19
[자료구조] 스택 STACK  (0) 2018.08.19


[4과목 : 소프트웨어 공학]

61. HIPO(Hierarchy Input Process Output) 

- 하향식 소프트웨어 개발을 위한 문서화 도구 

- 시스템 분석 및 설계, 문서화 시 사용되는 기법으로 입력, 처리, 출력 기능 

- 체계적 문서관리로 기호, 도표등을 사용(보기 쉽고 이해하기 쉬움) 

- 기능과 자료의 의존 관계를 동시에 표현 


62. 하향식 통합 검사(Top Down Integration Test) 

- 상위 모듈에서 하위 모듈 방향으로 통합하며 검사 

- 주요 제어 모듈을 드라이버로 사용, 주요 제어 모듈의 종속 모듈은 스터브로 대체 

- 깊이 우선, 넓이 우선 방식에 따라 종속 스터브들이 실제 모듈로 교체 

- 모듈이 통합 될 때마다 검사 실시 

- 새로운 오류가 생기지 않음을 보증하기 위해 회귀 검사 실시 


63. 사용 용이성(Usability) 

- 사용에 필요한 노력을 최소화, 쉽게 사용할 수 있는 정도 


64. 럼바우(Rumbaugh) 객체지향 분석 방법론

- 객체모델 → 동적모델 → 기능모델 


65. NS(Nassi-Schneiderman) Chart

- 논리 기술에 중점을 둔 도형을 이용한 표현 방법(Box Diagram, Chapin Chart) 

- 순차, 반복, 선택, 다중 선택 구조등 표현 

- GOTO나 화살표 사용하지 않음, 선택과 반복 구조를 시각화 

- 조건이 복합되어 있는 곳의 처리를 시각적으로 명확히 식별 


66. Coad와 Yourdon 방법

- E-R 다이어그램을 사용하여 객체의 행위 모델링, 객체 식별 등 객체지향 분석 기법 


67. 바람직한 설계의 특징

- 적당한 모듈의 크기를 유지하고, 모듈 간의 상호 의존도(결합도)는 약하게, 응집도는 강하게 설계 


68. 폭포수 모델의 단점

- 개발 과정 중 발생하는 새로운 요구를 반영하기 힘듬 


69. 중앙 집중형 팀

- 한 관리자가 의사결정을 하고, 구성원들은 그 결정을 따르는 방식 

- 보기 4.는 분산형 팀에 대한 설명 


70. 화이트 박스 테스트 

- 데이터 흐름검사는 화이트 박스 테스트 방식이며 나머지는 블랙박스 테스트 방식이다. 


71. 객체지향 기법의 구성요소 

- 클래스(Class) : 공통된 속성과 연산을 갖는 객체의 집합 


72. 럼바우 분석 기법(기능 모델링) 

- 입출력 결정 → 자료흐름도 작성 → 기능 상세 기술 → 제약 사항 결정 및 최소화 


73. 비용 산정 

- 구현해야 할 프로젝트의 복잡도와 크기 및 요구 신뢰도 

- 인력, 지원 하드웨어, 지원 소프트웨어 

- 인적 자원의 눙력과 경험 및 개발 기간 


74. 자료 사전 표기 기호 

- '=' : 자료의 정의(is) 

- '+' : 자료의 연결(and) 

- '()' : 자료의 생략(Optional) 

- '[|]' : 자료의 선택(or) 

- '{}' : 자료의 반복(Iteration) 

- '* *' : 자료의 설명(Comment) 


75. CPM(Critical Path Method) 

- 노드와 간선으로 구성된 네트워크 

- 프로젝트 완성에 필요한 작업을 나열하고 소요시간을 예측 

- 각 작업이 수행되는 시간과 각 작업 사이의 관계 파악 


76. 소프트웨어 재사용의 이점 

- 개발 시간과 비용 단축, 품질 및 생산성 향상, 실패 위험 감소, 시스템 구축 방법 지식, 문서 공유 


77. 블랙 박스 테스트의 종류 

- 동치 분할 검사, 경계값 분석, 원인-효과 그래프 검사, 오류 예측 검사, 비교 검사 


78. 정보 저장소 

- 소프트웨어를 개발하는 동안 모아진 정보를 보관, 관리 

- 사용자, 도구, 응용프로그램 공동 사용 

- 데이터베이스가 정보 저장소 역할 담당 


79. 정형 기술 검토(FTR) 

- 소프트웨어 기술자들에 의해 수행되는 소프트웨어 품질 보증 활동 

- 검토 회의, 검열 등 회의 형태로 수행 

- 제품 검토, 의제 제한, 논쟁 및 반박, 문제 영역 표현, 참가자 수 제한 및 사전 준비 


80. 객체(Object) 지향 기법 

- 현실 세계를 그대로 모형화 

- 구조적 기법의 문제점 해결책 

- 소프트웨어 재사용 및 확장 용이 



2018.04.28 필기 기출 해설 - 1. 데이터 베이스

2018.04.28 필기 기출 해설 - 2. 전자계산기 구조

2018.04.28 필기 기출 해설 - 3. 운영체제

2018.04.28 필기 기출 해설 - 5. 데이터 통신



질문 사항은 댓글로 달아주세요!



[3과목 : 운영체제]


41. 가상 기억장치

- 보조기억장치의 일부를 주기억장치처럼 사용, 현재 운영체제에서 흔히 사용 

- 주기억장치의 용량보다 큰 프로그램을 실행하기 위해 사용 

- 가상 기억장치의 프로그램을 실행하기 위해 주소 변환 작업(주소 매핑)이 필요 

- 기억장치의 이용률과 다중 프로그래밍 효율을 높일 수 있음 

- 가상 기억장치 구현 기법 : 페이징(Paging), 세그먼테이션(Segmentation) 기법 


42. HRN(Hightest Response-ratio Next) 

- 선순위 계산 공식 : 대기시간 + 서비스 시간 / 서비스 시간 

작업 A 우선순위 : 5 + 20 / 20 = 1.25 

작업 B 우선순위 : 40 + 20 / 20 = 3 

작업 C 우선순위 : 15 + 45 / 45 = 1.33 

작업 D 우선순위 : 40 + 10 / 10 = 5 


43. 프로세스의 정의

- 프로세스(Process) : 실행중인 프로그램, PCB를 가진 프로그램, 실기억 장치에 저장된 프로그램 

- 워킹 셋(Working Set) : 프로세스가 일정 시간 동안 자주 참조하는 페이지들의 집합 

- 세그먼테이션(Segmentation) : 가상 기억장치에 보관되어 있는 프로그램을 다양한 크기의 논리적인 단위로 나눈 후 주기억장치에 적재시켜 실행시키는 기법 

- 모니터(Monitor) : 동기화를 구현하기 위한 특수 프로그램 기법 


44. 매크로 프로세서

- 처리 과정 : 매크로 정의 인식 - 매크로 정의 저장 - 매크로 호출 인식 - 매크로 확장과 인수(매개 변수) 치환 


45. 작업 반환 시간

JOB 1 - 반환 시간 : 13 / 대기 시간 : 0 

JOB 2 - 반환 시간 : 13 + 35 / 대기 시간 : 3 (13 + 35 - 3 = 45) 

JOB 3 - 반환 시간 : 13 + 35 + 2 / 대기시간 : 8 (13 + 35 + 2 - 8 = 42) 

평균 반환 시간 = (13 + 45 + 42) / 3 = 33.333... 


46. 운영체제 성능 평가 기준 

- 처리 능력, 반환 시간, 사용 가능도, 신뢰도 


47. 자원 보호 기법 

- 접근 제어 행렬(Access Control Matrix) : 객체에 대한 접근 권한을 행렬로 표기 

- 전역 테이블(Global Table) : 영역, 객체, 접근권한 집합 형태의 테이블 

- 접근 제어 리스트(Access Control List) : 접근 제어 행렬 각 열을 중심으로 접근 리스트로 구성 

- 권한 리스트(Capability List) : 접근 제어 행렬 각 행을 중심으로 권한들로 구성 


48. 실시간 처리 시스템(Real-Time Processing System) 

- 데이터 발생 즉시, 또는 데이터 처리 요구가 있는 즉시 처리하여 결과를 산출 


49. 비선점 스케줄링 

- FCFS(First Come First Service = FIFO) : 큐에 도착한 순서에 따라 CPU 할당 

- SJF(Shortest Job First) : 실행시간이 가장 짧은 프로세서 부터 CPU 할당 

- HRN(Hightest Response-ratio Next) : 우선순위 결과값이 높은 순서대로 CPU 할당 

- 기한부(Deadline) : 일정시간 내 프로세스 완료 

- 우선순위(Priority) : 각 프로세스마다 우선순위 부여하여 CPU 할당 


50. 하이퍼 큐브

- 하나의 프로세서에 연결되는 다른 프로세서의 수가 n개 일 경우 프로세서는 총 2^n개 필요 


51.직접 파일(Direct File) 

- 파일을 구성하는 레코드를 임의의 물리적 저장공간에 기록 

- 레코드에 특정 기준으로 키 할당, 해싱 함수로 키에 대한 보조기억장치의 물리적 상대 주소를 계산하고 저장 

- 레코드는 해싱 함수에 의해 계산된 물리적 주소를 통해 직접 접근 가능 

- 임의 접근이 가능한 자기 디스크 또는 자기 드럼 사용 


52. 페이지 부재

3개의 페이지 프레임 기억장치에서 FIFO 방법으로 페이지 요청 시 수행 과정

1) 요쳥된 페이지 번호 순서대로 프레임에 들어온다(들어올 때 페이지 부재 발생)

2) 요청된 페이지가 프레임에 존재한다면 다음 순서로 넘어간다.

3) 프레임이 가득차면 가장 먼저 들어온 페이지(가장 위쪽)가 교체된다.


53. 커널

- 하드웨어 보호, 하드웨어 간 인터페이스 역할, 프로세스 관리, 기억장치 관리, 파일 시스템 관리, 입 출력 관리 


54. 링커

- 링커는 언어 번역 프로그램이 새엉한 프로그램과 라이브러리, 모듈 등을 연결하여 실행 가능한 모듈로 만드는 시스템 소프트웨어 


55. 분산 처리 시스템 

- 완전 연결(Fully Connection) - 각 사이트들이 다른 모든 사이트와 직접 연결 

- 부분 연결(Partially Connection) - 일부 사이트들 간 직접 연결 

- 트리/계층(Tree/Hierachy) - 각 사이트들이 트리 형태로 연결 

- 성(Star) - 하나의 중앙 사이트에 직접 연결 

- 환(Ring) - 인접한 사이트 끼리 직접 연결 


56. SJF 스케줄링 

- 최적이긴 하지만 CPU 버스트 시간을 미리 알 수 없음.(다음 버스트시간이 이전과 비슷할 거라고 예측) 


57. i-node 블록

- UID, GID, 파일 크기, 타입, 생성시기, 변경시기, 최근 사용시기, 권한, 링크수, 블록 시작 주소 등 


58. UNIX 특징

- 대화식 운영체제, 소스가 공개된 개방형 시스템 

- C언어로 작성(이식성 높음), 장치, 프로세스 간 호환성 높음 

- 다중 사용자(Multi-User), 다중 작업(Multi-Tasking) 지원 

- 트리구조의 파일 시스템 


59. 교착 상태와 불안전 상태

- 교착 상태가 발생 할 수 있는 상태를 불안정 상태라고 함. 


60. 제어 및 처리 프로그램 

- 감시(Supervisor) 프로그램: 각종 프로그램의 실행과 시스템 전체의 작동 상태를 감시, 감독 

- 작업 제어(Job Control) 프로그램 : 다음 업부로 이행을 자동으로 수행하기 위한 준비 및 완료 담당 

- 자료 관리(Data Management) 프로그램 : 주기억장치와 보조기억장치 간 데이터 전송, 자료 갱신 및 유지 보수 수행 

- 언어 번역(Language Translate) 프로그램 : 원시 프로그램을 기계어 형태의 목적 프로그램으로 번역 

- 서비스(Service) 프로그램 : 컴퓨터를 효율적으로 사용할 수 있는 사용빈도가 높은 프로그램 

- 문제(problem) 프로그램 : 특정 업무 및 해결을 위해 사용자 직접 작성한 프로그램 



2018.04.28 필기 기출 해설 - 1. 데이터베이스

2018.04.28 필기 기출 해설 - 2. 전자 계산기 구조

2018.04.28 필기 기출 해설 - 4. 소프트웨어 공학

2018.04.28 필기 기출 해설 - 5. 데이터 통신



오타 및 질문사항은 댓글로 달아주세요!


to Top