꾸준히 삽질하기,,

📍 문제 https://www.acmicpc.net/problem/9663 📍 문제 풀이  1. 2차원 배열 이용처음에 문제를 보자마자 엥? 했던 부분은 퀸은 어떻게 움직이는데...?라고 하면서 풀이를 조금 찾아봤다퀸은 상하좌우 일직선으로 움직일 수 있다.   첫번째 열부터 순차적으로 퀸을 배치한다. 2차원 배열을 이용해서 위치를 이동하며 퀸을 배치할 수 있는지 확인한다 `isValid` 메서드를 이용해서 확인해야하는 경우의 수해당 열에 퀸이 존재하는지윗 대각선에 퀸이 존재하는지아랫 대각선에 퀸이 존재하는지위의 경우를 모두 만족하지 않아야만 현재 위치에 퀸을 배치할 수 있다. 현재 위치에 배치할 수 있다면 배열의 값을 `1`로 두고 백트래킹을 통해 마지막까지 탐색한다.import java.io.IOE..

📍 문제 https://www.acmicpc.net/problem/1759  📍 문제 풀이 가능한 문자를 조합하여 갯수를 구하는 문제 -> 백트래킹가능한 문자를 조합하여 가능한 문자열을 모두 구하는 문제 -> 백트래킹 + 브루트포스때문에 이 문제는 백트래킹 + 브루트포스 문제라고 판단했다.  주어진 문자 배열에서 `L`개를 뽑을 때까지 값을 채워나간다.만약 `L`개를 뽑았다면 그 수가 가능성 있는 암호인지 판단해 가능성 있는 수라면 출력static void dfs(int start, int cnt) { if (cnt == L) { if (isValid()) { System.out.println(passwords); } return; } for (int i = start; i   ..

📍 문제 https://www.acmicpc.net/problem/1339  📍 문제 풀이 합을 최대로 만들려면  1. 가장 높은 자릿수를 가지는 알파벳을 판단해주고 숫자를 할당2. 더 빈번하게 나온 수에 큰 숫자를 할당 예제2로 생각해보면 GCF + ACDEB(100G + 10C + F) + (10000A + 1000C + 100D + 10E + B)10000A  + 1000C + 100G + 100D + 10C + 10E + F + B알파벳숫자A9C8G7D6E5F4B3 위의 표를 이용해 숫자를 대입해보면 98653 + 784 = 99437  📍 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStr..

📍 문제 https://www.acmicpc.net/problem/28353  📍 문제 풀이 투포인터로 합과 `k`를 비교하며 진행📍 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class boj_28353 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringT..

📍 문제 https://www.acmicpc.net/problem/1138 📍 문제 풀이  1. 키가 작은 사람부터 채워나가는 방법키가 작은 사람부터 빈자리에 채워나가는 식으로 구현했다. 키가 큰 사람이 왼쪽에 몇 명 있어야하는지 확인해 빈자리로 두고 값을 채우면 된다. 빈자리인지를 확인하기 위해서 `answer`를 둬서 값이 0이라면 빈자리, 다른 값이라면 채워진 자리로 판단했다.import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.Arrays;import java.util.StringTokenizer;public class boj_1138 { public sta..

📍 문제 https://www.acmicpc.net/problem/1253 📍 문제 풀이  두 개를 더해서 어떤 수가 나오려면 정렬해서 이분 탐색을 통해 찾아내자 기본적인 이분 탐색의 경우에는 아래의 경우만 확인해주면 되지만우리는 두 개를 더해서 구하려는 어떤수 가 지정된 하나의 값이 아니라몇 개인지를 구하려는 것이기 때문에 for문을 돌려줘야한다.int sum = nums[start] + nums[end];if (sum == nums[i]) { result++; break;} else if (sum  그리고 지정한 `start`와 `end` 값이 for문의 인덱스와 같다면어떤 수를 더해도 `nums[i]`보다 커지기 때문에 조건문으로 처리해줘야한다.if (start == i) { start++;} ..

📍 문제 https://www.acmicpc.net/problem/1715 📍 문제 풀이 데이터를 정렬 -> 조회 -> 삽입이 반복적으로 이루어진다우선순위 큐 사용 1. 데이터 전체를 오름차순으로 정렬2. 가장 작은 숫자를 더해서 다시 우선순위 큐에 삽입3. 우선순위 큐의 사이즈가 1이 될 때까지 (1)(2)과정 반복 📍 전체 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.PriorityQueue;public class boj_1715 { public static void main(String[] args) throws IOException { Buf..

📍 문제 https://www.acmicpc.net/problem/11000 📍 문제 풀이 가장 먼저 생각해야하는건 정렬시작 시간을 기준으로 오름차순 정렬해주고, 시작 시간이 같다면 끝나는 시간을 기준으로 오름차순 정렬 해줘야 가장 적은 강의실로 가장 많은 수업이 가능하다 1. 시작시간과 종료시간을 통한 정렬 -> `List` 이용2. 시작시간이 가장 빠른 강의의 종료시간을 우선순위큐에 저장  `pq.offer(times.get(0).end);`3. 가장 빨리 끝나는 강의의 종료시간 vs 배정 안된 강의의 시작 시간을 비교후자가 더 큰 경우에는 같은 강의실에 강의 배정 -> 해당 강의 제거하고 배정 안된 강의의 종료시간 우선순위큐에 삽입for (int i = 1; i  4. 2-3과정을 반복한 뒤 큐..

📍 문제 https://www.acmicpc.net/problem/2629 📍 문제 풀이  주어진 추의 무게로 구슬의 무게를 확인할 수 있는가의 문제이다무게를 확인해야하는 구슬을 한쪽으로 고정 -> 왼쪽그렇다면 경우의 수는 3가지더보기1. 구슬을 왼쪽에 추가2. 구슬을 오른쪽에 추가3. 구슬을 올리지 않음일종의 0-1 배낭문제이다.배낭문제의 경우에는 Max가 주어지고 그 안에서 그 한도내에서 넣을 수 있는 최대값을 골라내는 문제라면 이 문제의 경우에는 모든 숫자 조합을 저장해주면 된다.  🙋🏻 재귀 이용static void getWeights(int num, int weight) { if(dp[num][weight]) return; dp[num][weight] = true; if(num ==..