나그네

Round #859 (Div. 4) 대회 https://codeforces.com/contest/1807 Dashboard - Codeforces Round 859 (Div. 4) - Codeforces codeforces.com 푼 문제 A. Plus or Minus a, b, c를 입력받아 a+b=c가 성립하는지 여부를 출력하는 간단한 문제다. #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int a, b, c; cin >> a >> b >> c; if (a + b == c) cout t; while (t--) { int n, a = 0,..

1937번: 욕심쟁이 판다 문제 https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 풀이 2차원 배열에서 어느 한 점에서 출발해 상하좌우로 점차 증가하는 방향으로만 이동할 수 있을 때 가장 많이 이동할 수 있는 길이를 구하는 문제다. 따라서 dfs로 배열의 모든 점에 대해 가장 긴 이동 거리를 구하고 최댓값을 구했는데 시간초과를 받았다. 시간초과를 해결하기 위해 메모이제이션을 하는 방법밖에 없다고 생각했다. 따라서 visited 배열을 ..

3745번: 오름세 문제 https://www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 풀이 수열이 주어졌을 때 점차 증가하는 부분 수열을 오름세라 하고 가장 긴 오름세를 찾는 문제다. 즉, 가장 긴 증가하는 부분 수열을 구하는 문제다. 범위가 10^5이므로 시간복잡도가 O(NlogN)인 알고리즘을 사용해 풀어야 한다. O(NlogN)으로 푸는 법은 아래 링크에 설명되어 있다. [12015번 가장 긴 증가하는 부분 수열 2 문제] | [12015번 가장 긴..

1818번: 책정리 문제 https://www.acmicpc.net/problem/1818 1818번: 책정리 동혁이는 캠프가 끝나고 집에 가서 책꽂이 정리를 하고 있었다. 책들은 한 줄로 길게 꽂히 있었다. 동혁이의 책은 1번부터 N번까지 숫자로 표현되고 현재 뒤죽박죽 되어있는 순서를 왼쪽부터 www.acmicpc.net 풀이 책 번호를 오름차순으로 정렬하고자 하므로 가장 긴 이미 정렬되어 있는 책들은 놔두고 나머지 책들만 재배치를 하면 된다. 따라서 가장 긴 증가하는 부분 수열(LIS) 알고리즘을 사용해 LIS의 길이를 구하고, 책 수에서 LIS의 길이를 뺀 개수를 출력하면 된다. N의 범위는 2 × 10^5이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 시간초과가 나므로 시간복잡도가 O(NlogN..

3066번: 브리징 시그널 문제 https://www.acmicpc.net/problem/3066 3066번: 브리징 시그널 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 첫 번째 줄에 포트의 개수 N(1 ≤ N ≤ 40000)이 주어지고, 두 번째 줄부터는 왼쪽 블록의 포트와 연결되어야 하는 오른쪽 www.acmicpc.net 풀이 최대한 많은 시그널을 교차하지 않도록 연결해야 하므로 연결되는 포트의 번호가 증가하는 순서대로 많이 연결할 수 있도록 해야 한다. 따라서 이 문제는 가장 긴 증가하는 부분 수열의 크기를 구하는 문제다. N의 범위는 4 × 10^4이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 시간초과가 나므로 시간복잡도가 O(NlogN)인 알고리즘으로 풀어야 ..

12014번: 주식 문제 https://www.acmicpc.net/problem/12014 12014번: 주식 입력 파일에는 여러 테스트 케이스가 포함될 수 있다. 파일의 첫째 줄에 케이스의 개수 T(2 ≤ T ≤ 100)가 주어지고, 이후 차례로 T 개 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에 두 www.acmicpc.net 풀이 주가가 올랐을 때만 주식을 사고, 그리고 구매는 하루에 1번만 가능하고 최대 K번만 살 수 있다. 따라서 가장 긴 증가하는 부분 수열의 길이가 K 이상이면 조건을 만족하며 주식을 구매할 수 있다. N의 범위는 10^4이지만 테스트 케이스의 수가 10^2 이므로 시간복잡도가 O(N^2) 알고리즘으로 풀면 최대 시간복잡도가 10^10이 되므로 시간복잡도가 O(Nl..

9370번: 미확인 도착지 문제 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net 풀이 먼저 가장 큰 접근법은 G-H는 반드시 지나야 하므로 S -> G -> H -> ? 또는 S -> H -> G -> ? 이 최단 경로여야 한다. 따라서 S -> G, S -> H, G -> H, G -> ?, H -> ? 의 최단 거리를 구해야 한다. 즉, 간선 거리는 항상 양수고 몇몇 정점간 거리를 구해야 하므로 다익스트라 알고리즘을 사용했다. 따라서 ..

27868번: On My Way Dorm 문제 https://www.acmicpc.net/problem/27868 27868번: On My Way Dorm 첫 번째 줄에 입력 형식과 같은 방법으로 사무실이 있는 층에서 아인이의 기숙사가 있는 층으로 퇴근하기 위한 커맨드를 출력한다. 가능한 커맨드가 여러 가지일 경우 그중 아무것이나 출력한 www.acmicpc.net 풀이 엘리베이터를 사용한 출근 경로가 주어지고 퇴근 경로를 구하는 문제다. 지문만 보면 어려워 보이지만 출근 경로를 뒤집어서 출력하면 되는 문제다. 지문 난이도와 예제 때문에 헷갈리기 쉽다. 코드 #include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(NU..

1365번: 꼬인 전깃줄 문제 https://www.acmicpc.net/problem/1365 1365번: 꼬인 전깃줄 첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 www.acmicpc.net 풀이 가장 긴 증가하는 부분 수열(LIS)을 구하는 문제다. 전깃줄 문제와 같아 보이나 정렬할 필요가 없는 문제다. 왼쪽 전봇대의 위에서부터 차례대로 어디에 연결되어 있는지 주어지므로 순서대로 LIS를 구하면 된다. N의 범위가 10^5 이므로 시간복잡도가 O(NlogN)인 알고리즘으로 풀어야 시간초과가 안 난다. O(NlogN)으로 LIS를 구하는 방..

11003번: 최솟값 찾기 문제 https://www.acmicpc.net/problem/11003 11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net 풀이 차례대로 수를 입력받아 최소 힙(우선순위 큐)에 추가한다. 가장 작은 숫자가 현재보다 L만큼 이전 범위 안의 수가 아닌 경우, 범위를 벗어나므로 pop 한다. 최솟값이 범위를 만족할 때 top 원소를 출력해 준다. 코드를 줄이고 줄여서 C++ 기준 숏코딩 1등도 했다. (덱을 사용하는 풀이도 있다고 해서 공부한 후에 추가하겠다...