# 자료 구조
트리와 그래프만 비선형 구조 나머지는 다 선형 구조
- 선형 리스트
- 연속 리스트: 배열 사용
- 기억장소 이용 효율 좋음
- 중간에 데이터 삽입 시 연속된 빈공간 필요
- 연결 리스트(Linked List): 포인터 사용
- 노드의 삽입이나 삭제가 쉽다
- 포인터로 연결이 되어 검색이 느리다
- 포인터를 위한 추가 공간 필요
- 중간 노드 연결이 끊어지면 그 다음 노드 찾기 힘듬
-스택:
- 후입선출(LIFO)
- 왔던 길을 되돌아가는 연산에 사용(재귀 호출, 후위 표기법, 깊이 우선 탐색)
- 응용분야: 인터럽트의 처리, 수식의 계산 및 수식 표기법 응용, 서브루틴의 호출 및 복귀 주소 저장
- 큐
- 선입선출(FIFO)
- 한쪽은 입력만 다른쪽은 출력만 가능
- 운영체제의 작업 스케줄링에 사용
-데크
- 삽입과 삭제가 양쪽 끝에서 발생
- 인접행렬: 방향 간선이 있으면 1, 없으면 0
- 행=향하는 숫자?
- 열=해당 숫자
- 방향 그래프 최대 간선 수: n(n-1)
- 무방향 그래프 최대 간성 수: n(n-1)/2
# 트리
1. 트리 관련 용어
- 노드
- 근 노드(Root Node): 맨 위에 있는 노드
- 디그리(차수): 특정 노드에 연결된 노드의 수, 트리의 차수는 노드들 중 가장 많은 차수를 말한다.
- 단말 노드: 자식이 하나도 없는 노드
- 자식 노드: 어떤 노드의 다음 레벨의 노드들
- 부모 노드: 어떤 노드의 이전 레벨의 노드
- 형제 노드: 동일한 부모를 갖는 노드들
2. 트리의 운행법
- Preorder: 루트 → 왼 → 오
- Inorder: 왼 → 루트 →오
- Postoder: 왼 →오 →루트
3. 수식의 표기법
- 전위 표기법(PreFix): 연산자가 앞에
- 중위 표기법(InFix): 연산자가 안에
- 후위 표기법(PostFix): 연산자가 뒤에
거꾸로 변환 - 인접한 피연산자 두개와 각 표기법에 따라 해당하는 연산자를 괄호로 묶고 시작
# 30-정렬
삽입 정렬
- 두번째 값부터 이전 값들과 비교하여 올바른 위치에 삽입
- 시간 복잡도: O(n^2)
쉘 정렬
- 삽입 정렬의 확장 개념
- 평균 시간 복잡도: O(n^1.5)
- 최악 시간 복잡도: O(n^2)
선택 정렬
- 숫자 전체를 보고 가장 작은 숫자를 앞자리부터 순서대로 교환
- 전체 숫자를 보고 가장 작은 숫자를 골라서 앞자리에 자리 교환
- 그 다음으로 작은 숫자를 찾아서 두번째자리 교환
- 위 과정을 반복하면서 정렬
- 시간 복잡도: O(n^2)
버블 정렬
- PASS 1당 앞에서 끝까지 나아가며 번호 하나씩 뒤에 숫자가 더 작으면 교환
- 앞에서 부터 순서대로 진행
- 숫자가 이미 정렬이 되어있다면 교환 X , 왼쪽의 숫자가 더 크면 자리 교환
* 서로 인접한 두 개를 비교해간다는 것이 특징.
- 시간 복잡도: O(n^2)
퀵 정렬
- 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분
- 가장 빠른 정렬 방법
- 분할과 정복을 통해 자료를 정렬
- 평균 시간 복잡도: O(nlog2n)
- 최악 시간 복잡도: O(n^2)
힙 정렬
- 완전 이진 트리 이용
- 시간 복잡도: O(nlog2n)
- 값을 순서대로 완전 이진 트리로 배치
- 노드를 역순으로 자식 노드와 부모노드를 비교하여 큰 값을 위로 올리기 반복
2-Way 합병 정렬
- 이미 정렬 되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
- 두 개씩 묶어 묶음 안에서 정렬 반복
- 시간 복잡도: O(nlog2n)
기수 정렬
-Queue를 이용하여 자릿수 별로 정렬하는 방식
- 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배 후 버킷 순서대로 레코드를 꺼내 정렬
- 시간 복잡도: O(dn)
참고:
https://skstjdrhdgksek.tistory.com/11
https://pupbani.tistory.com/101
# 검색- 이분 검색/해싱
이분 검색(이진 검색)
- 찾고자 하는 값을 파일의 중간 값과 비교하면서 검색을 반복
- 탐색 효율이 좋고 탐색 시간 적게 소요
- 검색할 데이터가 정렬되어 있어야함
- 비교 횟수를 거듭할 수로 검색 대상 데이터의 수는 절반으로 줄어듦
해싱
- 키-주소 변환 방법
- 해시 테이블: 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간
| 버킷 | 하나의 주소를 갖는 파일의 한 구역 |
| 슬롯 | 한 개의 레코드를 저장할 수 있는 공간 n개의 슬롯이 모여 하나의 버킷 형성 |
| Collision(충돌현상) | 서로 다른 2개 이상의 레코드가 같은 주소를 갖는 현상 |
| Synonym |
같은 주소를 갖는 레코드의 집합 |
| Overflow | 홈주소의 버킷 내에 저장할 기억공간 없는 상태 |
- 해싱 함수의 종류:
| 제산법 | 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지 |
| 제곱법 | 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 사용 |
| 폴딩법 | 키를 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR한 값을 홈 주소로 사용 |
| 기수 변환법 | 키 숫자의 진수를 다른 진수로 변화시켜 주소 크기를 초과한 높은 자릿수를 절단하고, 이를 다시 주소 범위에 맞게 조정 |
| 대수적 코딩법 | 키 값을 이루고 있는 각 자리의 비트 수를 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수 |
| 숫자 분석법 | 숫자의 분포 분석해서 비교적 고른 자리를 필요한 만큼 택 |
| 무작위법 | 난수 |
- Collision(충돌) 해결법:
| 체이닝 | 버킷에 할당된 연결 리스트에 데이터를 저장하는 방법 |
| 개방 주소법 | 순차적으로 그 다음 빈 버킷을 찾아 데이터 저장 |
| 재해싱 | 새로운 해싱 함수로 새로움 홈 주소 구함 |
# 디지털 저작권 관리(DRM)
저작권 관리 구성 요소
- 클리어링 하우스: 키 관리 및 라이선스 발급 관리
- 콘텐츠 제공자(Contents Provider): 콘텐츠를 제공하는 저작권자
- 패키저: 콘텐츠를 메타 데이터와 함께 배포 가능한 형태로 묶어 암호화하는 프로그램
- 콘텐츠 분배자(Contents Distributor): 암호화된 콘텐츠를 유통하는 곳이나 사람
- 콘텐츠 소비자(Costomer): 콘텐츠를 구매해서 사용하는 주체
- DRM 컨트롤러: 배포된 콘텐츠의 이용 권한을 통제
- 보안 컨테이너(Security Container): 콘텐츠 원본을 안전하게 유통하기 위한 전자적 보안 장치
디지털 저작권 관리의 기술 요소
- 암호화: 콘텐츠 및 라이선스를 암호화하고 전자 서명을 할 수 있는 기술
- 키 관리: 콘텐츠를 암호화한 키에 대한 저장 및 분배 기술
- 암호화 파일 생성: 콘텐츠를 암호화된 콘텐츠로 생성하기 위한 기술
- 식별 기술: 콘텐츠에 대한 식별 체계 표현 기술
- 저작권 표현: 라이선스의 내용 표현 기술
- 정책 관리: 라이선스 발급 및 사용에 대한 정책 표현 및 관리 기술
- 크랙 방지: 크랙에 의한 콘텐츠 사용 방지 기술
- 인증: 라이선스 발급 및 사용의 기준이 되는 사용자 인증 기술
# 소프트웨어 버전 등록
현상 관리(SCM): 소프트웨어으 개발 과정에서소프트웨어의 변경사항을 관리하기위히 개발된 일련의 활동
가시성, 추적성 보장-> 소프트웨어의 생산성과 품질 향상
현상 관리 도구: Git, CVS, Subversion
현상 관리 도구의 주요 기능
- 동기화: 저장소에 있는 최신 버전으로 자신의 작업 공간을 동기화
- 체크인: 저장소에 새버전 갱신
- 체크아웃: 파일 받아옴
- 가져오기: 빈 저장소에 처음으로 파일 복사
- 커밋: 이전에 갱신된 내용이 있으면 충돌을알리고 diff 도구를 이용해 수정한 후 갱신을 완료
- 저장소: 최신 버전의 파일들과 변경 내역에 대한 정보가 저장된 곳
암기: 동체가 커저
# 테스트 기법에 따른 애플리케이션 테스트
화이트박스 테스트-내부 논리적 경로 검사
-NSchat 사용
화이트박스테스트 종류:
- 기초 경로 검사(Base Path Testing)
- 제어 구조 검사(조건, 루프, 데이터 흐름 검사)(Control Structure Testing)
화이트박스 테스트 검증 기준
- 문장 검증 기준
- 분기 검증 기준
- 조건 검증 기준
- 분기/조건 기준:
블랙박스 테스트: 출력 결과물 정확한지, 구조보다 기능
- 동치 분할 검사(Equivalence Partitioning Testing)
- 경계값 분석(Boundary Value Analysis)
- 원인-효과 그래프 검사(Cause-Effect Graphing Testing)
- 오류 예측 검사(Error Guessing)
- 비교 검사(Comparison Testing)
# 개발 단계에 따른 애플리케이션 테스트
1. 단위 테스트: 모듈이나 컴포넌트 초점
- 단위 테스트로 발견 가능한 오류: 알고리즘 오류, 탈출구 없는 반복문, 틀린 계산 수식
2. 통합 테스트: 단위 테스트가 완료된 모듈을 결합하여 하나의 시스템으로 완성시키는 과정에서의 테스트
3. 시스템 테스트: 컴퓨터 시스템에서 완벽히 수행하는지
4. 인수 테스트: 사용자 요구사항 충족하는지
인수 테스트 종류:
- 사용자 인수 테스트
- 운영상의 인수 테스트
- 계약 인수 테스트
- 규정 인수 테스트
- 알파 테스트: 사용자가 개발자 앞에서
- 베타 테스트: 사용자가 여러명의 사용자 앞에서(개발자X)
# 통합 테스트
하향식 통합 테스트
- 깊이 우선 통합법/넓이 우선 통합법 사용
- 스텁(하위 모듈 대체)
- 빠른 파악
상향식 통합 테스트
- 클러스터 사용
- 드라이버(상위 모듈 대체)
# 52-복잡도
복잡도 측정 방법: LOC, 순환 복잡도
시간 복잡도
- 빅오 표기법: 최악
- 세타 표기법: 평균
- 오메가 표기법: 최상
O(n): push, pop
O(log2n): 이진 트리, 이진 검색
O(n): for문
O(nlog2n): 힙 정렬, 2-way합병 정렬
O(n^2): 삽입 정렬, 쉘 정렬, 선택 정렬, 버블 정렬, 퀵 정렬
O(2^n): 피보나치 수열
순환 복잡도(Cyclomatic)=화살표수-노드수+2
# 53-애플리케이션 성능 개선
클린 코드 작성 원칙
- 가독성: 이해하기 쉽게
- 단순성: 코드를 간단히, 클래스/메소드/함수를 최소 단위로 분류
- 의존성 배제: 다른 모듈에 영향 최소화
- 중복성 최소화: 중복을 최소화하고 공통된 코드 사용
- 추상화: 상위 클래스/메소드/함수에 애플리케이션의 특성 나타내고, 하위엔 상세내용 구현
소스코드 품질 분석 도구
- 정적 분석 도구: 코드를 실행하지 않고 자료 흐름이나 논리 흐름을 분석(pmd, appcheck, SonarQube, checkstyle, ccm, cobertura)
- 동적 분석 도구: 코드를 실행하여 메모리 누수, 스레드 결함 들을 분석(Avalanche, Valgrind)
# 58-인터페이스 보안
인터페이스 보안 취약점 분석: 각 구간드르이 현황 확인하고 각 구간의 보안 취약점 확인
인터페이스 보안 기능 적용
- 네트워크 영역: 네트워크 트래픽에 암호화 설정
- 애플리케이션 영역: 코드 보안
- 데이터베이스 영역: 데이터베이스 동작 객체의 보안 취약점에 보안 기능 적용, 암호화나 익명화
IPsec: 데이터 변조 방지 및 은닉 기능 제공, 양방향 암호화 방식 사용
- 구성 요소: AH(발신지 인증/데이터 무결성), ESP(발신지 인증/데이터 무결성/기밀성)
- 운영 모드: 터널모드(Tunnel), 전송모드(Transport)
SSL: 인증, 암호화, 무결성 보장
S-HTTP: 클라이언트와 서버 간에 전송되는 모든 메시지를 암호화
데이터 무결성 검사 도구: 시스템 파일의 변경 유무 확인
- Tripwire, AIDE, Samhain, Claymore, Slipwire, Fcheck
# 59-인터페이스 구현 검증
인터페이스 구현 검증 도구
- xUnit: 자동화
- STAF: 서비스 호출 및 컴포너트 재사용 등 다양한 환경 지원, 데몬
- FitNesse: 웹 기반 테스트케이스
- NTAP: FitNessse의 협업 기능+STAF의 재사용과 확장성
- Selenium: 다양한 프라우저 및 개발 언어 지원
- watir: Ruby 사용
구현 감시 도구: 인터페이스 동작 상태는 APM을 사용하여 감시
APM: 애플리케이션의 흐름 모니터링과 성능 예측을 통해 최적의 애플리케이션 상태를 보장 및 관리하는 것
애플리케이션(Application)+성능(Performance)+관리(Management)
- 리소스 방식: Nagios, Zabbix, Cacti
- 엔드투엔드 방식: VisualVM, 제니퍼, 스카우터
'정보처리기사 > 필기' 카테고리의 다른 글
| 내가 기억해야 할 정처기 - 5과목 정보시스템 구축 관리 (0) | 2026.05.29 |
|---|---|
| 내가 기억해야 할 정처기 - 3과목 데이터베이스 구축 (0) | 2026.05.28 |
| 내가 기억해야 할 정처기 - 4과목 프로그래밍 언어 활용 (0) | 2026.05.21 |
| 내가 기억해야 할 정처기 - 1과목 소프트웨어 설계 (0) | 2026.05.07 |