문제 코딩테스트 연습 - 징검다리 출발지점부터 distance만큼 떨어진 곳에 도착지점이 있습니다. 그리고 그사이에는 바위들이 놓여있습니다. 바위 중 몇 개를 제거하려고 합니다. 예를 들어, 도착지점이 25만큼 떨어져 있고, 바위가 programmers.co.kr 문제 풀이 출발지점부터 거리만큼 떨어진 곳에 도착지점이 있다. 이때 그 사이에 있는 바위들 중 몇 개를 제거하려고 한다. 특정 바위를 `N`개만큼 제거할 때 거리의 최솟값이 최대가 되는 경우를 구하는 문제이다. 이 문제는 문제의 분류와 같이 `이분 탐색`으로 해결할 수 있다. `이분 탐색`을 통해 최소값 기준으로, 빠진 돌의 개수를 카운트한 후 거리의 최솟값이 최대가 되는 경우를 찾으면 된다. 코드 from math import inf def ..
문제 코딩테스트 연습 - 가장 긴 팰린드롬 앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요. 예를들 programmers.co.kr 문제 풀이 문자열이 주어질 때, 문자열의 부분 문자열 중 가장 긴 팰린드롬을 찾는 문제이다. 문제를 풀기 위해서는 `2중 반복문`을 통해 부분 문자열의 시작 위치와 끝 위치를 설정 후 팰린드롬인지 확인하면 된다. 코드 def solution(s): answer = -1 for i in range(len(s)): for j in range(i + 1, len(s) + 1): cur_string = s[i:..
문제 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 문제 풀이 남은 일의 작업량이 있을 때, 야근 지수를 최소화하여 반환하는 문제이다. 일의 작업량이 있고, 일을 할 수 있는 시간이 있다면 작업량이 가장 큰 작업부터 처리하여야 한다. 야근 지수는 `작업량의 제곱`이기 때문이다. 문제를 풀기 위해서는 `Python`의 경우 `heapq`를 사용하여 풀어야 한다. `heapq`는 최소 힙이기 때문에 최대 힙을 만들기 위해서는 음수 값으로 변환하여야 한다. (이는 works가 1 이상 이기에 가능하..
문제 코딩테스트 연습 - 숫자 게임 xx 회사의 2xN명의 사원들은 N명씩 두 팀으로 나눠 숫자 게임을 하려고 합니다. 두 개의 팀을 각각 A팀과 B팀이라고 하겠습니다. 숫자 게임의 규칙은 다음과 같습니다. 먼저 모든 사원이 무작위로 programmers.co.kr 문제 풀이 A, B 팀이 있을 때, 임의의 숫자가 주어진다. B 팀이 최대한 이길 수 있도록 하여 최대 승점을 반환하도록 하여야 한다. A, B를 정렬하고, 최대 값을 비교하여 처리해주면 쉽게 문제를 해결할 수 있다. 만약 `A팀의 최솟값`이 `B팀의 최대값` 보다 크다면 별도의 반복문을 진행할 필요 없이 바로 0을 반환하면 된다. (이길 수 없는 경우이기 때문이다.) 이외의 경우 `A의 최대값`과 `B의 최대값`에 따라 처리하면 된다. 코드..
문제 코딩테스트 연습 - 배달 5 [[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]] 3 4 6 [[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]] 4 4 programmers.co.kr 문제 풀이 문제 조건에 따라 K 시간 이하로 배달 가능한 마을에서만 주문을 받아야 한다. 이때 음식 주문을 받을 수 있는 마을의 개수를 반환하여야 한다. 모든 경우를 `BFS`로 탐색하는 것은 비효율적이다. 따라서 `다익스트라`를 적용하여 탐색을 하게 되면 문제를 해결할 수 있다. 코드 from math import inf from collections import deque def solution(N, road, K): visit..
문제 코딩테스트 연습 - N-Queen 가로, 세로 길이가 n인 정사각형으로된 체스판이 있습니다. 체스판 위의 n개의 퀸이 서로를 공격할 수 없도록 배치하고 싶습니다. 예를 들어서 n이 4인경우 다음과 같이 퀸을 배치하면 n개의 퀸은 programmers.co.kr 문제 풀이 앞서 다룬 백준: 9663 N-Queen, SWEA: 2806 N-Queen과 동일한 문제이다. Queen의 경우 상, 하, 좌, 우에 다른 Queen이 없어야 하고, 대각선으로도 Queen이 없어야 한다는 조건을 만족하여야 한다. 따라서 Queen을 배치할 수 있는 경우를 판단하는 것은 다음과 같다. 행의 경우 DFS를 호출하며 증가시키므로, 별도의 중복확인이 필요하지 않다. 열의 경우 해당 열을 선택하면 `set`에 추가하여 중..
문제 코딩테스트 연습 - 2 x n 타일링 가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 programmers.co.kr 문제 풀이 앞서 다룬 백준: 11726 2xn 타일링과 동일한 문제이다. N이 증가함에 따라 `f(n) = f(n - 1) + f(n - 2)`와 같은 규칙을 찾을 수 있고 이를 `N`만큼 반복하면 원하는 값을 찾을 수 있다. 코드 def solution(n): a, b = 1, 1 for _ in range(n): a, b = b, a + b return a % 1000000007
문제 코딩테스트 연습 - 거스름돈 Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다. 예를 들어서 손님께 5 programmers.co.kr 문제 풀이 거슬러 주어야 하는 돈 N이 있고, 화폐 단위가 주어진다. 이때, 돈을 거슬러 줄 수 있는 방법의 경우의 수를 계산하여 반환하는 문제이다. 이 문제는 이전에 다룬, 백준: 2293 동전 1 문제와 동일한 문제이다. `DP`를 통해 각 경우의 수를 계산하여야 하며, 그렇지 않을 경우 시간 초과가 발생한다. def solution(n, money): dp = [1] + [0] * n for coin in money: for price i..
