본문 바로가기

Computer Science108

[Computer Algorithms] KMP Algorithm https://www.youtube.com/watch?v=ynv7bbcSLKE&t=147s 영상에 소개된 것과 같이, O(m + n)에 text에서 pattern이 나타나는 인덱스를 찾는 알고리즘 import sysread = sys.stdin.readlinedef LPS(pattern): m = len(pattern) lps = [0] * m j = 0 i = 1 while i 2025. 7. 9.
[Computer Algorithms] Combination (조합) N개 들어있는 배열에서 i개 고르는 경우를 모두 출력하는 알고리즘이다. mask를 이용해서 true인 자리에 있는 것을 출력한다.#include #include #include using namespace std;int main(){ int N = 5; vector arr = {1, 2, 3, 4, 5}; for (int i = 1; i mask(arr.size(), false); fill(mask.begin(), mask.begin() + i, true); // 앞의 i개를 true로 설정 do { for (int j = 0; j  10000의 이전 조합: 0100001000의 이전 조합: 0010000100의 이전 조합: 00.. 2025. 3. 30.
[Computer Algorithms] Bellman-Ford Algorithm (벨만-포드 알고리즘) 벨만-포드 알고리즘 (Bellman-Ford Algorithm)벨만-포드 알고리즘은 가중 그래프에서 최단 경로를 찾는 알고리즘이다. 다익스트라 알고리즘과 비슷하지만, 음수 가중치(edge weight)를 가진 그래프도 처리할 수 있다는 점이 큰 차이점이다. 알고리즘 개요그래프 유형: 가중치 그래프(음수 가중치 가능), 방향 그래프(Directed Graph)시간 복잡도: O(VE) (V: 정점 개수, E: 간선 개수)장점: 음수 가중치를 가진 그래프에서도 최단 경로 계산 가능단점: 다익스트라(O((V+E) log V))에 비해 느림추가 기능: 음수 사이클(Negative Cycle) 존재 여부도 확인 가능알고리즘 동작 과정모든 정점의 거리를 무한대(∞)로 초기화하고, 시작 정점은 0으로 설정.V - 1번.. 2025. 3. 5.
[Software Engineering] Configuration Management Introduction1. 개요소프트웨어 형상 관리(SCM, Software Configuration Management)는 소프트웨어 개발 및 유지보수 과정에서 변경을 효과적으로 관리하는 기술 및 절차의 집합이다. 이는 소프트웨어 제품이 개발 및 배포되는 동안 일관성과 품질을 유지하기 위해 필요한 관리 기법을 포함한다. 2. 소프트웨어 형상 관리(SCM) 개념정의: 소프트웨어 엔지니어링 프로세스 내에서 특정 기준선을 설정하고 변경 사항을 평가 및 통제하는 관리 기법. 3. CMMI 내에서의 형상 관리CMMI(Capability Maturity Model Integration) 모델에서는 소프트웨어 구성 관리가 핵심 프로세스로 간주되며, 다음의 성숙도 수준으로 나뉜다:Level 1 - 초기(Initial.. 2025. 2. 23.
[Software Engineering] Software Maintenance and Evolution Software Maintenance and Evolution소프트웨어 변경 (Software Change)소프트웨어 변경은 불가피함소프트웨어 사용 중 새로운 요구사항이 발생비즈니스 환경 변화오류 수정 필요새로운 하드웨어 및 장비 도입성능 및 신뢰성 개선 필요기존 소프트웨어 시스템의 변경을 관리하는 것이 조직의 주요 과제소프트웨어 유지보수 및 발전 (Software Maintenance and Evolution)유지보수(Maintenance): 소프트웨어가 배포된 후 수정하는 작업유지보수, 발전(Evolution), 리엔지니어링(Reengineering)은 종종 같은 의미로 사용됨유지보수의 유형소프트웨어 결함 수정 유지보수시스템의 요구사항 충족을 위한 문제 해결운영 환경 변화에 따른 적응 유지보수새로운 .. 2025. 2. 23.
[Software Engineering] Debugging What is Debugging디버깅(Debugging)은 테스트 과정에서 발견된 오류를 수정하는 과정이다.디버깅 절차는 다음과 같이 진행된다:테스트 케이스 실행 → 오류 발생 → 원인 추정 → 원인 확인 → 수정 → 회귀 테스트(Regression Test) → 새로운 테스트 케이스 실행 디버깅 과정에서 오류의 증상과 실제 원인은 반드시 동일한 위치에 있거나 직접적으로 연결되지 않을 수도 있다. 다음과 같은 상황이 발생할 수 있다:증상과 원인이 지리적으로 분리될 수 있음 (Symptom and cause may be geographically separated)프로그램의 한 부분에서 문제가 발생했지만, 실제 원인은 다른 모듈이나 시스템에 있을 수 있다.예: 클라이언트 애플리케이션에서 UI가 깨지는 문제.. 2025. 2. 22.
[Software Engineering] Mutation Analysis, Automated Testing Mutation AnalysisMutation Analysis(돌연변이 분석)는 프로그램의 소스 코드나 바이트 코드에 의도적으로 변형(돌연변이)을 가하고 테스트를 실행하여, 테스트가 얼마나 효과적인지 평가하는 기법이다.목적테스트가 올바르게 작성되었는지 확인테스트가 소프트웨어 요구사항을 충분히 반영하고 있는지 검증개요Mutation Operators(변이 연산자)를 선택하여 원본 코드에 적용코드의 일부를 변형하여 Mutant(돌연변이 코드) 생성테스트 실행 후, 변경된 코드가 감지되면 Mutant는 "killed(사멸)" 되었다고 판단감지되지 않으면 해당 테스트가 충분히 강력하지 않다는 의미Weak and Strong Mutation Testing Mutation Operators (변이 연산자)문장 삭제.. 2025. 2. 21.
[Software Engineering] RBT, TDD, Test Coverage Risk-based Testing (RBT)1. What is Risk? 미래에 부정적인 결과를 초래할 수 있는 요소로, 일반적으로 영향(Impact)과 발생 가능성(Likelihood)으로 표현됨.2. Risk-based Testing 위험 식별 (Identify Risks)시스템의 어떤 부분에 위험이 있는지 식별위험 요소: 시스템 복잡도, 새로운 기술 사용, 부족한 비즈니스 지식, 코드 품질 등브레인스토밍 기법을 활용하여 최대 35개의 위험 요소 식별 가능위험 분석 (Analyze Risks)위험 점수 계산: 위험 = 영향(Impact) × 발생 가능성(Likelihood)발생 가능성을 결정하는 요소:복잡성, 재사용성, 인터페이스 개수, 크기, 기술, 개발팀의 경험 수준영향도를 결정하는 요소:사용자 .. 2025. 2. 20.
[Software Engineering] Testing Techniques White Box Testing화이트 박스 테스트는 소프트웨어의 내부 구조와 동작을 이해한 상태에서 수행하는 테스트 방법으로, 코드 기반 테스트라고도 한다. 내부 구현을 확인하면서 모든 논리 경로가 실행되도록 설계된다. 1. Basis Path Testing프로그램 내 모든 실행 경로를 검사하는 것이 목표.프로그램의 제어 흐름 그래프(Flow Graph)를 생성하여 노드와 간선(조건문)을 분석.독립적인 프로그램 경로(Independent Program Path)를 정의하여, 최소한의 경로만 테스트.사이클로매틱 복잡도(Cyclomatic Complexity)를 활용하여 테스트 경로의 개수를 산출.경로 계산 방법영역(region)의 수를 이용: V(G) = 영역의 개수간선(E)과 노드(N)을 이용: V(G).. 2025. 2. 19.
[Software Engineering] Software Testing 소프트웨어 테스트의 목표와 원칙(1) 테스트의 목표소프트웨어 테스트는 오류(결함, 버그)를 찾는 과정이다.성공적인 테스트란 아직 발견되지 않은 오류를 찾아내는 것이다.테스트는 버그가 없음을 증명하는 것이 아니라, 버그의 존재를 증명하는 것이다.(2) 소프트웨어 테스트의 원칙모든 테스트는 고객 요구 사항과 연계되어야 함→ 테스트는 고객의 요구 사항을 검증하는 방향으로 진행되어야 한다.테스트 계획은 가능한 빨리 수립해야 함→ 분석 모델이 완성되는 즉시 테스트 계획을 시작할 수 있다.파레토 법칙(80-20 법칙)이 적용됨→ 대부분의 오류(80%)는 코드의 일부(20%)에서 발생하는 경향이 있다.테스트는 작은 단위에서 큰 단위로 진행됨→ 개별 모듈부터 시작하여 전체 시스템까지 확장하는 방식이다.완벽한 테스트(모.. 2025. 2. 18.
[Software Engineering] Verification and Validation Verification and ValidationVerification (검증):"우리가 올바른 방식으로 제품을 만들고 있는가?'소프트웨어가 명세에 맞게 구현되었는지를 확인Validation (확인):"우리는 올바른 제품을 만들고 있는가?"소프트웨어가 사용자의 요구사항을 충족하는지를 확인차이점:Verification은 제품이 명세를 따르고 있는지 점검하는 과정Validation은 제품이 실제 사용자 요구를 충족하는지 평가하는 과정두 과정 모두 소프트웨어가 목적에 적합한지 확신을 가지게 하는 것이 목적 Two Complementary ApproachesSoftware Inspection (Static Verification)요구사항 문서, 설계 다이어그램, 소스 코드 등을 분석하여 문제를 발견Softwar.. 2025. 2. 17.
[Software Engineering] People Management Team Organization(1) 프로그래밍 팀 조직의 문제점프로젝트 완수를 위해 1년치 프로그래밍이 필요하지만, 3개월 내 완료해야 하는 경우 해결책으로 4명의 프로그래머를 배치한다고 가정.그러나 현실적으로 4명이 동시에 작업한다고 해서 시간이 1/4로 둘어들지 않으며, 품질 저하 가능성 존재.프로그래밍 팀은 서로 유기적으로 협력해야 하므로 복잡성이 증가.(2) 팀원 간의 협업 문제개발자가 모듈을 나누어 개발할 때, 인터페이스나 매개변수의 불일치 문제가 발생할 가능성이 큼.이는 기술적 능력 부족의 문제가 아니라 관리의 문제.(3) 커뮤니케이션 문제3명의 개발자가 있을 경우, 커뮤니케이션 채널은 3개.개발 마감이 다가와도 코드가 완성되지 않으면, 추가 개발자를 투입하는 것이 일반적인 해결책처럼 보이지.. 2025. 2. 16.
[Database Systems] Query Processing and Optimization Query ProcessingHigh-Level 쿼리 -> 스캔, 파싱, 유효성 검사 후, 쿼리의 중간 형태 -> 쿼리 최적화 후 실행 계획 -> 쿼리 코드 생성기가 쿼리 코드 생성 -> runtime DB processor가 쿼리의 결과 도출 Translating SQL Queries into Relational AlgebraSELECT-FROM-WHERE(-GROUP BY-HAVING)으로 이루어진 Basic Unit이 Algebraic operator로 변환된 후 최적화 된다. External SortingDB환경상에서 Disk에서 Main Memory에 한번에 로드할 수 없는 대용량 데이터를 정렬하기 위한 알고리즘으로 보통 JOIN, ORDER BY, 또는 DISTINCT를 수행하기 위해 사용한다.. 2025. 2. 15.
[Software Engineering] Agile Software Development Agile Software Development전통적인 Waterfall 모델의 한계를 극복하기 위해 등장한 소프트웨어 개발 방법론이다. 이는 팀 협업, 빠른 응답, 고객 중심 개발, 지속적인 개선을 중시하며, 변화하는 요구사항에 유연하게 대응할 수 있는 반복적(iterative)이고 증분적(incremental)인 개발 방식을 사용한다. 12 Principles of Agility1. 고객에게 가치 있는 소프트웨어를 조기에 지속적으로 전달함으로써 고객을 만족시킨다.2. 변화하는 요구사항을 환영한다. 개발의 후반부에서도 고객의 경쟁 우위를 높이기 위해 변경 사항을 수용한다.3. 짧은 주기로 동작하는 소프트웨어를 자주 전달한다.4. 비즈니스 담당자와 개발자는 프로젝트 전반에 걸쳐 긴밀하게 협력한다.5. 신.. 2025. 2. 14.
[Database Systems] Transactions, Concurrency Control TransactionsDB의 컨텐츠에 접근하거나 변경하기 위해 사용자 또는 애플리케이션에 의해 수행되는 일련의 ActionTransaction은 다음과 같은 두 가지의 결과를 낳을 수 있다.1. Failure: Transaction 실패 시, 이전 상태로 회복2. Success: Transaction 성공 시, 새로운 Consistent State로 전환 Properties of Transactions (ACID Properties)Atomicity: Transaction안에 있는 모든 action이 성공하거나, 성공하지 않아야 함Consistency: Transaction은 DB가 기존 Consistent State -> 새로운 Consistent State가 되게 함Isolation: 한 Transa.. 2025. 2. 13.

티스토리툴바