백트래킹?모든 가능한 방문 조합을 재귀적으로 시도해보고, 그중에서 유효한 것만 정답 후보로 선택모든 경우를 탐색하되, 중간에 불가능한 경로는 더 이상 가지 않고 돌아가는 알고리즘 해당 문제를 보고 백트래킹을 써야겠다는 생각이 들었다.하지만 구현하는 데에 좀 어려움을 겪었다.처음에 dx, dy로 한칸씩 이동하면서 초코우유를 먹으면서 체력을 늘리고 2를 0으로 바꾼 뒤에 다시 탐색해보는 방향으로 생각했는데 아주 잘못된 생각이었다. 이 문제의 목표는 최대한 많은 민트초코우유를 먹고, 집에 돌아올 수 있는 경우 중 우유의 최대 개수를 구하는 것이다.조건은 아래와 같다. N x N 크기의 마을 (map)진우의 집은 1, 민트초코우유는 2, 빈칸은 0진우는 상하좌우 한 칸 이동에 체력 1 소모민트초코우유를 먹으면..

https://www.acmicpc.net/problem/32387 문제를 읽으면서 대충 요약하면서 정리해보았다.Node 클래스가 필요하다는 것을 먼저 파악하고 어떤 값이 들어갈지 고민해보았고,먼저, 인덱스와 전력 그리고 행동 순서 를 기억하고 있어야겠다고 생각했다.그리고 예시를 직접 테스트해보면서 내가 이해한 바가 맞는지 확인하였다.첫 코드package baekjoon._32387;//https://www.acmicpc.net/problem/32387import java.util.*;import java.io.*;public class Main { static int N, Q; static List multitab; public static void main(String[] args) throws E..

https://www.acmicpc.net/problem/20040 유니온 파인드 관련된 문제를 찾아서 진행했다.두 점을 연결하는 과정을 거치면서 사이클이 완성되면 끝나는 게임이다. 두 점을 union하면서 isSameParent 로직으로 확인하면서 cycle이 발생하면 몇 번째 union 에서 발생했는지 출력하면 된다.* 중요 -> union하면서 parent[] 배열로 부모 점을 계속 변경해주어야 한다. 이때는 둘 중 작은 수로 부모를 변경해야 한다.union -> 두 점을 연결하고 같은 부모를 바라보게 한다.find -> 각 점의 부모를 찾는다.isSameParent -> 부모가 같은지 확인한다. 최종 코드package baekjoon._20040;import java.io.*;import java..

https://www.acmicpc.net/problem/2638처음 문제를 보았을 때 아래와 같이 판단하였다.1. BFS를 통해서 먼저 외부 공기(-1)를 구분한다.2. 배열을 순회하면서 외부 공기랑 2면 이상 닿으면 0으로 표시한다.3. 치즈가 없는지 판단한다.(1이 하나라도 있으면 true 반환) * 문제를 풀 때, 초기화 단계를 잊어버리는 경우가 많아서 체크하기 위해 따로 적어둔다. 하지만 while문을 통과하지 못하는 오류가 발생하였다.확인해보니 치즈를 녹이는 단계에서 외부 공기랑 2면 이상 닿았을 때 바로 0으로 바꾸는 것 때문에 제대로 다음 치즈들에 대해서 처리가 되지 않았다.또한 외부 공기를 한 번 확인하고 치즈를 녹이는데 다시 외부 공기를 확인할 때 외부 공기를 다시 판단해야하는데 초기화..

2024.12.27스터디원들과 2차 면접 스터디를 진행하였다. 이 날도 조금이긴 하지만 눈이 왔다... 만날 때마다 눈이라니~ 신기하다 허허한 3주 정도 Database 에 관해서 각자 공부를 진행하고, 공부한 내용을 발표하면서 많은 지식을 쌓았다.2차 면접 스터디도 6명이 각자 돌아가면서 면접 질문을 하고, 각자 정답을 알거나 아는 부분이 있으면 먼저 이야기하고, 다른 사람들은 답변이 부족하거나 틀리다면 다시 답변을 보충할 수 있도록 하였다!면접 질문 리스트1. 인덱스와 키의 차이점은 무엇인가요?더보기키는 데이터의 고유성과 참조 무결성을 보장하는 요소로 Primary Key, Foreign Key 등 이 있습니다. 인덱스는 검색 속도를 높이기 위해 사용하는 자료구조로, 데이터를 효율적으로 찾고 정렬하기..

