코딩테스트준비

문제 읽기🤔 문제 2048 게임은 4×4 크기의 보드에서 혼자 즐기는 재미있는 게임이다. 이 링크를 누르면 게임을 해볼 수 있다. 이 게임에서 한 번의 이동은 보드 위에 있는 전체 블록을 상하좌우 네 방향 중 하나로 이동시키는 것이다. 이때, 1)같은 값을 갖는 두 블록이 충돌하면 두 블록은 하나로 합쳐지게 된다. 2)한 번의 이동에서 이미 합쳐진 블록은 또 다른 블록과 다시 합쳐질 수 없다. (실제 게임에서는 이동을 한 번 할 때마다 블록이 추가되지만, 이 문제에서 블록이 추가되는 경우는 없다) 마지막으로, 3)똑같은 수가 세 개가 있는 경우에는 이동하려고 하는 쪽의 칸이 먼저 합쳐진다. 이 문제에서 다루는 2048 게임은 보드의 크기가 N×N 이다. 보드의 크기와 보드판의 블록 상태가 주어졌을 때, ..

문제 읽기🤔 문제 N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 500,000) 둘째 줄에 N자리 숫자가 주어진다. 이 수는 0으로 시작하지 않는다. 출력 입력으로 주어진 숫자에서 K개를 지웠을 때 얻을 수 있는 가장 큰 수를 출력한다. 예제 입력 1 4 2 1924 예제 출력 1 94 예제 입력 2 7 3 1231234 예제 출력 2 3234 예제 입력 3 10 4 4177252841 예제 출력 3 775841 문제 풀이📝 제일 먼저 떠올랐었던 풀이 방법은 조합이었다. 숫자를 k개 뽑을 수 있는 모든 경우를 고려하면 된다. 결과는 시간초과였지만... 조금 더 그리디스럽게 풀어..

문제 읽기🤔 문제 한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다. 각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다. 편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표..

문제 읽기🤔 문제 수강신청의 마스터 김종혜 선생님에게 새로운 과제가 주어졌다. 김종혜 선생님한테는 Si에 시작해서 Ti에 끝나는 N개의 수업이 주어지는데, 최소의 강의실을 사용해서 모든 수업을 가능하게 해야 한다. 참고로, 수업이 끝난 직후에 다음 수업을 시작할 수 있다. (즉, Ti ≤ Sj 일 경우 i 수업과 j 수업은 같이 들을 수 있다.) 수강신청 대충한 게 찔리면, 선생님을 도와드리자! 입력 첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (0 ≤ Si < Ti ≤ 10^9) N이 최대 200,000이기 때문에 모든 경우의 수를 따진다면 O(n^2) -. 200,000^2으로 무조건 시간초과 출력 강의실의 개수를 출력하라. 예제 입력 3 ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 읽기🤔 문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 1) 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 2) 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 1) 시작시간, 끝나는 시..

풀이 class Solution { public String[] solution(int n, int[] arr1, int[] arr2) { String[] answer = new String[n]; for (int i = 0; i < n; i++){ answer[i] = ""; // answer[i]를 빈 무자열로 초기화 String arr1Str = Integer.toString(arr1[i], 2); String arr2Str = Integer.toString(arr2[i], 2); // 자릿수에 맞게 앞쪽에 0을 채워줌 while (arr1Str.length() < n || arr2Str.length() < n){ if (arr1Str.length() < n) arr1Str = "0" + arr1S..

문제설명 자연수 n이 매개변수로 주어집니다. n을 3진법 상에서 앞뒤로 뒤집은 후, 이를 다시 10진법으로 표현한 수를 return 하도록 solution 함수를 완성해주세요. 제한사항 n은 1 이상 100,000,000 이하인 자연수입니다. 풀이 3진수에 대한 이해 10진수는 한 자리당 0부터 9까지 총 10개의 자연수가 들어갈 수 있다. 이와 마찬가지로 3진수는 한 자리당 0부터 3까지의 자연수가 들어갈 수 있다. ex. 0(0) -> 1(1) -> 2(2) -> 10(3) -> 11(4) -> 12(5) -> 20(6) 알고리즘 1. 10진수를 3진수로 변환했을 때의 자릿수를 구한다. (ex. 45는 3진수로 변환하면 1200이므로 4자릿수이다.) 주어진 10진수가 3의 k제곱보다 크다면 k++, ..