득이공간

2470번: 두 용액첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00www.acmicpc.net 문제풀이 적절한 두 용액을 선택하는 과정에서 완전 탐색을 이용하면 $100000 * 100000$번의 연산이 수행되므로 시간초과가 발생합니다.따라서 한 용액을 먼저 선택한 후 다른 용액을 이분 탐색을 이용해서 선택하도록 하면 $100000 * 16.6 (={log_{2}}{100000})$번의 연산만으로 풀 수 있습니다.Start, End 인덱스를 지정할 때는 선택한 두 용액의 합과 0의 크기를 비교해서 조절해주면 됩니다.코드#in..

16234번: 인구 이동N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모www.acmicpc.net 문제풀이 너비 우선 탐색을 이용해서 푸는 시뮬레이션 유형의 문제입니다.미방문 노드에서 BFS를 시작해서 연합 영역을 큐에 저장해주고연합의 크기가 2이상일 때 인구 이동을 시켜주었습니다.인구 이동이 더이상 이뤄지지 않을 때까지 해당 로직을 반복해서 시뮬레이션하도록 구현했습니다.코드#include #include #include using namespace std;typedef pair p;const int..

1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제풀이 DFS 알고리즘 & List 자료구조를 이용해서 풀었습니다. 각 노드 마다 부모 노드를 배열에 저장해주고, 자식 노드는 리스트로 구성해주었습니다. 그리고 삭제 노드를 입력받았을 때 해당 노드의 부모의 자식 리스트에서 제거해주고 루트노드로부터 깊이 우선 탐색을 수행하도록 구현했습니다. 코드 #include #include #include using namespace std; int N, Root, Cnt; int P[50]; list C[50]; v..

3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net 문제풀이 덱 자료구조를 이용해서 뱀 몸의 위치를 기록하는 방법으로 푸는 시뮬레이션 유형의 문제입니다. 각 초마다 문제에서 제시한 조건대로 이동을 구현해주어 풀었습니다. 덱에 push_back으로 머리 이동 위치를 저장해주었고, 사과를 먹지 않았을 때는 pop_front로 꼬리를 이동해주었습니다. 그리고 초가 끝났을 때는 입력받은 X, C 정보에 따라 뱀이 현재 향하고 있는 방향(0:L, 1:R, 2:T, 3:B)을 나타내는 변수를 바꿔주었습니다. 코드 #include ..

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..