문제https://www.acmicpc.net/problem/1874    풀이스택에는 자연수를 1부터 오름차순으로 밖에 넣지 못한다. 1부터 차례대러 스택에 push(삽입)하고 pop(빼고)하면서 주어진 수열을 만들수 있는지 + (push), - (pop)으로 표현하면 됩니다.  주어진 수열을 해당 방식으로 만들지 못하면 no를 출력 하면 됩니다. import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Stack;public class 스택으로수열만들기_1874 { public static void..

스택스택은 삽입과 삭제 연산이 후입선출 last in first out 로 이뤄진 자료구조 입니다. 후입선출은 삽입과 삭제가 한쪽에서만 이뤄진다는 특징이 있습니다.  그림을 보면 새로운 값이 스택에 들어가게 되면 top이 새 값을 가르키게 됩니다. 스택에서 값을 빼낼때 pop은 top이 가르키는 값을 스택에서 빼게 됩니다. 아래는 스택용어 입니다. 스택 용어- 위치 top : 삽입과 삭제가 일어나는 위치를 뜻합니다. - 연산push : top 위치에 새로운 데이터를 삽입 하는 연산입니다.peek : top 위치에 있는 데이터를 단순 확인만 하는 연산입니다.pop : top 위치에 있는 데이터를 삭제 하고 삭제한 데이터를 확인하는 연산입니다.  스택은 깊이 우선 탐색(DFS : Depth first sea..

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한채로 이동하며 문제를 해결합니다.투포인터 알고리즘과 매우비슷하고 원리도 간단합니다. 투포인터와 마찬가지로 슬라이딩 윈도우 알고리즘도 O( n )의 시간복잡도 알고리즘입니다. 아래는 슬라이딩 윈도우 문제와 풀이입니다.  문제https://www.acmicpc.net/problem/12891     풀이임의로 만든 DNA가 GATA이고 비밀번호로 사용될 문자열의 길이가 2, 포함되어야할 ACGT 최소갯수는 1001 일경우 아래와 같습니다. 첫번째 윈도우는 GA이기 때문에 현재상태 배열에 A와 G에 해당하는 인덱스에 숫자 1을 넣어줍니다.그리고 현재상태 배열과 비밀번호 조건 배열을 비교합니다. 비밀번호 조건은 A와 T가 최소한 한개는 ..

문제https://www.acmicpc.net/problem/2018    풀이우선 문제에 주어진 시간 제한은 2초입니다. 이런 상황에서 O( nlogn ) 의 시간 복잡도 알고리즘을 사용하면 제한시간을 초과하므로 O( n )의 시간복잡도 알고리즘을 사용해야 합니다. 이런 경우 자주 사용하는 방법이 투포인터 입니다.※ O ( n ) : 주어진 데이터 크기 n 만큼 연산횟수가 필요한 시간복잡도 연속된 자연수의 합을 구하는 것이 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수를 표현 하겠습니다.     import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.Ou..

구간합은 합배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘 입니다.  구간합을 사용하기 위해서 합배열을 구해야 하는데 합배열을 구하는 방식은 아래와 같습니다. 합 배열 S를 만드는 공식S[ i ] = S[ i-1 ] + A[ i ]     구간 합을 구하는 공식i 에서 j 까지의 구간합 = S[ j ] - S[ i-1 ]         // 위의 그림의 경우 2(i)에서 5(j)까지의 구간합 합배열을 미리 구해놨다면 위의 공식을 사용하여 구간합을 구할수 있는데 위의 그림 경우 S[5] - S[1] 을 하면 A[2] ~ A[5]까지의 합을 구할수가 있습니다.   출처 https://www.inflearn.com/course/lecture?courseSlug=%EB%91%90%..

문제https://www.acmicpc.net/problem/1546   풀이최고점 M 으로 나눈후 100을 곱한값의 평균값을 구하는 방식으로 다음과 같이 나타낼수 있습니다. - 변환 점수의 평균을 구하는 식 (점수가 a,b,c인 경우)(a / M * 100 + b / M * 100 + c / M * 100) / 3 위의 식은 다시 아래와 같이 최소화 할수 있습니다.( a + b + c ) * 100 / M / 3  그냥 연산을 편리하게 하기 위해 최소화 한거지만 처음 식대로 알고리즘을 짜도 문제는 없습니다.  import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.InputStreamReader;import java.io.O..