SY DevLog

백준 9095번 : 1, 2, 3 더하기 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 이 문제는 다이나믹 프로그래밍을 이용하여 풀 수 있다. dp 1차원 배열을 생성하고, dp[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다. dp[1] 은 1로만 나타낼 수 있으므로 1가지이다. n = 1 일 때, 1 한 가지이므로 dp[1] = 1 이다. n = 2 일 때, 1 + 1 2 두 가지이므로 dp[2] = 2 이다. n = 3 일 때, 1 + 1 + 1 2 + 1 1 + 2 3 총 4가지이므로 dp[3] = 4 이다. n = 4 일 때, 1 + 1 + 1 +1 2 + 1 + 1..

백준 16194번 : 카드 구매하기 2 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 다이나믹 프로그래밍으로 풀었다. dp 1차원 배열을 만들고 dp[N]는 무게 N일 때의 최소 비용을 담는다. dp[N]는 dp[0] + dp[N], dp[1] + dp[N-1] : 무게1 일 때의 최소비용 + 무게 N-1 일 때의 최소비용 dp[2] + dp[N-2] ... dp[N/2] + dp[N/2] 중에서 최소가 되는 비용을 담는다. 소스코드 :

백준 9184번 : 신나는 함수 실행 9184번: 신나는 함수 실행 입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다. www.acmicpc.net 다이나믹 프로그래밍으로 풀었다. 처음에 단순히 삼중 for문을 사용하여 풀었는데 결과가 '틀렸습니다' 가 떴다. import java.io.*; public class Main { static int[][][] dp = new int[51][51][51]; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(..

힙 정렬(Heap Sort) 힙(heap)을 이용하는 정렬 알고리즘 힙(heap) : 부모 노드의 값이 자식 노드의 값보다 큰 완전이진트리 부모 노드의 값이 자식 노드의 값보다 항상 크기 때문에 힙의 루트에는 제일 큰 수가 들어가게 된다. 이를 이용하여 힙의 루트 값을 꺼내어 배열의 오른쪽부터 채워넣으면서(오름차순 기준) 배열을 정렬할 수 있다. 힙으로 만들기 -> 배열의 맨 오른쪽부터 루트값 채워넣기 -> 다시 힙으로 만들기 -> 루트값 채워넣기 ... 이렇게 배열의 정렬이 완료될 때까지 힙 만들기와 루트값 넣기를 반복하여 정렬을 한다. 시간 복잡도 : O(NlogN) 힙으로 만들 때 걸리는 시간 복잡도는 O(NlogN), 힙에서 루트값을 꺼내는데 걸리는 시간 복잡도는 O(1) 이므로 힙 정렬의 시간 ..

LCS(Longest Common Subsequence) : 최장 공통 부분문자열 두 문자열에서 "공통되는 가장 긴 부분문자열"을 찾는 알고리즘 여기서 subsequence는 꼭 연속하지 않아도 되는 부분문자열이다. * 문자열에서 substring 과 subsequence의 차이 * 문자열 A가 있을 때, - substring : 문자열 A의 연속하는 부분 문자열 - subsequence : 문자열 A에서 연속하지 않은 부분 문자열(연속해도 되고, 연속하지 않아도 됨) 즉, 다시 한번 짚고 넘어가면 LCS 알고리즘은 두 개의 문자열에서 subsequence를 찾는 알고리즘이다. LCS 알고리즘은 DP(Dynamic Programming : 다이나믹 프로그래밍)을 이용한다. LCS 알고리즘은 예제를 보면서..

백준 1969번 : DNA 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 구해야 하는 DNA를 S라고 하면, S의 0번째 문자부터 M-1번째 문자를 정해야 한다. N개의 DNA의 k번째 문자들 중 가장 많이 등장한 문자가 S의 k번째 문자가 된다. 예를 들어, TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 와 같이 5개의 DNA가 있다고 하자. TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 5개의..

백준 2841번 : 외계인의 기타 연주 2841번: 외계인의 기타 연주 첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수 www.acmicpc.net 각 줄마다 P개의 프렛이 있다. 줄이 총 6개 이므로 각 줄별로 스택을 만들기 위해 스택 배열을 생성하고 크기를 6개로 하였다. 만약에 특정 줄(n)의 스택(stack[n])에 대해서 - 스택의 top에 있는 프렛이 현재 프렛보다 크다면, top의 프렛이 현재 프렛보다 작을 때까지 pop한다. 현재 프렛의 음을 내기 위해서는 그보다 큰 프렛에서 누르고 있는 손을 모두 떼야하기 때문이다..

백준 1935번 : 후위 표기식2 1935번: 후위 표기식2 첫째 줄에 피연산자의 개수(1 ≤ N ≤ 26) 가 주어진다. 그리고 둘째 줄에는 후위 표기식이 주어진다. (여기서 피연산자는 A~Z의 영대문자이며, A부터 순서대로 N개의 영대문자만이 사용되며, 길이 www.acmicpc.net 해시맵을 사용하여서 각 피연산자 알파벳을 key, 그 알파벳에 해당하는 정수를 value로 넣어주었다. 후위표기식으로 주어진 문자열의 문자를 차례대로 확인한다. 문자가 피연산자이면 해시맵에서 해당하는 정수값을 찾아서 스택에 넣고, 문자가 연산자이면 스택에서 연산할 값 2개를 pop한 후, 연산 결과를 다시 스택에 push 한다. 연산이 다 끝나고 마지막에 스택에 남아있는 값이 최종 연산 결과가 된다. 연산 결과가 실수..

병합 정렬(Merge Sort) 배열을 두 개로 쪼개어서 정렬을 한 뒤, 다시 병합하는 작업을 반복하는 정렬 알고리즘 배열을 중앙을 기준으로 앞(left ~ center)과 뒤(center+1 ~ right)로 나눈다. 이 작업을 배열의 요소가 2개가 될 때까지 반복한다. 나누어진 두 개의 배열을 정렬한 뒤 하나의 배열로 병합한다. 이렇게 배열을 모두 정렬 및 병합하면 종료한다. 시간복잡도 : O(NlogN) 퀵 정렬은 최악의 경우 시작복잡도가 O(N²) 이지만, 병합 정렬은 O(NlogN)로 유지된다. [예제] 배열 arr의 요소가 5 9 3 1 8 6 4 7 2 일 때, 이 배열을 오름차순으로 정렬하기 먼저 배열 arr의 left = 0, right = arr.length -1 로 초기화해준다. le..

백준 17298번 : 오큰수 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net res 배열에는 각 원소의 오큰수가 무엇인지를 넣어준다. 스택을 하나 만들고, 이 스택에는 수열 A의 원소의 인덱스(idx)가 들어간다. - A[idx] 가 아직 오큰수를 만나지 못했다면, idx는 스택에 계속 남아있게 된다. - A[idx] 가 오큰수를 만나면, 스택에서 idx가 pop되고, res[idx] 에는 A[idx]의 오큰수가 들어간다. 백준 문제의 첫번째 예제를 보면, 수열 A는 3 5 2 7 이다. 우선 res의 모든 값을 -1로 초기..