블로그 언저리인 무언가

문제 : 10165 버스노선 10165번: 버스 노선 첫 번째 줄에는 버스 정류소의 개수 N(3 ≤ N ≤ 1,000,000,000)이 주어지고 두 번째 줄에는 버스 노선의 수 M(2 ≤ M ≤ 500,000)이 주어진다. 각 버스 노선은 1부터 M까지의 번호로 구분된다. 그 다음 M개 www.acmicpc.net 원형으로 이루어진 버스 노선들 중에서 다른 노선에 포함되어있는 노선들을 제거한 후 출력하는 문제이다. 일단 원형노선을 알아보기 쉽게 일자로 펴기 위해서 0을 지나는 노선 들 중 가장 출발점이 앞선 것 기준으로 다시 정렬을 해주고 출발점 기준으로 찾으면서 도착점이 현재 최대 도착점보다 짧은 노선들을 제거 한 후 노선들을 정렬해 출력해주면 된다. Code #include #define ll lon..

1. VSCode 다운로드하기 Visual Studio Code - Code Editing. Redefined Visual Studio Code is a code editor redefined and optimized for building and debugging modern web and cloud applications. Visual Studio Code is free and available on your favorite platform - Linux, macOS, and Windows. code.visualstudio.com 2. 자신의 세팅 불러오기 3. C++ 환경 구축하기 3-1. MingW 다운로드하기 MinGW - Minimalist GNU for Windows Download MinG..

문제 : 2873 롤러코스터 2873번: 롤러코스터 첫째 줄에 가장 가장 큰 기쁨을 주는 롤러코스터는 가장 왼쪽 위 칸부터 가장 오른쪽 아래 칸으로 어떻게 움직이면 되는지를 출력한다. 위는 U, 오른쪽은 R, 왼쪽은 L, 아래는 D로 출력한다. 정답 www.acmicpc.net 롤러코스터가 갈 수 있는 칸이 주어지고 이를 지나면서 가장 최대의 행복값을 가지도록 경로를 구현하는 문제이다. 기본적으로 홀*홀, 짝*홀, 홀*짝 경우에서는 ㄹ자로 순회하면 모든 칸을 지날 수 있으므로 행이나 열이 홀수인 방향을 찾아 모든 칸을 지나도록 경로를 만들어 출력하면 된다. 결국 이문제의 문제는 짝*짝 상황에서 어떻게 최댓값을 찾아내냐는 것인데 어찌어찌 머리를 굴리다 보면 [짝, 홀] 칸이나 [홀, 짝] 칸 하나만 지나지..

문제 : 20041 Escaping 20041번: Escaping 첫 번째 줄에는 경찰의 수 N이 주어진다. 단, 1 ≤ N ≤ 500,000이다. 그 다음 N 개의 줄에는 각 경찰의 초기 위치의 좌표 (xi, yi)가 공백을 사이에 두고 주어진다. 다음 줄에는 도둑의 초기 위치의 좌 www.acmicpc.net 도둑의 좌표가 주어지고 경찰의 좌표가 주어졌을 때 도둑이 영원히 도망칠 수 있는지 확인하는 문제이다. 기본적인 아이디어로는 도둑이 도망치는게 가능하다고 할때 굳이 지그재그로 갈 필요없이 위, 아래, 오른쪽, 왼쪽 중에서 한방향을 정해 쭉 달리면 된다는것을 알수 있고 이를 이용해 위, 아래, 오른쪽, 왼쪽 모두에 경찰이 존재할때만 도망치는것이 불가능함을 알수있다. 여기에서 현재 경찰이 있는 점이 ..

문제 : 3321 가장 큰 직사각형 3321번: 가장 큰 직사각형 열의 순서를 적절히 바꿔, 2열, 4열, 5열이 서로 붙어있게 놓는다면, 크기가 21인 직사각형을 얻을 수 있다. (2행~8행 * 2,4,5열) www.acmicpc.net 기본적으로 1로 채워진 가장 큰 정사각형을 찾는 문제이지만 열의 순서를 바꿀 수 있으므로 결국 각 행에 대해서 열의 높이를 정렬하여 누적합을 이용하면 행의 길이를 1씩 늘려가면서 최대 넓이를 구할 수 있다. 이를 구현하게 되면 총 행의 개수 N번, 각 행을 정렬하는데 걸리는 시간이 퀵 정렬 사용 시 MlogM이므로 시간 복잡도가 O(NMlogM)이 되는데 시간제한이 0.6초이기 때문에 이를 O(NM)으로 줄여야 한다. 나 같은 경우에는 deque를 사용해 정렬 시간을 ..

문제 : 2573 빙산 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net 빙산의 위치와 높이가 주어질 때, 2개 이상으로 나누어지는 시간을 구해 출력하는 문제이다. 매해 빙산이 녹는 높이를 카운트해서 줄여주면서 BFS를 통해 빙산의 개수를 구해 0이나 2 이상이 되는 순간을 출력하면 된다. Code #include #define ll long long using namespace std; typedef pair pll; ll N, M, ans, arr[305][305], cnt[305][305], visi..

La Piscine 일정은 어떻게 진행되나요? 라 피신은 총 4주에 걸쳐서 진행되며 원래는 전일제로 진행해 모든 날에 출석했지만 저 같은 경우에는 코로나로 인해서 격일제(1그룹 월-수-토/2그룹 화-목-일)로 진행했습니다. 기본적인 일정은 아래와 같습니다. 월~목요일 : 개인과제 금요일 : 시험 토~일요일 : 팀 프로젝트 시험과 팀 프로젝트 같은 경우는 할 수 있는 기한이 정해져 있고 개인과제는 자율적으로 공부해서 해결해나가면 됩니다. 마지막 주 금요일에는 final exam을 치게 되고 이를 마지막으로 La Piscine 과정이 종료됩니다. 주로 어떤것들을 배우나요? 해결해야 하는 과제가 주어지면 그에 맞는 것을 공부하고 해결하시면 됩니다. 기본적으로는 리눅스, C언어에 대해 전반적으로 배우며 중요하게..