Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처예산 실버 2 📖 문제 이진 탐색이다. 하지만 국가 예산이라는 제한이 걸려있다.때문에 무턱대고 이진탐색 범위를 0 ~ 10억 이렇게 설정하면 정말 쓴 맛을 느낄 수 있다.  필자는 저렇게해서 삽질을 엄청하고, 반례는 다 통과하는데 75퍼에서 자꾸 틀리는 문제가 발생했다. 생각해보면 탐색을 할 범위를 명확하게 알고 설정해야하는데 무턱대고 큰 값을 설정한 것이 화근이였고이진탐색을 할 줄만 알지 정확하게 이 알고리즘에 대해 이해하지 못함을 느꼈다. 따라서 이진탐색을 파볼 예정이다.  요청 예산중 최댓값을 max로 이진 탐색한다. mid값을 각 요청 예산에 연산하여 mid > 요청 예산[i] 면 요청 예산값을 합 변수에 더하고,크다면 mid값을 상한값으로 더한다.그리고 국가예산과 합을..

🧫 문제 분석✔️ 출처소용돌이 예쁘게 출력하기 골드 3 📖 문제좌표 (0,0) 에서 시작해서 상하좌우로 이동한다. 이동 방향은→ ↑ ← ↓ 이렇게 반시계방향이며이동 거리는 1에서 시작해서2번 방향을 전환하면 이동거리는 1씩 증가  이동 한 좌표를 갱신하면서 현재 위치가 문제에서 주어진 r2,r1,c1,c2 박스 범위 안에 있는지 확인한다.범위 안에 있다면 그 위치에 숫자를 넣어주면 된다. (숫자는 이동할때마다 1씩 증가) 문제는 r1,c1,r2,c2가 -5000 ~ 5000까지 범위인데우리가 만드는 배열들은 음수 인덱스 표현이 안된다. 이렇게 시작지점을 0,0으로 끌어당겨야한다. arr[현재 위치r - r1] [현재 위치c - c1] 로 인덱스에 접근하면 r1, r2가 0,0으로 맞춰져서 배열 안 범..

🧫 문제 분석 ✔️ 출처20207번 달력 골드 5 📖 문제 열 : 365 + 2 (1부터 365까지, 그리고 마지막에 값이 남은채로 계산되는 거 방지용)행 : 중복 일정 가능성 1000개높이 배열 하나 생성 입력 값은 시작 날짜가 빠른 순, 같다면 길이가 긴 순으로 오름차 정렬→ 근데 시작 날짜가 빠른 순으로 해도 된다. 일정에 각 날짜 기간 저장, 중복이라면 현재 행 + 1에 날짜 기간 저장0 행에는 중첩 날짜를 이어서 저장높이 배열에는 각 날짜의 높이 최댓값을 저장 그리고 0행의 일정을 쭉 탐색해서 길이를 구하고 최대 높이를 구한다음 길이 * 높이를 더해 코팅지 면적을 구한다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { ..

🧫 문제 분석 ✔️ 출처별 찍기 - 11 골드 4 📖 문제    재귀로 풀어야 될거 같은 패턴 모양이다 삼각형을 3개로 나눠서 위쪽, 아래왼쪽, 아래 오른쪽 으로 분할한다. 높이는 N 이고밑변은 N * 2 - 1 이다. n 이 3일 때까지 재귀로 삼각형을 분할하고3이되면 위치에 맞게 별을 넣으면 된다.  아래의 그림을 참조하면 될 것 같다. 이 방식으로 삼각형을 분할한다.   처음 시도때 실수 한 것이 삼각형의 위쪽 별 위치를 재귀로 넘겨서 분할할려 했는데인덱스 벗어나거나 하는 문제가 발생했다.    🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static char[][] arr; public static void mai..

🧫 문제 분석 ✔️ 출처DNA 비밀번호 실버 2 📖 문제   투포인터 문제로 슬라이딩 윈도우에 대한 지식이 있다면풀이방법이 쉽게 떠오를 것이다.  모르겠다면 네트워크에서 흐름제어로 사용중인 슬라이딩 윈도우 에 대해서 학습해보자.  이 문제는 윈도우 역할을 할 배열을 하나 만들고,읽어들인 비밀번호가 DNA 문자에 맞는지 확인하기 위해 각 문자마다 개수를 저장할 배열을 만든다.  front 포인터와 back 포인터로 이용하되우선 부분 문자열 p 만큼윈도우에 채우고 만들 수 있는 DNA 비밀번호인지확인한다. 확인 후 새로운 문자를 받기위해  front를 뒤로 한 칸 땡겨서 윈도우의 맨 앞쪽을 빼고 윈도우 사이즈를 1 줄인 뒤 back을 늘려서 윈도우 사이즈를 p일때까지 채운다.  p 가4라 했을 때    ..

🧫 문제 분석 ✔️ 출처막대기 실버 5 📖 문제  비트 마스킹 문제인데 바른 방식으로 풀었다. 시간차는 비트마스킹이랑 4ms 차이정도 났다. 비트마스킹 제대로 공부해야겠다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); ..

