목록전체 글 (224)
득이공간
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 = ..
18185번: 라면 사기 (Small) 라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i www.acmicpc.net #include using namespace std; int Factory[10002]; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int N; cin >> N; for (int i = 0; i > Factory[i]; } int Price = 0; for (int i = 0; i < N; ++i) { int Num; ..