문제 코딩테스트 연습 - 숫자 게임 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
