본문 바로가기

전체 글140

[백준] 11437 - LCA https://www.acmicpc.net/problem/11437 11437번: LCA 첫째 줄에 노드의 개수 N이 주어지고, 다음 N-1개 줄에는 트리 상에서 연결된 두 정점이 주어진다. 그 다음 줄에는 가장 가까운 공통 조상을 알고싶은 쌍의 개수 M이 주어지고, 다음 M개 줄에는 정 www.acmicpc.net 이전 포스트를 참고하였다면 쉽게 풀 수 있는 문제이다. n 제한이 50000이라서 높이를 최대 16(2^16 = 65536)으로 주었다. #include #include using namespace std; vector v; int n, depth[50001], parent[50001][17]; void dfs(int pre, int node, int h) { depth[node] = h; .. 2022. 8. 3.
[백준] 3687 - 성냥개비 https://www.acmicpc.net/problem/3687 3687번: 성냥개비 각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다. www.acmicpc.net 제일 어려워하는 그리디 + dp 혼합문제였다. 가장 큰 수는 그리디, 가장 작은 수는 dp로 해결할 수 있다. 먼저 가장 큰 수가 될 수 있는 정답을 차례대로 보자. ans[2] = 1 ans[3] = 7 ans[4] = 4 ans[5] = 71 ans[6] = 111 ans[7] = 711 ans[8] = 1111 ... ans[15] = 7111111 무언가 규칙이 보인다. n이 홀수일 때는 7이 제.. 2022. 8. 3.
[백준] 1256 - 사전 https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net dp + 조합론 문제였다. 문제를 간단히 정리하자면, n개의 a와 m개의 z로 구성된 모든 문자열 중 k번째 문자열을 구하는 문제이다. n과 m의 제한이 100이므로, 모든 모든 조합을 구하는 것은 TLE가 날 것이고 따라서 dp를 이용할 것이다. k번째 문자열을 구하는 것은 어떻게 할 수 있을까? 처음 상황을 보자. 만약 첫번째 자리에 a를 배치했다고 하면, 남은 총 문자열의 길이는 (n + m - 1)이.. 2022. 8. 3.
[백준] 1562 - 계단수 https://www.acmicpc.net/problem/1562 1562번: 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 일반적인 계단 수(어떤 수를 사용해도 상관없는)는 dp[i][j] = 길이가 i일 때 j로 끝나는 계단 수의 개수로 해결이 가능하다. 하지만 이 문제는 0부터 9까지 숫자가 모두 등장하는 계단 수를 구하는 문제이다. 따라서 dp배열에 차원을 추가시켜 수의 조합을 나타내는 배열이 필요하다. 즉, dp[i][j][k] = 길이가 i이면서 j집합을 포함하고 k로 끝나는 계단수로 배열을 정의하면 풀 수 있다. 구현 단계에서 먼저 초기화가 필요하다. 바로 0부터 9까지의 단일 수로 표현된 수를 아래와 같이 dp배열에 저장한다. .. 2022. 8. 3.
[백준] 2610 - 회의준비 https://www.acmicpc.net/problem/2610 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 유니온 파인드 + 그래프 탐색 문제였다. 본인은 유니온 파인드를 통해 서로 이어져있는 그래프를 찾은 후에 모든 정점을 BFS를 통해서 해당 정점부터 가장 먼 정점까지의 거리의 최솟값을 이용해 답을 구하였다. 나중에 알고리즘 분류를 보니 플로이드-워셜이 있었는데 이걸 이용해서 더 간결하게 짤 수도 있었을 것 같다. #include #include #include #include #include u.. 2022. 8. 1.
[백준] 17136 - 색종이 붙이기 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 이 문제는 10 * 10 크기의 종이가 고정되어 있다는 걸로 보아 완전 탐색(+ 백트래킹)의 느낌이 났다. 처음에는 만약 1을 발견한다면 항상 가능한 큰 종이부터 붙이게끔 그리디 하게 풀었다. 하지만, 만약 8 * 8 크기의 1을 그리디 하게 붙이면 5 * 5 1장, 3 * 3 2장, 2 * 2 2장, 1 * 1 5장 총 10장을 사용하지만, 최선의 방법은 4 * 4를 4장 붙이는 것이다.. 2022. 7. 27.
[백준] 2533 - 사회망 서비스(SNS) https://www.acmicpc.net/problem/2533 2533번: 사회망 서비스(SNS) 첫 번째 줄에는 친구 관계 트리의 정점 개수 N이 주어진다. 단, 2 ≤ N ≤ 1,000,000이며, 각 정점은 1부터 N까지 일련번호로 표현된다. 두 번째 줄부터 N-1개의 줄에는 각 줄마다 친구 관계 트리의 에 www.acmicpc.net 이 문제를 풀고 나서 분류가 트리 dp에 있다는 것을 알았다. 하지만 본인은 dfs로만 풀었다. 본인이 해결방법은 다음과 같다. dfs를 돌리면서 해당 노드의 하위 노드가 얼리어답터가 아니면(ret = false), 무조건 해당 노드는 얼리어답터이어야 하므로 그때 ans을 1 증가시켰다. #include #include using namespace std; int.. 2022. 7. 27.
[백준] 9328 - 열쇠 https://www.acmicpc.net/problem/9328 9328번: 열쇠 상근이는 1층 빌딩에 침입해 매우 중요한 문서를 훔쳐오려고 한다. 상근이가 가지고 있는 평면도에는 문서의 위치가 모두 나타나 있다. 빌딩의 문은 모두 잠겨있기 때문에, 문을 열려면 열쇠가 www.acmicpc.net 이 문제는 두 가지로 나누어져 있다. 입구를 찾는 문제 열쇠를 찾으며 문서를 얻는 문제 입구를 찾는 문제는 주어진 입력에 빈 공간(.)으로 이루어진 테두리를 두르는 형태로 구현하였다. 그래서 그 테두리 중 어느곳에서 시작하여도 입구를 찾아서 진행할 수 있다. 다음으로 열쇠를 찾으며 문서를 얻는 문제이다. 기본적인 BFS와는 달리, 열쇠를 얻어야만 갈 수 있는 곳이 생기기 때문에 똑같은 곳을 한 번 이상 방문할.. 2022. 7. 27.
[백준] 1941 - 소문난 칠공주 https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 처음에 문제의 접근법을 깨닫지 몰라서 풀이를 참고하였다. 핵심은 제한이 그렇게 크지 않다는 것이었다. 학생의 수는 항상 25명이고, S를 최소 4개 이상, 총 7명 선택하면 된다. 즉 25C7 * (조건에 맞는지 탐색) 만큼의 복잡도가 걸리게 된다. 조건에 맞는지 탐색하는 부분은 S를 4명 이상 뽑았는가 뽑은 7자리를 모두 탐색한다. 총 7명이 이어져 있는가 bfs를 돌려서 서로 이어져 있는지 확인한.. 2022. 7. 27.

티스토리툴바