SLENDER ANKLES's 개발블로그

그래프의 첫번째 노드에서 출발해서 연결된 서로 연결된 노드들은 모두 감염된다. 

첫 번째 노드가 속하지 않는 그래프에는 감염되지 않는다. 

그렇다면 첫번째 노드가 속한 그룹의 개수를 세면 감염되는 컴퓨터의 수를 알 수 있게 된다. 

인덱스 위치를 앞 뒤로 주고 문제의 규칙에 맞게 인덱스를 옮겨다니며 값을 갱신하고 출력해주는 형식으로 

답을 출력하였다.

front_index, end_index를 이동시켰다. 

규칙

while(front_index != end_index){

1. front_index에서 출력하고 front_index++

2. front_index의 값을 end_index++ 위치에 갱신

3. front_index++해준다.

}

이 조건을 수행해주니까 답이 도출

[다시 풀었어도 난해한 문제]

오랜만에 드디어 문제가 풀렸다. ㅜㅜ

답이 잘 안 나오는 문제가 너무 많다. 분발하자. 

떡 먹는 호랑이 문제는 내가 너무 어렵게 생각한 거 같다. 

알고 봤더니 쉽고 정말 좋은 문제였다.라고 스스로 평가하고 싶다. 

우선 첫날 준 떡 + 두번째 날 준 떡 = 세번째 날 준떡 이어야 한다는 것은 피보나치 점화식을 가진다는 것을 알 수 있음!

문제에서는 n번째 날에 k의 떡을 준 것을 토대로 문제를 풀어 첫 번째 날과 두 번째 날에 준 떡의 개수를 알아내야 한다. 

처음은 점화식의

f(n) = a*f(n-2) + b*f(n-1) 이라는 식을 세워서 계수를 알아내야 한다고 생각 한다. 물론 맞다.

a와 b를 빼놓고 생각해본다면

f(n) = f(n-2) + f(n-1)이라는 점화식이 나오고

f(1) = 1, f(2) = 1로 놓으면 계수가 나오지 않겠는가!!!

결국 첫날 준 떡 a , 두번째 날 준 떡 b의 계수를 구할 수 있게 된다. 

이 계수를 토대로 a와 b를 구해야 한다. 어떻게?

처음은 다이나믹 프로그래밍으로 풀어야 하나를 생각해보면서 이상한 고민을 했었다. 

하지만 단지 이중 for문을 돌면서 때려 맞추고 break으로 빠져나오면 된다.

심각한 루프를 돌지도 않고 또한 워낙 범위가 많지 않아 무리 없이 수행 할 수 있다.!!!

문제의 조건들을 면밀히 살펴 시간분석도를 대략적으로 계산할 줄 알아야 한다는 생각을 했다. 이 부분을  좀 더 공부해야겠다.

동적계획법 다이나믹프로그래밍을 사용하여 풀 수 있는 문제이다. 

맨 처음은 완전탐색의 방법을 사용하였으나 테스트케이스 9개? 정도 맞추고 시간초과났다.

다이나믹프로그래밍을 쉽게 적용하여 풀 수 있는 문제라는 생각을 해보았다.

점화식은 간단하다.

dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + arr[i][j]로써

입력받은 배열을 arr로 놓았고 dp라는 배열을 만들어서 현재까지 지나오면서 채취할 수 있는 자원의 최대양을 저장하는 배열을 하나 더 만들었다. 

for문을 돌면서 현재의 위치에서 경로 중 가장 자원을 많이 채취 할 수 있는 양을 계산해주었다.(이게 가능한 것은 scv가 오른쪽 또는 아래쪽으로만 이동 할 수 있기 때문이다.)

현재의 배열의 위치는 왼쪽에서 진입하는 scv가 채취하는 최대의 양 또는 위쪽에서 진입하는 scv가 채취하는 최대의양을 말한다. 

다이나믹 프로그래밍 방법으로 풀 수 있다. 

i+1은 i와 같은 색깔이 아니면서 최소의 비용을 갖아야 한다. 

구조는 [집의번호][색깔]을 사용한다. => dy[i][j]

식 : i까지의 최소 비용 + 해당색깔로 칠했을 때의 비용

을 기본 식으로 사용하여 코딩해나간다.

다음과 같이 코딩해주었다.

경우의 수 문제는 항상 무엇인가 걸림돌이 된다. 

많은 문제를 풀어보면서 경험을 쌓아야하는 것이 좋은 것인지 아니면 접근법에 대한 나름의 규칙을 만들어야 하는 것이 좋은지

잘 모르겠다. 

좌석배치 문제 역시 마찬가지 였다. 

좌석들은 피보나치 수열의 관계를 가진다는 것을 알았다. 

좌석을 배치 받은 사람은 양 옆자리와 원래배정받은 자리에 앉을 수 있는 권한이 있다. 

예제 입출력에서 

9명의 좌석에서 4번좌석과 7번좌석은 고정좌석이라고 했다. 

그렇다면 고정좌석을 경계로 각 그룹들은 피보나치 수열의 관계를 갖는 경우의 수를 갖는다는 것을 알았다.

각 그룹들의 경우의 수는 독립적이므로 서로의 경우의 수를 곱하여 답을 도출 하였다. 

* 홀수번째에 먹는 포션은 포션의 수치만큼 점프력을 증강시킨다.

* 짝수번재에 먹는 포션은 포션의 수치만큼 점프력을 하강시킨다.

