VA - 11 HALL - A

Zenject Zenject(ExZenject)는 Unity에서 사용할 수 있는 무료 DI 프레임워크이다. 이 글에서는 DI가 무엇이며, 이를 왜 사용하는 것이고, 어떻게 활용할 수 있는지에 대해 정리했다. 의존 관계 역전 원칙(DIP, Dependency Inversion Principle) 프로그래머는 추상화에 의존해야 하고, 구체화에 의존하면 안 된다. 게임을 개발을 예시로 들어보자. 각 유닛은 무기를 가지고 있고, 무기는 각각의 대미지가 있다. 여기서 상대를 공격하는 코드를 작성하면 다음과 같다. public class Unit { private int _hp; private Normal_weapon; public void ReceiveDamage(int amount) { _hp -= amount..

외판원 문제(外販員問題, 영어: traveling salesman problem) 또는 순회 외판원 문제는 조합 최적화 문제의 일종이다. 줄여서 TSP라고도 쓴다. 이 문제는 NP-난해에 속하며, 흔히 계산 복잡도 이론에서 해를 구하기 어려운 문제의 대표적인 예로 많이 다룬다. 정의 여러 도시들이 있고 한 도시에서 다른 도시로 이동하는 비용이 모두 주어졌을 때, 모든 도시들을 단 한 번만 방문하고 원래 시작점으로 돌아오는 최소 비용의 이동 순서를 구하는 것이다. 그래프 이론의 용어로 엄밀하게 정의한다면, "각 변에 가중치가 주어진 완전 그래프(weighted complete graph)에서 가장 작은 가중치를 가지는 해밀턴 순환을 구하라"라고 표현할 수 있다. 이 문제는 반드시 시작점으로 돌아와야 한다는..

https://www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 정렬을 통해서 푸는 방법은 $O(N^{2}\log(N))$의 시간 복잡도가 필요하니 제한 시간에 걸려 풀 수 없고, 나는 최소 힙과 최대 힙을 통해 풀었다. 최대 힙으로 구현된 left, 최대 힙으로 구현된 right 변수를 각각 만들어준다. 어떤 정수 n이 입력으로 들어올 때, left에 있는 원소 중 최댓값(최대 힙으로 구현되어 있으니 $O(\log(N))$의 시간복잡도로 구할..

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 문제 정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다. A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주�� www.acmicpc.net 이전 글에서 설명한 부분 배열의 합과 상당히 유사하게 풀 수 있는 문제. 문제를 그대로 받아들이고 풀 경우 $O(N^4)$으로 최대 $4000^4 = 2.56e+14$, 약 256조정도의 경우의 수가 존재한다. 하지만 A[a], B[b], C[c], D[d]의 합의 종류는 가능한 (A[a] + B[b])들과 가능한 (C[c] +..

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 부분수열의 합 1과 다른 점은, N의 제한이 [1, 40]이라는 것이다. 때문에 N = 40일 경우 $2^{n}=10^{12}$라는 어마어마한 값이 나온다... 수열을 반으로 쪼개 각 부분수열의 합을 구한다음, 투 포인터를 사용해 두 수열의 합이 S가 나올 수 있는 경우를 돌아보면 된다. N과 S는 각각 6과 4라고 가정할 때, 구한 두 부분수열의 합을 정렬..

https://www.acmicpc.net/problem/4902 4902번: 삼각형의 값 문제 오른쪽 삼각형은 9개의 단위 삼각형이 총 3줄(N=3)로 이루어져 있다. 단위 삼각형은 N=1인 삼각형이다. 이때, 그림에서 서로 다른 부분 삼각형은 총 13개가 있다. (N=1인 삼각형이 9개, N=2인 삼각 www.acmicpc.net 단위 삼각형들로 이루어진 하나의 정삼각형이 주어지고, 그 정삼각형의 부분 삼각형들의 합 중 가장 큰 값을 찾는 문제이다. 줄의 개수가 n개일 때 나올 수 있는 부분 삼각형의 수는 $$\sum_{k = 1}^{n} (2n-1)$$ 으로, 식을 정리하면 $n^{2}$ 개가 된다. 줄의 개수가 400개 미만이기 때문에 나오는 부분 삼각형의 수는 그리 많지 않다. 그렇다면 각 부분..

https://www.acmicpc.net/problem/16988 16988번: Baaaaaaaaaduk2 (Easy) 서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 www.acmicpc.net 가끔씩 있는 서론이 긴 문제다. 이런거 읽는것도 소소한 재미 중 하나 브루트포스로 풀었을 때 놓을 위치 두 가지를 선택하는 것은 O((NM)^2)이고, BFS(물론 DFS로 구현해도 된다)를 통해 바둑판 위의 돌들에 대해 죽었는지 아닌지를 판단하는 건 O(NM)의 시간 복잡도가 든다. N과 M이 최대 20으로 작기 때문에, O((NM)^3)의 시간복잡도를..

https://www.acmicpc.net/problem/17406 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 말 그대로 배열을 돌린다. 가능한 회전 연산의 수는 최대 6가지이니 O(K!)에서 6! = 720 회전은 구현하기는 복잡해 보여도 시간 복잡도가 크진 않으니 무식한 방법으로 1초 안에 풀 수 있겠다. 배열 자체를 복사해도 딱히 타임아웃이 나지는 않는다. 값 형식으로 전달하면 코드도 깔끔해지고 어차피 배열을 다시 바꾸려면 벡터를 만들어야 하기에 그 방법으로 바꿨다. K..

https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 간단한 문제다. 순열을 생성해서 풀 수도 있고, 재귀함수로 가능한 경우를 모두 탐색해도 풀 수 있고, 비트마스킹을 써서 풀 수도 있다. 재귀함수로 가능한 경우를 모두 탐색하는 경우는 치킨 집이 N개 존재한다면, N개의 치킨집에 대해 각각 고른다/고르지 않는다를 선택할 수 있으니 O(2^N)이다. 순열이나 비트마스킹으로 푸는 경우 또한 치킨집의 개수가 N개일 때, (1 M; f..

https://www.acmicpc.net/problem/17088 17088번: 등차수열 변환 크기가 N인 수열 A = [A1, A2, ..., AN]이 있을 때, 모든 1 ≤ i < N에 대해서, Ai+1-Ai가 모두 일치하면 등차수열이라고 한다. 예를 들어, [3], [6, 6, 6], [2, 8, 14, 20], [6, 4, 2]는 등차수열이고, [4, 5, 4], [6, 3, 1]�� www.acmicpc.net 간단하게 생각해서 모든 원소에 -1 연산을 수행하는 경우, 아무 연산도 적용하지 않는 경우, +1 연산을 수행하는 경우로 나눌 수 있다. 하지만 입력의 최댓값이 수열 B의 크기가 N(1 ≤ N ≤ 10^5), 원소의 크기가(1 ≤ Bi ≤ 10^9)로 매우 크기 때문에 시간 복잡도가 O..