전체 글
-
[2146] 다리 만들기BOJ 2021. 9. 1. 23:10
https://www.acmicpc.net/problem/2146 2146번: 다리 만들기 여러 섬으로 이루어진 나라가 있다. 이 나라의 대통령은 섬을 잇는 다리를 만들겠다는 공약으로 인기몰이를 해 당선될 수 있었다. 하지만 막상 대통령에 취임하자, 다리를 놓는다는 것이 아깝다 www.acmicpc.net 쉬워보이지만, 생각보단 쉽지 않다. 떠올릴만한 효율적인 알고리즘들은 대부분 반례로 저격당한다. 결국, 일일히 하나씩 bfs를 돌려봐야 하는데, 사용 알고리즘은 다음과 같다. 입력에는 여러개의 섬이 존재한다. 섬의 개수가 M개 있다면, 이들에 각각 이름을 붙여준다. 1번섬, 2번섬, 3번섬...M번섬으로 하자. 1) 1번섬에서 이을 수 있는 다리의 최단길이를 알아보기 위해, 1번섬을 기준으로 bfs를 돌..
-
[1328] 고층 빌딩BOJ 2021. 9. 1. 22:54
https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼 www.acmicpc.net 아이디어를 잘 떠올리면 쉽게 풀 수 있다. 아이디어를 못떠올리면 한없이 어려워지는 문제였다. 기본 아이디어는 다음과 같다. 1) N개의 턴을 반복하고, 매턴이 시작하면 이미 지어진 건물의 높이를 1 증가시킨다. 2) 높이 1의 건물을 배치한다. 배치가 끝나면 턴이 종료된다. 2)를 진행할때에, 경우의수는 아래의 3가지로 나뉜다. 1. 맨 왼쪽에 배치하는 경우 -> 왼쪽에서 볼때의 건물의 개수가 1..
-
[1715] 카드 정렬하기BOJ 2021. 9. 1. 22:44
https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 가장 작은것 2개를 골라, 합치는걸 반복하면 된다. 우선순위큐를 사용해 간단하게 구현해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include using namespace std; priority_queueq; int n; unsigned long long sum; ..
-
[16235] 나무 재테크BOJ 2021. 9. 1. 22:42
https://www.acmicpc.net/problem/16235 16235번: 나무 재테크 부동산 투자로 억대의 돈을 번 상도는 최근 N×N 크기의 땅을 구매했다. 상도는 손쉬운 땅 관리를 위해 땅을 1×1 크기의 칸으로 나누어 놓았다. 각각의 칸은 (r, c)로 나타내며, r은 가장 위에서부터 www.acmicpc.net 문제가 길고, 구현해야 하는 것도 많다. 대략 다음을 구현해야 하는 문제이다. 1. 하나의 칸에 여러개의 나무가 존재할 수 있으며, 같은 칸중 어린나무부터 양분을 자신의 나이만큼 먹는다. 1-1 : 먹을 양분이 없다면, 나무는 죽고 죽은 나무가 양분이된다. 1-2 : 먹을 양분이 있다면, 나무는 양분을 먹고 나이가 1 증가한다. 2. 나이가 5의 배수일때, 인접한 칸에 나이1의 나..
-
[5615] 아파트 임대BOJ 2021. 9. 1. 22:22
https://www.acmicpc.net/problem/5615 5615번: 아파트 임대 첫째 줄에 아파트의 면적의 수 N이 주어진다. 다음 줄부터 N개 줄에 카탈로그에 적혀있는 순서대로 면적이 주어진다. N은 100,000이하이고 면적은 231-1이하인 양의 정수이다. www.acmicpc.net 매우 어려운 문제였다. 결론적으론 소수판별 문제인데... 이 문제에 사용된 소수판별을 논하기 전에 기본적인 소수판별에 대해서 먼저 정리해보자. 소수판별을 단순하게 구현하면 O(N)이다. 2부터, n-1까지 %연산을 하다 0이되는 순간이 1번이라도 있으면 소수가 아니다. 하지만, 모든 합성수는 sqrt(N) 이하의 인수를 갖는다는 사실을 적용해 같은 %연산에 브루트포스적인 방법이여도 시간복잡도를 O(sqrt(..
-
[1259] 팰린드롬수BOJ 2021. 9. 1. 21:41
https://www.acmicpc.net/problem/1259 1259번: 팰린드롬수 입력은 여러 개의 테스트 케이스로 이루어져 있으며, 각 줄마다 1 이상 99999 이하의 정수가 주어진다. 입력의 마지막 줄에는 0이 주어지며, 이 줄은 문제에 포함되지 않는다. www.acmicpc.net 투포인터같은 느낌으로 생각해보자. L를 맨 왼쪽, R을 맨 오른쪽에 위치시키고 항상 L++, R--을 진행한다. 도중에 한번이라도 s[L] != s[R]인 순간이 있다면 팰린드롬이 아니고, s[L] != s[R]인 순간이 한번도 없으며 L>=R이 되어 탐색이 끝나면, 팰린드롬이라고 판별하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25..
-
[10942] 팰린드롬?BOJ 2021. 9. 1. 21:37
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 구간에 대해 팰린드롬이 성립하는지에 대한 불리언 값을 출력해야하는 구간쿼리가 M개 들어온다. 일반적인 팰린드롬 판별에 O(N)의 시간복잡도가 소요되므로, 특별한 최적화가 없다면 O(NM)이 걸릴것이다. 문제는, N이 2천, M이 1백만, 0.5초의 시간제한으로 TLE이다. 이는 DP를 사용해 최적화가 가능하다. 아래와 같은 사실이 DP최적화의 핵심이다. 1. (S,E)가 팰린드롬이 아니면, (S-1, E+1)도 팰린드롬이 아니다 2. ..
-
[11053] 가장 긴 증가하는 부분 수열BOJ 2021. 9. 1. 21:30
https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net dp를 사용하면 O(N^2)의 시간복잡도를 갖는다. dp는 다음과 같이 구성하면 된다. dp[i] = i번째 수까지의 최대 길이 다만 이문제는 이분탐색을 사용하면 O(NlogN)만에도 해결이 가능하다. 비슷한 문제가 많은데, 대략 아래와 같은 구성을 갖는다. 가장 긴 증가하는 부분수열 : O(N^2), dp로 해결한다...
-
[1717] 집합의 표현BOJ 2021. 9. 1. 21:22
https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 유니온파인드 문제이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 #include int n, m; int a[1000001]; void _union(int x, int y); int _find(int x); void _union(int x, i..
-
[10819] 차이를 최대로BOJ 2021. 9. 1. 21:19
https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net N이 8로 매우작다. 완전탐색은 8! == O(N!) 수열을 모두 만들어서 일일히 score를 갱신해주면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 #include #include using namespace std; int a[10], b[10], n, ans = -12345; bool..