Meluu_의 코딩 공부 일지

🧫 문제 분석✔️ 출처2048 (Easy) 골드 1 📖 문제 보드 크기가 N이며, 매 이동마다 변화하기때문에완전탐색 말고는 답이없는 것 같아서 완전탐색으로 풀이방향을 정했다. 문제에서 알고리즘 분류는 백트래킹 쪽이지만 나는 BFS로 풀었다.BFS + 완전탐색 이 문제에서 어려웠던 건 단순히 어떻게 한 방향으로 보내면서 합치고, 다를땐 이동시키는가 이다. 합쳐지지않은 위치를 추적한다. notUnionIdxnotUnionIdx ~ 현재 위치 전까지를 이동 가능한 곳을 탐색한다. 이때 같은 값을 가지고 있다면 합친다. 값을 2배로 하고 현재 위치의 값은 0으로 저장한다. 그리고 notUinonIdx 를 합친 위치의 다음 위치로 갱신한다. 각 방향은 4개의 함수로 각각 작성하였다. 🔅 문제 풀이impo..

🧫 문제 분석 ✔️ 출처마인크래프트 실버 2 📖 문제 완전탐색 문제로 땅 고르기를 하면된다. 주어진 땅 높이들의 최소, 최댓값을 구한 후최소~최대 높이까지 탐색을 해서 최단 시간이면서 가장 높은 높이를 구하면된다. 나는 잘못 푼게 있는데 맵 탐색중 2번 작업시 인벤토리내에 블록이 없으면 바로 불가능하다고 판단하고 멈췄는데 생각이 짧았다..현재 위치에서 인벤토리가 비어있더라도다른 위치에서 1번 작업을 통해 블록을 인벤에 저장하고 현재 위치에서 사용할 수 있는데이걸 생각못한게 정말 .. 눈물이난다. 🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static int totalTime = Integer.MAX_VALUE; s..

🧫 문제 분석✔️ 출처N-Queen 골드 4 📖 문제 많은 깨달음을 준 문제다. 퀸의 특성상 상하좌우대각을 원하는 만큼 이동이 가능하기에 그에 따른 검증을 해야한다. 처음에는 이중 배열로 만들어서 각 퀸의 위치를 리스트에 저장하고 리스트를 순회하면서 검증하고 놨는데 시간복잡도가 너무 크게 나와서 O((N^2)^N) 힌트를 보고 풀었다. 퀸 특성상 n개의 체스판에서는 각 행에 하나씩 둬야 n개의 퀸을 둘 수 있다.때문에 퀸을 두고 다음 행을 탐색한 후 돌아온 다음 다시 퀸을 지울 필요없이 덮어씌우면된다. (백트래킹에서) 나의 잘못된 생각은검증시 0~n 행까지 전부 다 해서 쓸모없는 연산이 늘고, 잘못된 검증이 되어 값이 증가한 것이다. 말했듯이 n개의 퀸을 놓을려면 0행부터 순서대로 n행까지 하나..

🧫 문제 분석 ✔️ 출처N과 M (9) 실버 2 📖 문제 N과 M 9번째 시리즈N개의 자연수 중 M개를 고른 수열이면서 그 수열이 중복되면 안된다.  입력받은 N개의 자연수를 우선 오름차순으로 정렬한 후 백트래킹 탐색을 한다. 수열을 문자열로 만들고 Set에 중복 체크를 한 다음 없다면Queue에 넣어서 저장 탐색이 끝나면 Queue를 다 꺼내서 출력하면 된다.  🔅 문제 풀이import java.io.*;import java.util.*;public class Main { static Set set = new HashSet(); // 수열 중복 체크 static StringBuilder sb = new StringBuilder(); // 수열 만들기용 static List list..

🧫 문제 분석 ✔️ 출처영화감독 숌 실버 5 📖 문제 완전탐색 문제로6이 3개 이상 연속되어 들어가는 수를 말한다고 한다.즉 여러 수 중에 "666"이 포함되어 있으면 그 수는 종말의 수 라는 것이다. 문제의 이해를 잘 못했는데결국에는 사전 순서? 크기 순서대로 번호가 주어진다. 5666 -> 6660 -> 6661 -> ~ 6669 -> 7666 ... 이런식으로 가는 것이다. 나는 단순히 666부터 시작해서 intMax까지 완전탐색을 했다.현재 수를 문자열로 바꾸고 contains로 666이 포함되어있으면 count 하고count가 N과 같다면 count에 그 수를 저장하고 탐색을 종료한 뒤 count를 반환한다  🔅 문제 풀이import java.io.*;import java.util.*;pu..

🧫 문제 분석 ✔️ 출처고층건물 골드 4 📖 문제 핵심사실상 수학문제라고 봐도 과언이 아니라 생각한다.기울기의 증감을 따져서 비교하면 되는데  빌딩중 하나를 기준으로 생각해보자. 좌측 부분은 기울기가 증가 하는 형태이고우측 부분은  기울기가 감소하는 형태이다.  대략 이렇게 볼 수 있다.  뒷건물에 대해서는 기울기 최솟값을 저장하고 최솟값보다 기울기가 크다면 그 빌딩은 볼 수 없는 빌딩이다. 앞 건물에 대해서는기울기 최대값을 저장하고최댓값보다 기울기가 작다면 그 빌딩은 볼 수 없는 빌딩이다.  문제에서 A-B 빌딩 선분이 다른 빌딩을 지나거나 접하지 않아야한다 했으므로 기울기가 같으면 그 빌딩은 볼 수 없다.  🔅 문제 풀이import java.io.*;import java.util.StringTo..

🧫 문제 분석 ✔️ 출처감소하는 수 골드 5 📖 문제  핵심감소하는 수는 완전탐색 + 백트래킹 문제이다. 먼저 문제를 보면 321, 950 같은 수는 감소한다. 즉 각 앞 자리수보다 뒷 자리수가 더 작아야한다. ex)321이면 3보다 작은 수가 와야하고 여기서는 2 가 왔다2보다 작은수 1이 왔다. 수를 생각해보면 0~9 까지 있고 나올 수 있는  감소하는 수 최대 값은9 8 7 6 5 4 3 2 1 0 이다. (98억7654만..)즉 10자리수까지만 탐색하면 된다는 의미이다.  문제에서 주어지는 N번째 수가 무엇인지를 출력하면 된다.예제 1번을 예시로 보자 0~9까지는 각 수에 대한 각 번호이다. 0 은 0번째 , 1은 1번째그리고 10 은 10번째이고 11부터 19까지는 감소하는 수가 아닌 같거나..

백준 1065번 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 문제 풀이 import java.util.*; import java.io.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStream..