전체 글

[Algorithm] 최대 유량 문제

Maximum Flow Problem란? Source s에서 Target t까지 최대한 보낼수 있는 유량을 구하는 문제 Ford-Fulkerson method Residual Network에서 augmenting path가 더이상 존재하지 않을때까지 path에 augment값만큼 flow를 늘려나간다. 수도코드 1 Initialize flow f = 0; while( there exists an augmenting path p in Gf ) { augment the flow along p; } Output the final flow f; 수도코드 2 Ford-Fulkerson(G, s, t) { for (each edge (u, v) in E) f(u,v) = 0; f(v,u) = 0; // Gf : R..

[Algorithm] 최대 이분 매칭 문제

문제 Given a bipartite undirected graph G=(XUY, E), find the maximum-cardinality matching M*. 주어진 이분 비방향 그래프 G에서 (중복되지 않는) 최대 매칭 집합크기를 구해라. Matching이란? A subset M of E is called Matching if no two edges in M are adjacent in G. E의 부분집합 M에 인접한 두 edge가 존재하지 않는다면, M은 Matching이라고 부른다. 성질 In a bipartite undirected graph G=(XUY,E), if every vertex has degree k>0, then there exists a perfect matching M. 이..

[Project] Whodunit

프로젝트 개요 2021년 1학기 수업 'Co-op 실감형 게임 콘텐츠 개발트랙' 기말과제로 제출한 실감형 1인칭 추리 게임 실감나는 공간을 구현하고, 배경지식없이 단서와 논리적 사고로 살인사건의 전말을 추리할 수 있도록 노력했다. 개발기간 1달 개발 팀 Team Cipher (총 4명) 메인 기획 : 1명 < 본인 메인 개발 : 2명 메인 아트 : 1명 참여 부분 기획 추리(살인) 시나리오와 트릭을 기획했다. 시스템 명세를 기획했다. 인테리어 공간 기획했다. 프로그래밍 Unity Shader Graph로 필요한 Shader를 제작했다. Object Interact 시스템을 제작했다. 아트 주방, 식당의 오브젝트를 구하거나 제작해서 공간을 구현했다. 개발 툴, 구현 기능 Google Docs 시나리오(배경..

[Art] 도트 몰?루

그냥 해보고싶어서 찍어보았다

[BOJ] 6086번: 최대 유량

6086번: 최대 유량 첫째 줄에 정수 N (1 ≤ N ≤ 700)이 주어진다. 둘째 줄부터 N+1번째 줄까지 파이프의 정보가 주어진다. 첫 번째, 두 번째 위치에 파이프의 이름(알파벳 대문자 또는 소문자)이 주어지고, 세 번째 위 www.acmicpc.net 제한 조건 - 시간 제한 : 1s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 0ms - 사용 공간 : 1352KB - 시도 회수 : 6회 풀이 설명 - 최대 유량문제 - Ford-Fulkerson method에서 augmenting path를 DFS순서대로 찾는 Edmonds-Karp Algorithm을 사용하였다. - capacity[u][v] : u에서 v로 갈수있는 해당 파이프의 최대 용량 - flo..

[BOJ] 1162번: 도로포장

1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 100ms - 사용 공간 : 7068KB 풀이 설명 - 우선순위 큐를 이용한 다익스트라 순회를 하는 문제이다. - 또한 포장 횟수를 구분하면서 최소비용을 계산해야하기 때문에 Dynamic Programming을 해야한다. - DP[i][j] : 도로를 j번 포장하여 도시 i번에 도달하는 최소비용 - 위의 DP..

[BOJ] 1738번: 골목길

1738번: 골목길 첫째 줄에 골목길들이 교차하는 지점의 개수 n (2 ≤ n ≤ 100)과 골목길의 개수 m (1 ≤ m ≤ 20,000) 이 차례로 주어진다. 이어지는 m개의 행에 각각의 골목길을 나타내는 세 정수 u, v, w가 차례로 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 20ms - 사용 공간 : 1388KB 풀이 설명 - 밸맨포드 알고리즘 - 시작점에서 다른 점들까지 최소도달비용을 구할수 있는 알고리즘은 밸맨포드와 다익스트라 알고리즘이 있다. - 밸맨포드는 음의 가중치를 갖고있는 경로또한 계산 가능하므로 이를 사용하였다. - 밸맨포드 알고리즘을 돌리려면 비용이 음의 사이클이 존재해서는 ..

[Project] Unity HDRP Metro

프로젝트 개요 2021년 2학기 수업 'Co-op 실감형 게임 콘텐츠 개발트랙' 중간과제로 제출한 프로젝트 서울 교통공사 2호선 2000호대 VVVF 전동차 객실을 컨셉으로 제작함 주 개발기간 2~3 주 개발 팀 모델링, 텍스쳐, 스크립트 : 본인 개발 툴, 구현 기능 - Maya Low Poly Mesh 제작, UV mapping을 작업 - Zbrush Subdivide, Surface Noise, Draw 처리를 통해 High Poly Mesh를 제작 - Subtance Painter High Poly Mesh를 사용하여 Normal Map을 Bake 오브젝트와 어울리는 Texture Material Layer를 제작 - Unity High-Definition Render Pipeline 프로젝트 생..

[Project] 팩-챤! (Pac-Chan!)

프로젝트 개요 남코의 유명게임 Pac-man을 Unity-Chan!과 3D로 재해석한 게임 개발기간 2020.06 ~ 2020.08 개발 인원 1인 개발 사용 툴 Unity Engine Blender (3D 애니메이션 제작) 구현한 기능 Third-person Joystic Controller Ghost AI (Coroutine FSM) Minimap SceneLoading Animation Google Play Login 미구현한 기능 Google Play Scoreboard Google Play 도전과제 프로젝트 의의 첫 정식 출시한 게임 (Google Play Store) 출시하여 모르는 유저들에게 피드백을 받은 최초의 게임 (미니맵 추가해줌) 귀여운 유니티짱 에셋을 나름 잘 활용한 프로젝트 사용 ..

[BOJ] 2152번: 여행 계획 세우기

2152번: 여행 계획 세우기 첫째 줄에 네 정수 N, M, S, T가 주어진다. 다음 M개의 줄에는 각각의 비행로에 대한 정보를 나타내는 서로 다른 두 정수 A, B(1 ≤ A, B ≤ N)가 주어진다. 이는 A번 도시에서 B번 도시로 이동하는 항공 www.acmicpc.net 제한 조건 - 시간 제한 : 2s - 공간 제한 : 128MB 풀이 사용 - 사용 언어 : C++17 - 사용 시간 : 640ms - 사용 공간 : 15680KB 풀이 설명 - 플레3 문제 너무 어렵다. - directed cyclic graph를 SCC(Strongly Connected Components)로 묶어 DAG(Directed Acyclic Graph)로 바꾼다. - 이후 DAG에서 시작 SCC부터 끝 SCC까지 가..