Meluu_의 코딩 공부 일지

🧫 문제 분석 ✔️ 출처파도반 수열 실버 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번 더 간 다음 상하일 경우 좌우를 탐색좌우일 경우 상하를 탐색한다.  코드와 그림을 보면 이해하기 쉽다.    이와 비슷한 ..

✔️ 템플릿 메서드 패턴이전에 만들었던 로그 추적기를 더 향상시켜보자 템플릿 메서드 패턴은 변하지 않는 부분과 변하는 부분을 분리해서 변하지않는 부분을 템플릿(기본 틀)로 정의하고, 변하는 부분은 하위 클래스에서 정의하는 패턴이다.  로그 추적기의 변하지 않는 부분TraceStatus status = null;try { status = trace.begin("message"); //핵심 기능 호출 trace.end(status);} catch (Exception e) { trace.exception(status, e); throw e;}이 부분을 템플릿으로 정의한다. 추상 템플릿 클래스public abstract class AbstractTemplate { private final LogTrace ..

🧫 문제 분석 ✔️ 출처적록색약 골드 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 배열에 파싱하여 저장하였다.  두 개의 포인터를 사용하여 풀었다. 자세한건 코드를 참고해주면 좋을 것 같다.  🔅 ..

🧫 문제 분석 ✔️ 출처문제 바로가기📖 문제도시 이름이 모음 a,e,i,o,u 로 시작하는 도시 리스트를 출력단 중복을 포함해서는 안된다 . 정규표현식으로 모음으로 시작하는 도시들을 필터링하고SELECT에서 DISTINCT 로 중복을 제거한다. 🔅 문제 풀이-- MYSQLSELECT DISTINCT CITYFROM STATIONWHERE CITY REGEXP '^(a|e|i|o|u)'  간단하다.

🧫 문제 분석 ✔️ 출처문제 바로가기 📖 문제2개 도시 중 가장 긴 이름의 도시와 가장 짧은 이름의 도시 1개씩 출력단, 길이가 같다면 도시 이름을 알파벳 순으로 먼저된 것을 출력 Union 을 써보게 되는 귀중한 문제였다. 문제에서 2 개의 별도 쿼리를 작성해서 출력을 얻을 수 있다고 나와있기에 Union을 쓰라고 간접적으로 힌트를 줬다. 🔅 문제 풀이-- MySQL(SELECT CITY, LENGTH(CITY) AS CFROM STATIONORDER BY C, CITYLIMIT 1)UNION (SELECT CITY, LENGTH(CITY) AS CFROM STATIONORDER BY C DESC, CITYLIMIT 1)

🧫 문제 분석 ✔️ 출처신기한 소수 골드 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은 소수가 아니지만 여기..