문제 코딩테스트 연습 - 멀리 뛰기 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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],..
문제 코딩테스트 연습 - 입국심사 n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다. 처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 programmers.co.kr 문제 풀이 n명이 입국심사를 하는데 심사대에 따라 걸리는 시간을 반환하는 문제이다. 이때 심사 대마다 걸리는 시간은 각기 다르다. 이 문제는 분류와 같이 `이분 탐색`으로 풀어야 시간 내에 통과가 가능하다. 즉, `모두 입국하는데 걸리는 시간 // 각 심사대별 심사시간 = 입국자 수`를 만족하는 지를 찾아야 하기 때문에 `이분 탐색`으로 문제를 풀어야 한다. `이분 탐색`에서는 `left`, `right`를 설정하여야 하는데 이는 가장 짧게 걸리는 시간 1과..
문제 코딩테스트 연습 - 도둑질 도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다. 각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 programmers.co.kr 문제 풀이 인접한 두 집은 방범장치가 연결되어 털 수 없다는 제한 조건을 가지고 있다. 이때 집을 털어서 가장 큰돈을 훔칠 수 있는 최댓값을 반환하는 문제이다. 문제를 풀기 위해서는 다음과 같은 경우를 생각하면 쉽게 해결할 수 있다. 집 1개 : 해당 집을 터는 것이 최대 값이다. 집 2개 : 둘 중에 `money`가 큰 것을 터는 것이 최대 값이다. 집 3개 : `i와 i - 2` 또는 `i - 1` 집의 `money` 중 최대값인 경우를 터는 것이 최대이..
문제 코딩테스트 연습 - 조이스틱 조이스틱으로 알파벳 이름을 완성하세요. 맨 처음엔 A로만 이루어져 있습니다. ex) 완성해야 하는 이름이 세 글자면 AAA, 네 글자면 AAAA 조이스틱을 각 방향으로 움직이면 아래와 같습니다. ▲ - 다 programmers.co.kr 문제 풀이 조이스틱으로 알파벳 이름을 완성하고자 한다. 이때 조이스틱을 움직이면 다음과 같이 동작한다. ▲ - 다음 알파벳 ▼ - 이전 알파벳 (A에서 아래쪽으로 이동하면 Z로) ◀ - 커서를 왼쪽으로 이동 (첫 번째 위치에서 왼쪽으로 이동하면 마지막 문자에 커서) ▶ - 커서를 오른쪽으로 이동 문제를 풀기 위해서는 각 알파벳이 A에서 이동하는 것이 빠른지, Z에서 이동하는 것이 빠른지에 따라 초기에 조이스틱을 이동해야 하는 횟수를 가진..
문제 코딩테스트 연습 - 큰 수 만들기 programmers.co.kr 문제 풀이 어떤 숫자에서 K개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하는 문제이다. 문제를 풀기 위해서는 `stack`을 사용하면 해결할 수 있다. `stack`에 값이 없다면 수를 `append` 한다. `stack`에 값이 있다면 현재의 수와 `top`을 비교하여 값이 값이 크지 않는 경우 `pop`한다. 문제에 제거할 수 있는 `K`가 주어지므로, 이 역시 같이 판단하여야 한다. 만약 `K`가 0이 된다면 즉시 중단하고, 남은 수들을 `stack`에 삽입한다. 코드 def solution(number, k): stack = [] for i, num in enumerate(number): while stack and..
문제 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고생한 www.acmicpc.net 문제 풀이 입력된 문자열의 두 번 이상 나오는 부분 문자열 중 가장 긴 길이를 찾는 문제이다. 이는 앞서 다룬 16916 부분 문자열, 1786 찾기에서 문자열 일치에 따라 정보를 생성하는 `make_table`을 활용하면 해결할 수 있는 문제이다. 코드 def make_table(patten): length = len(patten) table = [0] * len(patten) j = 0 for i in range(1..
문제 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 문제 풀이 문자열과 패턴이 주어지면, 이를 통해 몇 개가 일치하고 어느 위치에 일치하는지 반환하는 문제이다. 앞서 다룬 16916 부분 문자열과 같이 `KMP 알고리즘`을 이해하고 있으면 쉽게 해결할 수 있는 문제이다. 앞서 다룬 문제와 다른 점이 있다면 패턴과 일치하는 경우 바로 결과를 반환하지 않고, 값을 추가하여 모든 탐색이 끝난 후에 반환하는 부분을 수정하면 된다. 코드 def make_table(): length = len(p) table =..
