반응형 분류 전체보기133 백준 11660번 : 구간 합 구하기 5 java 이 문제는 일정 범위의 구간 합을 미리 구해놓아서 원하는 범위의 합을 알고 싶을 때 빠르게 결과를 구하는 문제입니다. 저는 이 문제를 좌에서 우로 위에서 아래로 갈수록 수들을 합하여 저장해 놓도록 설계하였습니다. 아래에서 그림을 통해 자세히 설명드리도록 하겠습니다. 문제에 나와있는 예제로 구간 합을 구해보겠습니다. 위에서 설명드린 대로 화살표 방향으로 갈수록 값이 커집니다. 우선 가장 윗줄과 왼쪽 줄에서 구간합을 구하겠습니다. 첫 번째 구간합에서는 윗 줄은 자신 왼쪽에 있던 수만 더하면 되고 왼쪽 줄은 자신의 위에 있던 수만 더하면 됩니다. 하지만 이 수들을 제외하고는 자신을 오른쪽 아래 꼭짓점으로 하는 사각형 안의 구간합을 구해야 합니다. 예를 들어 파란 박스 안에 있는 숫자가 있는 공간에는 빨간 박스.. 2022. 5. 25. 백준 9663번 : N-Queen java 이 문제는 N x N 사이즈의 체스판에 서로 공격하지 않게 퀸을 몇 개 놓을 수 있는지를 구하는 문제입니다. 퀸이 이동할 수 있는 공간은 위에 보이는 것과 같이 상 하 좌 우 각 방향의 대각선입니다. 이 문제를 풀기 위해서 퀸이 체스판의 어디 어디에 들어갈 수 있는지를 N이 4일 때를 예시로 보여드리겠습니다. 다음과 같이 퀸이 위치해 있을 떄 하얀 점이 있는 곳은 퀸이 갈 수 없습니다. 1열에 퀸이 왔으니 2열에 이제 새로운 퀸을 추가하고 퀸이 위치할 수 없는 위치를 흰 점으로 표시합니다. 다음 3열에 들어갈 수 있는 위치는 1개이니 그 자리에 퀸을 넣어줍니다. 이제 마지막 퀸까지 넣어주면 완성입니다. 이런 식으로 퀸이 들어갈 수 있는 자리들을 조건에 맞추어 찾으면 이 문제를 해결할 수 있습니다. imp.. 2022. 5. 25. 백준 11729번 : 하노이 탑 이동 순서 java 이 문제는 유명한 하노이 탑을 움직이는 문제입니다. 하노이 탑을 옮기는 규칙을 옮기는 원판이 3개일 때로 예를 들어 설명하겠습니다. 위의 그림과 같이 옮기고자 하는 과정을 그림으로 보여드리겠습니다. 우선 처음 상황입니다. 그다음 1번 원판을 1번 자리에서 3번 자리로 옮깁니다. 2번 원판을 1번 자리에서 2번 자리로 옮깁니다. 1번 원판을 3번 자리에서 2번 자리로 옮깁니다. 그 다음 3번 원판을 1번에서 3번 자리로 옮깁니다. 1번 원판을 2번 자리에서 1번 자리로 옮깁니다. 2번 원판을 2번 자리에서 3번 자리로 옮깁니다. 이제 1번 원판을 1번 자리에서 3번으로 옮기면 이동이 완료되었습니다. 예시와 같이 7번의 이동으로 3개의 원판이 이동되었습니다. 그런데 이렇게 3개의 원판을 옮기는 과정은 아래의.. 2022. 5. 24. 백준 2447번 : 별 찍기 -10 java 이 문제에는 왼쪽 그림과 같이 큰 정사각형의 그림을 9 등분해서 각각의 영역으로 나누어 나타낼 수 있습니다. 1 2 3 이런 식으로 각 공간에 숫자를 붙인다면 1 2 3 4 6 7 8 9가 4 5 6 채워져 있고 5만 패턴이 없는 비어있는 형태입니다. 7 8 9 우리는 이러한 반복되는 성질을 이용하여 이 문제를 해결할 수 있습니다. 이렇게 반복되는 패턴이 주어지는 수에 따라서 달라지는 경우 우리는 재귀를 이용해서 문제를 해결할 수 있습니다. 이제 재귀를 이용해 문제를 풀어보도록 하겠습니다. import java.io.*; public class Main{ static char[][] array; public static void main(String[] args) throws IOException{ Bu.. 2022. 5. 24. 백준 14888번 : 연산자 끼워넣기 java 백준에서 백트래킹 항목에 해당하는 문제는 연산자 끼워넣기입니다. 이 문제는 숫자를 몇 개를 입력받을 것인지를 먼저 입력받은 후 그 사이즈만큼 숫자를 입력받으면 됩니다. 이 문제에서는 연산자를 '+', '-', '*', '/', 이 4개만 사용하므로 연산자를 저장할 배열은 4개의 공간이 필요할 것입니다. 추가 설명은 코드를 보면서 하겠습니다. import java.util.*; import java.io.*; public class Main{ static int[] num; static int N; static int min = Integer.MAX_VALUE; static int max = Integer.MIN_VALUE; public static void main(String[] args) throws.. 2022. 5. 24. 이전 1 ··· 14 15 16 17 다음 반응형
