본문 바로가기

Baekjoon86

[백준] 1010번 다리 놓기 JAVA (자바) 풀이 문제 1010번 (DP) :  도시에는 도시를 동쪽과 서쪽으로 나누는 큰 일직선 모양의 강이 흐르고 있다    :  다리를 짓기에 적합한 곳 = 사이트    강 서쪽 사이트 = N개, 동쪽 사이트 = M개 (N ≤ M)  :  한 사이트 - 한 다리 연결     크로스처럼 다리끼리 겹칠 수 없다  :  서쪽과 동쪽을 연결하는 다리를 지어라   [입력]  : 첫 줄에는 테스트 케이스의 개수 T : 그 다음 줄부터 서쪽과 동쪽의 있는 사이트의 개수 정수 N, M (0    [출력] : 다리를 지을 수 있는 경우의 수를 출력   [과정]  1:1로 연결해야하므로 최대 N개의 다리를 설치할 수 있다 단, 크로스처럼 다리가 겹쳐서는 안된다  크로스는 동쪽 다리의 인덱스가 순서대로 (이전 인덱스 되어야한다고 생각.. 2024. 6. 29.
[백준] 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.

티스토리툴바