Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처설탕 배달 실버 4 📖 문제 풀었던 문제를 보다가 꼭 다시 풀라고 메모를 적어놔서 다시 풀었다. DP로 풀 수 있는 문제이다. 3 과 5로 나눠 떨어지지 않는 1 , 2, 4, 7 은 -1로 3 5 은 1로 미리 초기화한다.6도 미리 2로 초기화한다. N - 3과 N - 5 중 더 작은 값을 취하고 +1해주면 dp[N] 이 된다.  N에서 3키로를 한 봉지를 담고 [N-3] 키로일때 얻은 봉지 최솟값과N에서 5키로를 한 봉지를 담고 [N-5] 키로일때 얻은 봉지 최솟값 중 더 작은 값을 취하는 것이다. dp[i] = Math.min(dp[i - 3], dp[i - 5]) + 1;       🔅 문제 풀이import java.io.*;public class Main { p..

🧫 문제 분석✔️ 출처모음사전 level 2📖 문제 정말 어려워했던 문제이다.결국에는 풀었다.  A : 1E : 2I : 3O : 4U : 5로 바꾸고  이에 맞춰서 완전탐색을 해서 매개변수로 넘어온 word 와 equals로 비교한 후 같다면 깊이 탐색을 멈추고 count를 반환한다. 🔅 문제 풀이class Solution { int count = 0; boolean flag = false; StringBuilder sb = new StringBuilder(); public int solution(String word) { dfs(trans(word), 0); return count; } private void dfs(Stri..

🧫 문제 분석✔️ 출처회의실 배정 실버 1 📖 문제 정렬 문제로 회의가 끝나는 시간을 기준으로 정렬하되 같다면 시작시간을 오름차순으로 정렬해야한다.주의할 점은 끝나는 시간에 바로 다른 회의가 시작할 수 있다는 것이다.  정렬 후 마지막 회의 시간 보다 다음 회의의 시작시간이 크거나 같으면 이는 가능한 회의이므로 마지막 회의시간을 다음 회의가 끝나는 시간으로 바꾼다.   종료시간이 같다면 시작시간을 오름차순 정렬을 해야하는 이유예를 들어보면41 22 24 42 4 이것을 끝나는 시간으로만 정렬했을 경우입력 순서대로 1 22 24 42 4 이대로 들어왔을 것이고 마지막 회의시간은 2 -> 2-> 4로 되고 2 4 일때 마지막 회의시간 = 4 이기에 이 회의는 무시된다. 따라서 잘못된 답을 내놓게 ..

🧫 문제 분석 ✔️ 출처파도반 수열 실버 3 📖 문제  DP문제다. 중복 연산이 포함되어있다.  12번째는 12 + 4 로 번호를 매겨보면 11번째 + 7번째 를 더한 것이다.  그런데 4또한 3 + 1이며 번호를 매겨보면6번째 + 2번째 를 더한 것이다.   이를 점화식으로 보면dp[n] = dp[n-1] + dp[n-5]  이렇게 볼 수 있다.  이전값 + dp[n-5] 가 아닌 이유는 이전 값 또한 어떠한 숫자들의 덧셈 결과일 수 있기 때문이다.   🔅 문제 풀이import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new ..

🧫 문제 분석 ✔️ 출처IOIOI 실버 1📖 문제주어진 문자열에서 IOI 패턴으로 나오는 문자열의 개수를 찾는 문제이다. 몰랐는데 서브태스크는  여러가지 채점 방식이 있나보다. 배점이 50점 2개가 있다.  처음에는 match를 썼다가 너무 오래걸려서 50점 받았다.  IOI를 찾고 카운팅 + 1 하고 현 위치에서 +2로 이동한 후 (이러면 IOI 에서 마지막 I자리로 간다.)또 현 위치에서부터 +2 위치까지 IOI를 찾는다. 이런식으로 카운팅한 개수가 n과 같다면 answer 에 +1을 하고 count를 - 1 해주는데 이유는 겹쳐져있는 IOI를 빠르게 구별하기 위함이다. 예를들어n = 2라 하자IOIOI 를 찾아야한다. IOIOIOI 가 있다면 i = 0 일 때 IOI 찾고 카운팅 +1 위치는 i..

🧫 문제 분석✔️ 출처백준 2206번 벽 부수고 이동하기 골드 3 📖 문제 그래프 BFS 탐색 문제이다.여러가지 방법으로 탐색, 최단 거리로벽을 부순 경우와 부수지 않은 경우 방문을 체크해줘야한다.  그외에는 단순한 넓이 우선 탐색을 해주면 된다.  조심할 것은 시작지점도 거리에 포함  비슷한 문제 백준 1600번 : 말이 되고픈 원숭이 자바   🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int[][] graph; static boolean[][][] visited; static int[] dx = {0, 0, 1, -1}; static int[] dy = {1, -1, 0, 0}; publ..

🧫 문제 분석 ✔️ 출처말이 되고픈 원숭이 골드 3 📖 문제 상하좌우, 체스의 나이트 이동방식을 BFS 방식으로 푸는 문제이다. 이 문제에서 핵심은 말 움직임은 k번만 가능하다이때 중요한 것은 0~k번 말 움직임의 경우를 각각 따져서 가장 빠르게 오른쪽 끝으로 도달한 경우를 찾는 것이다. 말 움직임을 0번도 안쓰고 상하좌우로만 목표점에 도달한 경우말 움직임을 1번 쓰고 상하좌우로만 목표점에 도달한 경우 ...말 움직임을 k번 쓰고 상하좌우로만 목표점에 도달한 경우  이때 각 말 움직임 횟수마다 방문 체크를 해줘야한다.  말 움직임 구현상하좌우로 먼저 탐색을 하고그 방향으로 1번 더 간 다음 상하일 경우 좌우를 탐색좌우일 경우 상하를 탐색한다.  코드와 그림을 보면 이해하기 쉽다.    이와 비슷한 ..

🧫 문제 분석 ✔️ 출처적록색약 골드 5 📖 문제 BFS 혹은 DFS 그래프 탐색 문제이다.나는 BFS를 좋아해서 BFS로 풀었다.  적록색약은 적록색(R) 과 초록색(G)의 차이를 거의 못느낀다.따라서 둘중 하나로 통일하면 된다.   나는 문제를 잘못 이해해서적록색과 초록색의 상화좌우로 인접해 있는 부분만 차이를 못느끼는 줄 알고 문제의 난이도를 더 높여서 풀다가 자꾸 틀리고 이상해서 문제를 다시봤더니 초록색과 적록색 차이가 없다고 보는게 맞았다...(이때문에 시간을 많이 소요함) 이 풀이법도 밑에 올리겠다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static boolean[][] visited; static i..

🧫 문제 분석✔️ 출처AC 골드 5 📖 문제 문자열, 구조 문제이다.덱이 생각이 안나서 그냥 투 포인터로 풀었다..ㅎㅎㅎㅎ 문제에서 핵심은 문자열 파싱 : [1,2,3,4] 이런 식으로 입력이 주어지기에 이를 적절하게 파싱한다.R : 배열 순서 뒤집기D : 첫번째 요소 삭제빈 배열에 D를 사용할 경우 에러 발생 [1,2] 에서 DD 를 하면 [] 을 출력한다. error가 아니다.   문자열 파싱은 subString으로 앞 뒤의  ' [ ' , ' ] ' 를 짤라내고split으로 정규표현식을 사용하여 [^0-9]로 숫자가 아닌 모든 것을 기준으로 짤라 문자열 배열을 만들었고이를 int 배열에 파싱하여 저장하였다.  두 개의 포인터를 사용하여 풀었다. 자세한건 코드를 참고해주면 좋을 것 같다.  🔅 ..

🧫 문제 분석 ✔️ 출처신기한 소수 골드 5 📖 문제  (첫번째 수 + 두번째 수) 가 소수면 첫번째 수 * 10 + 두번째 수 를 파라미터로 넘겨 재귀로 호출한다.  백트래킹으로 풀어주면 된다. 소수 판별은 제곱근을 이용한 방법을 사용했다.  판별할 수의 제곱근을 구해서2~제곱근까지의 수로 나눠떨어지면 소수가 아니다. 자세히 말하자면 n = p*q 라 했을 때 (n > 0) p >=√n 일때p로 나누면 그 몫은 q이며q 이다.한쪽이 √N이상이고, 한쪽이 √N이하인 수의 곱이다.  4를 생각해보자p x q √N = 2      p            q1 x 4  1  ≤ √N,  4  ≥ √N 2 x 22  ≤ √N,  2  ≥ √N4 x 14  ≥ √N,  1 ≤  √N1은 소수가 아니지만 여기..