더블릿 - 감 옥(jail)
첫 번째 죄수는 모든 방문을 연다.
두 번째 죄수부터는 자신의 방번호의 배수인 방번호를 열린것은 닫고, 닫힌것은 연다.
,....
데이터가 10만까지 들어온다고 한다.
각 죄수마다 방문에 장난을 치는 동작을 iterative 하게 구현해도 되고, recursive하게 구현되도 되겠다고 판단했다.
데이터가 10만 까지인 것이 영 찝찝해봤는데
생각해보니까 자기 자신의 방번호의 배수마다 장난 을 치므로
10만개의 죄수 방중에서 5만번째의 죄수까지만 장난치는 것을 연산하고 그 다음부터는 어차피 아무 일도 할 수 없었다.
n/2번의 for문을 돌면서 해당하는 죄수들이 장난치는 결과를 재귀함수를 사용해서 수행해주었다.
마지막에 한 번 전체 방의 상태를 체크해서 풀려난 죄수의 명수를 계산해주었다.
더블릿 - 직사각형 면적
사각형 네 개의 좌표가 입력값으로 주어진다.
문제에서 주어지는 좌표를 2차원 배열의 형태로 바꾸어주고 해당하는 배열의 인덱스에 1을 갱신하고 마지막에 1의 개수를 통해 넓이를 알아내겠다는 식으로 구현했다.
약간 헷갈리는 부분이 문제에 있는 좌표를 배열화 해주는 부분인데
일단 x축을 기준으로 뒤집고 입력의 y값은 배열의 x(행)으로, 입력의 x값은 배열의 y(열)형태로 바꾸어주고 계산했더니 금방 답을 구할 수 있었다.
======> (배열의 형태로)
이런식으로 바꾸어서 1의 개수를 계산해주면 답을 구할 수 있다.
더블릿 - 오일러패스
오일러 패스에 대한 몇 가지 성질을 알고있어야 한다. 나는 외웠다.
한 붓 그리기가 가능하기 위해서는 정점이 가지는 간선의 개수에 대한 조건이 맞아야 한다.
한 정점이 연결된 간선의 수에서 홀수개가 연결된 것을 홀수정점, 짝개수가 연결된 것을 짝수정점이라고 하면,
1) 모든 정점이 짝수정점이면 오일러패스(한붓그리기) 가능!
2) 두 개만 홀수정점이고 나머지는 짝수정점이면 오일러패스(한붓그리기)가능!이다.
- 1)은 시작정점과 종료정점이 똑같다. 조건을 만족하는 한점에서 한붓으로 그리고, 종료되는 점이 자기 자신이다.
- 2)은 시작정점과 종료정점이 다르다.
여기까지만 알면 대충 그림이 그려졌다. 그런데 정작 오일러패스의 경로를 구하기가 힘들었다.
우선 dfs를 수행하면서 지나온 경로들을 삭제해준다. 이렇게 하니까 답이 안 나온다.
내가 생각해낸 방법은 아니고 찾아봤더니, 거꾸로 출력하면 답이 나온다고 한다!
예를 들어 dfs재귀함수 부분만 써보자면
와 같이 출력부분을 dfs수행 마지막에 넣어주면 꺼꾸로 출력이 되게 되는데 이 것이 답이 된다.
더블릿 - 최단거리미로
bfs를 사용하는 문제이다.
중요한 문제는 아니나 연속해서 배열 값들은 char 형태로 받아주어야 한다.
또 배열의 초기화와 관련하여 길이 있는 부분은 0보다는 1이 낳으므로 문제에 주어진 부분에서
0으로 입력되는 부분을 1로 바꾸어주고, 1로 입력되는 부분을 0으로 바꾸어주어서 계산했다.
그 이후에는 (n,1)에서 출발하여 bfs를 수행해주고 난 후에 (1,m)에 저장된 길이좌표를 알아내어 구현했다.
더블릿 - 가장가까운조상
우선, 완전 이진 트리가 아니다.
최대 10000개의 노드를 가질 수 있어 10000*10000배열을 사용하기에도 무엇인가 껄끄럽다.
간단히 계산해보니까 나의 코딩 방식으로는 엄청난 연산 횟수가 필요했다.
그래서 노드간의 부모 자식과의 관계를 어떻게 저장할까에 대해서 생각해봤다.
다음과 같이 부모, 자식과의 관계를 나타내었다.
node[버텍스개수] = {자신의부모버텍스, 자신의부모버텍, ....}
이런식으로 나타내었다. 배열의 인덱스는 해당 노드를 말하며, 그 배열의 값은 자신의 부모의 값을 가진다. 이렇게 되면 자신의 부모를 타고 올라가는 재귀적인 명령을 수행을 하는데 충분한 자료를 가지게 된다. 자식에 대한 정보는 필요 없어 저장하지 않는다.
그리고 입력 받은 두 개의 노드 중에 하나를 루트노드까지 재귀적으로 부모를 타고 올라가는
수행을 하면서 그 리스트를 저장했다.
두 번째 입력 받은 노드를 또 다시 재귀적으로 부모를 타고 올라가면서 앞써 저장된 리스트의 값들과 비교했다. 만약 있으면 그 값을 저장하고 재귀함수를 멈추었다.
** 시그를 통해 알게 된 것인데 이 문제는 우선 숫자들을 나열해보고, 그 것의 수열에서 나오는
특징에 대해서 파악해보면 공통적인 부분을 찾을 수 있게 된다. 그 것을 통해 답을 아주 간단히 풀 수 있다.
