본문 바로가기

Baekjoon100

[백준] 16926번 배열 돌리기 1 JAVA (자바) 풀이 문제 1707 크기가 N×M인 배열이 있을 때, 배열을 다음과 같이 반시계 방향으로 돌려야 한다 A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] ↓ ↓ ↑ ↑ A[3][1] A[3][2] → A[3][3] → A[3][4] A[3][5] ↓ ↑ A[4][1] → A[4][2] → A[4][3] → A[4][4] → A[4][5] 예) 아래와 같은 배열을 2번 회전시키면 다음과 같다 1 2 3 4 2 3 4 8 3 4 8 6 5 6 7 8 1 7 7 6 2 7 8 2 9 8 7 6 → 5 6 8 2 → 1 7 6 3 5 4 3 2 9 5 4 3 5 9 5 4 [입력] : 첫째 줄에 배.. 2024. 1. 23.
[백준] 18111번 마인크래프트 JAVA (자바) 풀이 문제 18111 마인크래프트는 1 × 1 × 1 크기의 블록들로 건축 가능 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업 필수 세로 N, 가로 M 크기의 집터 내가 가진 블럭 B 집터 맨 왼쪽 위의 좌표는 (0, 0) 블록을 제거해 인벤토리에 넣기 = 2초 소요 인벤토리에서 블록 하나를 꺼내어 놓기 = 1초 소요 땅 고르기’ 작업에 걸리는 최소 시간과 그 경우 땅의 높이를 출력해라 (집터 아래에 빈 공간은 존재 X, 집터 바깥에서 블록 수집 X, 땅의 높이는 256블록을 초과 X, 음수 X) [입력] : 첫째 줄에 N, M, B (1 ≤ M, N ≤ 500, 0 ≤ B ≤ 6.4 × 107) : 둘째 줄부터 N개의 줄에 각각 M개의 정수로 땅의 높이 : (i + 2)번째 줄의 (j + 1)번째 수.. 2024. 1. 23.
[백준] 1707번 이분 그래프 JAVA (자바) 풀이 문제 1707 그래프의 정점의 집합을 둘로 분할 각 집합에 속한 정점끼리는 서로 인접하지 않도록 분할 그러한 그래프를 특별히 이분 그래프 (Bipartite Graph) 이 그래프가 이분 그래프인지 아닌지 판별해라 이분그래프란? 모든 정점을 두가지 색으로 표현 인접한 정점을 연결할 때에는 무조건 다른 색상의 것을 연결 (예시) [입력] : 첫째 줄에 테스트 케이스의 개수 K : 각 테스트 케이스, 첫째 줄에는 정점의 개수 V와 간선의 개수 E (공백으로 구분) (각 정점 = 1 ~ V까지 차례로 번호 부여) : 각 테스트 케이스, 둘째 줄부터 연결된 정점 u, v 2 3 2 1 3 2 3 4 4 1 2 2 3 3 4 4 2 → 테스트 케이스 2개 → 1번 케이스) 정점 3개 / 간선은 2개 → 정점 = .. 2024. 1. 23.
[백준] 10026번 적록색약 JAVA (자바) 풀이 문제 10026 크기가 N×N인 그리드의 각 칸에 R(빨강), G(초록), B(파랑) 중 하나를 색칠한 그림이 있다 구역은 같은 색으로 이루어져 있다 같은 색상이 상하좌우로 인접해 있는 경우 같은 구역으로 취급 적록색약인 사람은 초록과 빨강은 같은 색으로 보여진다 적록색약인 사람이 봤을 때와 아닌 사람이 봤을 때 구역의 수를 구해라 (예시) RRRBB GGBBB BBBRR BBRRR RRRRR 적록색약이 아닌 사람 : 구역 총 4개 (빨강 2, 파랑 1, 초록 1) 적록색약인 사람은 : 구역 총 3개 볼 수 있다. (빨강 & 초록 2, 파랑 1) [입력] : 첫째 줄에 N (1 ≤ N ≤ 100) : 둘째 줄부터 N개 줄에는 그림 5 RRRBB GGBBB BBBRR BBRRR RRRRR [출력] : 적록.. 2024. 1. 22.
[백준] 2468번 안전 영역 JAVA (자바) 풀이 문제 2468 (dfs, 백트래킹)지역의 높이 정보를 파악지역에 많은 비가 내렸을 때 물에 잠기지 않는 안전한 영역이 최대로 몇 개가 만들어 지는 지를 조사장마철에 내리는 비의 양에 따라 일정한 높이 이하의 모든 지점은 물에 잠긴다고 가정각 지역의 높이 정보 = N크기의 2차원 배열 형태배열의 각 원소 = 높이 침수 정도를 어떤 높이로 설정해야 안전한 영역이 최대가 되는지 계산해라 예) N=5 → 5 x 5 배열 6826232346673327253689527 높이가 4 이하인 지점 물에 잠겼다 = 회색6826232346673327253689527 →  안전한 영역 = 물에 잠기지 않는 지점 상, 하, 좌, 우로 인접하며 그 크기가 최대인 영역→  안전한 영역 = 5개 높이가 6이하인 지점이 잠긴다면 안전.. 2024. 1. 22.
[백준] 2210번 숫자판 점프 JAVA (자바) 풀이 문제 2210번 : 5 x 5의 숫자판 존재 각 칸에는 0~9까지의 숫자가 들어갈 수 있다 : 처음 칸에서 5번 더 이동 가능 (상하좌우로만) 모두 이동한 칸은 처음 칸을 포함해서 총 6칸 중복으로 이동 가능 (즉 갔던 자리 다시 갈 수 있다는 뜻) : 나올 수 있는 6칸의 숫자를 붙여서 6자리의 경우의 수를 구하여라 [입력] : 다섯 개의 줄에 다섯 개의 정수로 숫자판 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 [출력] : 경우의 수 출력 15 [문제접근] 모든 경로를 하나하나 다 파악해줘야 하기 때문에 DFS 선택! 다른 문제와 달리 방문기록을 표시하는 객체가 없다 → 해당 문제는 중복을 허용하기 때문이다 → 즉, 같은 자리를 다시 찾아갈 수 있다 다만 .. 2024. 1. 21.
[백준] 1182번 부분수열의 합 JAVA (자바) 풀이 문제 1182번  :  N개의 정수로 이루어진 수열    크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하기  [입력] :  첫 줄에 정수 개수 N, 정수 S (1 ≤ N ≤ 20, |S| ≤ 1,000,000)     둘째 줄에 N개의 수열이 공백으로 구분[출력] : 합이 S가 되는 부분수열 개수 출력 [과정] - [공통] 공집합일 경우를 생각해야 하므로 S = 0 이라면 -1 하고 시작한다  - 재귀적 백트래킹반복문을 쓰지 않아서 좀 더 직관적으로 코드를 간결하게 볼 수 있다dfs(next,sum);         dfs(next,sum+arr[start]); 예) [3, 7, 2] / S=9        backtrack(0, 0)              ├.. 2023. 11. 27.
[백준] 15649번 N과 M(1) JAVA (자바) 풀이 문제 15649번 (백트래킹) :  자연수 N과 M이 주어졌을 때,     1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열을 모두 구하는 프로그램        (예) N = 3, M = 1 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1 / 2 / 3 이렇게 만든 수열을 한줄에 하나씩 출력한다  [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8)[출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력  [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 문제 조건) 숫자 중복금지 → 완전 탐색이 아닌.. 2023. 11. 13.
[백준] 1914번 하노이 탑 JAVA (자바) 풀이 문제 1914번 : 3개의 장대 중 첫번째 장대에 반경이 서로 다른 n개의 원판이 크기 순서대로 쌓여있다 : 첫번째 장대를 세번째 장대로 옮긴다 한 번에 한 개의 원판씩 옮기기 가능 쌓아놓은 원판은 항상 크기별로 (아래로 갈수록 더 크다) : 이동횟수는 최소 [입력] : 첫 줄에 첫번째 장대에 쌓인 원판 개수 N (1 ≤ N ≤ 100) [출력] : 첫째줄에 옮긴 횟수 출력 : 두번째 줄부터 K개의 줄까지 수행과정 출력 (N ≤ 20) 예) 두 정수 A B 출력 = A번째 탑의 가장 위 원탑을 B번째 탑의 가장 위로 옮긴다 : N > 20 경우 과정 출력 X [설명 예시] 원반개수 [n = 1] A → C 1회 총 1회 원반개수 [n = 2] A → B 1회 A → C 1회 B → C 1회 총 3회 원반.. 2023. 10. 30.
[백준] 14888번 연산자 끼워넣기 JAVA (자바) 풀이 문제 14888번 : N개의 수열 (A1, ... , AN) 주어진다 수 사이에 끼워넣을 수 있는 N-1개의 연산자 (+ 덧셈, - 뺄셈, × 곱셈, ÷ 나눗셈) 주어진다 숫자 순서 바꿀 수 X, 연산자 순서 바꿀 수 O : 우선순위 무시하고 앞에서부터 계산 나눗셈은 몫만 구하고, 음수를 양수로 나눌 때에는 숫자끼리만 나누고 몫에 -만 붙여준다 (=음수처리) : 결과식 최대인 것과 최소인 것을 구해라 [입력] : 첫 줄에 수열 개수 N : 둘째 줄 N개의 수열 : 연산자 개수 ( +, -, ×, ÷ 순서 ) [출력] : 식 최댓값 첫째줄에, 식 최솟값 둘째줄에 출력 [알고리즘] 모든 경우를 분석해야 하는구나 = 완전 탐색 = 브루트 포스 연산자의 조합을 이용해야 한다 = 순열 순열을 쉽게 구하기 위해서는.. 2023. 10. 29.

티스토리툴바