📝 Computer Science

[C++] 이분 그래프

이분 그래프 1. 개념 이분 그래프란 인접한 정점끼리 서로 다른 색으로 칠하여 모든 정점을 두 그룹으로 나누고, 서로 다른 그룹의 정점을 간선으로 연결한 그래프를 말한다. 2. 이분 매칭 알고리즘 이분 매칭이란 이분 그래프에서 한쪽 그룹(A)과 다른 한쪽 그룹(1)이 매칭을 했을 때 최대 유량을 구하는 문제를 말한다. 3. 문제 https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net #include #include #include #include us..

[Git] Git README, .gitignore 파일

Git Repositories를 만들 때, README 파일과 .gitignore 파일을 생성할 수 있다. README 파일 README 파일은 프로젝트와 리포지토리를 설명하는 책의 표지와 같은 문서이다. 프로젝트 소개, 사용한 기술, 활용 방법 등을 기록한다. 파일의 확장자는 md로 마크다운(Markdown)의 약자이다. https://coding-factory.tistory.com/620 [Git] GitHub README 작성법 (마크다운, 이미지, Gif, 코드 블록 사용법) 리드미(README)란? README는 쉽게 말해서 프로젝트 소개글이라고 할 수 있습니다. 일반적으로 디렉토리나 압축 파일에 포함된 기타 파일에 대한 정보를 포함하고 있으며, 일반적으로 소프트웨어와 coding-factory..

[C++] 편집 거리 알고리즘(Edit Distance Algorithm)

편집 거리 알고리즘 1. 개념 편집 거리 알고리즘(Edit Distance Algorithm)은 두 개의 문자열 A, B가 주어졌을 때, 두 문자열이 얼마나 유사한 지를 알아낼 수 있는 알고리즘이다. 즉, 문자열 A가 문자열 B와 같아지기 위해서는 몇 번의 연산을 진행해야 하는지 알 수 있다. 여기서의 연산이란 삽입(Insertion), 삽입(Deletion), 대체(Replacement)를 말한다. 문자열 간의 유사도 측정처럼 기본적으로는 두 데이터 사이의 유사도를 알아내기 위해 사용할 수 있으며 특히 프로그램의 표절 여부, 철자 오류 검사 등에 사용할 수 있다. 2. 기본 원리 3. 문제 https://leetcode.com/problems/edit-distance/description/ Edit D..

컴포지트 패턴(Composite Pattern)

컴포지트 패턴(Composite Pattern) 컴포지트 OOP에서 컴포지트는 하나 이상의 유사한 객체로 구성된 집합 객체로 모두 유사한 기능을 나타낸다. 이를 통해 객체 그룹을 조작하는 것처럼 단일 객체를 조작할 수 있다. 컴포지트 패턴 컴포지트 패턴은 복합 객체나 단일 객체를 동일하게 취급하는 것을 목적으로 한다. 트리 구조로 작성하여 전체-부분(whole-part) 관계를 표현한다. 1. 구현 사용자는 Leaf와 Composite 클래스를 직접 참조하지 않고, 공통 인터페이스 Component를 참조한다. 1) Component 모든 Component들을 위한 추상화된 개념이다. Leaf와 Composite 클래스의 인터페이스이다. interface Graphic { public void print..

스트래티지 패턴(Strategy Pattern)

스트래티지 패턴(Strategy Pattern) 전략 패턴이란 비슷한 동작을 하지만 다르게 구현되어 있는 행위(전략)들을 공통의 인터페이스를 상속받는 각각의 클래스로 구현하고 동적으로 바꿀 수 있도록 하는 패턴이다. 전략 패턴으로 구현된 코드는 직접 행위에 대한 코드를 수정할 필요 없이 전략만 변경하여 유연하게 확장할 수 있게 된다. 1. 구현 만약 전략 패턴을 사용하지 않는다면, 단순히 if-else를 사용하여 구현해야 하며 게임이 업데이트되어 직업이 추가되거나 수정이 필요하다면 attack() 메서드를 수정해야 할 것이다. class Character { private final String job; Character(String job) { this.job = job; } void attack() ..

[게임 프로그래밍 패턴] 게임 개발에서 사용되는 디자인 패턴

게임 개발에서 사용되는 디자인 패턴 게임 개발의 관점에서 각 디자인 패턴에 대해서 다룰 것이다. 그러나 모든 앱이나 게임 개발에서도 적용된다. 1. Singleton Design Pattern 프로그램이 시작될 때 클래스가 최초 한 번만 메모리를 할당하고 그 메모리에 인스턴스를 만들어 사용 2020.05.16 - [📝/✏ Design Pattern] - 싱글톤 패턴(Singleton Pattern) 게임에서는 영화처럼 한 명의 디렉터가 존재한다. 디렉터는 게임에서 일어나는 모든 것을 수행하는 클래스이다. 오브젝트를 랜더링 하고 위치를 업데이트하고 플레이어의 입력을 정확한 캐릭터에 전달해 주는 등의 역할을 수행한다. Singleton 패턴을 통해 디렉터가 하나 이상 생성되는 것을 방지한다. 2. Strat..