스톤헤드 부수기

https://programmers.co.kr/learn/courses/30/lessons/60062 코딩테스트 연습 - 외벽 점검 레스토랑을 운영하고 있는 스카피는 레스토랑 내부가 너무 낡아 친구들과 함께 직접 리모델링 하기로 했습니다. 레스토랑이 있는 곳은 스노우타운으로 매우 추운 지역이어서 내부 공사를 하는 programmers.co.kr 약 0.6%의 정답률인 문제입니다. 투 포인터 + dfs로 풀려다가 도저히 답이 안 나와서 풀이를 보고 다시 풀어봤습니다. 가장 간단한 방법은 취약 지점을 한 칸씩 밀어주고, 친구들의 거리를 순열로 뽑은 후 검사하는 것입니다. 취약 지점을 예로 들자면 [1, 5, 6, 10] [5, 6, 10, 13] [6, 10, 13, 17] [10, 13, 17, 18] 이..

https://programmers.co.kr/learn/courses/30/lessons/60059 코딩테스트 연습 - 자물쇠와 열쇠 [[0, 0, 0], [1, 0, 0], [0, 1, 1]] [[1, 1, 1], [1, 1, 0], [1, 0, 1]] true programmers.co.kr 약 7%의 정답률인 문제입니다. 완전 탐색으로 풀 수 있지만 어떻게 구현해야 할지 몰라서 많이 헤맸습니다. 자물쇠의 크기를 n에서 n+2*(m-1)로 늘려줍니다. 파란색은 자물쇠의 범위, 초록색은 키의 범위입니다. 초록색을 한칸씩 이동해가며 자물쇠와 맞춰보는 것입니다. 단, 한칸씩 이동하며 검사를 할 때 키는 90도씩 회전하여 칸당 총 4번을 검사합니다. 키의 1과 자물쇠의 1이 겹치지 않는지 검사하고, 자물쇠..

https://programmers.co.kr/learn/courses/30/lessons/17685 코딩테스트 연습 - [3차] 자동완성 자동완성 포털 다음에서 검색어 자동완성 기능을 넣고 싶은 라이언은 한 번 입력된 문자열을 학습해서 다음 입력 때 활용하고 싶어 졌다. 예를 들어, go 가 한 번 입력되었다면, 다음 사용자는 g � programmers.co.kr 약 34%의 정답률인 문제입니다. 레벨 4치고는 매우 쉬운 문제였습니다. 카카오에서는 이 문제를 풀기 위한 자료구조로 트라이(Trie)를 소개해줬습니다. 문제를 풀 당시에는 이런 자료구조를 모르고 풀었습니다. 입력된 단어들을 사전 순으로 정렬하여 특정 단어의 앞, 뒤 단어와 겹치는 부분을 검사하고, 최댓값을 통하여 해당 단어의 최소 입력 횟..

https://programmers.co.kr/learn/courses/30/lessons/17676 코딩테스트 연습 - [1차] 추석 트래픽 입력: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748 programmers.co.kr 약 18%의 정답률인 문제입니다. 하루 중 1초에 가장 많이 걸리는 트래픽의 개수를 출..

더보기 비밀지도 네오는 평소 프로도가 비상금을 숨겨놓는 장소를 알려줄 비밀지도를 손에 넣었다. 그런데 이 비밀지도는 숫자로 암호화되어 있어 위치를 확인하기 위해서는 암호를 해독해야 한다. 다행히 지도 암호를 해독할 방법을 적어놓은 메모도 함께 발견했다. 지도는 한 변의 길이가 n인 정사각형 배열 형태로, 각 칸은 공백(" ) 또는벽(#") 두 종류로 이루어져 있다. 전체 지도는 두 장의 지도를 겹쳐서 얻을 수 있다. 각각 지도 1과 지도 2라고 하자. 지도 1 또는 지도 2 중 어느 하나라도 벽인 부분은 전체 지도에서도 벽이다. 지도 1과 지도 2에서 모두 공백인 부분은 전체 지도에서도 공백이다. 지도 1과 지도 2는 각각 정수 배열로 암호화되어 있다. 암호화된 배열은 지도의 각 가로줄에서 벽 부분을 1..

더보기 셔틀버스 카카오에서는 무료 셔틀버스를 운행하기 때문에 판교역에서 편하게 사무실로 올 수 있다. 카카오의 직원은 서로를 '크루'라고 부르는데, 아침마다 많은 크루들이 이 셔틀을 이용하여 출근한다. 이 문제에서는 편의를 위해 셔틀은 다음과 같은 규칙으로 운행한다고 가정하자. 셔틀은 09:00부터 총 n회 t분 간격으로 역에 도착하며, 하나의 셔틀에는 최대 m명의 승객이 탈 수 있다. 셔틀은 도착했을 때 도착한 순간에 대기열에 선 크루까지 포함해서 대기 순서대로 태우고 바로 출발한다. 예를 들어 09:00에 도착한 셔틀은 자리가 있다면 09:00에 줄을 선 크루도 탈 수 있다. 일찍 나와서 셔틀을 기다리는 것이 귀찮았던 콘은, 일주일간의 집요한 관찰 끝에 어떤 크루가 몇 시에 셔틀 대기열에 도착하는지 ..

https://www.acmicpc.net/problem/15662 15662번: 톱니바퀴 (2) 총 8개의 톱니를 가지고 있는 톱니바퀴 T개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 난이도 : 실버 2 문제가 많이 깁니다. 문제의 길이와 친절함은 대부분 비례합니다. 문제를 정리해보자면 각 톱니바퀴는 8개의 톱니를 가지고 있고 T개의 톱니바퀴가 주어집니다. 12시부터 시계방향으로 톱니의 상태가 주어지고(1-S, 0-N) 톱니는 1번부터 T번까지입니다. 톱니는 회전 방향이 1일 때 시계방향, -1일 때 반시계 방향입니다. 양 옆의 톱니가 맞닿아있는 부분이 같다면 옆의 ..

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 난이도 : 골드 5 제일 자신 없는 다이나믹 프로그래밍입니다. 많이 풀다 보니 조금은 풀이가 보이네요. 연속된 수를 선택하여 가장 큰 합을 구하는 문제입니다. 단, 연속된 수에서 1개의 수를 제거할 수 있습니다. 저는 2차원 배열로 제거를 안 한 경우, 제거를 한 경우의 최댓값을 구했습니다. 0은 수를 제거하지 않은 경우의 최대값, 1은 수를 제거한 경우(제거 안 한 경우 포함)의 최댓값입니다. 0번..