[3주차_월요일] 디버깅

[Jewan1120]

• 사이트 : 코드트리(CT)
• 문제: 디버깅
• 년도: 2018년

[yeongleej]

🤔 시간복잡도 고려사항

시뮬레이션 문제, 특이사항 X

💡 풀이 아이디어

• 각 고객에 연결된 취약 지점의 개수 or 유실 선의 개가 홀수 인경우, 유실선을 추가해야 함
• 백트래킹을 이용해서 선의 개수가 홀수인 고객들에게 선을 추가
• 가능여부 체크 : 각 고객의 연결된 선 리스트를 만들어서 모두 짝수인지 체크

[baexxbin]

🤔 시간복잡도 고려사항

• 2 ≤ n ≤ 10, 1 ≤ h ≤ 30
• 완전탐색 가능 O(N^2)
  • 시도 횟수 3이하의 조건

💡 풀이 아이디어

• dfs로 완전탐색하기

• 사다리 구성

  • Node를 통해 왼쪽, 오른쪽에 사다리 있는지 체크 변수 둠

• 사다리 타기 play()

  • 한 사람씩(열) 사다리 타기
  • 왼쪽, 오른쪽에 사다리있으면 해당 열로 이동
  • 밑으로 한칸씩 이동(공통)

• 선 추가하기 addLine()

  • 재귀로 depth로 깊이 관리하기(선의 갯수)
  • 사다리 놓을 수 있는지 여부 체크 후 사다리 놓기
  • 놓은 사다리로 play했을때 성공하면 정답
  • 실패하면 해당 사다리를 놓은 상태에서 사다리 추가 (dfs)
  • 상태 원상 복구하기

성공했을 경우에도 상태 되돌려주기

[Jewan1120]

🤔 시간복잡도 고려사항

• 2 ≤ n ≤ 10, 1 ≤ h ≤ 30
• 재귀의 최대 깊이가 3
• 구현 문제였으므로 따로 신경쓰진 않았음

💡 풀이 아이디어

• 사다리 타기로 문제를 간단하게 변환
• 문제를 읽고 N개 중 C개를 선택하는 조합 문제라고 생각 → 백 트래킹
  1. 사다리가 있는 곳을 구현하기 위해 다음과 같이 boolean[][]을 사용
  2. 사다리가 놓여져 있지 않은 곳(false)들 중 설치가 가능한 0~3개를 선택했을 때 움직임이 올바른지 확인
  3. 움직임을 구현 시 아래로 내려가면서 현재 기준으로 좌 우 인덱스에 사다리가 있다면 위치 변경
  4. 각 깊이마다 올바르지 않다면 백 트래킹으로 선택을 취소하고 다음 선택으로 넘어감

[KodaHye]

🤔 시간복잡도 고려사항

• power set를 이용해서 사다리가 있을 수 있는 경우를 고려
  • power set으로 모든 경우를 고려한다면 시간 복잡도는 2 ^ (사다리 전체 개수)가 되므로 시간 초과 발생함
  • 사다리를 고르는 개수가 3개일 때까지 고르는 것이므로 powerset으로 구현해도 될 것이라 판단
  • (사다리 개수C0 + 사다리 개수C1 + 사다리 개수C2 + 사다리 개수C3)

💡 풀이 아이디어 (1) Powerset 이용

• Hashset에 처음 사다리가 있는 위치의 idx를 저장해서 power set을 구할 때, 처음 있는 위치의 사다리가 없어지는 경우가 발생하지 않도록 함 (임시 배열을 만들면 Hashset을 만들지 않아도 됨)
• 모든 조합의 경우를 고려한게 power set이므로 그냥 조합으로 0, 1, 2, 3개 선택하는 방법이 더 나을듯

(2) 조합 이용

• 모든 사다리 중 조합으로 0, 1, 2, 3개 선택했을 때, 버그를 고치는 것이 가능한지 확인
  • 조합을 구할 때, 같은 행에 대해서 연속돼서 사다리가 올 수 없다는 조건 만족해야 됨

[icegosimperson]

🤔 시간복잡도 고려사항 변수 값이 작아서 고려X

💡 풀이 아이디어

1. 버그를 고치기 위해 필요한 메모리 유실선 개수의 최솟값 출력하는 문제
2. 사다리 오른쪽 이동 가능, 왼쪽 이동 가능 상태 초기값 설정

   map[a][b] = 1; // 사다리 오른쪽 이동 가능
   map[a][b+1] = 2; // 사다리 왼쪽 이동 가능 (오른쪽으로 이동한 상태이므로 2로 표현)

3. dfs 가로선(메모리 유실선)이 추가되지 않았다면
4. 가로선 추가 후 재귀 호출, 백트래킹으로 가로선 제거

[yeahdy]

🤔 시간복잡도 고려사항

• 알고리즘: dfs
• 시간복잡도: 1 ≤ h ≤ 30 크기로 dfs 가능

💡 풀이 아이디어 ※ 코드 작성 전 문제를 풀기 위해 필요한 조건에 대해 생각했는데, 조건을 구하기 위한 아이디어가 전혀 안떠올라서 해설을 참고했습니다. 해설을 통해 왜 이런 방법으로 문제를 풀었는지에 대해 적었습니다.

유실선을 추가하는 기준? 왜 조합 알고리즘인지?

1. 알맞는 유신선인지는 추가한 후에 확인 가능하기 때문에 모든 경우에 대해서 유실선을 추가해야 함
2. 문제에서 제시한 유실선의 최대갯수는 3
3. 따라서 유실선을 연결할 수 있는 모든 유실선 순회하며 유실선을 1개~3개 연결
4. 방문체크로 유실선을 연결 해 조건을 충족하는지 알 수 있음
5. 조건을 충족하는 조합 중 가장 최소 조합을 뽑는 것

사다리를 타는 방법?

내 생각: 번호를 기준으로 내려가며 좌우를 확인하고 1을 발견하면 이동 → 유실선을 추가할때 마다 모든 사다리 줄을 이 과정을 거치면 시간초과가 발생할 것 같음 해설: 유실선을 기준으로 연결된 지점끼리 번호를 교환 → 두 지점을 한번에 교체가능

dfs 백트래킹한 이유?

1. 유실선 하나를 추가했을 경우 모든 사다리줄이 알맞은 고객에게 찾아가는지 확인 해야 함
2. 조건에 충족하지 않을 경우 더이상 사다리를 타지 않고 깊이 탐색에서 제외