백준_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)의 시간 복잡도로 문제를 해결할 수 있다. 코드..
백준_2018 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 투 포인터 투 포인터의 기초적인 설명은 아래 링크 참고. [백준] 2018_수들의 합5 - JAVA 백준_2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타 devhan.tistory.com 이번 문제도 저번 문제(주몽)와 마찬가지로 정렬을 이용하면 더욱 간단하게 풀 수 있다. 그래서 정렬 후 투 포인터를 ..
백준_1940 1940번: 주몽 첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고 www.acmicpc.net 투 포인터 투 포인터에 대한 설명은 아래 링크를 참고 [백준] 2018_수들의 합5 - JAVA 백준_2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타 devhan.tistory.com 이 문제는 두 재료의 번호의 합을 구하고 크기를 비교하는 문제라 받..
백준_2018 2018번: 수들의 합 5 어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한 www.acmicpc.net 투 포인터 투 포인터는 말 그대로 2개의 포인터이다. 이 두 개의 포인터를 이용해서 알고리즘의 시간 복잡도를 최적화할 수 있다. 예제에 나온대로 N의 값이 15라 할때 연속된 자연수의 합은 15(자기 자신), 7+8, 4+5+6, 1+2+3+4+5 이렇게 4개이다. 연속된 자연수의 합을 구하는 문제이므로 시작 인덱스와 종료 인덱스를 지정하여 연속된 수의 범위를 표현한다. 투 포인터의 이동 원칙 sum > N : sum -= s..
나머지 합 이 문제도 구간 합 배열을 이용해야 한다. 구간 합 배열의 설명은 아래 링크로 이동하면 볼 수 있다. [백준] 11659_구간 합 구하기4 - JAVA 구간 합 구간 합은 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 알고리즘이다. 구간 합을 이용하려면 합 배열을 구해야 한다. 합 배열 만들기 S[i] = S[i-1] + A[i] 인덱스 0 1 2 3 A 10 10 10 1 devhan.tistory.com 배열의 연속 구간의 합을 구하려면 (A+B) % C로 구할 수 있다. 예제를 참고해서 풀어보자. 예제의 배열 {1, 2, 3, 1, 2} 중에 2와 3의 값을 대입해 보자. (2+3) % 3은 2이다. 또, 모듈러 연산은 분배법칙이 가능하다. 그러므로 ((2 % 3) + (3 % ..
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..
