Hello, Freakin world!

www.acmicpc.net/problem/11723 11723번: 집합 첫째 줄에 수행해야 하는 연산의 수 M (1 ≤ M ≤ 3,000,000)이 주어진다. 둘째 줄부터 M개의 줄에 수행해야 하는 연산이 한 줄에 하나씩 주어진다. www.acmicpc.net 집합 요소를 삭제하는 연산의 구현이 조금 까다로운 면이 있다. 이를 구현하기 위해 모든 집합의 요소를 포함하는 111.. 11와 같이 1로 완전히 채워진 비트를 만들고, 지우려는 요소 위치의 원소를 XOR 연산을 통해 0으로 만들어 준다. 그리고 집합 S와 and 연산을 해주면 해당 요소가 지워진 집합을 얻을 수 있다. import java.io.*; import java.util.ArrayList; import java.util.List; im..

www.acmicpc.net/problem/2357 2357번: 최솟값과 최댓값 N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100 www.acmicpc.net 전형적인 구간 트리 문제. 구간 트리를 초기화하는 과정에서 중복되는 과정들이 많아 BiFunction을 이용해 함수를 전달받게 만들어 봤는데, 역시 느리다. 가끔씩 문제들을 풀어오면서 느끼고 있었는데, 자바 Stream, 람다의 경우 연산량이 많이지는 경우 for문에 비해 엄청나게 느리다. 속도가 몇 초씩 차이가 날때가 있기 때문에, PS에서는 조심해서 사용할 것. impo..

import java.io.*; import java.util.*; /* 나이트의 이동 https://www.acmicpc.net/problem/7562 */ public class Main { static int t,n; public static void main(String[] args) throws IOException { //InputReader reader = new InputReader("testcase.txt"); InputReader reader = new InputReader(); t = reader.readInt(); StringBuilder sb = new StringBuilder(); for (int tc = 0; tc < t; tc++) { n = reader.readInt(); ..

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 백트래킹의 개념을 알고 있다면 풀이 방법을 쉽게 떠올릴 수 있습니다. 위 그림을 보시면 재귀적인 구조를 쉽게 눈치챌 수 있습니다. 재귀 구조를 통해 sum을 구한 다음, 리턴하면서 대소를 비교하며 최대/ 최소를 각각 구해내면 됩니다. 그리고 각 연산자들의 숫자를 백트래킹을 이용해 계산해주면서 연산자 개수 > 0 일 때만 재귀호출 하도록 합니다. 말로 ..

www.acmicpc.net/problem/5397 5397번: 키로거 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스는 한줄로 이루어져 있고, 강산이가 입력한 순서대로 길이가 L인 문자열이 주어진다. (1 ≤ L의 길이 ≤ 1,000,000) 강산이가 백스페이 www.acmicpc.net 핵심은 같은 쉬프트 연산을 어떻게 구현할 것인가에 달려 있습니다. 단순 리스트로 구현해서 인덱스를 추적해가면서 문자열을 조작해 구현할 수도 있겠으나 덱 구조를 이용하면 쉽게 구현이 가능합니다. 풀이 임의의 문자열 S가 있다고 합시다. 문자열을 추가할 때, 커서가 추가된 문자의 뒤에 생성된다고 가정합니다. 초기의 문자열 S는 다른 연산없이 문자를 추가만 한 상태입니다. 각 과정은 S에 대해 차례로 왼쪽, ..

www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모� www.acmicpc.net 문제 풀이 검사 대상 문자열 : S, 폭발 문자열 : C 1. S의 문자열을 차례대로 순회하면서 Stack에 추가한다. 2. 만약 추가한 문자가 C의 마지막 문자열과 같다면 C의 길이만큼 스택을 역탐색해 폭발 문자열인지 검사한다. - 폭발 문자열인 경우, 폭발 문자열의 길이만큼 pop한다. 다시 1번으로 - 아닌 경우 pass. 다시 1번으로 라이브러리에서 주어지는 Stack에는 배열처럼 순회하..

www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 �� www.acmicpc.net 풀이 방법 문자열을 정렬한 뒤, 앞의 문자가 뒤의 문자에 포함되는지 살펴가면서 전체 순회하면 답을 얻어낼 수 있는 문제였습니다.(저는 결국 풀이를 보고 나서야 알았지만..) import java.io.*; import java.util.ArrayList; import java.util.Comparator; import java.util.List; /* 전화번호 목록 https://w..

www.acmicpc.net/problem/16521652번: 누울 자리를 찾아라첫째 줄에 방의 크기 N이 주어진다. N은 1이상 100이하의 정수이다. 그 다음 N줄에 걸쳐 N개의 문자가 들어오는데 '.'은 아무것도 없는 곳을 의미하고, 'X'는 짐이 있는 곳을 의미한다.www.acmicpc.net 정규표현식 반복자를 활용할 수 있다면 간단하게 풀 수 있는 문제입니다. 그리고 문제 이해시 주의할 점은 단순하게 한 줄에 2개 이상의 자리가 있는지 판별하는게 아니라는 사실입니다.예를 들어 한 줄이 ......X.. 일 경우 자리는 2개가 됩니다. 정규표현식 반복자에 대해 다른 분이 잘 정리한 글을 첨부합니다. 정규표현식 반복찾기정규표현식 — 반복찾기정규표현식의 가장 핵심 기능이라고 생각되는 부분이다.med..

www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 먼저 다익스트라 알고리즘으로 최단 거리를 구하면서 최단거리를 갱신할 때 노드의 부모들을 저장해줍니다. 그리고 최단 거리 노드들의 부모들을 순회하면서 간선을 없애고 다시 최단 거리를 구해 반환합니다. 구현 상의 팁 부모 정점들을 저장할 때 최단 거리가 갱신될 경우, 이전의 부모 정점 리스트를 버리고 새로운 리스트를 할당해 저장해야 합니다. 그리고 저장해놓은 최단 거리와 큐에 저장..

www.acmicpc.net/problem/2493 2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 �� www.acmicpc.net 왜 스택구조인가? 먼저 아래의 상황을 관찰해보자. 먼저 i번째 건물에서 신호 보내는 상황을 살펴보면, i 건물에서 보낸 신호가 i-2에 닿고 있다. 다음 i+1에서 신호를 보낼 때는 i 건물에 신호가 닿는다. 여기서 i-1 건물에 살짝 주목해보자. 이 건물의 정보는 저장할 필요가 없다. i+1 위치에서 보면 i 건물에 가려 보이지 않기 때문이다. 그렇기 때문에 i번째 단계에서 i 건물보다 낮은 건물의 정..