농부공학자

https://programmers.co.kr/learn/courses/30/lessons/12921 코딩테스트 연습 - 소수 찾기 1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요. 소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.) 제한 조건 n은 2이상 programmers.co.kr 옹이 생각보다 어렵네 에스테라토스의 체를 써야 효율성 테스트를 통과한다. n개만큼 빈 boolean 배열을 만들어서 2~n까지 값의 배수를 true로 바꾸고 배열 속 false 개수를 세어주면 된다. class Solution { public int solution(int n) { int answer = 0; boolean number[..

https://programmers.co.kr/learn/courses/30/lessons/12925 코딩테스트 연습 - 문자열을 정수로 바꾸기 문자열 s를 숫자로 변환한 결과를 반환하는 함수, solution을 완성하세요. 제한 조건 s의 길이는 1 이상 5이하입니다. s의 맨앞에는 부호(+, -)가 올 수 있습니다. s는 부호와 숫자로만 이루어져있습니 programmers.co.kr 쉬운거 하나 풀려고 한거긴 한데 너무 쉽네...ㅠㅠ class Solution { public int solution(String s) { return Integer.parseInt(s); } } String -> int 다른 사람 풀이 parseInt 함수 쓴거를 풀어서 쓰면 저거란다. charAt()으로 하나씩 읽어와..

https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 설명이 참 불친절하다. 이분 그래프는 1 - 2 - 3 으로 연결되어 있는 그래프가 있다고 쳤을 때 1과 3이 연결되어있지 않은 그래프를 말한다. 이렇게 인접한 꼭짓점을 빨, 검으로 칠했을 때 빨빨과 검검이 연결되지 않은 그래프이다. 푼 방법은 예를 들어 예시를 보면 3 2 1 3 2 3 일케 되어있음. 그러면 간선이 1 - 3 - 2 로 연결되어있다고 보면 됨. 이렇게 연결이 되어있다고 보..

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)이라고도 한다. ..