1 분 소요

나중에 푼 문제가 있으면, 링크를 걸어서 코드끼리 비교할 수 있도록 해보자!

2.3 문제 해결 전략

같은 알고리즘의 변형

최단 경로 문제 응용, 혹은 아예 다른 접근이 필요한 문제 쌍들!

  • 합친 LJS(ID: JLIS, 8장)
  • 신호 라우팅(ID: ROUTING, 30장)
  • 음주 운전 단속(ID: DRUNKEN, 30장)
  • 선거 공약(ID: PROMISE, 30장)

손으로 문제를 풀다보면(수식화)..?

  • Quantization(ID: QUANTIZE, 8장)
  • 두니발 박사의 탈옥(ID: NUMB3RS, 8장)
  • 실험 데이터 복구하기(ID: RESTORE, 9장)
  • 출전 순서 정하기(ID: MATCHORDER, 10장)
  • 마법의 약(ID: POTION, 14장)
  • 함정 설치(ID: TRAPCARD, 32장)

단순화한 문제에서 해법이 나옴

2차원 좌표 문제를 1차원 좌표 2개로 나눠보니, 각 부분 알고리즘의 합이 답이 되는 경우가 있더라!

  • 비대칭 타일링(ID: ASYMTILING, 8장)
  • 드래곤 커브(ID: DRAGON, 9장)
  • 도시락 데우기(ID: LUNCHBOX, 10장)
  • 어린이날(ID: CHILDRENDAY, 29장)
  • 근거리 네트워크(ID: LAN, 31장)

그려보기

숫자에 관한 문제더라도, 그려볼 수는 있잖아?

  • 문자열 합치기(ID: STRJOIN, 10장)
  • 너드인가, 너드가 아닌가?(ID: NERDS, 15장)
  • 너드인가, 너드가 아닌가? 2(ID: NERDS2, 22장)

수식으로 표현해보기

반대로 문장이나 그림에 대한 문제를 수식으로 변환할 수도?

  • 수강 철회(ID: WITHDRAWAL, 12장)

거꾸로 살펴보기

조건에서 답으로 방법을 찾는 것 외에도, 답으로부터 선택지를 찾아가는 접근도 좋다

  • 삽입 정렬 뒤집기(ID: INSERTION, 22장)
  • 감시 카메라 설치(ID: GALLERY, 28장)
  • Sorting Game(ID: SORTGAME, 29장)

순서를 강제로 만들기

풀이법이 다양한 문제라면, 사고/풀이 과정에서 편하도록 임의로 순서를 정해보자

  • 게임판 덮기(ID: BOARDCOVER, 6장)
  • 폴리오미노(ID: POLY, 8장)
  • 웨브바짐(ID: ZIMBABWE, 9장)

정규화(canonicalization)

가능한 수가 다양한데 너무 많다면, 대표 케이스 하나만을 도출하는 알고리즘으로 대체해보자

  • 소풍(ID: PICNIC, 6장)
  • 단어 제한 끝말잇기(ID: WORDCHAIN, 28장)

참고