o_onn5

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄..

https://www.acmicpc.net/problem/12015 12015번: 가장 긴 증가하는 부분 수열 2 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000,000) www.acmicpc.net 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다. 입력 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 A..

https://www.acmicpc.net/problem/1965 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net 문제 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 있다. 예를 들어 앞에서부터 순서대로 크기가 (1, 5, 2, 3, 7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를..

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. www.acmicpc.net 문제 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 ..

https://www.acmicpc.net/problem/1890 1890번: 점프 첫째 줄에 게임 판의 크기 N (4 ≤ N ≤ 100)이 주어진다. 그 다음 N개 줄에는 각 칸에 적혀져 있는 수가 N개씩 주어진다. 칸에 적혀있는 수는 0보다 크거나 같고, 9보다 작거나 같은 정수이며, 가장 www.acmicpc.net 처음에는 접근을 BFS와 DP를 섞어서 하면 될 것 같은데? 했지만 메모리초과가 나왔다. BFS로 풀려고하면 생각보다 조건들이 까다로워져서 다른 방법을 생각해봤다. 그래서 생각해낸것이 이중 for문으로 전부 확인하면서 DP 돌리는거였다(진작에 이렇게 할걸..ㅋㅋㅋ) DP에는 해당 위치로 올 수 있는 경로의 개수를 저장한다. 그리고 이중 for문을 돌릴 시 맨 마지막 (n-1, n-1) ..

https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 최소스패닝 트리를 만드는 크루스칼 문제다. 전형적인 크루스칼 문제라서 개념을 아는 사람이라면 쉽게 풀 수 있다. import math # 특정 원소가 속한 집합 찾기 def find_parent(parent, x): # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출 if parent[x] != x: parent[x] = find_parent(parent, parent[x]) ret..

https://www.acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크 www.acmicpc.net 처음에 문제 보고 어떻게 해야할지 막막했다. 바이러스를 막을 최적의 벽 3개를 어떻게 알아내지????? 근데 그런 걱정을 하는 문제가 아니었다. 입력 조건을 보면 그래프 크기 최대가 8*8 이다ㅋㅋㅋ 그냥 벽을 세울 수 있는 모든 경우의 수를 구하면 되는 문제. 나는 아래와 같이 풀었다. (안전 영역 = 그래프 크기 - 바이러스 개수 - 벽 개수) BFS로 풀었고, 모든 경우의 수를 알기 위해서 itertoo..

https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net Topology(위상정렬) 알고리즘 문제다. 위상정렬의 알고리즘은 다음과 같이 진행된다. 1. indegree(진입차수)가 0인 노드를 찾고 큐에 넣는다. 2. 큐에서 노드를 꺼내고 해당 노드와 연결되는 모든 노드를 탐색한다. 3. 탐색되는 노드들의 indgree 값을 1씩 감소시킨다. 4. 탐색된 노드들 중 indgree 값이 0인 노드를 큐에 넣는다...

https://www.acmicpc.net/problem/5430 5430번: AC 각 테스트 케이스에 대해서, 입력으로 주어진 정수 배열에 함수를 수행한 결과를 출력한다. 만약, 에러가 발생한 경우에는 error를 출력한다. www.acmicpc.net deque에 대해서 알아볼 수 있는 문제다. 처음에는 R을 받을 때마다 q.reverse()를 통해 역순정렬을 해서 시간초과가 나왔다. cnt 변수를 하나 만들어서 R을 받을 때마다 1씩 증가시키며 마지막에 한 번만 reverse를 해주면 되는 문제였다. 이게 핵심이었던 것 같고, 공부하면서 reverse(), rotate(), 리스트와 덱의 차이점 등을 알 수 있어서 좋은 문제라 생각한다. 끗 from collections import deque de..

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 크루스칼 문제다. 일반적인 크루스칼 개념을 적용시켜서 푸는 것은 동일하다. 각 노드의 x축 y축 z축 차이를 탐색한 뒤에 절댓값이 가장 작은 가중치를 선택하면 된다. 그렇다고 모든 노드를 하나씩 비교해보면 시간초과가 난다. 따라서 간선의 가중치와 노드를 저장한 뒤에 우선순위 정렬을 시행한 뒤 비교해줘야한다. 정리해보면 1. x축 y축 z축의 리스트를 하나 만든다. ..