알고리즘/문제 풀이92 [Java] 백준 1149번 RGB거리 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다. www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); int N = s.nextInt(); //집의 수 int dp[][] = new int[N][3]; for(int i=0;i 2020. 4. 28. [Java] 백준 1463번 1로 만들기 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net import java.util.Scanner; public class Main { public static void main(String args[]) { Scanner s= new Scanner(System.in); int N = s.nextInt(); int dp[]= new int[N+1]; dp[0]=0; dp[1]=0; //초기화 //만약 N=2,3일때 1로 만드는 경우의 수는 1이다. /* N을 1로 만드는 경우의 최소 횟수는 = 1) 'N-1을 1로 만드는 최소 횟수 +1' 2) 'N/2를 1로 만.. 2020. 4. 28. [Java] 백준 2156번 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다. 효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고 www.acmicpc.net import java.util.Scanner; public class Main { public static void main(Stri.. 2020. 4. 28. [Java] 동적 계획법 DP(Dynamic Programming) 동적 계획법 Dynamic Programming 동적 계획법은 큰 문제를 작은 문제로 나눠서 최종 문제를 해결하는 알고리즘이다. 작은 문제를 처리할 때 수행되는 답을 저장해 놓고 다음번에 필요할 때 그 값을 불러와서 처리한다. 재활용 개념이라고 이해하면 쉽다. 분할 정복과 비슷한 개념이지만 분할 정복과 동적 계획법의 차이점은 분할 정복에서의 쪼개진 작은 문제들은 중복되지 않지만 동적 계획법에서 쪼개진 문제는 서로 연관성이 있다는 점이다. 동적 계획법의 조건 1. 겹치는 부분문제 - 어떤 문제가 여러 개의 작은 문제로 쪼개질 수 있어야 한다. 2. 최적 부분구조 - 어떤 문제의 최적의 해결책이 그 부분 문제의 최적의 해결책으로부터 해결할 수 있어야 한다. 동적 계획법 구현 방식 Top-down 방식 (재귀.. 2020. 4. 27. [Java] 백준 10845번 & 큐 큐란? 큐(queue)는 스택과 같은 선형 리스트 구조로 선입선출 FIFO(First in First out) 방식이다. 즉, 먼저 들어간 것이 먼저 나오므로 원소는 큐의 맨 뒤에 삽입되고 맨 앞 원소가 먼저 삭제된다. 큐의 구조 큐 연산 add(item): item을 리스트의 끝부분에 추가. poll(): 리스트의 첫 번째 항목을 제거. peek(): 큐에서 가장 위에 있는 항목을 반환. / 제거 X isEmpty(): 큐가 비어 있을 때 true / 아니면 false https://www.acmicpc.net/problem/10845 10845번: 큐 첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다.. 2020. 4. 21. [Java] 백준 10828번 & 스택 스택(Stack)이란? 사전적 의미로 ‘쌓다, 채우다, 무더기’ 라는 뜻으로 선형 리스트의 형태로 한쪽 끝에서만 자료를 넣고 뺄 수 있는 후입선출 LIFO(Last in first out) 구조이다. 즉, 스택에 가장 나중에 추가한 항목이 가장 먼저 제거되는 구조이다. 스택 연산 pop() : 스택에서 원소를 삭제하는 연산. push(Element item) : 스택에 원소를 추가하는 연산. size() : 스택의 크기 반환 peek() : 맨 위의 원소 조회(확인) / pop()과 다르게 삭제X isEmpty() : 스택이 비었는지 확인/ 비었으면 true , 아니면 false 스택 구현 1. 배열을 통한 스택 구현 장점 : 접근 속도가 빠르고 구현하기도 쉽고 메모리가 적다. 단점 : 변경이 용이하지 .. 2020. 4. 21. 이전 1 ··· 11 12 13 14 15 16 다음
