농부공학자

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net DFS 썼다. 근디 걍 DFS만 쓰면 시간 초과가 된다. 시간 초과된 코드(실패) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Baek1520 { // 내리막길 DFS public static int..

https://programmers.co.kr/learn/courses/30/lessons/12919?language=java 코딩테스트 연습 - 서울에서 김서방 찾기 String형 배열 seoul의 element중 "Kim"의 위치 x를 찾아, "김서방은 x에 있다"는 String을 반환하는 함수, solution을 완성하세요. seoul에 "Kim"은 오직 한 번만 나타나며 잘못된 값이 입력되는 경우는 없습니 programmers.co.kr 아! 서울에서 김서방 찾기 참 쉽다!! class Solution { public String solution(String[] seoul) { String answer = ""; for(int i = 0; i < seoul.length; i++) if(seoul[..

https://programmers.co.kr/learn/courses/30/lessons/12918 코딩테스트 연습 - 문자열 다루기 기본 문자열 s의 길이가 4 혹은 6이고, 숫자로만 구성돼있는지 확인해주는 함수, solution을 완성하세요. 예를 들어 s가 "a234"이면 False를 리턴하고 "1234"라면 True를 리턴하면 됩니다. 제한 사항 s는 길이 1 programmers.co.kr 아놔 이거를 문자열 s의 길이가 4나 6이어야 한다는 조건을 제대로 안봐서 처리를 안해줬다가 테스트케이스 5,6 틀렸다ㅠ 문제 제대로 보기.... class Solution { public boolean solution(String s) { for(int i = 0; i < s.length(); i++){ ..

문제 3. 효율적인 화폐 구성 문제 풀이 방식 다음과 같이 점화식을 만들 수 있다. 화폐는 10,000 이하인 값이므로 각 인덱스는 10,001 값으로 초기화 해준다. 화폐의 단위가 2일 때를 살펴보면 인덱스 2의 값은 2 하나로, 4는 2 두 개로, 6은 2 세 개로 만들 수 있다. 화폐의 단위가 3일 때를 살펴보면 인덱스 3의 값은 3 하나로, 6은 3 두 개로 표현할 수 있다. 여기서 인덱스 5와 7도 만들 수 있다. 인덱스 5에서 3칸 앞을 살펴보면 2가 있으므로 2의 값에 3을 더하면 5라서 인덱스 2의 값인 1 + 1을 해줘 2가 됨 인덱스 7도 3칸 앞을 살펴보면 인덱스 2를 두 개 활용한 4가 있음. 인덱스 4 값인 2 + 1 해줘서 3이 됨 화폐의 단위가 5일 때를 살펴보면 인덱스 5는 ..

문제 2. 1로 만들기 문제만 봤을 때 그리디를 활용해서 풀려고 했다. 그런데 그리디로 풀면 안된다. 왜냐하면 예시를 살펴보면 입력이 26일 때 그리디를 사용하면 우선 순위가 5로 나누기, 3으로 나누기, 2로 나누기, -1 빼기 순서가 될 것이기 때문에 26 -> 13 -> 12 -> 4 -> 2 -> 1 순서로 될 것이기 때문에 최소 연산인 26 -> 25 -> 5 -> 1 이 수행될 수 없다. 그래서 DP를 활용할 방법을 살펴볼 것이다. 함수가 호출되는 과정을 살펴보면 입력으로 6이 들어왔을 때 -1을 한 값인 f(5), ÷3을 한 값인 f(3), ÷2를 한 값인 f(2) 로 나누어 지며 그 밑으로 f(1)이 나올 때까지 뻗어갈 수 있다. 이렇게 작은 문제들을 조합해서 해결될 수 있기 때문에 DP를..

문제 1. 개미 전사 DP를 활용하여 문제를 풀 수 있다. 문제를 해결하기 위해 i번째 식량창고까지의 최적의 해를 살펴보자 창고 0에서 최적의 해는 1이다. 창고 1에서 최적의 해는 1과 3을 비교했을 때 큰 값인 3이다. 창고 2에서 최적의 해는 1+1인 2와 3을 비교했을 때 큰 값인 3이다. 창고 4에서 최적의 해는 1+1인 2와 3+5인 8을 비교했을 때 큰 값인 8이다. 이런식으로 차례로 DP에 넣어 확인할 수 있다. 왼쪽부터 차례대로 식량창고를 털 때 i 번째를 털지 안털지의 여부는 2가지가 있다. 바로 앞의 창고가 털렸다면 i번째 창고는 털 수 없으며 털리지 않았다면 i번째 창고를 털 수 있다. 두 가지 중에 더 많은 식량을 털 수 있는 경우를 선택하면 된다. 글고 i - 1번째와 i - 2..

다이나믹 프로그래밍(Dynamic Programming) 알고리즘 다이나믹 프로그래밍은 동적 계획법이라고도 불리며, 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. 자료구조에서 동적(Dynamic)이란 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. DP는 이미 계산된 결과는 별도의 메모리 영역에 저장하고 다시 계산하지 않게 하는 방법이며, 탑다운(하향식)과 보텀업(상향식)이라는 두 가지 방식이 있다. 1. 탑다운(하향식) 방법 메모이제이션(Memoization)은 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져오며, 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다. ..

https://programmers.co.kr/learn/courses/30/lessons/12916 코딩테스트 연습 - 문자열 내 p와 y의 개수 대문자와 소문자가 섞여있는 문자열 s가 주어집니다. s에 'p'의 개수와 'y'의 개수를 비교해 같으면 True, 다르면 False를 return 하는 solution를 완성하세요. 'p', 'y' 모두 하나도 없는 경우는 항상 True를 programmers.co.kr 코드 class Solution { boolean solution(String s) { boolean answer = true; int p = 0, y = 0; for(int i = 0; i < s.length(); i++){ if(s.charAt(i) == 'P' || s.charAt(i)..

https://programmers.co.kr/learn/courses/30/lessons/12915 코딩테스트 연습 - 문자열 내 마음대로 정렬하기 문자열로 구성된 리스트 strings와, 정수 n이 주어졌을 때, 각 문자열의 인덱스 n번째 글자를 기준으로 오름차순 정렬하려 합니다. 예를 들어 strings가 ["sun", "bed", "car"]이고 n이 1이면 각 단어의 인덱 programmers.co.kr 정렬을 해야하니까... n번째 인덱스를 맨 앞에 놓고 원래 문자를 붙인걸 저장한 arrayList를 sort 하고 substring으로 1부터로 저장하면됨.... (Collections.sort() 시 사전순 sort되므로 조건을 더이상 구현하지 않아도 됨) 코드 import java.util...

https://programmers.co.kr/learn/courses/30/lessons/12917 코딩테스트 연습 - 문자열 내림차순으로 배치하기 문자열 s에 나타나는 문자를 큰것부터 작은 순으로 정렬해 새로운 문자열을 리턴하는 함수, solution을 완성해주세요. s는 영문 대소문자로만 구성되어 있으며, 대문자는 소문자보다 작은 것으로 programmers.co.kr 코드 import java.util.*; class Solution { public String solution(String s) { String answer = ""; String character[] = s.split(""); Arrays.sort(character, Collections.reverseOrder()); for(in..