본문 바로가기

Java123

[백준] 15649번 N과 M(1) JAVA (자바) 풀이 문제 15649번 (백트래킹) :  자연수 N과 M이 주어졌을 때,     1부터 N까지 자연수 중에서 중복 없이 M개를 골라서 수열을 모두 구하는 프로그램        (예) N = 3, M = 1 인 경우    1~3까지의 수 중에서 1개만 골라서 만들 수 있는 수열을 모두 만든다    1 / 2 / 3 이렇게 만든 수열을 한줄에 하나씩 출력한다  [입력] :  첫 줄에 자연수 N, M (1 ≤ M ≤ N ≤ 8)[출력] : 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력 (중복 수열 X)   수열의 원소는 공백으로 구분해서 출력  : 수열은 사전 순으로 증가하는 순서로 출력  [과정]  탐색하자 → 브루트포스 / dfs → 조건이 있다 → 백트래킹 문제 조건) 숫자 중복금지 → 완전 탐색이 아닌.. 2023. 11. 13.
[백준] 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.
[백준] 2531번 회전 초밥 JAVA (자바) 풀이 문제 2531번 (투포인터, 슬라이딩 윈도우) : 초밥 벨트 임의의 위치부터 k개의 접시를 연속해서 식사 : 쿠폰에 쓰여진 초밥은 무료 시식 가능 : 손님이 먹을 수 있는 최대 초밥 가짓수를 구해라 [입력] : 첫 줄에 접시 수 N / 초밥 가짓 수 d / 연속해서 먹는 접시의 수 k / 쿠폰 번호 c 둘째 줄에는 수열 N개의 줄에는 각 줄 마다 초밥 종류가 하나씩 주어진다 [출력] : 먹을 수 있는 초밥의 최대 가짓 수 출력 [설명] (예시) k=4, 30번 초밥을 쿠폰 획득일 경우 - 가능한 모든 경우의 수 (7,9,7,30),(9,7,30,2),(7,30,2,7),(30,2,7,9),(2,7,9,25),(7,9,25,7),(9,25,7,9),(25,7,9,7) - 최대한 많은 종류를 먹어야해서 초밥.. 2023. 10. 23.
[프로그래머스] Lv.2 두 큐 합 같게 만들기 JAVA 풀이 문제 Lv.2 두 큐 합 같게 만들기 : 길이가 같은 두 개의 큐 : 하나의 큐를 골라 원소를 추출(pop)하고 추출된 원소를 다른 큐에 집어넣는(insert) 작업 : 각 큐의 원소 합이 같도록 만드는 최소의 횟수 출력 어떤 방법으로도 같을 수 없다면 -1 출력 : 한 번의 pop과 한 번의 insert를 합쳐서 작업을 1회 수행한 것으로 간주 : 1 ≤ queue1의 길이 = queue2의 길이 ≤ 300,000 1 ≤ queue1의 원소, queue2의 원소 ≤ 109 주의: 언어에 따라 합 계산 과정 중 산술 오버플로우 발생 가능성이 있으므로 long type 고려가 필요 : 입력 예 queue1 = [3, 2, 7, 2] queue2 = [4, 6, 5, 1] 출력 예 result = 2 [코드.. 2023. 10. 10.
[프로그래머스] Lv.2 호텔 대실 JAVA 풀이 문제 Lv.2 호텔 대실 : 최소한의 객실만을 사용하여 예약 손님 받기 사용한 객실은 퇴실하고 10분간 청소를 한 다음 다른 손님들 사용가능 : 예약 시각 = book_time ( 문자열 형태 2차원 배열 ) 1 ≤ book_time의 길이 ≤ 1,000 book_time[i] = ["HH:MM", "HH:MM"] = [대실 시작 시각, 대실 종료 시각] 형태 : 예약 시각이 자정을 넘어가는 경우는 X 시작 시각은 항상 종료 시각보다 빠르다 : 입력 예 [["15:00", "17:00"], ["16,40", "18,20"], ["14:20", "15:20"], ["14:10", "19:20"], ["18:20", "21:20"]] : 출력 예 book_timeresult = 3 [알아두기] < Repla.. 2023. 10. 10.
[프로그래머스] Lv.1 크레인 인형뽑기 JAVA 풀이 문제 Lv.1 크레인 인형뽑기 : 게임화면 = N × N 격자 아래부터 차곡차곡 쌓여있음 크레인 위치를 좌우로 옮겨 가장 위에 있는 인형 집어올려 바구니에 넣는다 바구니에 같은 모양의 인형이 두 개 만나면 터져서 없어진다 (바구니는 모든 인형이 다 들어갈 수 있는 여유로운 크기이다) [예시문제] : 격자 = 2차원 배열 board, 크레인 위치 = moves : board = [0,0,0,0,0] [0,0,1,0,3] [0,2,5,0,1] [4,2,4,4,2] [3,5,1,3,1] : moves = [1,5,3,5,1,2,1,4] : result = 4 : 바구니 = [4,3,1,1,3,2,4] [코드] import java.util.*; class Solution { public int solution.. 2023. 10. 2.
[백준] 11053번 가장 긴 증가하는 부분 수열 JAVA (자바) 풀이 문제 11053번 : 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우, 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 각 dp[] 의 길이들은 다음 부분 수열을 의미하는 것이다 출처 https://st-lab.tistory.com/137 dp[0] = 10 이제 나온 것 {10} 중에 가장 길다 = 1 dp[1] = 20 이제 나온 것 {10, 20} 중에 가장 길다 = 2 dp[2] = 10 이제 나온 것 {10, 20} 중에 10까지는 길이가 1밖에 안된다 dp[3] = 30 이제 나온 것 {10, 20, 30} 중에 가장 길다 = 3 dp[4] = 20 이.. 2023. 9. 25.
[백준] 1463번 1로 만들기 JAVA (자바) 풀이 문제 1463번 : 정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 X가 3으로 나누어 떨어지면, ÷ 3 X가 2로 나누어 떨어지면, ÷ 2 - 1 위와 같은 연산 세 개를 사용해서 N = 1을 만들려고 할 때 연산의 최소 횟수를 출력 [입력] : 첫 줄에 N (1 ≤ N ≤ 106) [출력] : 첫째 줄에 연산을 하는 횟수의 최솟값을 출력 [설명] DP 알고리즘 : 이미 계산된 결과는 별도의 메모리 영역에 저장하여 다시 계산하지 않음으로서 수행 시간 단축시키는 방법 DP 구현 방법은 일반적으로 Top-down(하향식)과 Bottom-up(상향식)으로 구성된다 1) Top-down(하향식) 하위 문제를 재귀적으로 호출하여 해결함으로서 상위 문제를 해결하는 방식 이 때 해결해놓은 하위 문제를 저장해.. 2023. 9. 25.

티스토리툴바