Algorithm/백준42

• 

  백준 - 스도쿠 문제 설명 가로, 세로 그리고 현재 위치한 작은 사각형 내부에 숫자를 1-9까지 고유하게 존재해야하는 스도쿠 판을 완성하는 문제이다. 고유한 숫자가 나오기 위해서 이처럼 검사를 진행해야한다. 1) 행, 열 유일성 검사 2) 작은 사각형 내부 안에서의 숫자의 유일성 검사 시작점을 찾는 규칙을 찾아야하며 해당 시작점부터 +3,까지 숫자의 유일성을 검사해야한다. 풀이 static final int N = 9; static int[][] grids; public static void main(String[] args) throws IOException { grids = new int[N][N]; BufferedReader reader = new BufferedReader(new InputStreamReader(.. Algorithm/백준 2023. 4. 22.

• 

  백준 - 줄어드는 수 문제 설명 줄어드는 수 중 n번째인것을 출력하는 문제이다. 줄어드는 수를 321,950과 같은 숫자가 왼쪽에서 오른쪽으로 한자리씩 봤을 때, 작은 수여야 한다고 한다. 322와 859는 줄어드는 수가 아니라고 한다. 해당 문제는 아이디어를 잘 내야한다.. 주의사항 n의 입력을 명시적으로 주고 있지만 얼만큼의 줄어드는 수를 만들어야 할지 고민일 것이다. 위 문제를 보면 줄어드는 수 중 가장 큰수는 987654321이라는 것을 알 수 있다. TRY 선형적으로 1부터 987654321까지 String으로 변환하여 stack을 이용하여 줄어드는 수인지 판별 [시간초과] 백트래킹 9876543210을 배열에 위치시켜 하나씩 골라 수를 만든다. [성공] 수를 만들때 이전에 골랐던 범위는 절대 선택하지 않도록 해야한.. Algorithm/백준 2023. 4. 15.

• 

  백준 - 계란으로계란치기 문제 설명 계란에 대해 왼쪽부터 차례로 들어서 한 번씩만 다른 계란을 쳐 최대한 많은 계란을 깨는 문제 계란으로 계란을 치면서 가장 많이 깨뜨릴 수 있는 경우의 수를 구하는 문제이다. 계란을 하나를 잡고 계란을 친다. 그런데 중간에 손에든 계란이 깨졌거나 깨지지 않는 계란이 없으면 넘어간다.이후 손에 든 계란을 자리에 놓고 다음 계란을 들고 다시 다른 계란들을 깨뜨린다 주의사항 다른 계란을 깨뜨릴때 항상 오른쪽에만 있는 계란을 깨드리지 않아도 된다! 계란이 안깨져 있으면 모두 쳐보는 것이다! 풀이 public static void hit(int cnt) { if (n egg[0]) .filter(durability -> durability Algorithm/백준 2023. 4. 15.

• 

  백준 - 계단 오르기 문제 설명 계단오를때 점수를 받는다. 계단을 오를때 점수를 받을 수 있는 총 점수를 구하는 문제이다. 단 ,규칙이 존재한다. 연속된 3 계단을 밟아 점수를 얻을 수 없다. 마지막 계단은 반드시 밟아야 한다. TRY 계단의 최대 입력으로 들어올 수 있는 수는 300이다. 이것은 기본적으로 완전탐색을 한다면 시간 초과가 나올 수 있다. 다이나믹으로 풀어낼 수 있다. dp[i]=MAX(dp[i-2]+ dp[i-3] + stair[i-1])+ stair[i] 위점화식을 해석하면 현재 계단에서 뒤로 두번째 칸을 밟아왔던 값 ,뒤로 세칸 밟아왔던 값 + 뒤로 한칸 밟은 값 이다. dp[i-3] + stair[i-1]은 역속된 3칸을 밟지 않아야한다는 조건때문이다. dp[i-1]만 보면 dp[i-1]이 이미 연속된 .. Algorithm/백준 2023. 4. 11.

• 

  백준 - A와B2 문제 설명 A⇒ B로 바꿀수 있는지 가능여부를 물어보는 문제이다. 주의사항 완전탐색 시간복잡도를 측정해봐야한다. 50의 길이 시도 완전탐색 FAIL 백트래킹만들어질 수 없는 경우는 탐색하지 않도록 한다. 일반 완전탐색은 2^50까지 나온다. 풀이 - [덱을 이용한 풀이] 문자를 추가하는 것은 괜찮다 하지만 뒤집고 뒤집고 .. 이런행위가 시간초과에 영향을 줄 수 있다고 생각했기 때문에 사용하지 않았다. static boolean isPossible = false; public static boolean isChange(String A, String B) { LinkedList results = new LinkedList(); for (char c : A.toCharArray()) { results.offe.. Algorithm/백준 2023. 4. 5.