이 문제 역시 많은 고민을 해보았지만 딱히 해법이 떠오르지 않았다.

모든문제들을 너무 어렵게만 접근하는 것은 아닌지 모르겠다는 생각을 했다. 

문제는 그리디하게 풀면 풀리는 문제였다. 

꼭지점에서의 포션을 마시면 가장 높이 점프 할 수 있는 요건을 충족시키게 된다. 

- 현재의 지점이 이전과 이후보다 크면 마셔라

- 현재의 지점이 이전과 이후보다 작으면 마셔라

- 연속되는 부분이 나오면 한 점으로 만들어라

(이 부분 때문에 에러가 났지만 입력 받을 때 똑같은 값이 연속으로 들어오게 되면 한 점으로 만들어주게 처리해주니까 오류가 사라졌다)

=> 꼭지점 부분의 포션을 먹으면 된다. 

=> 가장 왼쪽과 가장 오른쪽은 안 마셔야 한다.

(먹을 이유가 없다. 최소지점을 먹는 이유는 다음에 최고 지점이 나타나는 것을 먹기 위해서다)

=> 연속해서 들어오는 입력 값은 하나로 처리하는 것이 문제를 푸는 데 수월하다. 로직에서 같은 값을 처리하는 부분에 대해 예외처리하는 것이 오히려 더 까다롭다.

알파벳 배열에 대한 익덱스를 풀어나가는 것이 관건이었다.

진입한 지점의 알파벳 - 'A'를 배열에 넣어주어 배열의 인덱스를 관리하였다.

dfs를 순회하면서 백트래킹을 사용하였다. dfs함수의 마지막에 알파벳을 거두어 들이면 된다.

오답이 10번 넘게 났는데 이유는 visited배열을 사용해서 였다.

visited배열을 사용하게 되면 제대로 dfs를 순회할 수 없게 된다.

어차피 지나온 경로에 있는 알파벳에는 진입하지 않을 테니까 무한루프에 빠질 이유도 없다.

[틀에박힌 dfs사용으로 인한 오답이었다.]

그래프 문제였다. 

핵심은 이거 였다. 

해당 학생의 키순서의 상대비교를 정확히 알기 위해서는 

내 앞에 있는 학생들과 연결되어있어야 하며

나보다 작은 학생들과도 연결되어야 한다.

dfs한번!

backtracking한번!을 수행하여

visited배열의 갱신되는 부분을 체크하여

모두 방문했으면 이 학생은 상대적인 키순서를 알 수 있는 사람이고

모든 버텍스를 방문하지 못 하는 경우에는 이 학생은 상대적인 키순서를 알 수 없는 사람이다.

더블릿 - 감 옥(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재귀함수 부분만 써보자면

<span style="color: rgb(51, 51, 51);">void dfs(int vertex){ for (int i = 1; i <= vertex_n; i++){ if (arr[vertex][i] == 1){ arr[vertex][i] = 0; arr[i][vertex] = 0; dfs(i); } } cout << vertex << " "; } </span>

와 같이 출력부분을 dfs수행 마지막에 넣어주면 꺼꾸로 출력이 되게 되는데 이 것이 답이 된다. 

더블릿 - 최단거리미로

bfs를 사용하는 문제이다. 

중요한 문제는 아니나 연속해서 배열 값들은 char 형태로 받아주어야 한다. 

또 배열의 초기화와 관련하여 길이 있는 부분은 0보다는 1이 낳으므로 문제에 주어진 부분에서

0으로 입력되는 부분을 1로 바꾸어주고, 1로 입력되는 부분을 0으로 바꾸어주어서 계산했다. 

그 이후에는 (n,1)에서 출발하여 bfs를 수행해주고 난 후에 (1,m)에 저장된 길이좌표를 알아내어 구현했다. 

더블릿 - 가장가까운조상

우선, 완전 이진 트리가 아니다. 

최대 10000개의 노드를 가질 수 있어 10000*10000배열을 사용하기에도 무엇인가 껄끄럽다.

간단히 계산해보니까 나의 코딩 방식으로는 엄청난 연산 횟수가 필요했다. 

그래서 노드간의 부모 자식과의 관계를 어떻게 저장할까에 대해서 생각해봤다.

다음과 같이 부모, 자식과의 관계를 나타내었다. 

node[버텍스개수] = {자신의부모버텍스, 자신의부모버텍, ....}

이런식으로 나타내었다. 배열의 인덱스는 해당 노드를 말하며, 그 배열의 값은 자신의 부모의 값을 가진다. 이렇게 되면 자신의 부모를 타고 올라가는 재귀적인 명령을 수행을 하는데 충분한 자료를 가지게 된다. 자식에 대한 정보는 필요 없어 저장하지 않는다.

그리고 입력 받은 두 개의 노드 중에 하나를 루트노드까지 재귀적으로 부모를 타고 올라가는 

수행을 하면서 그 리스트를 저장했다.

두 번째 입력 받은 노드를 또 다시 재귀적으로 부모를 타고 올라가면서 앞써 저장된 리스트의 값들과 비교했다. 만약 있으면 그 값을 저장하고 재귀함수를 멈추었다. 

** 시그를 통해 알게 된 것인데 이 문제는 우선 숫자들을 나열해보고, 그 것의 수열에서 나오는

특징에 대해서 파악해보면 공통적인 부분을 찾을 수 있게 된다. 그 것을 통해 답을 아주 간단히 풀 수 있다.