'백준' 태그의 글 목록 (3 Page)

2021. 11. 17. 15:32 Algorithm/BOJ

문제 링크 http://icpc.me/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 풀이 이분 매칭과 에라토스테네스의 체를 이용하여 풀 수 있다. 우선 2000이하의 모든 소수를 에라토스테네스의 체를 이용하여 판별해놓는다. 그 후에 첫번째 수와 소수를 만들 수 있는 수 k를 하나 잡고 나머지 수들을 모두 소수 쌍으로 만들 수 있는 k들을 모두 구하면 된다. 나머지 수들을 모두 소수 쌍으로 만들 때 이분 매칭을 이용한다. 간선을 연결할 때는 소수 쌍을..

백준[2243] 사탕상자

2021. 11. 17. 14:31 Algorithm/BOJ

문제 링크 http://icpc.me/2243 2243번: 사탕상자 첫째 줄에 수정이가 사탕상자에 손을 댄 횟수 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 두 정수 A, B, 혹은 세 정수 A, B, C가 주어진다. A가 1인 경우는 사탕상자에서 사탕을 꺼내는 경우이 www.acmicpc.net 풀이 백준 12899 데이터 구조 이 문제와 거의 동일한 문제다. 세그먼트 트리를 이용하여 k번째 수를 빠르게 구하는 문제다. 업데이트는 일반 세그먼트 트리 업데이트와 비슷하게 하고, 쿼리를 약간 다르게 구현한다. k번째 수를 구할 때, 왼쪽 자식 노드의 값은 L이라 한다면, k L이라면 오른쪽 자식 중 k - L번째 수를 구하는 ..

백준[16927] 배열 돌리기 2

2021. 11. 16. 20:47 Algorithm/BOJ

문제 링크 http://icpc.me/16927 16927번: 배열 돌리기 2 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] www.acmicpc.net 풀이 구현 문제다. 위의 그림과 같이 돌려야 하는 수들을 미리 덱에 저장해 두고, 덱의 맨 앞에 맨 뒤의 수를 집어넣는 것을 R번 하면 된다. 그런데 이때 R이 10^9으로 매우 크기 때문에 그냥 돌리면 시간 초과가 난다. 그렇기 때문에 덱의 크기만큼 돌리면 다시 덱이 초기의 상태랑 똑같아지기 때문에 R % (덱의 크기)만..

백준[19581] 두 번째 트리의 지름

2021. 11. 15. 13:27 Algorithm/BOJ

문제 링크 http://icpc.me/19581 19581번: 두 번째 트리의 지름 트리에 N개의 정점이 있고, 각 정점 별로 1부터 N까지의 번호가 붙어있다. 트리에서 가장 먼 두 정점 간의 거리를 트리의 지름이라고 한다. 트리의 지름을 구하는 문제는 너무 많기 때문에 우리 www.acmicpc.net 풀이 bfs/dfs를 이용하여 풀 수 있다. 임의의 점을 하나 잡고, 그 점에서 가장 먼 점을 구한다. 그때 이 가장 먼 점을 a라고 하자. a에서 가장 먼 점을 구한다. 그때 이 점을 b라고 하자. 그럼 이때 a, b의 거리가 트리의 지름이 되고, 이 두 점이 트리에서 가장 먼 두 점이다. 그럼 이제 이 두 점 사이 거리를 제외한 가장 먼 거리를 찾아야하기 때문에, a에서 b를 제외한 가장 먼 거리를 ..

백준[16978] 수열과 쿼리 22

2021. 11. 13. 23:20 Algorithm/BOJ

문제 링크 http://icpc.me/16978 16978번: 수열과 쿼리 22 길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다. www.acmicpc.net 풀이 세그먼트 트리를 이용하여 풀 수 있다. 쿼리를 입력받은 순서대로 하지 않고, i번째 1번 쿼리를 하기 전에 k n; for (int i = 1; i > ipt; update(1, 0, N, ipt, i); } vector a; vector b; int t = 0; int q; cin >> q; for (int i = 0; i < q; i++) ..

