본문 바로가기

Java123

[백준] 1068번 트리 JAVA (자바) 풀이 문제 1068번 (dfs)  :  리프 노드 = 자식의 개수가 0인 노드    노드를 지우면 그 노드와 노드의 모든 자손이 트리에서 제거     남은 트리에서 리프 노드의 개수를 구하는 프로그램을 작성   예) 리프 노드의 개수는 3개  이때, 1번을 지우면, 다음과 같이 변한다. 회색으로 색칠된 노드가 트리에서 제거 이제 리프 노드의 개수는 1개   [입력] :  첫째 줄에 트리의 노드의 개수 N (N은 50보다 작거나 같은 자연수) :  둘째 줄에는 0번 ~ N-1번 노드까지 각 노드의 부모가 주어진다    (만약 부모가 없다면 -1) :  셋째 줄에는 지울 노드의 번호    [출력] :  첫째 줄에 주어진 노드를 지웠을 때, 남은 리프 노드의 개수를 출력    [과정]  탐색하자 → 브루트포스 / .. 2024. 8. 1.
[백준] 1931번 회의실 배정 JAVA (자바) 풀이 문제 1931(그리디, 정렬) :  한 개의 회의실, N개의 회의, 회의실 사용표 :  각 회의 I에 대해 시작시간과 끝나는 시간    각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수 찾기  :  회의는 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의 시작    (회의의 시작시간과 끝나는 시간이 같다면 시작하자마자 끝나는 회의)  [입력] :  첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000) :  둘째 줄부터 N+1 줄까지 각 회의의 시작시간과 끝나는 시간    (시작 시간과 끝나는 시간은 2³¹-1보다 작거나 같은 자연수 또는 0)    [출력] :  첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력    [문제접근]  1. 정렬 이용하.. 2024. 7. 17.
[백준] 2636번 치즈 JAVA (자바) 풀이 문제 2636(BFS)  : 회색으로 표시된 부분 = 치즈   X친 부분 = 판의 가장자리 (치즈 없음)   ‘c’로 표시된 부분만 한 시간 후에 녹고 빈칸과 접촉하는 치즈는 c 표시 해준다   단 치즈로 둘러쌓여있는 빈칸은 접촉해도 c표시 없어도 된다 :  치즈가 모두 녹아 없어지는 데 걸리는 시간과 모두 녹기 한 시간 전에 남아있는 치즈조각 개수 구해라  [입력] :  첫째 줄에는 사각형 모양 판의 세로와 가로의 길이가 양의 정수 (길이는 최대 100)    판의 각 가로줄의 모양이 윗 줄부터 차례로 둘째 줄부터 마지막 줄까지    (치즈가 없는 칸은 0, 치즈가 있는 칸은 1)     [출력] :  첫째 줄에는 치즈가 모두 녹아서 없어지는 데 걸리는 시간을 출력 :  둘째 줄에는 모두 녹기 한 시간.. 2024. 7. 13.
[백준] 3055번 탈출 JAVA (자바) 풀이 문제 3055(BFS)  :  티떱숲의 지도는 R행 C열로 이루어져 있다    비어있는 곳은 .    물이 차있는 지역은 *    돌은 X    비버의 굴은 D    고슴도치의 위치 S  :  매 분마다 고슴도치는 현재 있는 칸과 인접한 네 칸 중 하나로 이동가능    물도 매 분마다 인접한 비어있는 칸으로 확장    물과 고슴도치는 돌을 통과할 수 없다    고슴도치는 물로 차있는 구역으로 이동할 수 없고, 물도 비버의 소굴로 이동할 수 없다  :  고슴도치가 안전하게 비버의 굴로 이동하기 위해 필요한 최소 시간을 구하는 프로그램    (다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다)  [입력] :  첫째 줄에 50보다 작거나 같은 자연수 R과 C :  다음 R개 줄에는 티떱숲의 지도 .. 2024. 7. 12.
[백준] 9019번 DSLR JAVA (자바) 풀이 문제 9019(BFS)  :  네 개의 명령어 D, S, L, R    계산기에는 레지스터 = 0 이상 10,000 미만의 십진수 저장 가능     예) 레지스터에 저장된 n (n의 네 자릿수를 d1, d2, d3, d4)          즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)D = n x 2 (결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지)S = n - 1 (n이 0 이라면 9999 가 대신 레지스터에 저장)L = n의 각 자릿수를 왼편으로 회전 (d2, d3, d4, d1)R = n의 각 자릿수를 오른편으로 회전 (d4, d1, d2, d3) :  A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램  [입력] :  첫 줄에 T 개의.. 2024. 7. 11.
[백준] 16234번 인구 이동 JAVA (자바) 풀이 문제 16234(BFS)  :  N×N크기의 땅    각 땅에는 나라가 하나씩 존재 ( r행 c열에 있는 나라에는 A[r][c]명이 산다)  :  인구 이동이 없을 때까지 지속된다.붙어있는 두 나라의 인구 차이가 L명 이상, R명 이하라면 인구 이동 시작인접한 칸만을 이용해 이동할 수 있으면 연합연합을 이루고 있는 각 칸의 인구수는 (연합의 인구수) / (연합을 이루고 있는 칸의 개수)편의상 소수점은 버린다연합을 해체하고 모든 국경선을 닫기 :  각 나라의 인구수가 주어졌을 때, 인구 이동이 며칠 동안 발생하는지 구하는 프로그램  [입력] :  첫째 줄에 N, L, R (1 ≤ N ≤ 50, 1 ≤ L ≤ R ≤ 100)    둘째 줄부터 N개의 줄에 각 나라의 인구수    r행 c열에 주어지는 정수는 .. 2024. 7. 11.
[백준] 9205번 맥주 마시면서 걸어가기 JAVA (자바) 풀이 문제 9205(BFS)  :  출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발    맥주 한 박스에는 맥주가 20개     맥주 1병에 50미터 전진 가능    편의점에 들렸을 때, 빈 병은 버리고 새 맥주를 살 때 박스에 들어가는 총 맥주가 20병을 넘을 수 없다    (편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다)    편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다  [입력] :  첫째 줄에 테스트 케이스의 개수 t (t ≤ 50)    테스트 케이스의 첫째 줄에는 편의점의 개수 n (0 ≤ n ≤ 100)    다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 미터 좌표 ( -32768 ≤ x, y ≤ 32767)    두 좌표 사.. 2024. 7. 6.
[백준] 16928번 뱀과 사다리 게임 JAVA (자바) 풀이 문제 16928(BFS)  :  주사위를 조작해 원하는 수를 만들면 최소 몇 번만에 도착할까    게임은 크기가 10×10이고, 총 100개의 칸으로 된 보드판은 1~100까지 수가 적혀있다    주사위를 굴려 나온 수만큼 이동  :  예) 현위치 =  i  /  주사위 = 4라면 i+4번 칸으로 이동  :  도착칸 = 사다리 경우 위로 이동  /  도착칸 = 뱀 경우 뱀을 따라 이동    모든 칸은 최대 하나의 사다리 또는 뱀을 가지고 있다 (동시에 둘 다 갖는 경우는 없다)   :  게임의 목표 = 1번 칸에서 시작해서 100번 칸에 도착하는 것    100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값 구하기  [입력] :  첫째 줄에 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(.. 2024. 7. 3.
[백준] 13549번 숨바꼭질 3 JAVA (자바) 풀이 문제 13549(BFS)  :  수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다     현 위치가 X일 때    걷기 = 1초 후에 X-1 또는 X+1로 이동    순간이동 =  0초 후에 2*X의 위치로 이동    수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구해라  [입력] :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K  [출력] :  동생을 찾는 가장 빠른 시간을 출력    [문제접근] 1. 기존 숨바꼭질 1697번과 차이점!기존 문제에서는 모든 이동이 동일한 1초를 소요현 문제에서는 순간 이동은 0초 / 걷기 이동만 1초 소요 2. 출력 배열 사용하지 말고 큐에다 넣어버리기count[] 배열보다 .. 2024. 7. 3.
[백준] 11048번 이동하기 JAVA (자바) 풀이 문제 11048번 (DP) :  N×M 크기의 미로    1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다    현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다    (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동 가능, 각 방의 사탕 획득 가능    (N, M)으로 이동할 때, 가져올 수 있는 사탕 개수의 최댓값  [입력] :  첫째 줄에 미로의 크기 N, M (1 ≤ N, M ≤ 1,000)    둘째 줄부터 N개 줄에는 총 M개의 숫자가 주어지며 각각의 사탕의 개수 ( 0 ≤ 사탕 ≤ 100 )  [출력]  :  가져올 수 있는 사탕 개수를 출력  [설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지.. 2024. 7. 2.

티스토리툴바