재귀6 [프로그래머스] Lv.2 타겟 넘버 JAVA 풀이 문제 Lv.2 타겟 넘버 (dfs, bfs)n개의 음이 아닌 정수정수들을 순서를 바꾸지 않고 더하거나 빼서 타겟 넘버를 만들자예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있다-1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3 [과정] 탐색하자 → 브루트포스 / dfs 1. count 계산은 맨 마지막에모든 넘버들을 다사용해서 타겟넘버를 만들어야해서 마지막까지 가고나서 타겟넘버랑 같으면 count++각자 타고 타고 들어가 dfs를 실행하면 count 별도 연산 없이도 차곡차곡 쌓인다!-> 최종적으로 solution메서드에서 그렇게 쌓인 count만 출력해주면 끝 2. for문을 .. 2025. 3. 18. [백준] 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. 이전 1 다음