백준[1011] Fly me to the Alpha Centauri

2021. 11. 12. 23:53 Algorithm/BOJ

문제 링크 http://icpc.me/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 규칙을 찾으면 되는 문제다. 어떤 거리만큼 가장 짧은 거리로 가려면 한 번에 많은 거리를 움직여야 한다. 한 번에 움직이는 거리가 최대가 되는 상황을 잘 구하면 된다. 만약 한번에 k만큼 움직인다면, k만큼 움직이기 위해서는 1 2 3 4 .. k k-1 k-2 .. 1 이런 식으로 움직여야 할 것이다. 이때 1 + 2 + 3 + 4 + .. + k + k-1 + k..

백준[3830] 교수님은 기다리지 않는다

2021. 11. 12. 02:05 Algorithm/BOJ

문제 링크 http://icpc.me/3830 3830번: 교수님은 기다리지 않는다 교수님의 질문 (? a b)이 입력으로 들어올 때 마다, 지금까지 측정한 결과를 바탕으로 a와 b의 무게 차이를 계산할 수 있다면, b가 a보다 얼마나 무거운지를 출력한다. 무게의 차이의 절댓값이 1,000, www.acmicpc.net 풀이 유니온 파인드를 이용하여 풀었다. 대소 관계를 이용하여 무게 차이를 구할 수 있는 것들을 같은 집합으로 묶는다. 이때, dist 배열에 두 개의 무게 차를 저장해 놓는다. dist 배열의 정의는 dist [i]는 i와 i의 부모의 거리이다. 또한 두 집합의 루트 사이의 거리를 정의해줘야 하는데, a, b를 union 할 때 a의 루트를 pa, b의 루트를 pb라고 하면, dist [..

백준[1761] 정점들의 거리

2021. 11. 8. 17:26 Algorithm/BOJ

문제 링크 http://icpc.me/1761 1761번: 정점들의 거리 첫째 줄에 노드의 개수 N이 입력되고 다음 N-1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에 M이 주어지고, 다음 M개의 줄에 거리를 알고 싶은 노드 쌍이 한 줄에 한 쌍씩 www.acmicpc.net 풀이 LCA(최소 공통 조상)를 구하여 풀 수 있다. root에서 a까지의 거리를 cost[a]라고 할 때, 트리에서 정점 a, b의 거리는 cost[a] + cost[b] - 2 * cost[lca]라고 할 수 있다. 코드 #include #include #include using namespace std; const int N = 4e4 + 4; vector v[N]; int dp[22][N], cost..

백준[1043] 거짓말

2021. 11. 8. 14:30 Algorithm/BOJ

문제 링크 http://icpc.me/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 풀이 유니온 파인드를 이용해서 풀 수 있다. 진실을 아는 사람들을 같은 집합에 넣어두고, 파티 구성원들을 같은 집합에 넣을 때, 만약 이 집합에 진실을 아는 사람들이 있다면 진실을 아는 사람 그룹에 그 파티 구성원들을 모두 넣어야 한다. 그 후에 파티 구성원들 집합을 확인하며 진실을 모르는 사람들만 모여있는 집합의 개수를 세면 된다. 코드 #include #include #include using namespace std; i..

백준[6549] 히스토그램에서 가장 큰 정사각형

2021. 11. 7. 19:13 Algorithm/BOJ

문제 링크 http://icpc.me/6549 6549번: 히스토그램에서 가장 큰 직사각형 입력은 테스트 케이스 여러 개로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 직사각형의 수 n이 가장 처음으로 주어진다. (1 ≤ n ≤ 100,000) 그 다음 n개의 정수 h1, ..., hn (0 ≤ hi ≤ www.acmicpc.net 풀이 스택과 분할 정복을 이용하여 풀 수 있다. 스택을 이용한 풀이는 O(N)에 풀 수 있지만 아이디어를 떠올리기 힘들고, 분할 정복은 O(NlogN)에 풀 수 있지만 세그먼트 트리를 알아야 한다. 분할 정복 구간 [l, r]에서 가장 큰 직사각형의 넓이는 (가장 작은 기둥 높이) * (r - l + 1) 그렇기 때문에 가장 작은 기둥 왼쪽, 가장 작은 기둥 ..

