재귀
-
[BOJ18235]지금 만나러 갑니다백준알고리즘 2020. 2. 7. 11:43
사실 내가 한방식대로하면 일반적으로 터지기 마련이다. 그나마 가능했던 이유는, 이동 속도의 증가량이 Positon(위치) + x^(n-1) 의 숫자로 늘어나기때문에, 50만이라는 숫자에서 충분히, 2차원 배열 메모이제이션을 가능하게했다. 배열 구성은 arr[위치][차수] 로 나타낼수있는데, 50만이라고 해봐야, 1에서 시작했을시, 극단적으로 20회 미만이기 떄문에, 50만x20배열을 생성해 메모이제이션을 할수있고, 이를 통해 다음 순서에 올녀석과 겹치는 포지션을 찾아내서 답으로 도출해내는 과정을 작성할수 있었다.
-
비숍백준알고리즘 2019. 8. 27. 00:46
백준 온라인저지의 비숍문제다. 예전에 풀어본 경험이 있는 N-Queen문제와 비슷한문제 였고, NQueen 풀떄보다 훨씬 더 많이 시간을잡아먹었고 많이틀렸다. 다른것보다, 이런 2차원 배열에서 대각선으로 주는 조건은 행 + 열 , 행 - 열 이런식으로해서 규칙성을 찾아낼수가 있어서, r[21] c[21] 배열에, 해당하는 규칙에서 맞는것들을 체킹해주면서 진행하는 재귀함수를 한큐에 썼는데 이게 시간복잡도가 생각보다 엄청나게 큰모양이다. 사실상 전부 해보는거니까 O(N*N)의 시간복잡도가 소요될거라 예상한다. 그래서 일단 비숍이 들어갈수 있는 후보인 맵의 1을 벡터 페어로 잡아서 해봤는데, #include #include #include #include using namespace std; int n; in..