Game Tech Blog

자랑할 만한 일도 아니지만 브론즈에서 올라오는데 의외로 많은 문제를 풀어야했다. 급하게 준비하고 bfs,dfs 를 많이 풀어서 내용 정리를 못한 부분도 있으나, 추후 정리가된다면 포스팅할 예정.

DFS / BFS 란? 그래프 탐색 알고리즘들 이다. 이들을 사용해서 구할 수 있는건 무엇인가? 1) 최단 경로 구하기 2) 지나온 경로 구하기 3) 사이클링 구하기 4) 조합 수들 구하기 정도가 있다. DFS / BFS 의 차이점은 무엇인가? 1) DFS => 루트에서 시작해서 시작한 가지를 완전히 탐색 후 다음 분기를 탐색하는 방식 => Stack, 재귀함수를 이용해 구현한다. a) 장점 i) 인접한 관계가 아닌 Depth 상 깊이 있을때, BFS 보다 더 우선적으로 탐색된다. ii) 일련의 다른분기로 넘어가기 전에, 끝까지 탐색하면서 완전 탐색을 수행한다. b) 단점 i) 앞 선, 가지의 수가 많은 경우에 매우 비효율적이다. c) 사용효율 i) 모든 노드를 방문 할 경우, DFS ii) 서로 다른 ..

[문제] 주몽은 철기군을 양성하기 위한 프로젝트에 나섰다. 그래서 야철대장을 통해 철기군이 입을 갑옷을 만들게 하였다. 야철대장은 주몽의 명에 따르기 위하여 연구에 착수하던 중 아래와 같은 사실을 발견하게 되었다. 갑옷을 만드는 재료들은 각각 고유한 번호를 가지고 있다. 갑옷은 두 개의 재료로 만드는데 두 재료의 고유한 번호를 합쳐서 M(1 ≤ M ≤ 10,000,000)이 되면 갑옷이 만들어 지게 된다. 야철대장은 자신이 만들고 있는 재료를 가지고 갑옷을 몇 개나 만들 수 있는지 궁금해졌다. 이러한 궁금증을 풀어 주기 위하여 N(1 ≤ N ≤ 15,000) 개의 재료와 M이 주어졌을 때 몇 개의 갑옷을 만들 수 있는지를 구하는 프로그램을 작성하시오. [입력] 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ ..

[문제] 윤영이는 3의 배수 마니아이다. 그는 모든 자연수를 3개의 3의 배수의 자연수로 분해하는 것을 취미로 가지고 있다. 문득 그는 자신에게 주어진 수를 3개의 3의 배수로 분리하는 경우의 수가 몇 개인지 궁금해졌다. 하지만 윤영이는 마지막 학기이기 때문에 이런 계산을 하기에는 너무 게을러졌다. 그래서 당신에게 이 계산을 부탁했다. 즉, 임의의 3의 배수 자연수 n이 주어졌을 때, 해당 수를 3의 배수의 자연수 3개로 분리하는 방법의 개수를 출력해라. 단 분해한 수의 순서가 다르면 다른 방법으로 간주한다. 예를 들어 12 = 3 + 6 + 3 과 12 = 3 + 3 + 6 은 다른 방법이다. [입력] 임의의 3의 배수 자연수 n이 주어진다. (3 ≤ n ≤ 3000) [출력] 자연수 n을 분해하는 방..

[문제] 세준이는 기말고사를 망쳤다. 세준이는 점수를 조작해서 집에 가져가기로 했다. 일단 세준이는 자기 점수 중에 최댓값을 골랐다. 이 값을 M이라고 한다. 그리고 나서 모든 점수를 점수/M*100으로 고쳤다. 예를 들어, 세준이의 최고점이 70이고, 수학점수가 50이었으면 수학점수는 50/70*100이 되어 71.43점이 된다. 세준이의 성적을 위의 방법대로 새로 계산했을 때, 새로운 평균을 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 시험 본 과목의 개수 N이 주어진다. 이 값은 1000보다 작거나 같다. 둘째 줄에 세준이의 현재 성적이 주어진다. 이 값은 100보다 작거나 같은 음이 아닌 정수이고, 적어도 하나의 값은 0보다 크다. [출력] 첫째 줄에 새로운 평균을 출력한다. 실제 정답과 출..

[문제] 자연수 N과 정수 K가 주어졌을때 이항계수를 구하는 프로그램을 작성하시오. [입력] 첫째 줄에 N와 K가 주어진다. ( 1 r; int ret= facto(n)/(facto(n-r)*facto(r)); cout

[순열 - 재귀 방식] 재귀 방식 커스텀 순열은 지겹도록 반복해서 코드를 외워버렸다. 이해하는 손 디버깅에도 반복했던 시간을 다하면 못해도 2시간이상은 할당했던것 같다. void permutation(int n, int r, int depth) { if (depth == r) { permutationPrint(); return; } for (int i = depth; i < n; ++i) { swap(a[i], a[depth]); permutation(n,r,depth+1); swap(a[i], a[depth]); } } void permutationPrint() { for (int i = 0; i < (sizeof(a) / sizeof(int)); ++i) cout

코딩테스트에 사용하기 위해 공부하고 있는 언어는 C++ 이다. 제대로 처음 했을때 공부했던 언어가 다이렉트X를 다루기 위한 C++ 이기도 했고, 더 성장하기 위해선 Unity 도 좋지만 Unreal 도 충분히 매력적인 엔진이라고 생각하여 선택했다. [Split] -> C++ 에는 다른 많은 함수들이 제공된다고 들었으나, Split에 관해서는 커스텀으로 만들어야 한다는 강의 내용이 있어서 작성해보았다. 초안 작성 후 버그나는 부분들은 참고했으니 거의 교안과 동일하다. #include #include #include #include #include #include using namespace std; class Functions { public:vector Split(string s, string delim..