본문 바로가기

분류 전체보기172

[백준] 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.
[프로그래머스] Lv.1 바탕화면 정리 JAVA 풀이 문제 Lv.1 바탕화면 정리 (배열 탐색)  : 컴퓨터 바탕화면은 각 칸이 정사각형인 격자판   컴퓨터 바탕화면의 상태를 나타낸 문자열 배열 = wallpaper   빈칸은 = "."   파일이 있는 칸 = "#"   최소한의 이동거리를 갖는 한 번의 드래그로 모든 파일을 선택해서 한 번에 지우기   드래그는 "점 S에서 점 E로 드래그한다"    "드래그 한 거리" = |rdx - lux| + |rdy - luy|      예)   wallpaper = [".#...", "..#..", "...#."]   S(0, 1)에서 E(3, 4)로 드래그하면 세 개의 파일이 모두 선택   드래그 한 거리 = (3 - 0) + (4 - 1) = 6을 최솟값 1 ≤ wallpaper[i]의 길이 ≤ 50모든 원소의.. 2024. 6. 28.
[프로그래머스] Lv.1 공원 산책 JAVA 풀이 문제 Lv.1 공원 산책 (방향 탐색 시뮬레이션)  :  지나다니는 길 O 장애물 X    ["방향거리", "방향거리"..]     "E 5" = 현재 위치에서 동쪽으로 5칸 이동했다는 의미     공원의 가로 길이가 W, 세로 길이가 H     공원을 나타내는 문자열 배열 park    명령이 담긴 문자열 배열 routes 3 ≤ park[i]의 길이 ≤ 50S : 시작 지점 (1개) O : 이동 가능한 통로X : 장애물1 ≤ routes의 길이 ≤ 50수행할 명령어routes의 원소는 "op n"과 같은 구조 (op는 이동할 방향, n은 이동할 칸의 수)N : 북 이동 / S : 남 이동 / W : 서 이동 / E : 동 이동1 ≤ n ≤ 9  [과정] - 2차원 배열 헷갈리지 말자!! - arr[행.. 2024. 6. 28.
[백준] 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.

티스토리툴바