📝 Computer Science

교착상태(Deadlock)

교착상태(Deadlock) 둘 이상의 프로세스가 공유 자원을 무한정 기다리고 있고 공유 자원을 사용 중인 프로세스는 진입 대기 중인 프로세스가 진행돼야만 빠져나올 수 있는 상황 1. 4가지 조건 상호 배제(Mutual Exclusion): 한 번에 한 프로세스만 자원 사용 점유와 대기(Hold & Wait): 공유 자원에 대한 접근 권한을 갖고 있는 프로세스가 다른 자원에 대한 접근 권한을 요구 비선점(Non-preemptive): 다른 프로세스가 자원 접근 권한을 강제로 빼앗을 수 없다. 환형 대기(Circular Wait): 두 개 이상의 프로세스가 자원 접근을 기다리는데 그 관계에 사이클 존재 2. 해결법 예방 기법: 4가지 조건 부정 회피 기법: 교착 상태 발생 시 피해나가는 방법 은행원 알고리즘..

[Git] Git Flow

Git Git은 서버를 분산시켜 구축할 수 있게 하는 소프트웨어로 지역 저장소를 만들고 파일, 코드 등을 관리하는 작업을 한다. GitHub는 Git으로 관리하는 자료를 다른 사람과 공유하거나 백업할 수 있는 웹 사이트이다. Git Flow 기본 브랜치는 5가지를 이야기한다. feature > develop > release > hotfix > master 브랜치가 존재하며 머지 순서는 앞에서 뒤로 진행된다. release 브랜치와 hotfix 브랜치의 경우, develop 브랜치의 오른쪽에 존재하기에 모두 develop 브랜치도 머지를 하도록 구성이 되어있다. 1) Master Branch 제품으로 출시될 수 있는 브랜치로 배포(Release) 이력을 관리하기 위해 사용. 즉, 배포 가능한 상태만을 관..

[C++] 트라이(Trie)

트라이(Trie) 여러 문자열을 효율적으로 저장하고 탐색하기 위한 트리 형태의 자료구조로 시간 복잡도는 O(n)이다. 기본 원리 struct Trie { Trie* next[26]; bool finish; Trie() :finish(false) { for (int i = 0; i < 26; ++i) next[i] = NULL; } ~Trie() { for (int i = 0; i < 26; i++) if (next[i]) delete next[i]; } void insert(const char* key) { if (*key == 0) { finish = true; return; } int curr = *key - 'a'; if (next[curr] == NULL) next[curr] = new Trie(..

TDD(Test Driven Development)

TDD(Test Driven Development) 테스트가 개발을 이끌어 나간다. 반복적인 테스트와 수정을 통해 고품질의 소프트웨어를 탄생시킬 수 있다. 개발자는 요구되는 새로운 기능에 대한 자동화된 테스트 케이스를 작성하고 해당 테스트를 통과하는 가장 간단한 코드를 작성한다. 일단 테스트 통과하는 코드를 작성하고 상황에 맞게 리팩토링하는 과정을 거친다. 장점 작업과 동시에 테스트를 진행하면서 실시간으로 오류 파악이 가능하다. 짧은 개발 주기를 통해 고객의 요구사항 빠르게 수용, 피드백이 가능하고 진행 상황 파악이 쉽다. 자동화 도구를 이용한 TDD 테스트케이스를 단위 테스트로 사용이 가능하다. 단점 기존 개발 프로세스에 테스트케이스 설계가 추가되므로 생산 비용이 증가한다. 테스트의 방향성, 프로젝트 ..

동시성(Concurrency)과 병렬성(Parallelism)

동시성(Concurrency)과 병렬성(Parallelism) 1. 동시성(Concurrency) 싱글 코어에서 멀티 스레드를 동작시키기 위한 방식 멀티 태스킹을 위해 여러 개의 스레드가 번갈아가면서 실행되는 성질을 말한다. 각 스레드들이 병렬적으로 실행되는 것처럼 보이지만 사실은 번갈아가면서 조금씩 실행되고 있는 것이다. 즉 동시에 실행되는 것처럼 보이는 것이다. 독립적으로 실행하는 프로세스들을 구성한다. 1명이 5개의 작업을 빠른 시간에 이것저것 실행한다. 문맥 교환이 발생한다. 2. 병렬성(Parallelism) 멀티 코어에서 멀티 스레드를 동작시키는 방식 한 개 이상의 스레드를 포함하는 각 코어들이 동시에 실행되는 성질을 말한다. 멀티 코어에서도 동시성 사용이 가능하다. 5명이 5개의 작업을 동시..

[C++] 유니온 파인드(Union-Find)

유니온 파인드(Union-Find) 서로소인 집합들을 분할하여 저장한 집합 Union(): 두 집합의 루트 부모를 합침 Find(): 자신의 루트 부모를 찾아 계속해서 거슬러 올라가는 과정 문제 https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1≤n≤1,000,000), m(1≤m≤100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미이다. 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산은 1 a b의 형태로 입력이 주어진다. 이는 a와 b가 같은 집합에 포함되어..