<실전 알고리듬> 체크리스트 체크하기!

일하던 중

코드를 개판으로 짠게 발견해서 수정이 필요해 보였다.
과거의 나는 지금의 kaebalsaebal이 처리(?)해야 하니 알고리듬을 다시 만들어야 하는데…

문제 사항

대충 이런 식의 체크리스트인데…혹시 눈치채셨습니까?

네 맞아요… 이 글 직전에 올린 글 맞아요..

정확히는 저 글에서 다룬 문제가 아닌 다른 것으로
api로 받아온 리스트를 보고 거기에 맞게 저 항목들을 체크하는 로직이 개판이었던 것이다.

개판코드 예시

코로 코드블록을 먹지 않기 위해 수도코드(pseudo-code)로 아~~~주 대충 작성합니다.

# api로 가져온 리스트를 a, 체크리스트 목록을 b라고 합니다.
# b의 각 항목에는 하위 체크리스트 목록 속성인 checklists가 있을 수 있습니다. 없으면 null
# b의 각 항목 체크 여부는 checked라는 부울 속성으로 관리합니다.
# 하위항목이 있는 b 항목은 a 리스트에 없습니다.

for(i in b) # b 하위 항목 탐색
{
  i.checked = false # 체크여부 초기화
  icount = 0 # i 하위 항목 얼마나 체크했는지 보는 카운트

  for (j in i.checklists) # i 하위 항목(j) 탐색
  {
    jcount = 0 # j 하위 항목 얼마나 체크했는지 보는 카운트
    for (k in j.checklists) # j 하위 항목(k) 탐색
    {
      if (k가 a에 있으면)
      {	
        k.checked = true # k 체크표시
        jcount += 1 # k 체크됐으니 jcount 증가
      }
    }
    if (len(j.checklists) != 0) # j 하위 항목이 있는 경우에만
    {
      if (jcount == len(j.checklists)) # j 하위 항목 전체 체크되었는지 확인
      {
        j.checked = true
      }
      else
      {
        j.checked = false
      }
    }
    else # j 하위 항목 없을 경우
    {
      if (j가 a에 있으면)
      {
        j.checked = true
      }
    }
    if (j.checked == true) # j 체크되었을 시 icount 증가
    {
      icount += 1
    }
  if (icount == len(i.checklists)) # i 하위 항목 전체 체크되었는지 확인
  {
    i.checked = true
  }
  else
  {
    i.checked = false
  }
}      

복잡하다!
실제로는 저 외에 별별 자잘한 로직도 있지만 그것까지 적었다간 본인 신변이 좋지 않을것 같아..
결정적으로 그건 별로 중요하지 않다!

물론 코드를 자세히 보면 알겠지만 왜 저걸 자세히 볼 이유가 있습니까..(정론) 불필요한 로직이 있어 시간복잡도를 잡아먹는다거나 하지는 않는다. 현재 기능에는 충실하단 말이다.

그러나 문제는…

• 만약 저기서 레벨 한단계가 추가되면? 즉

  

  이렇게 깊이가 현재 3단계에서 4단계로 늘어난다면?

근데 분명 언젠가 저기에 레벨 하나 추가해달라 할게 분명하니 미리 선수를 치기로 했다.
마침 x지전자 코딩테스트도 통과한 본인 아닌가! 통과하기만 하면 뭐해

DFS를 사용하여 개선

DFS 알고리듬

2년하고도 반년 전에 올려놓은 DFS 알고리듬 문서가 있는데, 이걸 써먹을 것이다.
그땐 참 열심히도 글 썼다. 지금은 분기에 하나 쓸까 말까인데
이유는 간단합니다만, 저 체크리스트를 뜯어보면

이렇게 생긴 체크리스트는

이렇게 그래프로 표현할 수 있기 때문이다!

이걸 DFS를 쓴다면 위 그림처럼 탐색할 것이다. 여기서 BFS 대신 DFS를 선택한 이유가 나오는데, 로직에 하위 레벨 체크 여부에 따른 상위 레벨 체크도 들어가야 하기 때문이다.

사실 주객이 전도된건데, 기존 로직 그대로 두고 코드만 최적화해보던 거지만 알고 보니 이거 DFS네! 라고 찾은 거에 더 가까운…

아무튼 DFS를 사용하여 개선한 코드

# a는 리스트, b는 체크리스트!
int makechecklist(b)
{
  count = 0
  for(i in b)
  {
    count += makechecklist(i.checklists)
  }
  if (i.checklists is null)
  {
    b.checked = (a에 b가 있는지 여부)
    if b.checked return 1
  }
  if (count !=0 and count == len(b.checklists))
  {
    b.checked = true
    return 1
  }
  else
  {
  	b.checked = false
    return 0
  }
}

아까보다 훨~씬 간략화 된 것을 볼 수 있다!

• 해석

만약 체크리스트가 위와 같을 경우…(체크 여부는 보지 말아주세요)

1. 체크리스트 2의 count는 0이 된다.
2. 체크리스트 2의 하위 항목 리스트([2-1,2-2,…])에 makechecklist() 함수를 재귀한다.
3. 2-1~2-3, 2-5~2-6의 경우는 하위 항목 리스트가 null이 된다. 따라서 for문은 안 탈 것이다.
4. 그럼 if (i.checklists is null) 이 부분으로 넘어갈텐데, 만약 체크가 되어 있으면 1을 반환하므로, 체크리스트 2의 count에 1이 추가된다. 없으면 맨 아래 else문으로 넘어가므로 0 추가
5. 2-4의 경우에는 하위 항목 리스트([2-4-1,2-4-2])가 있으므로 makechecklist()를 한번 더 돌 것이다. 이 때 2-4의 count는 0
6. 2-4-1,2-4-2의 재귀가 끝나면 2-4는 if (count !=0 and count == len(b.checklists)) 여기로 넘어간다.
7. 만약 2-4-1,2-4-2가 전부 체크되어서 2-4의 count값과 checklists 개수가 같아지면 2-4는 체크된다. 체크되면 1이 반환되므로 2의 count는 1이 추가된다.
8. 마찬가지로 2-6까지 전부 돌고, 그것들이 전부 체크되면 2의 count가 checklists 개수와 같아진다. 그럼 체크!

그럼 여기서 유력한 질문이 “하위 항목이 일부만 체크되어 있으면요?”
본인 기준으로는체크리스트 라이브러리에 일부만 체크하는 플래그가 있어서, 맨 마지막 if문에 그걸 판단하는 로직을 넣어줬는데.. 이건 라바라니까 각자 적~절히 처리하면 되겠다!