백준[1010] 다리 놓기

2021. 11. 7. 18:49 Algorithm/BOJ

문제 링크 http://icpc.me/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 풀이 조합을 이용하여 풀 수 있다. 고등학교 때 확통 공부를 해봤다면 아주 자주 볼 수 있는 문제다. 다리가 겹치지 않아야 하기 때문에 오른쪽의 어떤 다리에 연결할지만 정한다면, 왼쪽 다리가 어느 다리랑 연결될지는 알아서 결정이 되게 된다. 그렇기 때문에 mCn을 하면 된다. 코드 #include int dp[32][32]; int dpf(int n, int k) { int &ret = dp[n][k]; if (n ..

백준[10999] 구간 합 구하기 2

2021. 11. 5. 15:00 Algorithm/BOJ

문제 링크 http://icpc.me/10999 10999번: 구간 합 구하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄 www.acmicpc.net 풀이 lazy propogation 기본 문제이다. lazy propogation은 세그먼트 트리를 응용한 구간 업데이트와 구간 쿼리를 모두 O(logN)에 할 수 있는 자료구조다. 자세한 설명은 다른 더 대단한 분들이 많이 올리셨으니 생략하겠다. 내가 참고한 글은 여기에 적어놨다. 코드 #include using namespace std; using..

백준[1182] 부분수열의 합

2021. 11. 5. 14:09 Algorithm/BOJ

문제 링크 http://icpc.me/1192 1192번: 장갑 임의로 왼쪽 통에서 2개, 오른쪽 통에서 8개를 가져온다면 최소한 한 쌍의 같은색의 장갑이 나옴을 보장할 수 있다. www.acmicpc.net 풀이 백트레킹으로 조합을 만들면 된다. 만약 s가 0일때는 아무것도 뽑지 않는 경우가 생길 수 있기 때문에 정답에 -1을 해준다. 코드 #include int n, s, ret; int arr[22]; bool visited[22]; void solve(int cur, int sum) { if (sum == s) ret++; for (int i = cur; i < n; i++) { if (visited[i]) continue; visited[i] = true; solve(i, sum + arr[i]..

백준[5052] 전화번호 목록

2021. 11. 4. 10:40 Algorithm/BOJ

문제 링크 http://icpc.me/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 t가 주어진다. (1 ≤ t ≤ 50) 각 테스트 케이스의 첫째 줄에는 전화번호의 수 n이 주어진다. (1 ≤ n ≤ 10000) 다음 n개의 줄에는 목록에 포함되어 있는 전화번호가 www.acmicpc.net 풀이 트라이를 이용하여 풀 수 있다. 트라이에 전화번호를 넣는 과정에서 prefix가 똑같은 문자열을 발견하면 NO를 출력하면 된다. cf) new Trie()를 하여 동적 할당을 하는 것보다 전역 변수로 Trie를 많이 만들어 할당해주는 방식이 더 빠르기 때문에 아래와 같이 구현했다. 코드 #include struct Trie; Trie* new_trie(); struct Trie { int..

백준[1913] 달팽이

2021. 11. 2. 16:50 Algorithm/BOJ

문제 링크 http://icpc.me/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 풀이 구현 문제다. 달팽이처럼 뱅글뱅글 돌면서 순회를 하는 문제다. 구현하는 방식을 알아두자. 코드 #include #include int n, k; int dir[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; bool visited[1003][1003]; int arr[1003][1003]; bool movable(int r, int c, int d) { int nr = r + dir..

티스토리툴바