문제 1305번: 광고 첫째 줄에 광고판의 크기 L이 주어지고, 둘째 줄에 현재 광고판에 보이는 문자열이 주어진다. L은 백만보다 작거나 같은 자연수이다. www.acmicpc.net 문제 풀이 전광판에 N개의 문자열을 광고를 표시한다. 이때 시간이 지남에 따라 문자열은 한 칸씩 옆으로 이동한다. 어느 순간 광고판을 볼 때, 쓰여 있는 문자가 입력으로 주어진다면 가능한 광고의 길이 중 가장 짧은 것을 출력하는 문제이다. 이는 `KMP 알고리즘`에서 접미사와 접두사가 되는 문자열의 최대 길이를 생성하면 쉽게 해결할 수 있는 문제이다. 만약 `KMP 알고리즘`에 대해 이해하고 있지 않다면 문제를 풀 수 없다. 코드 def make_table(patten): table = [0] * l j = 0 for i ..
문제 코딩테스트 연습 - 줄 서는 방법 n명의 사람이 일렬로 줄을 서고 있습니다. n명의 사람들에게는 각각 1번부터 n번까지 번호가 매겨져 있습니다. n명이 사람을 줄을 서는 방법은 여러가지 방법이 있습니다. 예를 들어서 3명의 사람 programmers.co.kr 문제 풀이 처음 문제를 접하였을 때는 `DFS`를 통해 각 경우의 수를 구하고 `K`인 경우를 반환하면 되지 않을까 생각했다. 하지만 이 방식은 `N`이 20이므로 시간 초과가 발생한다. 따라서 `K`인 경우를 바로 구할 수 있는 방법을 통해 풀어야 시간 초과가 발생하지 않는다. 즉, 이 문제는 단순히 `DFS`를 통해 조합을 구할 수 있는가?를 묻는 문제가 아닌 팩토리얼 성질을 통해 효율적으로 K인 경우의 조합을 찾을 수 있는가?를 묻는 문..
문제 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2 programmers.co.kr 문제 풀이 멀리 뛰기를 할 수 있는 방법이 1칸 또는 2칸으로 정해져 있다. 이때 N개의 칸을 뛰고자 하는 경우, 경우의 수가 몇 개인지 찾는 문제이다. 이는 각 경우에 따라 어떤 규칙을 이루는지 확인하면 쉽게 해결할 수 있다. N이 1인 경우 1개 : 1칸 N이 2인 경우 2개 : (1 + 1칸), 2칸 N이 3인 경우 3개 : (1 + 1 + 1칸), (2 + 1칸), (1 + 2칸) 즉 N에 따..
문제 코딩테스트 연습 - 방문 길이 programmers.co.kr 문제 풀이 캐릭터가 [0, 0] 좌표에서 시작해 명령에 따라 상, 하, 좌, 우로 이동한다. 중복하여 이동한 거리와 범위 밖으로 이동한 경우를 제외하여 이동한 거리의 합을 계산하여 반환하는 문제이다. 문제를 풀기 위해서는 딕셔너리를 통해 `U, D, L, R`로 이동할 경우 변화하는 좌표를 선언한 후, 범위에 따라 방문하지 않은 경우 `visited`에 추가하면 된다. 문제에서 구하고자 하는 답은 `visteid // 2`가 된다. 이와 같은 이유는 이동할 때는 출발한 곳과 도착한 곳 양방향으로 기록하여야 한다. 즉 현재 좌표가 `[x, y]` 다음 좌표가 `[next_x, next_y]`라면 `[x, y, next_x, next_y],..
