Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처좌표 압축 실버 2 📖 문제 이분탐색을 이용해서 주어진 좌표의 인덱스 위치를 빠르게 찾는 문제이다. 우선 문제를 이해하기 위해 좌표평면을 그린다. Xi > Xj 를 만족하는 '서로 다른' Xj의 개수가 Xi를 압축한 좌표이다. 예제 1번을 예로 정렬해보자 -10  -9     2    4(2개) 이제 첫 입력 좌표인 x1의 경우 2 > Xj의 개수를 찾으면 된다여기서 2보다 작은건 -10, -9이므로 2개즉, X1의 압축된 좌표는 2이다.  이 문제에서 중요한 점은 중복값 처리이다.  예제 2번에서 친절히 알려준다. 999 999 999 1000 1000 1000  사실상 좌표평면에서는 999 1000 이 두개이다.따라서 중복을 제거해야한다.  배열에 중복을 제거한 좌표들을 정..

🧫 문제 분석 ✔️ 출처가장 긴 증가하는 부분 수열 2 골드 2 📖 문제 가장 긴 증가하는 부분 수열 1에 이어 2문제는 DP로는 불가능하고이분탐색을 통한 대치, 추가를 하여 부분 수열을 만들어 가야한다.  많은 블로그들이 원리를 설명하고 있으므로 생략하고 내가 헷갈렸던 것만 정리한다.  범위 탐색에서 front 무분별하게 front  이문제는 이렇게 풀면 좋지 않다.  근데 이렇게 해서 풀긴했다... ㅋㅋ front 이유는 front == back일때도 탐색함으로써 정확한 탐색이 가능하기 때문이다.  front front = mid + 1;back = mid; 이런식으로 범위를 줄이는데 현재 mid 위치의 값 front는 mid + 1을 하는 이유가 뭘까 라는 의문점이 생겼다. LIS는 증가하는 부..

🧫 문제 분석 ✔️ 출처예산 실버 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[][]..