본문 바로가기

백준83

[백준] 2579번 계단 오르기 JAVA (자바) 풀이 문제 2579번 (DP) : 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다 계단 오르는 규칙한 번에 한 계단씩 또는 두 계단씩 오르기연속된 세 개의 계단을 모두 밟아서는 안 된다 (단, 시작점은 미포함)마지막 도착 계단은 반드시 밟아야 한다총 점수의 최댓값을 구하는 프로그램을 작성하시오    [입력] :  입력의 첫째 줄에 계단의 개수    둘째 줄부터 한 줄에 하나씩 계단 점수    (계단 개수는 300이하의 자연수, 계단 점수는 10,000이하의 자연수) [출력] :  첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력 [설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단.. 2024. 6. 29.
[백준] 1003번 피보나치 함수 JAVA (자바) 풀이 문제 1003번 (DP)int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); }} fibonacci(3) = fibonacci(2)와 fibonacci(1) fibonacci(2) = fibonacci(1)과 fibonacci(0)    [입력] :  첫째 줄에 테스트 케이스의 개수 T    각 테스트 케이스에 N이 주어진다 ( N은 40보다 작거나 같은 자연수 또는 0)  [출력] :  각 테스트 케이스.. 2024. 6. 29.
[백준] 9095번 1, 2, 3 더하기 JAVA (자바) 풀이 문제 9095번 (DP) : 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지   합을 나타낼 때는 수를 1개 이상 사용1+1+1+11+1+21+2+12+1+12+21+33+1정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.    [입력] :  첫째 줄에 테스트 케이스의 개수 T    각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다 ( n은 양수이며 11보다 작다)  [출력] :  각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력[설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  DP 구현 방법은 일반적으로 Top-do.. 2024. 6. 29.
[백준] 10819번 차이를 최대로 JAVA (자바) 풀이 문제 10819번 (브루트포스, 백트래킹)  :  N개의 정수로 이루어진 배열 A    배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구해라 |A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|   [입력] :  첫째 줄에 N (3 ≤ N ≤ 8) :  둘째 줄에는 배열 A에 들어있는 정수 ( -100 ≤ 정수 ≤ 100 )   [출력] :  식의 최댓값을 출력    [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹  수열을 모두 바꿔가며 max 값을 찾기 때문에 브루트포스가 맞다  종료 조건) depth==N N개의 숫자를 모두 뽑았기 때문에 종료하고 sum 계산 후 result로 max값 뽑아내기  1. 계산은 i.. 2024. 6. 26.
[백준] 2529번 부등호 JAVA (자바) 풀이 문제 2529번 (백트래킹)  :  부등호 기호 ‘’가 k개 나열된 순서열 A가 있다    부등호 기호 앞 뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다    숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다  :  부등호 기호를 제거한 뒤, 숫자를 모두 붙이면 하나의 수를 만들 수 있다    부등호 순서를 만족하는 (k+1)자리의 정수 중에서 최댓값과 최솟값을 찾아야 한다   [입력] :  첫 줄에 부등호 문자의 개수 정수 k :  그 다음 줄에는 k개의 부등호 기호 (k의 범위는 2 ≤ k ≤ 9)    [출력] :  k+1 자리의 최대, 최소 정수를 첫째 줄과 둘째 줄에 각각 출력 (첫 자리가 0인 경우도 정수에 포함)   [과정]  탐색하자 → 브루트.. 2024. 6. 25.
[백준] 10971번 외판원 순회2 JAVA (자바) 풀이 문제 10971번 (백트래킹)  :  1번 ~ N번 도시    한 도시에서 출발해 N개의 도시를 거쳐 원래의 도시로 돌아오는 순회 여행 경로    (한 번 갔던 도시로는 다시 갈 수 없다)  :  이동 비용 W[i][j] = 도시 i에서 도시 j로 가기 위한 비용 (W[i][j] ≠ W[j][i])    W[i][i]는 항상 0 / 갈 수 없는 경우도 0  :  가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.   [입력] :  첫째 줄에 도시의 수 N (2 ≤ N ≤ 10) :  다음 N개의 줄에는 비용 행렬 (각 행렬의 성분은 1,000,000 이하의 양의 정수)    (갈 수 없는 경우는 0) [출력] :  순회에 필요한 최소 비용을 출력    [과정]  탐색하자 .. 2024. 6. 22.
[백준] 2589번 보물 JAVA (자바) 풀이 문제 2589(BFS)  :  보물섬 지도의 각 칸은 육지(L)나 바다(W)로 표시    이동은 상하좌우로 이웃한 육지로만 가능, 한 칸 이동하는데 한 시간이 걸린다    보물은 육지 두 곳에 나뉘어 묻혀있고 두 곳을 이동하는 최단거리를 구해라    같은 곳을 두 번 이상 지나가거나, 멀리 돌아가서는 안 된다  예) 보물은 아래 표시된 두 곳에 묻혀 있고, 이 둘 사이의 최단 거리로 이동하는 시간은 8시간  [입력] :  첫째 줄에는 지도의 가로, 로 ( 가로, 세로의 크기는 각각 50이하 ) :  다음 줄부터 L과 W로 표시된 보물 지도 (빈칸없이)   [출력] :  보물이 묻혀 있는 두 곳 사이를 최단 거리로 이동하는 시간을 출력     [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기co.. 2024. 6. 21.
[백준] 1697번 숨바꼭질 JAVA (자바) 풀이 문제 1697(BFS)  :  수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다  :  수빈이는 걷거나 순간이동을 할 수 있다     현위치가 X일 때     걷기 = 1초 후에 X-1 or X+1    순간이동 = 1초 후에 2*X  :  동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램  [입력] :  첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K   [출력] :  동생을 찾는 가장 빠른 시간을 출력     [문제접근] 1. 출력 배열 사용하지 말고 큐에다 넣어버리기count[] 배열보다 큐 자체에 넣는 것이 더 간단하다 q.add(new int{start,0}) 추천 2. for문 상하좌우 이동을 떠올릴.. 2024. 6. 20.
[백준] 24444번 알고리즘 수업 - 너비 우선 탐색 1 JAVA (자바) 풀이 문제 24444번 (bfs) :  N개의 정점과 M개의 간선으로 구성된 무방향 그래프(undirected graph)    정점 번호는 1번부터 N번이고 모든 간선의 가중치는 1이다    정점 R에서 시작하여 노드의 방문 순서를 출력하자    인접 정점은 오름차순으로 방문한다bfs(V, E, R) { # V : 정점 집합, E : 간선 집합, R : 시작 정점  for each v ∈ V - {R}  visited[v]    [입력] :  첫째 줄에 정점의 수 N (5 ≤ N ≤ 100,000), 간선의 수 M (1 ≤ M ≤ 200,000), 시작 정점 R (1 ≤ R ≤ N) :  다음 M개 줄에 간선 정보 u v (가중치 1인 양방향 간선) (1 ≤ u  ≤ N, u ≠ v)    .. 2024. 6. 20.
[백준] 11060번 점프 점프 JAVA (자바) 풀이 문제 11060번 (bfs) :  1×N 크기의 미로 ( 1×1 크기의 칸으로 이루어져 있다)    i번째 칸에 쓰여 있는 수를 Ai  :  Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프가능    (예 : 3번째 칸에 쓰여 있는 수가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프가능)  :  현위치 = 미로의 가장 왼쪽 끝 / 가장 오른쪽 끝으로 가려고 할 때 최소 몇 번 점프를 해야하는지 구해라    (가장 오른쪽 끝으로 갈 수 없다면 -1을 출력)   [입력] :  첫째 줄에 N(1 ≤ N ≤ 1,000) :  둘째 줄에 Ai (0 ≤ Ai ≤ 100)  [출력] :  최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력     (갈 수 없다면 -1 출력) [설명] 1. 출.. 2024. 6. 19.

티스토리툴바