목록알고리즘/백준 (65)
개발자 김수진
[문제] www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net [풀이] N이 1인 경우부터 모든 경우의 수를 구하다 보면 규칙을 금방 발견할 수 있다. 규칙을 통해 아래와 같이 점화식을 세워서 DP를 사용해 풀었다. DP[i] = DP[i-1]+DP[i-2]; [코드] 시간 : 0ms #include #define MAX 90 using namespace std; long long DP[MAX]={0,}; int N; int main(void) { ci..
[문제] www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net [풀이] DP를 사용해서 이전 경로까지의 최대, 최솟값을 저장해놓고 이전 경로와 현재 위치의 값을 더해서 최대, 최솟값을 구했다. 처음에는 N의 범위가 N(1 ≤ N ≤ 100,000)이므로 DP배열을 [100001][3]의 크기고 잡고 시작했는데 메모리 초과가 나왔다. 생각해보니 문제 조건에서 주어진 메모리 제한은 4MB인데 [100001][3]의 크기로 잡고 풀면 min, max 배열이 2개 이므로 4MB를 넘어..
[문제] www.acmicpc.net/problem/1946 1946번: 신입 사원 첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성�� www.acmicpc.net [풀이] 처음에는 2중 for문 사용해서 하나를 기준으로 현재 지원자를 기준으로 서류 점수가 더 우수한 지원자가 있다면 면접 점수를 비교하는 방식으로 풀었다. 모든 면접자에 대해서 한번씩 모두 비교해야 하므로 당연히 시간초과가 나왔다. 따라서 두번째에는 서류 점수를 기준으로 오름차순으로 정렬하고 한명의 지원자를 기준으로 앞에 있는 지원자보다 면접 점수도 낮다면 제외하였다. 이렇..
[문제] www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 � www.acmicpc.net [풀이] MST의 가중치를 구하는 문제로 Kruskal 알고리즘을 사용해서 풀었다. 정점간의 연결 정보를 입력 받고 벡터에 저장했다. 가중치를 기준으로 벡터를 정렬하고 , 가중치가 작은 것부터 Union-Find를 사용해 묶어줬다. Union을 하기 전에 Find를 통해 부모가 같은지 미리 확인한다. ( 부모가 같은 상태에서 union을 해버리면 사이클..
[문제] www.acmicpc.net/problem/3020 [풀이] 처음에는 반복문을 사용해서 풀려고 했지만 N,H 범위를 생각해서 따지면 반복문 10억번에 1초라고 생각하면 20,000 * 50,000 이므로 1초를 훨씬 넘길 것이다. 따라서 이분 탐색 방법으로 풀어야겠다고 생각했다. lower_bound는 x 이상인 값이 처음 나오는 index를 return하고 upper_bound는 x 이하인 값이 처음 나오는 index를 return 하므로 전체 갯수에서 return 된 값을 빼면 파괴하는 장애물의 수를 구할 수 있다. [코드] 시간 : 60ms ( 이분 탐색 직접 구현해서 다시 풀어봐야겠다.) #include #include #include #define MAX 100000 using name..
[문제] www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net [풀이] 표의 크기 N과 합을 구해야 하는 횟수 M이 입력으로 주어진다. 그 다음으로 표의 값이 주어지고 구간의 시작 좌표, 마지막 좌표가 주어진다. 이 구간의 합을 구해서 출력하면 된다. 처음에는 이중 for문을 사용해서 시작점인 (x1,y1)부터 구간의 마지막 부분인 (x2,y2) 까지의 합을 구했다. 당연히 시간초과가 나왔고 다른 방법을 찾아봤다. 찾아보..
[문제] www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1≤N≤32,000), M(1≤M≤100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미이�� www.acmicpc.net [코드] N 명의 학생들을 M번 비교하고 그 결과가 입력으로 주어진다. 이를 통해 학생들을 줄을 세우는 결과를 출력하면 된다. 학생들의 키가 모두 주어진 것이 아니고 일부만 주어졌으므로 '위상 정렬'을 사용해서 풀었다. Degree에 각 노드에 대한 연결 차수를 저장하고 연결 차수가 0인 노드만 queue에 push 하여 순서대로 출력했다. [풀이] 시간 : 44ms..
[문제] www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net [풀이] DP를 사용해서 2부터 N까지의 1을 만들 때 필요한 연산의 최소 횟수를 구했다. bottom-up 방식을 사용해 2부터 N까지의 최솟 값을 구했다. 연산은 아래와 같이 3가지 연산이 있다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 따라서 1을 빼는 연산은 모든 숫자에 대해 가능하므로 구하고 X가 2로 나눠지는 경우, 3으로 나눠지는 경우에는 이에 대한 경우도 구해서 최솟 값을 구했다. [코드] 시간 : 4ms #include #define MAX..