득이공간

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

11003번: 최솟값 찾기 N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다. www.acmicpc.net #include #include using namespace std; typedef pair p; int Seq[5000000]; priority_queue PQ; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N, L; cin >> N >> L; for (int i = 0; i > N..

14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net #include #include using namespace std; int Sequence[1000]; int DP[1000]; stack LIS; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int Max = 0; int Index = 0; int N; cin >> N; for (int i = ..