2024.11.28 스터디원들과 면접 스터디를 진행하였다. 이 날은 눈이 정말 많이 왔다... 진짜 너무 많이 쌓여서 걷는게 불편하고 버스에서는 도로 표시선도 흐릿하고 눈보라 때문에 앞이 하얗게 보일 정도였다...그럼에도 스터디는 진행되었다!!!!! 모두들 수고했다~ 먹물 최고!한 3주 정도 Java에 관해서 각자 공부를 진행하고, 공부한 내용을 발표하면서 많은 지식을 쌓았다.각자 서로 공부한 부분을 공유하고 궁금한 부분에 대해서 질문도 하고 잘 정리되지 않는 부분에 대해서 토의하면서 생각과 지식을 정리하니 혼자 공부할 때보다 훨씬 잘 기억에 남고 이해가 되었다.1차 면접 스터디는 6명이 각자 돌아가면서 면접 질문을 하고, 각자 정답을 알거나 아는 부분이 있으면 먼저 이야기하고, 다른 사람들은 답변이 부..

문제접근이 문제는 문자열 S 안에서 특정 패턴 Pn이 몇 번 등장하는지 확인하는 문제입니다.처음엔 입력 값을 제대로 확인하지 않고 서브 태스크1에 있는 것을 보고 1. i번째에서 i+3까지 자르고 i를 1개씩 올려가면서2. Substring한 문자열이 Pn과 같은지 확인하였습니다.이 경우 N이 매우 커졌을 경우에 2N+1 크기의 문자열을 M 번 확인해야하는 큰 연산이 걸려 매우 큰 시간복잡도가 나오게 됩니다.그렇기 때문에 다른 방법을 사용하여야겠다고 생각하였습니다.- 슬라이딩 윈도우 고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘슬라이딩 윈도우를 사용하여 Pn 문자열에서는 공통된 pattern이 존재하기 때문에 'IOI'를 고정 윈도우로 지정하여 윈도 내에 있..

문제접근DP 사용해서 이전의 결과값을 사용해서 효율적인 계산을 진행하였다.예시스티커를 뗀 부분이 O이고찢겨진 부분은 X라고 하자.(0,2) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. 지금 목표는 스티커를 뗀 경우 중 가장 큰 값을 얻었을 때이기 때문에 이때 둘 중에 큰 값을 선택하고 (0,2) 위치의 스티커 값을 더해주면 된다.이외에 아무것도 떼지 않은 경우(1,1) 위치의 스티커를 뗀 경우 (0,3) 위치의 스티커를 뗀 경우는 아래와 같이 나누어진다. (1,2) 위치의 스티커를 뗀 경우(1,1) 위치의 스티커를 뗀 경우해당 값 중에 큰 값을 선택하고 (0,3) 위치의 스티커 값을 더해주면 된다. 그러면 아래와 같은 점화식을 얻을 수 있다.구한 점화식을 코드에 적용하면 아래 코드와 같다.코드im..

문제접근DFS 탐색을 통해서 말을 이동할 수 있는 경로 탐색이때, alphabets 배열을 통해서 중복된 알파벳의 경로로 가지 않도록 해야 한다고 생각하였다.alphabets 배열을 A~Z까지의 26의 크기를 가진 배열로 설정하였다.해당 알파벳의 정수 값에서 'A'의 정수값을 빼면 해당 알파벳의 인덱스 값이 되기 때문에 탐색한 경우 해당 배열 인덱스에 위치한 값을 true로 변환해주었다.백트래킹!!!!알파벳을 탐색하면서 중복 처리를 한 map에서 말의 움직임을 count한다.이때 다른 경로를 탐색하기 위해 중복 처리를 한 부분을 다시 원복시킨다.원복 시킨 것에서 다른 경로로 탐색하고 다시 중복처리를 진행하면서 말의 움직임을 또 count한다.탐색할 때마다 maxCount를 최댓값으로 갱신해주면서 최종 값..

문제접근2*1 의 경우는 1가지2*2의 경우는 2가지2*3의 경우는 3가지...규칙이 있는 것을 찾아냈다.예를 들어 n=5인 경우, 마지막 2*1 부분  빼고 모두 차있는 경우 + 마지막 2*2 부분이 가로로 채워져 있고 모두 차있는 경우두 가지 경우를 더한 경우의 수가 모든 경우의 수이다.점화식 : dp[i] = dp[i-1] + dp[i-2]코드import java.util.*;public class Main { static int[] dp; static int N; public static void main(String[] args) { Scanner sc = new Scanner(System.in); N = sc.nextInt(); dp = n..