강정이좋아의 생각조리실

 9663번 N-Queen 문제를 제 시간(1시간) 에 풀지 못했다...
 나름 유명한 문제고 못하지는 않는다는 생각에 가볍게 도전했다가, 거대한 망치로 크게 뒤통수를 맞은 기분이다.
 접근방식은 맞... 았다고 할 수가 없다. 문제 해결의 원리를 전혀 파악하지 못했으니까...

  제대로된 가지치기도 못하고 그냥 완전 탐색으로 풀려고하니... 그게 되나... 바보야...

  내가 한 실수 중 가장 큰 것은 가지치기 접근을 잘못 한것이다.
 "시간초과"가 났을 때, 문제의 원리에 초점을 두고 어떻게 해야 불필요한 부분을 생략할 수 있는지를 생각해야하는데, 시스템적-if문을 쓰지 말 것, memcpy로 이전 배열을 복사하는게 아니라 대신 이중 for문으로 배열 초기화 하는것-으로 어떻게 해야하는지 보고있으니... 
정말 바보같다...
알고리즘 공부하고 있는거 맞니??? 에휴...

  오늘의 충격을 토대로 다른 문제 풀 때, 더욱 기운내서 머리를 회전시키자!!! 파이팅!!! ...흑흑흑

 *** 문제 : https://www.acmicpc.net/problem/9663

[옳은 접근 방식] (정답)
  일반적으로 경우의 수를 구하는 문제는 백트래킹으로 전체탐색을 한다. 그 중 중요한 것이 '가지치기'로 전체탐색을 할 때, 불필요한 부분을 탐색하지 않게 하는 것이다. 따라서, 문제의 원리를 파악해 불필요한 탐색을 줄여 "시간초과"를 면하는게 해당 문제의 본질이라고 할 수 있다.
  체스에서 퀸은 가로, 세로, 대각선 어디든 갈 수 있는 말이다. 그렇기 때문에, N x N 체스판에 N개의 퀸을 놓는 상황이라면, 1행에 1개의 퀸만 둘 수 있다. 퀸이 하나라도 있는 줄에는 다른 퀸을 절대로 놓을 수 없기 때문이다. 
  따라서, 체스판이 2차배열 형태라고 이중for문을 해주는 것이 아니라, 퀸이 놓여있는 행만 탐색해 주면된다.
  이렇게 되면 O(N^2N)의 시간복잡도가 O(N^N)으로 줄어든다. 고로 시간초과는 안남!!!

P.S. 시간 복잡도 구할 때, 백트래킹에서 재귀 함수 불러주는 횟수로 본다면, O(N!)이다. 8,7,6,5...1

 2225번 문제를 풀지 못해 다른 사람들의 접근방식을 참고했었는데, 그 접근 방식들로 인해 충격을 받았다.

 "와... 저렇게도 볼 수 있구나..."라는 생각에 여기에 기록을 남깁니다.

 *** 문제를 보면, 정수 N을 K개의 정수의 합으로 나타낸다고 할 때, 경우의 수를 구해야 한다.

 *** https://www.acmicpc.net/problem/2225

[내 접근 방식](틀림)

0  ─ 0

[옳은 접근 방식] (정답)
1. N개의 1을 나열한 뒤, K개의 나무 를 두는 경우의 수를 생각해라
ex) N = 5, K = 3
1 1 1 1 1 & l l l    =>    l 1 l 1 1 1 l 1 or l l l 1 1 1 1 1
와 같은 경우의 수를 구하면 된다.

2. 시작점에서 N까지 K개의 경로로 갈 때, 갈 수 있는 방법의수를 생각해라
ex) N = 4, K = 4

에서 N과 K에 맞는 점까지의 최단 거리 횟수를 구하면 된다.
K 열의 번호를 "1번째 수 + 2번째 수 + 3번째 수 + 4번째 수"로 생각해서, 오른 쪽으로 이동한 횟수 만큼 해당 번째의 수를 표시해주면 된다.

위와 같은 경우라면,
 "1번째 수 + 2번째 수 + 3번째 수 + 4번째 수"  ->  "1 + 2 + 0 + 1"  으로 4가 이루어 진다는 말이다.

최단 거리 횟수를 구하는 이유는, 하나의 K에서 될 수 있는 숫자는 N이 최대이기 때문이다.

 Unity Engine을 사용하면서, 특정 Object의 Transform에 접근해서 사용하는 경우가 많습니다. 이 때, 주의해야할 점이 있다면, Transform은 생성이 되지 않는다는 것입니다. 이게 무슨 말이냐면, 일반적으로 어떤 데이터형의 값을 임시적으로 보관하기위해 temp변수를 만듭니다. 해당 변수의 데이터형은 보관하고 싶은 데이터의 데이터형이죠. Transform 다룰 때에도 보관해야할 상황이 나오는데, 이 때 Transform형의 변수를 만들 수 없다는 것입니다.

Error : 보호 수준 때문에 'Transform.Transform()'에 액세스할 수 없습니다.

 이 문제를 해결하고 싶으면 Empty GameObject를 생성한 뒤, 해당 Object의 Transform을 사용하시면 됩니다.