SLENDER ANKLES's 개발블로그

dfs를 돌릴 때 특정 사각형 밖의 영역을 구하는 문제 였다. 

- 문제점은 dfs의 4방향 처리 때 끝에서 바깥부분을 검사할 때 발생했다.

- 예외처리를 거의 날로 한 거 같다.

- 풀기는 풀었지만 제 정신이 아니었다. 

- 바깥 부분을 -1로 다 만들어 놓았다면 이렇게 코드가 난잡해지지 않을 것 같다. 

- 다시 풀어봐야 한다.

- 소트는 버블 소트를 사용한다. 

- stl에서 제공해주는 소트를 사용하여서도 구현해보아야겠다.

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

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

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

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

답을 출력하였다.

front_index, end_index를 이동시켰다. 

규칙

while(front_index != end_index){

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

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

3. front_index++해준다.

}

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

gcd는 

예를 들어 

8, 28의 최대 공약수를 구해보면

3 = 28 / 8 ...4

2 = 8 / 4 ...0

AB/GCD = GCD*a*b;

결국 AB/GCD는 최소공배수가 된다

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

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

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

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

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

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

문제에서는 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사용으로 인한 오답이었다.]