알고리즘30 1로 만들기 ( 백준 1463 ) https://www.acmicpc.net/problem/1463 * dp 알고리즘을 활용하는 문제* 순차적으로 증가하는 수열이 아니라서 어떻게 풀어야할지 고민함* dp[] 배열을 사용할때 3가지 연산이 존재함* %2, %3을 해서 나누어 떨어질때 하는 연산들은 2의배수 3의배수 일때만 가능함* -1하는 연산은 어떤 값이든 간에 가능하기 때문에 제일 먼저 연산 시작* dp[i]-1 = dp[i-1] 해서 1되는지 보지만 dp[i] 값을 보기위해 이항해서 dp[i] = dp[i-1] + 1 식을 활용한다* dp[i] = dp[i-1] + 1과 2로 나누어 떨어지면 dp[i/2], 3으로 나누어 떨어지면 dp[i/3] 비교해 최소값으로 갱신* 최종 input 배열에 있는 값을 출력 * 아이패드에 끄적여 보.. 2025. 2. 24. 1, 2, 3 더하기 백준 9095 ( dp ) https://www.acmicpc.net/problem/9095 dp를 활용한 문제.처음에는 덧셈 결과를 가지고 점화식을 세우는줄 알았는데,합이 1일때 경우의수합이 2일때 경우의수합이 3일때 경우의수 ,,,, 이렇게 해서 dp[i] = dp[i-3]+dp[i-2]+dp[i-3] 점화식을 세워서for 루프를 한번만 돌려서 O(N) 시간 복잡도가 걸린다. 이렇게 규칙을 발견하면 i-1, i-2, i-3 더한 값이 i 에 할당되는 점화식을 세울 수 있다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class onetwothree { sta.. 2025. 2. 17. # 25 - 1 테스트 보호되어 있는 글 입니다. 2025. 2. 5. 프로그래머스 LV.2 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 설명 : 무인도에 갖힌 사람들을 구해야한다. 구명보트는 작아서 한 번에 최대 2명씩 밖에 탈 수 없다.[70, 50, 80, 50] 을 예를 들면 2번째 4번째 사람과 같이 탈 수 있지만, 1번째 3번째 사람은 limit가 초과해서 안된다.문제 출력 조건은 구명보트를 최대한 적게 사용하여 모든 사람을 구출 해야한다. 문제 해설 : 최대 2명씩 이라는 조건을 보았을때 투 포인터 알고리즘을 떠올렸으면 성공이다.배열을 Arrays.sort() .. 2025. 2. 4. 프로그래머스 LV2 ( 디펜스 게임 ) https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr * 남은 병사수와 무적권의 횟수를 잘 사용하여 최대로 막을 수 있는 횟수를 반환하면 되는 문제.* 처음에는 병사수를 최대한 사용하고 무적권을 사용하면 되는줄 알았다.* 그렇게 구현하기 쉽지않았고 결국 문제 풀이를 보니까 pq를 사용한 풀이였다.* enemy 배열을 순차적으로 한개씩 가져와서 문제를 풀어야한다. ( 적은 인덱스 0번부터 접근하니까 )* enemy 배열에 접근을 순차적으로 해서 무적권 갯수만큼은 pq에 저장하고 continue 한.. 2025. 1. 30. 프로그래머스 뒤에 있는 큰 수 찾기 ( LV 2 ) https://school.programmers.co.kr/learn/courses/30/lessons/154539?language=java 프로그래머스SW개발자를 위한 평가, 교육, 채용까지 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr * 문제 제목 그대로 뒤에 있는 숫자중 가장 큰 숫자를 고르는 것이다. + 제일 가까이 있는 숫자중에서.* 처음에는 BruteFroce를 돌려서 현재 숫자보다 큰 숫자가 등장하면 break를 걸고 결과를 갱신하는 코드를 작성했는데 시초가 났다.* 아무리 짱구를 굴려봐도 답이 안나와서 GPT한테 물어봤다. * Stack을 활용하면 O(N) 시간 복잡도로 끝낼수 있다.* 알고리즘 흐름을 설명하면. 1) numbers 길이.. 2025. 1. 21. 이전 1 2 3 4 5 다음
