골드 3 https://www.acmicpc.net/problem/17299 17299번: 오등큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 문제 크기가 N인 수열 A = A1, A2, ..., AN이 있다. 수열의 각 원소 Ai에 대해서 오등큰수 NGF(i)를 구하려고 한다. Ai가 수열 A에서 등장한 횟수를 F(Ai)라고 했을 때, Ai의 오등큰수는 오른쪽에 있으면서 수열 A에서 등장한 횟수가 F(Ai)보다 큰 수 중에서 가장 왼쪽에 있는 수를 의미한다. 그러한 수가 없는 경우에 오등큰수는 -1이다. 예를 들어, A = [1, 1, 2..
https://www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 입력받은 문자열을 돌면서 '('가 나오면 스택에 쌓고, ')'이 나오면 스택에서 하나 꺼낸 뒤 남은 스택의 크기를 더해가면 해결할 수 있다. 단, ')'가 연속으로 나올 경우 남은 스택의 크기가 아닌 1만 더해줘야 한다. ')'가 연속으로 나왔다는 것은 다 잘린 막대기가 있다는 것이고 그것은 1개이기 때문이다. 덜 잘려 남은 막대가 있다고 하더라도 다음 레이저에서 그 개수가 더해지기 때문에 ')'가 연속으로..
https://www.acmicpc.net/problem/17413 17413번: 단어 뒤집기 2 문자열 S가 주어졌을 때, 이 문자열에서 단어만 뒤집으려고 한다. 먼저, 문자열 S는 아래와과 같은 규칙을 지킨다. 알파벳 소문자('a'-'z'), 숫자('0'-'9'), 공백(' '), 특수 문자('')로만 이루어져 www.acmicpc.net 입력받은 문자열을 하나씩 탐색해 가면서 태그 안에 있다면 문자 그대로 출력하고, 태그 밖이라면 스택에 쌓은 후 꺼내서 출력해 주어 해결할 수 있다. 태그 안밖을 구분하기 위해 boolean형 변수를 사용할 수 있다. import java.util.*; import java.io.*; // 단어 뒤집기 2 https://www.acmicpc.net/problem/17..
https://school.programmers.co.kr/learn/courses/30/lessons/12940 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 최대공약수는 유클리드 호제법으로 구할 수 있다. 유클리드 호제법 https://ewok.tistory.com/365#%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%20%EA%B3%84%EC%82%B0(%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C%20%ED%98%B8%EC%A0%9C%EB%B2%95)%20%EC%98%88%EC%A0%9C-1 ..
문제 1 더보기 import java.util.*; public class Main { // 앞서 계산된 결과를 저장하기 위한 DP 테이블 초기화 public static int[] d = new int[100]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); // 정수 N을 입력받기 int n = sc.nextInt(); // 모든 식량 정보 입력받기 int[] arr = new int[n]; for (int i = 0; i < n; i++) { arr[i] = sc.nextInt(); } // 다이나믹 프로그래밍(Dynamic Programming) 진행(보텀업) d[0] = arr[0]; d[1] = Mat..
다이나믹 프로그래밍 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 한다. 다이나믹 프로그래밍의 구현은 일반적으로 두 가지 방식(Top Down, Bottom Up)으로 구성된다. 동적 계획법이라고 부른다. 다이나믹 프로그래밍의 조건 1. 최적 부분 구조 (Optimal Substructure) 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있다. 2. 중복되는 부분 문제 (Overlapping Subproblem) 동일한 작은 문제를 반복적으로 해결해야 한다. 피보나치 수열 피보나치 수열은 아래와 같은 형태의 수열이며, 다이나믹 프로그래밍으로 효과적으로 계..
