[Algorithm] 문자열

in Algorithm

Elice Algorithm Code Challenge - Day 3 (문자열)

목차

  1. 코딩테스트에 자주 나오는 문자열 1) 회문 2) 올바른 괄호 문자열
  2. 분할 정복과 백트래킹 1) 분할 정복 2) 백트레킹

코딩테스트에 자주 나오는 문자열

1. 회문 (Palindrome)

  • 앞뒤 방향으로 볼 때, 같은 순서의 문자로 구성된 문자열을 의미
  • 예시
    • “소주 만 병만 주소”, “Madam, I’m Adam”, “1234321”

2. 올바른 괄호 문자열 (VPS = Valid Parenthesis String)

  • 조건
    1. 빈 문자열은 올바른 괄호 문자열이다
    2. S가 올바른 괄호 문자열이라면, (S)도 올바른 괄호 문자열이다.
    3. S, T가 괄호 문자열이라면 ST도 올바른 괄호 문자열이다.
  • 보통은 Stack을 사용해서 해결
  • ’)’가 입력될 때마다, 스택에 있는 ‘(‘를 하나씩 지움
    • 이때, 스택(top)이 비어있거나, ‘(‘가 없으면 올바른 괄호 문자열이 아님
  • 모든 문자열을 순회한 뒤, 스택이 비어있으면 올바른 괄호 문자열
  • 치환 사용하기
    • ’(‘를 1, ‘)’를 -1로 치환
    • 문자열 S를 전부 순회하며 합 계산
    • 중간에 합이 음수가 되거나, 모든 계산이 끝나고 0이 아니면 올바른 괄호 문자열이 아님

분할 정복과 백트래킹

분할 정복 (Divide and Conquer)

  • 큰 문자를 작은 문제로 분할하여 작은 문제의 답을 모다 큰 문제의 답을 구함
  • 기저 사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야 함
  • 보통 재귀로 구현
  • 예시
    • 피보나치 수열
    • Z
      • Full-width image
      • Full-width image

백트래킹

  • 답이 될 수 없는 경우는 탐색 대상에서 제외하며 효율적으로 답을 구하는 알고리즘
    • 가지치기(pruning)를 통해 연산량을 유의미하게 줄여줌
  • 가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야 함
  • 정확한 시간 복잡도 측정 어려움
  • 보통 재귀로 구현
  • 많이 연습해봐야 익힐 수 있음
  • 예시
    • 스도쿠
      • 대입해보고 현재 상태에서 스도쿠를 완성할 수 없다면, 분기점으로 다시 돌아옴
    • Nqueen