본문 바로가기

재귀5

[백준] 9184번 신나는 함수 실행 JAVA (자바) 풀이 문제 9184번 (DP) :  재귀함수 w(a, b, c)가 있다if a 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20)if a   a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램   otherwise w(2a-2, 2b, c) 출력력  [입력] :  입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다    (입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다)  [출력]  :   w(a, b, c)를 출력  [설명] DP 알고리즘: 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법  .. 2024. 7. 2.
[백준] 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.
[백준] 17609번 회문 JAVA (자바) 풀이 문제 17609번 (투포인터) : 회문이란? 앞뒤로 같은 순서의 문자로 구성된 문자열 (예) 'abba’, ‘kayak’, ‘reviver’, ‘madam’ : 유사회문이란? 한 문자를 삭제해서 회문으로 만들 수 있는 문자열 (예) 'summuus’ 에서 5 or 6 번째 문자 제거하면 회문이 된다 : 회문이면 0, 유사회문이면 1, 그 외는 2를 출력한다 [입력] : 첫 줄에 문자열 개수 T 둘째 줄부터 T개의 줄에 문자열 하나씩 입력 ( 3 ≤ 문자열 길이 ≤100,000 ) (문자열 길이는 3영문 알파벳 소문자로 이루어져있다) [출력] : 회문이면 0, 유사회문이면 1, 그 외는 2를 출력 [설명] 양 끝에서부터 검사하기 시작한다 → 이때 시작지점, 끝지점 두 개의 포인터 필요 시작 = 끝 이라면 .. 2023. 10. 23.
[프로그래머스] Lv.2 광물 캐기 JAVA 풀이 문제 Lv.2 광물 캐기(DFS) -   곡괭이로 광물을 캘 때 피로도 소모 -   캐기 시작하면 한 곡괭이로 광물 5개까지 연속 캐기  -   광물은 주어진 순서대로 캐기 -   광산에 있는 광물 모두 캐거나 사용할 곡괭이가 없을 때까지 캔다  [ 피로도 ]  [ 입력 ]  -   곡괭이 개수 : picks = [다이아, 철, 돌] (정수 배열) -   광물 순서: minerals (문자열 배열)  [알고 가기]   -  깊이 우선 탐색-  그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘-  스택 or 재귀함수 이용 -  제일 깊게 내려간 뒤 더이상 갈 수 없을 때 옆으로   이동해서 다시 깊게 내려가기를 반복-  구현 : DFS (간단) > BFS -  검색 속도 : BFS  > DFS (느림) .. 2023. 9. 4.

티스토리툴바