Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처리모컨 골드 5 📖 문제 부서진 버튼을 제외한 버튼들을 가지고 BackTracking으로 완전탐색해서 이동하려는 채널 길이와 가장 가까운 수를 찾는다. 이동하려는 채널 길이 - 1 ~ 이동하려는 채널 길이 +1 까지의 수를 찾는데 그 이유는 998  이문제 15% 와 32%에서 계속 틀렸었다. 15% 실패처음 백트래킹 메서드를 호출할때 매개변수로 깊이를 0, 숫자를 0으로 줘서 n = 1 이고0버튼이 부숴졌다고 했을 때 매개변수로 시작 숫자를 0으로 줘서 버튼이 부숴졌음에도 불구하고 if문에 걸려 바로 최솟값으로 반환되버렸다.  32% 실패단순 Math.abs(n - 탐색으로 찾은 수) Math.abs(n - 탐색으로 찾은 수), len = 현재 num의 길이 이런식으로 구하고탐..

🧫 문제 분석 ✔️ 출처뱀과 사다리 게임 골드 5 📖 문제 주사위를 굴려서 1~6까지 숫자를 현재 위치에 더하면서 BFS 탐색을 하면 된다. (최단 경로) 1차원 배열을 게임 판이라 생각하고 100칸을 만든다. x번 도착하면 y번 칸 이동 , u번 도착하면 v번 칸 이동 이므로왼쪽 입력을 인덱스로 사용, 오른쪽 입력을 값으로 사용한다.  BFS 탐색을 하면서 주사위를 굴려 이동할때 이동한 위치가map에서 값이 있다면 그 값으로 이동한다.  물론 방문 체크를 해줘야한다. 이 경우 특별한 이동방법이 없으므로 1차원 배열로 체크해주면 된다.  특별한 이동 방법을 쓰는 문제 포스팅 보러가기 백준 1600번 : 말이 되고픈 원숭이 자바 백준 2206번 : 벽 부수고 이동하기 자바  🔅 문제 풀이import ..

보통 String.matches, replaceAll 에 많이 사용하므로 거기에 맞춰서 정리1. 기본적인 정규 표현식 요소1.1 문자 클래스(Character Classes).임의의 한 문자 (개행 제외)[abc]a, b, c 중 하나[^abc]a, b, c를 제외한 어떤 문자[a-z]소문자 알파벳 한 글자 (a~z)[A-Z]대문자 알파벳 한 글자 (A~Z)[0-9]숫자 (0~9)[a-zA-Z0-9]영문 대소문자 + 숫자\d숫자 (0-9) (== [0-9])\D숫자가 아닌 문자 (== [^0-9])\w알파벳 또는 숫자 또는 _ ([a-zA-Z0-9_])\W\w가 아닌 문자 (공백, 특수 문자 등)\s공백 문자 (스페이스, 탭, 개행 등)\S공백이 아닌 문자1.2 앵커(Anchors)정규식설명^문자열의 시..

🧫 문제 분석 ✔️ 출처비밀번호 발음하기 실버 5 📖 문제 정규표현식 연습하고싶어서 풀게된 문제다.정규표현식은 매번 까먹기때문에 많이 해봐야하고 잘 숙지해야한다.  3번째 조건 ee, oo는 허용하면서 나머지 같은 글자 연속 2번을 제외하는게 조금 어려웠다. (결국 검색해봄..) 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static String[] eval = {"is acceptable.", "is not acceptable."}; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader..

🧫 문제 분석 ✔️ 출처중량제한 골드 3 📖 문제 최단 경로 + 최대신장(최소 신장의 반대라서 이렇게 붙였다) + 이분탐색 문제다.근데 본인은 최대 신장 트리로 안풀고, 현재 이분탐색 문제를 공부중이므로 이분탐색 + BFS 최단경로로 풀었다.  이분탐색으로 찾고자 하는 것은 두 섬 사이의 경로 이동 비용 최댓값이다. 가장 비용이 큰 값을 max로 잡고 1 ~ max 사이를 이분탐색하면서 mid값으로 BFS 탐색을 한다. BFS 탐색에서는 공장이 있는 섬A에서부터 탐색을 하되 mid 값 (중량)을 다리의 중량제한이 버틸 수 있다면 다음 다리로 탐색한다. 공장이 있는 섬 B에 도착하면 현재 mid 값의 중량은 버틴다는 의미이므로 true를 반환해 알린다.이분탐색에서는 BFS 결과가 true이면 mid 값..

🧫 문제 분석 ✔️ 출처과자 나눠주기 실버 2 📖 문제 이 문제는 조카에게 최대한의 막대 과자 길이를 균등하게 나눠주는 것이 목표이다.  그러기 위해서는 적절한 과자길이를 찾아야하는데 여기서 이분탐색을 활용한다. 문제에서 알려줬듯이 과자를 하나로 합칠 순 없다.  예제 2번을 보면 왜 7인지 의문을 품을 수도 있다. 길이가 8이면 2 2 7 로 합치면 11이되는데 문제에서 여러 조각으로 나눠질 수 있지만 하나로 합칠 수 없다. 라고 나왔기에합치면 안된다. 이분탐색으로 적절한 길이를 찾고, 각 막대과자를 탐색한 길이로 나눈 개수가 조카M명을 넘는지 안넘는지 비교하면서 찾으면 된다.  나눠줄 수 없다면 0을 출력한다. 5 31 1 1 이런 경우 0이다.🔅 문제 풀이import java.io.*;impo..

🧫 문제 분석 ✔️ 출처좌표 압축 실버 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값을 상한값으로 더한다.그리고 국가예산과 합을..

🧫 문제 분석✔️ 출처부대 복귀 level 3📖 문제 최단경로인데 길이가 1이라해서 그냥 BFS로 풀었다.  몰랐던 사실인데 n이 10만이고, roads에서 모든 노드를 주지 않으므로, 메모리 낭비라고 생각해서 HashMap을 사용하는것이 좋아보인다고 생각해서 사용했다.  목적지 (destination)부터 끝노드까지 (탐색이 종료될때까지 ) 돌게 하되방문한 곳이 source[i] 면 거리값을 저장한다.   물론 다익스트라 알고리즘을 쓰는게 맞는것 같다. 내 로직보다 속도는 약 5배 정도 더 빠르다. 문제에서 최단 경로 라고 주어졌는데 비용이 1이라는 말에 BFS로 밀고 가려해서 저렇게 짠 것이다.   참고 HashMap은 해시 충돌을 대비한 내부 구조 (엔트리 배열, 체이닝 등)로 인해 메모리 오버..