득이공간

16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제풀이 이분 탐색, 유니온-파인드 연산을 이용해서 푸는 문제입니다. 민수의 카드를 오름차순 정렬하고 upper_bownd 함수(이분 탐색)를 사용해서 내야하는 카드를 찾아 출력하면 됩니다. 그런데 한 번 낸 카드는 다시 낼 수 없기 때문에 다음 탐색에서는 제외해야 합니다. 카드의 총 개수가 많기 때문에 이 때 원소를 삭제하는 방식으로 풀면 시간초과가 발생합니다. 따라서 유니온-파인드 연산을 이용해서 한번 낸 ..

2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제풀이 N-1개의 에지를 구성하는 최소 비용을 구하는 MST 유형의 문제입니다. 각 에지의 비용을 구할 때, 모든 행성끼리 연결해버리면 O($N^{2}$)으로 시간초과가 발생합니다. 따라서 행성들을 X값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Y값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개), Z값으로 정렬했을 때 인접한 행성끼리의 에지(N-1개)를 구합니다. 이렇게 되면 3N-3개의 에지만으로 문제를 풀 수 ..

2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제풀이 다이나믹 프로그래밍을 이용해서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제입니다. 오름차순으로 나열한 A의 번호에 각각 연결된 B의 번호들을 순서대로 나열한 것을 하나의 수열로 생각하고 해당 수열에서 가장 긴 증가하는 부분 수열을 만들었을 때, 이 부분 수열에 해당하지 않는 숫자의 개수가 제거해야 하는 전깃줄의 최소 개수와 같습니다. 문제의 예제를 살펴보면, A 1 2 3 4 6 7 9 10 B (8) 2 (9) (1) 4 6 7 10 B의 최장 증가 부..

9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 문제풀이 시뮬레이션 유형의 BFS & 구현 문제입니다. 열쇠를 획득했을 때, 맵 내에 해당 열쇠에 의해 열리는 문이 생기면 방문배열을 초기화해서 탐색을 다시 반복할 수 있도록 해서 풀었습니다. 그리고 맵의 가장자리를 통해 건물 내부로 들어올 때 꼭 '.'만이 입구가 아니라는 점을 유의해야 합니다. 또한 열쇠를 획득했을 때, 맵 내의 같은 열쇠를 모두 지워주어 불필요한 탐색을 반복하게 되는 경우를 없앴습니다. (이 작업을 통해서 시간복잡도가 10배 이상 최적화되었습니다.) 코..

2263번: 트리의 순회 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 문제풀이 중위 순회와 후위 순회 노드 순서가 주어졌을 때 전위 순회 노드 순서를 출력하는 문제입니다. 후위 순회의 맨 뒷 노드를 루트 노드로 지정할 때, 해당 루트 노드를 기준으로 중위 순회 정보에서 양 옆을 쪼개서 재귀 함수를 호출하도록 구현했습니다. 다음은 예시입니다. 중위 순회: 14 5 10 1 16 7 13 3 9 11 2 6 15 4 12 8 후위 순회: 14 10 7 16 1 5 3 13 11 2 4 8 12 15 6 (9) 이런 모양의 트리가 주어졌을 때, 후위 순회의 맨 ..

1509번: 팰린드롬 분할 세준이는 어떤 문자열을 팰린드롬으로 분할하려고 한다. 예를 들어, ABACABA를 팰린드롬으로 분할하면, {A, B, A, C, A, B, A}, {A, BACAB, A}, {ABA, C, ABA}, {ABACABA}등이 있다. 분할의 개수의 최솟값을 출력하 www.acmicpc.net 문제풀이 2차원 배열에 i 번째 문자부터 j 번째 문자까지의 부분 문자열이 팰린드롬인지 판별해서 저장해준 다음, DP[k]에 0 번째 문자부터 k 번째 문자까지의 팰린드롬 분할 수의 최소값을 저장해주어 푸는 문제입니다. 팰린드롬 판별은 i번 문자와 j번 문자가 같고, i+1번~j-1번 문자열이 팰린드롬이면, i번~j번 문자열 또한 팰린드롬임을 알 수 있습니다. 코드 #include #includ..

1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 문제풀이 1182번(부분수열의 합) 문제에서 N의 크기만 다른 문제입니다. N의 크기가 20일 때는 브루트포스 알고리즘을 이용해서 한 번에 풀 수 있지만($2^{20}$번 연산 수행), 이 문제에서는 N의 크기가 40이기 때문에 같은 방법으로 풀면 시간초과가 발생합니다. ($2^{40}$번 연산 수행) 따라서 전체 수열을 반으로 나눠서 왼쪽 부분 수열, 오른쪽 부분 수열의 합을 각각 구해주어 풀어야 합니다. 풀이 과정은 다..

17387번: 선분 교차 2 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 문제풀이 기하학 & 많은 조건 분기 유형의 문제입니다. 두 선분이 교차하는 세 가지 경우를 체크해서 풀었습니다. 1. (양쪽 선분 모두) 현재 선분을 기준으로 상대 선분의 두 점이 좌우 양쪽에 위치하는 경우 2. 상대 선분의 한 점이 현재 선분을 기준으로 동일선상에 위치하고 상대 선분은 1번 조건에 해당하는 경우 3. (양쪽 선분 모두) 상대 선분의 한 점이 현재 선분을 기준으로 동일선상에 위치하는 경우 3-a. 두 선분이 같은 일직선 상에 존재하므로 네 점의 좌표 비교를 통해 두 선분이 겹치는지 판별 이 경우들을 두 벡터..

16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net #include #include #include using namespace std; const int DX[4] = { -1, 0, 1, 0 }; const int DY[4] = { 0, -1, 0, 1 }; int N, M; bool Wall[1000][1000]; bool Visited[1000][1000]; int Area[1000][1000]; int AreaSize[1000000]; int BFS(int AreaNum, int SR..

10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net #include using namespace std; bool LandingGate[100001]; int Root[100001]; int Find(int Node) { if (Node == Root[Node]) { return Node; } return Root[Node] = Find(Root[Node]); } void Union(int NodeA, int NodeB) { int A = Find(NodeA); int B = Fi..