백준

DP 문제 풀이 팁을 유튜브로 찾아보던 중 '개발자로 취직하기' 유튜버님의 DP 문제해설 영상을 보게 되어 해당 문제를 풀게 되었다. 해설 영상을 기존에 봤기 때문에 해당 문제에 대해 다시 정리한다. 풀이 접근4. 2개 이상 전구들 간의 최솟값 계산1. 입력 받은 숫자를 전구 배열에 추가 - 입력 받은 숫자가 연달아 입력되는 경우 색상 변경 시 일괄 변경되므로 추가하지 않음2. 전구 배열에 추가된 숫자 개수만큼 DP 배열 크기 설정3. DP 배열 최댓값으로 초기화(나중에 최솟값 비교) - |1,1|2,2|3,3|4,4|5,5| 0으로 세팅 최솟값 계산 기준 먼저 인접해 있는 동일한 수를 모두 배제한 전구 배열(lamp)에 5개의 요솟수가 있다고 가정한다.이후 1개부터 5개로 분할하여 나온 묶음에서 하..

퇴근할 때쯤 디자이너 선임님께서 15퍼즐이라는 문제와 해당 문제를 풀 때 사용하는 A-Star 알고리즘을 알고 있냐고 물어봤다. 처음 들어봐서 공부도 할 겸 백준에서 검색을 해보니 비슷한 문제가 나와서 위 문제를 풀려고 했는데 뭔가 이상했다. 문제를 읽었을 때는 선임님에게 들은 내용(퍼즐이 움직이는 것)과 다르게 단순히 각 정사각형이 이동해야 하는 거리만 계산하면 해결되는 문제라고 느꼈지만... 이것도 이 문제와 인연이겠지 하면서 그냥 풀었다.  풀이퍼즐에서 각 정사각형 문자와 'A' 문자를 빼서 얻은 정수는 다음과 같다.[ 각 문자 - 'A' 값 ]A: 0B: 1C: 2...O: 14이렇게 보면 현재 위치에 있는 숫자를 4로 나눈 값이 x이고 4로 나눈 나머지 값이 y인 규칙이 하나 보인다. 현재 위치..

개요위 문제는 최대 연산의 수(M)가 3,000,000이기 때문에 반복문을 사용하면 안될 것 같아 HashMap 자료구조를 사용하여 문제를 해결하였다. 해당 문제를 해결한 후 다른 사람들이 어떤 방식으로 풀었는지 확인할 결과 비트마스크 알고리즘을 사용하여 푼 방식이 존재하여 필자는 아래 2가지 방법으로 문제를 풀어보았다. 성공소스1. HashMap 사용add: map의 containsKey와 put 메서드를 사용하여 x값을 추가한다.remove: map의 remove 메서드를 사용하여 x값을 제거한다.toggle: map의 containsKey 메서드와 put, remove 메서드를 활용한다.all: 반복문을 사용하여 1 ~ 20을 map에 put한다.empty: map의 clear 메서드를 사용한다.참..

이번 문제는 1%에서 틀렸다고 나왔는데 아직 해당 문제의 원인을 찾지 못했다... 원인을 계속 찾아보는데 시간이 너무 오래 걸릴 것 같아 기존에 듣던 인강을 마저 듣기로 하고 내일 다시 문제를 풀 예정이다. 오늘까지 작성한 소스는 아래와 같다. 실패한 소스public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); // 최대 인벤토리 크기 final i..

이번 문제의 난이도는 실버 4이고 정답률은 낮지만 상당히 쉬운 문제였다. 브론즈 난이도의 문제 중에 이 문제보다 어려운 문제들이 더 많은데 왜 실버 4인지는 잘 모르겠다. - 구현 소스public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arrDifficulty = new int[n]; for (int i = 0; i    이제 solved.ac 사..

이번 문제는 친절하게도 문제에서 어떻게 연산을 하라고 다 알려주고 있지만 필자는 처음에 50점을 맞았다... 필자의 처음 생각으로는 알파벳 a가 1이 나와야 하고 a의 아스키코드 값이 96이니까 -95를 더했고$a_i * r^i$ 이 수식은 반복문을 사용하며 제곱의 경우 Math 클래스의 pow 메서드를 사용하면 되겠다고 생각을 하였다.그러나 오버플로우가 발생하여 50점이 나왔다. 실패한 소스 - 오버플로우 발생final int NUMBER = 31;final int M = 1234567891;int l = Integer.parseInt(br.readLine());String str = br.readLine();long sum = 0L;for (int i = 0; i  어떻게 보면 당연한 것을 놓쳐버렸다..

이번 문제는 아래 4가지 요소들을 찾는 문제로 난이도가 낮아보였는데 정답 비율도 낮아서 처음엔 의아했다. 산술평균 : N개의 수들의 합을 N으로 나눈 값중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값최빈값 : N개의 수들 중 가장 많이 나타나는 값범위 : N개의 수들 중 최댓값과 최솟값의 차이 산술평균 소스산술평균은 입력된 모든 값들을 더한 후 배열의 길이로 나누어 주었다. 입력된 값의 범위가 -4000 ~ 4000이고 입력값의 최대 개수가 50만개이기 때문에 sum 변수의 자료형을 double로 선언하였다.int n = Integer.parseInt(br.readLine());final int[] arr = new int[n];double sum = 0;// 산술평균for..

이번 문제는 문제를 이해하는 데에만 시간이 좀 걸렸다. 처음에는 예제 입력 3번째 줄의 각 수를 8진수로 변환한 후 출력하는 것으로 알고 풀어 예제 출력 중 6이 아닌 4 2가 나와서 이상함을 느꼈다. 예제 입력을 정리하면 입력의 2번째 줄은 A진법 수의 자릿수의 개수를 나타내고 3번째 줄은 각 자릿수이다. 예를 들어 3번째 줄 첫 번째 입력인 2는 $2 * 17^1$, 16은 $16 * 17^0$이고 10진수로는 $34 + 16 = 50$이다. 그러므로 10진수로 변환한 50을 B진법으로 변환하면 해결된다.      성공 소스public class _11576 { public static void main(String[] args) throws IOException{ BufferedR..