반응형 전체 글123 백준 1149번 : RGB거리 java 이 문제는 이전의 row와 다음의 row를 비교하여 같은 column에 수들이 들어있지 않게 더하여 최솟값이 나오게 하는 문제입니다. 저는 이 문제를 아래로 내려가면서 각 항의 합이 최솟값이 되는 조건을 찾아서 더해가며 풀었습니다. 왼쪽의 그림은 예제 1번의 입력값입니다. 이 그림을 통해서 어떤 규칙으로 문제를 푸는지 보여드리겠습니다. 이미 지나간 row는 파란색으로 표시하였고 지나가지 않은 row는 검은색으로 표시하였습니다. 이제 다음 row의 항들의 중에서 합이 최솟값이 되기 위해서는 어떤 항을 더해야하는지를 알아보겠습니다. 이 그림에서 빨간 항에서의 조건에 따른 최솟값을 구하기 위해서는 빨간 항이 있는 row의 위의 row에서 column이 다를 때의 최솟값을 더해야 합니다. 더할 수 있는 항들을 .. 2022. 5. 27. 백준 1932번 : 정수 삼각형 java 이 문제는 다이나믹 프로그래밍을 이용하여 이전의 최선의 경우의 수를 배열에 저장하며 푸는 문제입니다. 코드를 보면서 이 문제를 설명해드리겠습니다. 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)); int n = Integer.parseInt(br.readLine()); int[][] intArr = new int[n][]; for(int i = 1; i 2022. 5. 27. 백준 9465번 : 스티커 java 이 문제는 2줄에 총 2 x N개의 자료가 들어왔을 때 주어진 조건에 따라 가장 큰 합을 구하는 문제입니다. 이 문제를 예제의 첫 번째 경우를 예로 들어 설명하겠습니다. 예시를 표로 나타내면 이렇게 됩니다. 이 표에서는 1번째 column에서 무조건 1개의 항을 선택해야 합니다. 그 이유는 2번째 column에서 혹은 3번째 column에서 어떠한 항을 선택하더라도 첫 번째 column에서 선택할 수 있는 항이 남기 때문입니다. 이를 그림으로 설명해드리겠습니다. 저는 선택한 항을 빨간 박스로 표시했고 그 주변에 문제에 따라서 찢어져서 사용할 수 없는 스티커들을 초록백 박스로 표시하였습니다. 이 경우에 1번 column에서 30이 추가가 될 수 있습니다. 반대로 2번 column에서 10이 아닌 50을 선.. 2022. 5. 26. 백준 11286번 : 절댓값 힙 java 이 문제는 자료구조 힙 안에 자료를 저장하고 제거하는 기능을 구현하는 문제입니다. 힙이란 완전 이진트리로 구성되어 있는 일종의 자료구조로써 자료들을 저장할 수 있게 도와줍니다. 완전 이진 트리란 왼쪽의 그림과 같이 트리가 있을 때 가장 위의 트리부터, 위 층이 다 채워지면 왼쪽부터 채우는 이진 트리를 의미합니다. 트리에서는 자료가 있는 칸을 노드라고 부릅니다. 이 그림에서 노드가 채워지는 순서는 알파벳 순입니다. 왼쪽의 그림과 같이 왼쪽에서부터 차례대로 채우지 않은 이진 트리는 완전 이진트리가 아닙니다. 힙은 보통 최대 힙, 최소 힙으로 나뉩니다. 최대 힙은 다음과 같이 가장 큰 수가 가장 위에 위치한 힙을 나타냅니다. 최대 힙에서는 새로운 자료가 들어오면 비교를 통해 자식 노드보다 부모 노드가 항상 큰.. 2022. 5. 26. 백준 14889번 : 스타트와 링크 java 이 문제는 백트래킹 파트 안에 있는 깊이 우선 탐색(dfs)을 이용하여 푸는 문제입니다. 이 문제를 풀 때 유의해야 하는 점은 N이 6이라고 할 때 1 2 3이 한 팀이고 4 5 6이 한 팀일 때 1->2, 2->1로 받는 능력치 1->3, 3->1로 받는 능력치 2->3, 3->2로 받는 능력치 이렇게 안에 포함된 모든 팀원들의 능력치 합을 더해서 구해주어야 된다는 겁니다. 코드를 보면서 추가로 설명드리도록 하겠습니다. import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.StringTokenizer; public class Main{ static int[][].. 2022. 5. 25. 백준 14500번 : 테트로미노 java 이 문제는 길이가 4가 되면 종료하는 조건을 가진 dfs를 이용하여 풀면 됩니다. 이 문제에서 나온 5개의 도형은 길이가 4인 도형을 모두 나타낸 것입니다. 이 중에서 ㅏㅓㅗㅜ로 표현 가능한 하나의 형태를 제외하고는 모두 dfs를 이용하여 각각의 테트로미노의 합을 구할 수 있습니다. 바로 코드를 보면서 설명드리도록 하겠습니다. import java.util.*; import java.io.*; public class Main{ static LinkedList ll = new LinkedList(); static int[] drow = {1, -1, 0, 0}; static int[] dcol = {0, 0, 1, -1}; static int[][] intArr; static boolean[][] gone.. 2022. 5. 25. 백준 11660번 : 구간 합 구하기 5 java 이 문제는 일정 범위의 구간 합을 미리 구해놓아서 원하는 범위의 합을 알고 싶을 때 빠르게 결과를 구하는 문제입니다. 저는 이 문제를 좌에서 우로 위에서 아래로 갈수록 수들을 합하여 저장해 놓도록 설계하였습니다. 아래에서 그림을 통해 자세히 설명드리도록 하겠습니다. 문제에 나와있는 예제로 구간 합을 구해보겠습니다. 위에서 설명드린 대로 화살표 방향으로 갈수록 값이 커집니다. 우선 가장 윗줄과 왼쪽 줄에서 구간합을 구하겠습니다. 첫 번째 구간합에서는 윗 줄은 자신 왼쪽에 있던 수만 더하면 되고 왼쪽 줄은 자신의 위에 있던 수만 더하면 됩니다. 하지만 이 수들을 제외하고는 자신을 오른쪽 아래 꼭짓점으로 하는 사각형 안의 구간합을 구해야 합니다. 예를 들어 파란 박스 안에 있는 숫자가 있는 공간에는 빨간 박스.. 2022. 5. 25. 백준 9663번 : N-Queen java 이 문제는 N x N 사이즈의 체스판에 서로 공격하지 않게 퀸을 몇 개 놓을 수 있는지를 구하는 문제입니다. 퀸이 이동할 수 있는 공간은 위에 보이는 것과 같이 상 하 좌 우 각 방향의 대각선입니다. 이 문제를 풀기 위해서 퀸이 체스판의 어디 어디에 들어갈 수 있는지를 N이 4일 때를 예시로 보여드리겠습니다. 다음과 같이 퀸이 위치해 있을 떄 하얀 점이 있는 곳은 퀸이 갈 수 없습니다. 1열에 퀸이 왔으니 2열에 이제 새로운 퀸을 추가하고 퀸이 위치할 수 없는 위치를 흰 점으로 표시합니다. 다음 3열에 들어갈 수 있는 위치는 1개이니 그 자리에 퀸을 넣어줍니다. 이제 마지막 퀸까지 넣어주면 완성입니다. 이런 식으로 퀸이 들어갈 수 있는 자리들을 조건에 맞추어 찾으면 이 문제를 해결할 수 있습니다. imp.. 2022. 5. 25. 이전 1 ··· 12 13 14 15 16 다음 반응형