🧫 문제 분석 ✔️ 출처프렉탈 평면 골드 3 📖 문제  분할 정복 문제증말 어려웠던 문제였다. 필자는 먼저 s초가 흐른 뒤의 크기부터 n으로 나눠가며 분할했다.n^s → n ^s / n → n ^s - 1 / n ...핵심black 체크 (어떻게 계속해서 분할되는 정사각형에서 black인지 아닌지 확인할 것인가)주어진 범위를 벗어나면 탐색 범위 제외 black 체크black 체크의 경우 문제에서 나와있듯이 (N - K) % 2 = 0이다.즉 , 분할한 각 구역의 시작 위치에서 대각선으로 (N - K) / 2 만큼 떨어져있다는 의미이기도 하다.이를 블랙 포인트라 하자.문제는 시간이 지날수록 n*n 씩 나눠지고, 사각형은 k*k 크기로 만들어진다.  앞서 말했듯이 n^s 부터 시작한다. 여기서 구한 블랙..

🧫 문제 분석 ✔️ 출처별 찍기 골드 5 📖 문제 분할정복 문제로N이 3의 거듭 제곱으로 주어지고 3의 거듭 제곱을 3으로 나눌때 중앙이 공백이 되어야한다. 재귀로 주어진 N / 3 을 하여 3등분을 하고 (이에 따라 N/3 개의 위치가 생김)각 위치에 따라 재귀로 호출한 후재귀가 끝나면 각 구역의 가운데 부분을 for문을 돌면서 빈칸을 채운다.  예를 들어 27이면y : 0, 9, 18 x : 0 , 9, 18  이런 식으로 3등분 했을 때 구역의 첫 위치를 재귀로 넘긴다.   나는 먼저 배열을 *로 가득 채운 상태에서 공백을 넣는 방법을 사용하였다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static char[][]..

🧫 문제 분석 ✔️ 출처오르막 수 실버 1 📖 문제 깊이 별로 나누되 0~10까지 에 대해서 동적프로그래밍을 한다. 중요한 점수는 0으로 시작할 수 있다는 것이다.  현재 깊이의 각 수는 이전 깊이의 현재 수부터 9까지의 개수 합을 더하면 된다.   수 \ 깊이12301깊이 1의 0~9까지 : 10깊이 2의 0~9 까지 : 5511깊이 1의 1~9까지 : 9깊이 2의 1~9까지 : 4521깊이 1의 2~9까지 : 8깊이 2의 2~9까지 : 36 잘 모르겠다면 노드로 직접 그려보면 바로 알기 쉽다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws I..

🧫 문제 분석  ✔️ 출처연구소 골드 4 📖 문제 완전탐색  + BFS 문제이다. ( + 백트래킹...?) 단순하게 0인 곳에서 1을 세우되 3개까지만 세우고 BFS로 탐색해보고 퍼진 바이러스 개수의 최솟값을 구한다. 1을 세우는 것은 모든 구역에 대해서 진행하면 된다.  1로 된 벽 개수를 세고바이러스 위치를 list에 담고안전한 구역을 zeroList에 담는다.  list는 bfs에서 빠르게 사용하기 위함이고,zeroList는 완전탐색을 빠르게 하기 위함이다. 전체 크기 - (벽의 개수 + 새롭게 세운 벽 3개 + 바이러스 개수의 최솟값) 이 안전구역의 최댓값이다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static..