일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |
- SQL
- 객체지향
- 이클립스 설치
- 식별자
- 반복문
- 논리 연산자
- SpringSecurity 로그인
- SpringSecurity 로그아웃
- @PreAuthorize("isAuthenticated()")
- 객체
- 산술 연산자
- SQL 튜닝
- 연산자
- SQL튜닝
- join
- 상속
- 오버로딩
- 자바의정석
- StringBuffer
- 친절한 SQL
- 스프링시큐리티 로그아웃
- 친절한 SQL 튜닝
- 인텔리제이 Web 애플리케이션
- 비교 연산자
- spring 게시판 삭제
- java
- 배열
- 예약어
- 오버라이딩
- 함수
- Today
- Total
gi_dor
소프트웨어 개발 - 2 자료구조 본문
🔸 자료 구조 : 논리적으로 설계된 데이터구조 , 관계
어떻게 구성하는지에 따라 성능에 많은 영향을 끼친다
데이터 용량과 실행시간을 최소한으로 사용
데이터의 추가 삭제 탐색을 효율적으로 연산하게 설계 한다
🔹 단순구조
- 기본 데이터 타입을 사용하는 구조
- 단순구조를 확장하여 자료구조가 구성된다
🔹 선형구조 : 대응관계가 1:1로 구성되는 구조 , 순차구조와 연결구조로 구분
- 배열
- 선형리스트
• 연속 리스트 : 배열처럼 연속되는 기억장소에 저장 , 중간에 삽입 ,삭제시 자료의 이동이 필요하다 , 탐색속도 우선
• 연결리스트 : 연속적으로 배열시키지는 않고 임의의 공간에 기억, 순서에 따라 연결시킨 구조
데이터 이동 (삽입 , 삭제) 속도 우선 , 연속적이지 않아도 저장할 수 있다 - 스택 LIFO
- 큐 FIFO
- 데크
- 연결 리스트
스택
1. 데이터의 입출력이 반대쪽에서 일어나는 구조 LIFO
2. 삽입 - PUSH , 추출 POP
3. 오버플로 언더플로 발생
큐
1. 데이터의 입출력이 각각 반대쪽에 일어나는 구조 FIFO
2. 삽입 Rear , 삭제 Front
3. 대기 행렬에 적합한 자료구조
데크
1. 입출력이 양쪽 모두에서 일어나는 구조 (양방향 큐)
2. 각각 포인터가( Left , Right) 데이터 삽입 , 삭제에 따라 1씩 증감
3. 입력제한 (Scroll) - 출력은 양쪽에서 , 입력한 한쪽에서만 가능
4. 출력제한 (Shelf) - 입력은 양쪽에서 , 출력은 한쪽에서만 가능
선형 리스트
1. 같은 유형 데이터가 연속된 공간에 저장
2. 가장단순 , 접근속도가 빠르다
3. 삽입 삭제시 위치 이동 때문에 시간이 오래걸린다
4. 대표적인 배열이 있다
연결 리스트
1. 데이터의 삽입 , 삭제가 어려운 배열의 단점을 보완
2. 노드 : 데이터와 자신이 연결된 데이터 포인터
3. 다른 위치의 노드와 노드의 연결로 구성
4. 기억공간이 추가로 필요 , 배열보다 느리다
🔹 비선형구조 : 1 : M , M : N 등으로 구성
- 트리
- 그래프
• 무방향 그래프
• 방향 그래프
🔹 수식 prefix infix postfix
a * ( b + c ) * d
1. 중위식 -> 전위식
- ( ( a * ( b + c ) ) * d )
- ( * ( * a (+ bc ) ) d )
- 괄호제거 ** a * bc d
2. 중위식 -> 후위식
- ( ( a * ( b + c ) ) * d )
- ( ( a ( b c + ) * ) d * )
- 괄호제거 a b c + *d*
3. 전위식 ( - / * a + b c d e ) 를 후위식으로 변경
- 연산자 , 피연산자 , 피연산자 형태로 묶는다 + 피연산자 형태도 묶으면 피연산자됨
- - / * a (+ b c ) d e
- - / (* a ( + b c ) ) d e
- - ( / ( * a ( + b c ) ) d ) e
- ( - ( / ( * a ( + b c ) ) d ) e )
- 기호들을 괄호 안에서 가장 뒤로
- ( ( ( a ( b c + ) * ) d / ) e -)
- 괄호 제거 a b c + * d / e -
🔸 알고리즘 : 문제를 해결하기 위한 효율적인 해법
알고리즘 과 데이터 구조가 결합하면 프로그램이 완성된다
🔹 원칙
- 입력은 없을 수 있지만 출력은 반드시 1개 이상 존재
- 모든 기능은 명확한 의미를 가지며 완벽히 구성 되어 있어야 한다
- 모든 기능은 지정된 횟수만큼 반복되어야 하며 , 실제 연산이 가능해야 한다
성능 판단기준 : 정확성 , 명확성 , 수행량 , 메모리 사용량
🔹 알고리즘 표현
- 순서도 : 도형과 기호로 표현
- 의사코드 : 일반적인 언어로 코드와 유사하게 표현
- 이해할수 있게 일관성
🔹 설계기법
동탐재근분퇴
DGRADB
1. 동적 계획법 (Dynamic) - 플로이드 , 피보나치
더 작은 문제의 연장선으로 생각하는 방식 - 쉬운단계 문제부터
2. 탐욕적 알고리즘 (Greedy)
분기마다 가장 최적의 풀이를 선택 , 반드시 최적의 풀이를 보장하지 않는다
3. 재귀적 알고리즘 (Recursive)
같은 풀이를 다시 불러오는 과정을 반복
4. 근사 알고리즘 (Approximation) (근사치 값이라 생각하자)
비교적 빠른시간에 계산이 가능하도록
5. 분할 정복 (Divide) - 퀵정렬 , 병합 정렬
풀수있는 단위로 작게 나누는 방식
6. 퇴각 검색법(BackTacking)
탐색이 실패할 경우 탐색이 성공했던 이전분기로 되돌아가는 방식
새로운 탐색이 가능한 분기까지 되돌려 진행된다
대표 : 깊이우선 탐색 알고리즘 DFS
🔸 시간 복잡도에 따른 알고리즘
- 문제를 해결하기 위한 시간의 횟수를 말한다
- 최적화를 위해 필요
- 자료의 수 n 이 증가할 때 시간이 증가하는 대략적인 패턴을 의미
🔹 시간복잡도 Big-O 표기법
O(1) | 입력값(n)에 관계 없이 일정하게 문제 해결에 단 하나의 단계만을 거친다 (해시함수) |
O(log2n) | 로그시간 복잡도 입력값(n) 또는 조건에 의해 감소 (이진탐색) / |
O(nlog2n) | 선형로그 시간복잡도 입력값 n(log2n)번만큼 수행시간을 갖는다 - 증가 (퀵정렬 , 병합 정렬) |
O(n) | 선형시간 복잡도 입력값(n)이 1:1의 관계를 가짐(순차 탐색) |
O(n^2) | 제곱시간 복잡도 입력값(n)의 제곱만큼 수행(삽입, 선택,버블) |
O(C^2) | 주어진 상수값C의 n제곱 |
🔸 순환 복잡도
- 프로그램 이해 난이도는 , 제어 흐름 난이도의 복잡도에 따라 결정
- 싸이클로메틱의 개수와 , 원시프로그램의 오류 개수는 밀접한 관계
🔹 복잡도 계산방식
복잡도 = 화살표 수 - 노드 수 + 2
복잡도 = 영역수 (폐 구간) + 1
복잡도 = 의사결정 수 + 조건수 + 1
순환 복잡도 : 화살표 수 6 - 노드 수4 + 2 = 4
E - N + 2
🔸 해싱 함수
🔹 해싱
- 직접 접근 파일을 구성 할 때 사용
- 속도는 가장 빠름 , 충돌 현상시 오버플로 해결의 부담이 가중된다 , 많은 기억공간을 요구
🔹 제산방법 Division Method
- 나머지 연산자 % 를 사용해 테이블 주소를 계산
🔹 중간 제곱방법 Mid-Squre
- 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 몇비트를 선택해 테이블 홈 주소로 사용
🔹 중첩 방법 Folding 폴딩
- 해싱함수 중 레코드 키를 여러부분으로 나누고 나눈부분의 각 숫자를 더하거나 XOR 한 값을 홈 주소로 사용
🔹 기수 변환방법 Radix Conversion
- 모든 키 내에서 자리별로 어떤 분포인지를 조사해 고른분포를 나타내는 자릿수를 필요한 만큼 선택해 홈주소로 사용
🔹 퀵정렬
- 피벗
- 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으러 나누어 가며 정렬
- 최적 O(nlog^n)
- 평균 O(nlog^n)
- 최악 O(n^)
🔹 합병정렬
- 전체 원소를 하나의 단위로 분할후 분할한 원소를 다시 합병해서 정렬
- 최적 O(nlog^n)
- 평균 O(nlog^n)
- 최악 O(nlog^n)
🔹 힙정렬
- 가장 큰 키 값을 갖는 루트노드를 제거하는 방식으로 반복해 정렬
- 최적 O(nlog^n)
- 평균 O(nlog^n)
- 최악 O(nlog^n)
🔹 버블정렬
- 2개의 레코드 키값을 비교해 그 크기에 따라 레코드 위치를 교환하는 알고리즘
- Pass = 요소개수 -1 번 수행된다
'자격증 > 정보처리' 카테고리의 다른 글
모의고사 1과목 오답노트 - 기록 (1) | 2024.02.18 |
---|---|
정보 시스템 구축관리 (1) | 2024.02.17 |
데이터베이스 구축 (1) | 2024.02.12 |
소프트웨어 개발 - 1 (0) | 2024.01.27 |
소프트웨어 설계 (1) | 2024.01.22 |