알고리즘문제해결전략 p189 문제 울타리 잘라내기 (문제ID:FENCE, 난이도 중) 알고스팟 링크 풀이 개인적으로 분할정복 문제는 아직 어려워서 고생을 좀 했다. 분할정복 문제가 으레 그렇듯이 나누는 개념 자체는 어렵지 않다. 가운데를 자르고 앞의 절반의 최대값과 뒤의 절반의 최대값을 구해 비교한다. 물론 이 때 분할되는 부분을 처리해주어야 한다. 즉, 잘리는 부분의 울타리 2개를 포함하는 최대값을 구해서 같이 비교해 주어야 한다. 이 때, 이 가운데 부분을 처리하는 부분이 주된 문제인데 절반씩 줄어드므로 logN번 반복되는 연산으로 이 연산을 N시간에 해내야 NlogN으로 풀 수 있다. 내가 처리한 방법은 가운데 2개의 울타리에서 시작해서 좌우로 넓어지면서 최대값을 구하는 것이다. 이때 커지는 방향을..
알고리즘문제해결전략 p189 문제 쿼드 트리 뒤집기 (문제ID:QUADTREE, 난이도 하) 알고스팟 링크 풀이 분할 정복 카테고리에 있지만 문제의 내용 자체가 분할 정복의 원리를 사용한 것일 뿐이고 실제로 풀이는 그냥 stack을 사용해서 하면 된다. (DFS) 풀이의 아이디어는 상하를 뒤집는 방법에 있어서, x마다 하위의 노드들을 전부 앞뒤로 바꿔주면 전체적으로 상하로 뒤집은 결과가 된다는 것. 책의 그림 7.6과 그 밑에 개념적인 설명이 잘 되어있으니 잘 읽어보자 그걸 구현 하는 방법은 stack을 통해서 뒤집을게 모이면 계속 뒤집어 주면 된다. 단지 살짝 주의해야 하는 점은 뒤집은 직후에 그 뒤집었던 x를 루트로 하는 부분트리가 상위 x의 4번째 node였을 때 곧바로 한번 더 뒤집어야 한다는 점..
알고리즘문제해결전략 p168 문제 시계 맞추기 (문제ID:CLOCKSYNC, 난이도 중) 알고스팟 링크 풀이 이 문제는 완전탐색의 탈을 쓴 연립방정식 문제이다. 전체 경우의 수가 4^10이므로 완전탐색을 하라고 책에서는 말하지만 많은 사람들이 손으로 연립방정식을 풀고 그냥 옮겨 적어서 풀었다. 나도 상호 종속적인 몇 개의 버튼을 적당히 거르고 적당히 코드로도 검증을 해서 풀었다. 완전탐색으로 구현하고 싶다면 한 스위치를 4번 누르는것은 0번 누르는 것과 같다는 것만 명심하면 된다. 그래서 나온 경우의 수가 4^10으로 그냥 모든 버튼의 모든 경우의 수를 적당히 구하면 된다. 약 100만개 정도라서 아마 시간이 오래 걸릴 것 같지는 않다. 코드 이 코드는 AC를 받은 코드지만 별로 참고하기는 좋은 코드가 ..
알고리즘문제해결전략 p159 문제 게임판 덮기 (문제ID:BOARDCOVER, 난이도 하) 알고스팟 링크 풀이 나는 2차원 입력값을 브루트포스로 뭔가 시뮬레이팅 하는 문제가 제-일 싫다. 그래서 원래 이 포스팅을 시작하면서 한번 풀었던 문제도 다시 풀려고 마음 먹었는데 이 문제는 그냥 옛날 코드를 조금 손보기만 했다. 아이디어는 좌상단에서 우하단으로 좌표를 이동시키면서 빈 칸이 있으면 재귀호출을 하는 방식으로 4가지의 블럭 모양의 기준을 좌상단 좌표로 맞추는게 핵심이다. (위나 왼쪽으로 삐져나가지 않는 방법으로) 이렇게 했을 경우에 항상 한번 지나온 좌표는 더 이상 신경 쓸 필요가 없기 때문에 한번의 DFS로 모든 경우의 수를 다 찾을 수 있다. 조금 깔끔하게 코드를 쓰기 위해서 '.' 과 '#'을 각각..
알고리즘문제해결전략 p155 문제 소풍 (문제ID:PICNIC, 난이도 하) 알고스팟 링크 풀이 입력 크기가 작고 메모리나 시간도 넉넉하기 때문에 큰 고민없이 DFS를 했다. 재귀 함수 안에서 중복을 검사하는 students리스트를 집합으로 하면 더 빠르게 동작할 거라고 생각되지만 집합이 정렬을 보장해 주지 않기 때문에 리스트를 사용했다. 따라서 시간복잡도가 좋지는 않은 것 같다. (매번 검사를 할때마다 리스트의 길이 만큼의 시간이 소모되므로) 하지만 정답을 받는데는 문제가 없었으므로 pass 만약 시간적으로 더 개선이 필요하다면 중복처리를 숫자 자체를 집어넣은 리스트가 아니라 포함 유/무를 bool형으로 관리해주면 훨씬 더 개선될 거라고 생각한다. (책에서도 그렇게 관리 한 것 같다.) 코드
최조 작성일 : 2019.02.11 출처 및 참고자료 유니티 모바일 최적화 문서 : https://docs.unity3d.com/kr/current/Manual/MobileOptimizationPracticalGuide.html수양버들님의 블로그 : https://egohim.blog.me/70170987774어른이의 공부방 : https://usroom.tistory.com/entry/효과적인-C-메모리-관리-기법?category=553244 1. 오브젝트 풀링(object pooling) 짧게 사용되고 사라진 뒤에 다시 사용되는 오브젝트의 경우 (총알이나 퍼즐게임의 블럭등)매 번 다시 생성/해제를 반복하면 메모리 부하가 심해진다.그래서 화면에 보이지 않게만 하고 해제시키지 않은 채로 필요할 때 마다 ..