문제 설명https://www.acmicpc.net/problem/1464 ▸ 문제세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 것이다. 세준이는 1부터 N까지 수를 차례대로 생각한다. 그리고, 뒤집을지 안 뒤집을지 선택할 수 있다.예를 들어, S="BCDAF" 이고, 세준이가 길이 1만큼을 뒤집지 않고, 길이 2만큼도 뒤집지 않고 세준이가 길이 3만큼을 뒤집는다고 하면 문자열은 DCBAF가 된다. 다시 여기서 4만큼 뒤집으면 ABCDF가 된다. 그리고, 마지막으로 길이를 5만큼 뒤집지 않으면 주어진 문자열 S를 사전순으로 가장 앞서게 만들 수 있다.문자열 S가 주..
DequeDeque는 Double-Ended Queue의 줄임말로,큐의 양쪽(앞·뒤)에서 엘리먼트의 삽입과 삭제가 모두 가능한 자료구조를 의미한다. 덱은 입력과 출력 방향을 어떻게 사용하느냐에 따라 스택(Stack)과 큐(Queue) 역할 모두 수행할 수 있다.특히, 한쪽으로만 입력이 가능하도록 제한한 덱을 스크롤(scroll) 한쪽으로만 출력이 가능하도록 제한한 덱을 셸프(shelf) 라고 부른다. 📍 자바에서 Deque자바에서 덱은 인터페이스(Deque)로 제공되며, 덱에서 지원하는 여러 연산이 정의되어 있다.Deque 인터페이스를 구현한 대표적인 클래스는 다음과 같다. ArrayDeque LinkedList LinkedBlockingDeque ConcurrentLinkedDeque Deque..
문제 설명https://www.acmicpc.net/problem/2252 ▸ 문제N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. ▸ 입력첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 횟수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이다.학생들의 번호는 1번부터 N번이다...
위상정렬(Topological Sorting) 알고리즘이란?위상정렬 알고리즘이란 정렬 알고리즘의 일종으로, 선후관계가 존재하는 작업들을 순서에 맞게 나열할 때 사용하는 알고리즘이다. 즉, 사이클이 없는 방향 그래프(DAG, Directed Acyclic Graph)에서 모든 노드를 방향성을 위배하지 않도록 정렬한 순서를 의미한다. 예를 들어, 아래와 같이 총 3개의 과목이 있다고 해보자.자료구조알고리즘데이터베이스3개의 과목을 모두 듣기 위해 자료구조 → 알고리즘 → 데이터베이스 순서로 과목을 들어야한다면,자료구조 → 데이터베이스 → 알고리즘과 같은 순서는 잘못된 학습 순서이다. 집입차수와 진출차수진입차수(Indegree) : 특정 노드로 들어오는 간선의 수진출차수(Outdegree) : 특정 노드에서 다..
문제 설명https://www.acmicpc.net/problem/20002 ▸ 문제N × N 크기의 정사각형 모양 과수원이 있고, N × N 개의 사과나무가 1 × 1 크기의 간격으로 모든 칸에 심어져있다.농부 형곤이가 가을을 맞아 사과를 수확하려는데, 땅주인 신영이가 "너는 과수원 내에 사과나무를 K × K 의 크기의 정사각형 모양으로만 수확해 가져갈 수 있어, 이때 K는 1보다 크거나 같고 N보다 작거나 같은 정수라구! 나머지는 내가 먹을께! 하하!" 라고 통보했다.하나의 사과나무를 수확할 때, 사과를 통해 얻을 수 있는 이익과 노동비로 빠져나가는 손해가 동시에 이루어진다.그래서 형곤이는 나무의 위치를 좌표로 하여, 사과를 통해 얻은 이익과 노동비를 더한 총이익을 2차원 배열의 형태로 정리했다.악독..
문제 설명https://www.acmicpc.net/problem/21921 ▸ 문제찬솔이는 블로그를 시작한 지 벌써 N일이 지났다.요즘 바빠서 관리를 못 했다가 방문 기록을 봤더니 벌써 누적 방문 수가 6만을 넘었다.찬솔이는 X일 동안 가장 많이 들어온 방문자 수와 그 기간들을 알고 싶다.찬솔이를 대신해서 X일 동안 가장 많이 들어온 방문자 수와 기간이 몇 개 있는지 구해주자. ▸ 입력첫째 줄에 블로그를 시작하고 지난 일수 N와 X가 공백으로 구분되어 주어진다.둘째 줄에는 블로그 시작 1일차부터 N일차까지 하루 방문자 수가 공백으로 구분되어 주어진다. ▸ 출력첫째 줄에 X일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다.만약 최대 방문자 수가 0명이 ..
