백준_17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net 스택 참고 포스팅 [백준] 1874_스택 수열 - JAVA 백준_1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc. devhan.tistory.com 코드 import java.io..
백준_1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 스택(Stack) 삽입과 삭제 연산이 후입선출(LIFO : Last-in First-out)으로 이루어진 자료구조이다. 후입선출은 산입과 삭제가 한 쪽에서만 이루어진다. 스택 용어 top : 삽입과 삭제가 일어나는 위치 push : top 위치에 새로운 데이터를 삽입하는 연산 pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산 peek : top 위치..
백준_11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 덱(deque) 위 문제는 슬라이딩 윈도우와 정렬을 사용하면 될 것 같지만 정렬은 nlog(n)의 시간 복잡도를 가지고, N과 L의 범위가 5,000,000인 이 문제에서는 정렬을 사용할 수 없다. O(n)의 시간 복잡도로 해결해야 한다. 정렬 대신 슬라이딩 윈도우와 덱(deque)이란 자료구조를 사용하면 이 문제를 풀 수 있다. 덱은 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조이다. 왼쪽에서는 addFi..
백준_12891 12891번: DNA 비밀번호 평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA” www.acmicpc.net 슬라이딩 윈도우 슬라이딩 윈도우 알고리즘은 두 개의 포인터로 범위를 지정한 다음, 그 범위를 유지한 채로 이동하며 문제를 해결한다. 예를들면, 슬라이딩 윈도우의 배열이 3인 슬라이딩 윈도우의 첫 번째 for문 범위는 아래와 같다. 그 다음 반복일 때는 슬라이딩 윈도우가 옆으로 이동하여 아래 그림과 같이 범위가 지정된다. 슬라이딩 윈도우의 범위만큼만 탐색을 진행하기 때문에 O(n)의 시간 복잡도로 문제를 해결할 수 있다. 코드..
2차원 배열 구간 합 일단 1차원 배열의 구간 합부터 이해해야한다. [백준] 11659_구간 합 구하기4 - JAVA 구간 합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다. 구간 합을 이용하려면 합 배열을 구해야 한다. 합 배열 만들기 S[i] = S[i-1] + A[i] 인덱스 0 1 2 3 A 10 10 10 1 devhan.tistory.com 2차원 배열의 구간 합은 어려운 거 같으면서도 이해하면 쉽다. 일단 문제의 예시로 설명해보자. 위 원본 배열을 A라 하자. 원본 배열의 크기가 +1 된 이유는 구간 합 배열의 크기와 똑같이 만들어주기 위함이다. 이 A의 합 배열(S)을 채워보자. for문의 시작 인덱스는 0이 아닌 1이다. index 계산 시 0부터 시작이면..
구간 합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다. 구간 합을 이용하려면 합 배열을 구해야 한다. 합 배열 만들기 S[i] = S[i-1] + A[i] 인덱스 0 1 2 3 A 10 10 10 10 S 10 20 30 40 이런 식으로 합 배열을 만든다. S 배열에 값을 계산해서 저장하는 for문의 변수 초기화는 1부터 시작해야한다. 구간 합 공식 S[j] - S[i-1] 1부터 3까지의 구간 합을 구한다치면 S[3] - S[1-1]이 된다. 40-10 = 30이 된다. A배열의 값이 모두 10이라 뭔가 헷갈릴 수 있으니 다른 배열로도 계산해보자. 인덱스 0 1 2 3 A 10 16 3 49 S 10 26 29 78 위 배열에서도 1부터 3까지의 합을 구해보자. 78..
