본문 바로가기

전체 글108

[BOJ] 백준 1024번: 수열의 합 https://www.acmicpc.net/problem/1024 1024번: 수열의 합 첫째 줄에 N과 L이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이고, L은 2보다 크거나 같고, 100보다 작거나 같은 자연수이다. www.acmicpc.net L 이상 100이하 길이의 연속된 수로 구성된 수열의 합이 N을 구하는 문제입니다. 도저히 풀이가 떠오르지 않아 모든 L에 대하여 이분탐색으로 가능한 경우의 수를 탐색했습니다. #include #include #include using namespace std; typedef long long ll; ll n, l; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(.. 2020. 8. 12.
[BOJ] 백준 1014번: 컨닝 https://www.acmicpc.net/problem/1014 1014번: 컨닝 문제 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼 www.acmicpc.net 교실 정보가 주어질 때, 위의 그림처럼 컨닝이 가능해 A,C,D,E 중 한 자리라도 사람이 앉아있으면 컨닝을 방지하기 위하여 해당 자리를 앉지못하게 합니다. 위의 규칙을 만족하면서 최대한 몇명의 사람이 앉을 수 있는지 구하는 문제입니다. 저는 동적계획법으로 해결하였습니다. (입력이 10X10이므로 꽤 다양한 알고리즘으로 해결가능하다고 생각합니다.) DP[i][j] 는 i-1번째 줄에 j 상태로 앉아있을 때 i번째.. 2020. 8. 11.
[BOJ] 백준 1011번: Fly me to the Alpha Centauri https://www.acmicpc.net/problem/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행�� www.acmicpc.net x 지점에서 출발하여 y 지점으로 가는데 이전에 k번 건너뛰었다면 다음번엔 k-1번 k번 k+1 번 건너 뛸 수 있을때 x에서 y로 가는데 최소 점프수를 구하는 문제입니다. 다만 마지막 y 지점에 도착할 땐 반드시 1번 뛰어야 합니다. 만약 내가 x에서 y로 갈때 최소 점프수로 가고 싶다면 점프할때 k를 1씩 늘리거나 유지하다가 어느 시점에서 부터 .. 2020. 8. 11.
[BOJ] 백준 1007번: 벡터 매칭 https://www.acmicpc.net/problem/1007 1007번: 벡터 매칭 평면 상에 N개의 점이 찍혀있고, 그 점을 집합 P라고 하자. 집합 P의 벡터 매칭은 벡터의 집합인데, 모든 벡터는 집합 P의 한 점에서 시작해서, 또 다른 점에서 끝나는 벡터의 집합이다. 또, P에 속 www.acmicpc.net N개의 좌표점이 주어지고 (N은 짝수) N/2개의 벡터를 만들 때, 모든 벡터의 합이 최소가 되는 크기를 구하는 문제입니다. 20개의 벡터 쌍을 구하는 경우의 수는 20C2 + 18C2 +...+ 4C2 + 2C2 이므로 20! / 2^10 으로 다른 방법을 찾아봐야겠습니다. 2,432,902,008,176,640,000 / 1024 = 2,375,880,867,360,000 위의 벡터의.. 2020. 8. 11.
[BOJ] 백준 1004번: 어린 왕자 https://www.acmicpc.net/problem/1004 1004번: 어린 왕자 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 첫째 줄에 출발점 (x1, y1)과 도착점 (x2, y2)이 주어진다. 두 번째 줄에는 행성계의 개수 n이 주�� www.acmicpc.net 점과 원사이 관계로 푸는 문제. 출발 지점과 도착 지점이 주어진 원에 대하여 두 점이 모두 원 안쪽에 속하는지, 둘다 속하지 않은 경우 해당 원을 진입하거나 이탈 할 필요가 없습니다. 어느 한 지점만 속한 경우 반드시 진입 또는 이탈을 해야하므로 이 경우에만 1 증가 시켜주면 됩니다. #include #include using namespace std; typedef long l.. 2020. 8. 11.
[BOJ] 백준 1002번: 터렛 https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 두 원의 중심과 반지름이 주어질 때, 두 원의 교점의 개수를 구하는 문제입니다. 소수점 연산의 오차를 줄이기 위하여 두 점사이 거리의 제곱을 활용합니다. 두 원의 중심 간의 거리 dist = (x1-x2)^2 + (y1-y2)^2 두 반지름의 합 sumr = (r1 + r2) * (r1 + r2) 두 원의 반지름 중 큰 것 r1, 작은것 r2 (같으면 순서 상관 없음) 1. 동심원의 경우 if (!dist) { // 동심원 cout > y1 >> r.. 2020. 8. 11.
유니온 파인드 (Union Find) 혹은 분리 집합 (Disjoint Set) 유니온 파인드 알고리즘은 같은 집합에 속한 원소들을 O(1)의 시간 복잡도로 확인하는 방법으로 다양한 문제들에서 많이 사용됩니다. 특정 노드는 자신의 부모를 의미하는 P[node] 배열값을 갖습니다. 즉 P[node] = node 인 경우 자기 자신을 부모로 한다는 의미이며, P[node] != node 인경우 다른 노드 번호를 부모로 한다는 뜻입니다. 그럼 대체 이걸 어디에 사용할 수 있을까요? 예를 들어 1번 노드와 3번 노드가 연결되어 있고, 2번 노드와 3번 노드가 연결되어 있다면 1번과 3번이 연결되어있는 것을 알 수 있습니다. 여기서 연결된 노드간 같은 부모를 갖는다고 정의한다면 P[1] = P[2] = P[3] 이며 1 또는 2 또는 3의 값을 가집니다. 편의상 부모 노드의 번호가 작은쪽으로.. 2020. 8. 9.
[BOJ] 백준 1956번: 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 u를 완전탐색 O(n^3)로 구할 수 있습니다. 초기값을 입력 경로로 넣어주고 나머지는 꽤 큰값 (1e9)로 초기화한 뒤 3중 포문으로 구해 나가는 코드입니다. #include #include #include #include #include #include #include #include using namespace std; int n, m; int buf[401][401]; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i a .. 2020. 8. 9.
[BOJ] 백준 9370번: 미확인 도착지 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지�� www.acmicpc.net 시작점 s와 지나간 두 정점 g와 h의 정보, 전체 경로들에 대한 정보 및 목적지 후보 t가 주어질 때, 시작점에서 목적지까지 최단 경로가 시작점에서 g와 h를 잇는 간선을 지나 목적지까지 가는 최단경로의 비용이 같은 목적지 후보들을 찾는 문제입니다. 먼저 시작점에서 모든 정점까지 가는 최단 경로를 구합니다. 우선순위 큐를 사용한 다익스트라로 빠르게 구할 수 있습니다. (SPFA + SL.. 2020. 8. 9.

티스토리툴바