반응형 알고리즘113 백준 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. 백준 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. 이전 1 ··· 11 12 13 14 15 다음 반응형
