본문 바로가기

자바141

[백준] 2156번 포도주 시식 JAVA (자바) 풀이 문제 2156번 (DP)  포도주 잔을 선택하면 모두 마시고 원래 위치에 놓기연속으로 놓여 있는 3잔을 모두 마실 수는 없다 :  n개의 포도주 잔이 순서대로 놓여있고 포도주의 양이 주어졌을 때 가장 많은 양을 마셔라  예) 6개의 포도주 / 각각 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때       첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대이다  [입력] :  첫째 줄에 포도주 잔의 개수 n (1 ≤ n ≤ 10,000)  :  둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다    (포도주의 양은 1,000 이하의 음이 아닌 정수)  [출력]  :   첫째 줄에 최대로 마실 수 있는 포.. 2024. 8. 20.
[백준] 1932번 정수 삼각형 JAVA (자바) 풀이 문제 1932번 (DP)  7 3 8 8 1 0 2 7 4 44 5 2 6 5  :  위 그림은 크기가 5인 정수 삼각형    맨 위층부터 시작해서 아래에 있는 수 중 하나를 선택하여 내려온다    선택된 수의 합이 최대가 되는 경로를 구해라    현재 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택 가능    삼각형의 크기는 1 이상 500 이하 / 삼각형을 이루고 있는 각 수 범위는 0 이상 9999 이하  [입력] :   첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형   [출력]  :   첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력  [설명] DP .. 2024. 8. 9.
[백준] 1149번 RGB거리 JAVA (자바) 풀이 문제 1149번 (DP) :  RGB거리에는 집이 N개 있다   집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다   모든 집을 칠하는 비용의 최솟값을 구해보자.  :  규칙2번 집의 색 ≠ 1, 3번 집의 색i(2 ≤ i ≤ N-1)번 집의 색 ≠  i-1번, i+1번 집의 색  [입력] :  첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000) :  둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다    (집을 칠하는 비용은 1,000보다 작거나 같은 자연수)  [출력]  :   첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력  [설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간.. 2024. 8. 8.
[백준] 9663번 N-Queen JAVA (자바) 풀이 문제 9663번 (백트래킹)  :  N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제    N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램   [입력] :   첫째 줄에 N이 주어진다. (1 ≤ N    [출력] :   첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력   [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹   pos메서드를 통해 참이 아니라면 다시 바꿔서 탐색한다 참이면 더 깊이 들어간다  종료 조건) depth==N 모두 종료되는 것이 아니라 N의 퀸을 세웠으면 경우의 수 1개를 카운트한다  1. 퀸의 공격 방향은 대각선, 세로, 가로같은 행, 같은 열, 같은 대각선은 피해야한다하나의 행씩.. 2024. 8. 6.
[백준] 1987번 알파벳 JAVA (자바) 풀이 문제 1967번 (백트래킹)  :  세로 R칸, 가로 C칸으로 된 표 모양의 보드    각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다    말은 상하좌우로 이동 가능    새로 이동한 칸의 알파벳 ≠ 지금까지 지나온 모든 칸에 적혀 있는 알파벳    (즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다)    좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구해라 (좌측 상단의 칸 포함)   [입력] :  첫째 줄에 R과 C가 빈칸을 사이에 두고 주어진다 (1 ≤ R,C ≤ 20)  :  둘째 줄부터 R개의 줄에 걸쳐서 보드에 적혀 있는 C개의 대문자 알파벳   [출력] :  첫째 줄에 트리의 지름을 출력   [과정]  탐색하자 → 브루트.. 2024. 8. 6.
[백준] 1967번 트리의 지름 JAVA (자바) 풀이 문제 1967번 (dfs)  :  트리(tree)는 사이클이 없는 무방향 그래프    트리에서는 어떤 두 노드를 선택해도 둘 사이에 경로가 항상 하나만 존재    어떤 두 노드를 선택해서 양쪽으로 쫙 당길 때, 가장 길게 늘어나는 경우가 있을 것 :  이런 두 노드 사이의 경로의 길이를 트리의 지름    입력으로 루트가 있는 트리를 가중치가 있는 간선들로 줄 때, 트리의 지름을 구해라  :  아래와 같은 트리가 주어진다면 트리의 지름은 45    [입력] :  파일의 첫 번째 줄은 노드의 개수 n (1 ≤ n ≤ 10,000) :  둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보 (세 개의 정수)    (연결하는 두 노드 중 부모 노드의 번호, 자식 노드, 간선의 가중치)     간선에 대한 정보는 부.. 2024. 8. 6.
[백준] 2573번 빙산 JAVA (자바) 풀이 문제 2573번 (BFS)  : 빙산의 각 부분별 높이 정보는 배열의 각 칸에 양의 정수로 저장   바다 = 0        2453   3 252  7624           :  빙산의 높이는 바닷물에 많이 접해있는 부분에서 더 빨리 준다    동서남북 네 방향으로 붙어있는 0이 저장된 칸의 개수만큼 줄어든다 (0보다 더 줄어들지 않는다)             241   1 15   5412                                             1년 후 빙산  :  빙산이 두 덩어리 이상으로 분리되는 최초의 시간(년)을 구하는 프로그램을 작성하시오    전부 다 녹을 때까지 두 덩어리 이상으로 분리되지 않으면 프로그램은 0을 출력   [입력] :  첫 줄에는 행의 개수와 열의.. 2024. 8. 6.
[백준] 15686번 치킨 배달 JAVA (자바) 풀이 문제 15686번 (백트래킹, 브루트포스)  :  크기가 N×N인 도시    도시의 각 칸은 빈 칸, 치킨집, 집 중 하나  :  사람들은 "치킨 거리"라는 말을 주로 사용    치킨 거리는 집과 가장 가까운 치킨집 사이의 거리    각각의 집은 치킨 거리를 가지고 있고 도시의 치킨 거리는 모든 집의 치킨 거리의 합이다.    거리는 |r1-r2| + |c1-c2|로 구한다  :  0은 빈 칸, 1은 집, 2는 치킨집    이 도시에 있는 치킨집은 모두 같은 프랜차이즈이며 일부 치킨집을 폐업시키려고 한다    이 도시에서 가장 수익을 많이 낼 수 있는 치킨집의 개수는 최대 M개    나머지 치킨집은 모두 폐업시켜야 한다    어떻게 고르면, 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성   .. 2024. 8. 3.
[백준] 1927번 최소 힙 JAVA (자바) 풀이 문제 1927번(자료구조, 우선순위 큐) :  최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오배열에 자연수 x를 넣는다 (비어있는 배열에서 시작) 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거   [입력] :  첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000) :  다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x (x 는 2³¹보다 작은 자연수 또는 0)     (x가 자연수라면 배열에 x라는 값을 추가, 0이라면 배열에서 가장 작은 값을 출력하고 제거)  [출력] :  입력에서 0이 주어진 횟수만큼 답을 출력 (만약 배열이 비어 있는 경우 0을 출력)    [설명] 힙은 우선순위 큐와 원리가 비슷해 우선순위 큐로 구현할 수 있다  우선순위 큐의 정렬 기.. 2024. 8. 2.
[백준] 13023번 ABCDE JAVA (자바) 풀이 문제 13023번 (dfs, 백트래킹)  : 총 N명이 참가   사람들은 0번 ~ N-1번으로 번호가 매겨져 있고, 일부 사람들은 친구A는 B와 친구B는 C와 친구C는 D와 친구D는 E와 친구위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성   [입력] :  첫째 줄에 사람의 수 N (5 ≤ N ≤ 2000), 친구 관계의 수 M (1 ≤ M ≤ 2000) :  둘째 줄부터 M개의 줄에는 정수 a와 b가 주어지며, a와 b가 친구라는 뜻 (0 ≤ a, b ≤ N-1, a ≠ b)    (같은 친구 관계가 두 번 이상 주어지는 경우는 없다)   [출력]  :  문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력   [과정]  탐색하자 → 브루트포스 / dfs → .. 2024. 8. 2.

티스토리툴바