https://www.acmicpc.net/problem/16937 16937번: 두 스티커 첫째 줄에 모눈종이의 크기 H, W, 둘째 줄에 스티커의 수 N이 주어진다. 다음 N개의 줄에는 스티커의 크기 Ri, Ci가 주어진다. www.acmicpc.net 이 문제는 조합을 통한 완전 탐색을 이용하면 해결할 수 있다. 문제에서 두 개의 스티커만 이용하라고 되어 있어, 2 개의 스티커를 고르면 가로나 세로로 붙인 결과의 최대 값을 출력하면 된다. 입력된 스티커의 가로, 세로 값과 90도 회전할 수 있으면 회전한 가로, 세로 값을 배열에 삽입한다. 회전 가능한 스티커는 가로, 세로 값이 같지 않은 스티커만 가능하다. 또한 뒤집은 스티커와 뒤집지 않은 스티커를 고르지 않게 해야한다. 즉, 동일한 스티커를 고르..
Baekjoon Review
https://www.acmicpc.net/problem/16508 16508번: 전공책 곧 졸업을 앞둔 민호는 대학교 생활 동안 구매만 해놓고 한 번도 펴보지 않은 전공책에 먼지가 쌓여 있는 것을 보고는, 이 책들을 어떻게 처리해야 할지 고민 중이다. 열심히 고민한 끝에 민호는 www.acmicpc.net 이 문제는 조합을 이용한 완전 탐색을 이용해 해결해야한다. 선택한 책들의 알파벳 개수와 T의 알파벳 개수를 비교하여, 선택한 책들로 T를 만들 수 있다면 result를 갱신해 준다. 이때, result는 더 작은 값만 넣어준다. 선택한 책들로 T를 만들 수 있는지 확인하는 함수는 check 함수이며, alpha 배열에 들어있는 (입력한 문자열) 문자와 책들을 통해 얻은 문자(target) 배열을 비교..
https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 이 문제는 투 포인터를 사용해서 회문인지 유사 회문인지 검사하면 해결할 수 있다. 문제에서 주어지는 회문 검사는 algorithm에 있는 reverse 함수를 통해서도 검사할 수 있다. reverse 함수에 의해 구할 수 있는 결과는 유사 회문은 검사할 수 없다. 따라서 회문인지 유사회문인지 그냥 문자열인지 한번에 판단하기 위해서 모든 검사를 투 포인터를 사용하는 것이 좋다. 회문인지는 0번째 인덱스(left)와 input.s..
https://www.acmicpc.net/problem/22862 22862번: 가장 긴 짝수 연속한 부분 수열 (large) 수열 $S$에서 최대 $K$번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 출력한다. www.acmicpc.net 이 문제는 투 포인터를 사용해서 해결할 수 있다. 문제에서 주어지는 최대 K 번 삭제한 짝수로만 이루어진 연속한 부분 수열이라는 뜻은 홀수가 K번 이하 존재하는 연속한 부분 수열을 찾으라는 의미이다. 이러한 생각을 바탕으로 예제를 접근하면 아래와 같은 결과가 나온다. 1 2 3 4 5 6 7 8 이 주어지면 2 4 6 이 정답이 될 수 있다. 초기 start 포인터가 가리키는 0번째 인덱스가 홀수 인 경우 1 아닌경우 0으로 c..
https://www.acmicpc.net/problem/21921 21921번: 블로그 첫째 줄에 $X$일 동안 가장 많이 들어온 방문자 수를 출력한다. 만약 최대 방문자 수가 0명이라면 SAD를 출력한다. 만약 최대 방문자 수가 0명이 아닌 경우 둘째 줄에 기간이 몇 개 있는지 출력한다 www.acmicpc.net 이 문제는 투 포인터를 사용해서 해결할 수 있다. 이 문제의 핵심은 구간 합을 반복문이 아닌 누적 합을 사용해서 해결해야한다는 것이 핵심이다. 구간 합을 반복문을 사용하면 O(N^2)이 되어 시간 초과가 발생한다. 따라서 값을 계속 해서 누적하고 합이 X보다 커지면 end 지점의 값을 빼고 end 포인터를 이동시킨다. 이러면 구간의 합을 계속해서 누적할 수 있다. #include using..
https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어 홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열 www.acmicpc.net 이 문제는 투 포인터를 통해 해결할 수 있다. K의 값에 따라 연속 수열에 들어올 수 있는 같은 값의 개수가 달라진다. 예시에 있는 3 2 5 5 6 4 4 5 7은 K가 2이므로 수열에 같은 값이 2개 이하 존재해야한다. 즉, 3 2 5 5 6 4 4와 2 5 5 6 4 4, 5 5 6 4 4, 5 6 4 4 5 7, 6 4 4 5 7, ... 이 가능하다. 이중 가장 긴 수열의 길이는 7..
https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 활용해야한다. 노드간의 이동 방법과 가중치를 입력 받기 때문에 일반적인 다익스트라 알고리즘을 사용하면 된다. 출력 시 INF인 경우 INF를 출력하도록 출력만 신경쓰면 된다. #include #include #include using namespace std; #define INF 100000000 int V, E; int di..
https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 이 문제는 다익스트라 알고리즘을 이용해 해결할 수 있다. 최단 거리 K에 해당하는 노드를 구하면 된다. #include #include #include #define INF 100000000 using namespace std; vector nodes[300001]; int dist[300001]; int N, M, K, X..
