본문 바로가기
반응형

Computer Science86

[백준 1912번] 연속합 (C++, Python) https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 이번 포스트에서는 백준 알고리즘 문제인 연속합을 포스팅하도록 하겠습니다. 해당 문제는 solved.ac 기준 실버 2에 위치한 문제입니다. 먼저 문제입니다. 정수 N이 주어지고, N의 길이의 수열이 주어집니다. 이때, 연속된 몇 개의 수를 선택해서 구할 수 있는 합중 가장 큰 합을 구하는 문제입니다. 수는 한개 이상 선택해야합니다. 이 문제도 DP 알고리즘 문제로 바텀업 방식으로 해결합니다. 브루트포스 알고.. 2023. 9. 25.
[백준 1904번] 01 타일 (C++, Python) https://www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이 www.acmicpc.net 이번 포스트에서는 백준 알고리즘 문제인 01타일을 포스트하겠습니다. 해당 문제는 solved.ac 기준으로 실버 3에 위치한 문제입니다. 먼저 문제입니다. 문제에서 완성된 타일의 길이 N이 주어졌을 때, 00 타일과 1 타일로 N 길이의 타일을 만드는 모든 경우의 수를 출력하는 문제입니다. 해당 문제는 이전 문제인 1로 만들기 문제와 비슷하게 바텀업 방식의 DP 알고리즘으로 해결할 수 있습니다. 먼저 .. 2023. 9. 24.
[백준 1463번] 1로 만들기 (C++, Python) https://www.acmicpc.net/problem/1463 이번 포스트에서는 백준 알고리즘 문제인 1로 만들기 를 포스트하겠습니다. 해당 문제는 solved.ac 기준 실버 3에 위치한 문제입니다. 먼저 문제입니다. 문제에서 주어진 연산 3가지를 사용할 때, 정수 N을 입력받고 연산 3개를 골라서 사용했을 때, 가장 적은 횟수의 연산 횟수를 찾아서 출력하는 문제입니다. 해당 문제에서는 입력이 1인 경우는 0으로 알고 있는 값이기 때문에 2부터 시작해서 바텀업으로 해결하는 DP 알고리즘으로 해결할 수 있습니다. N이 10으로 주어졌을 때, 10 -> 9 -> 3 -> 1 이 가장 적은 연산을 수행하는 방법입니다. 이때 N이 9일때도 9 -> 3 -> 1 이 가장 빠른 순서입니다. 또 다시 N이 3일.. 2023. 9. 22.
[백준 11758번] CCW (C++, Python) 이번 포스트에서는 백준 알고리즘 문제인 CCW 를 포스트하겠습니다. 해당 문제는 solved.ac 기준으로 골드 5 에 위치한 문제입니다. 먼저 문제입니다. 입력으로 2차원 좌표 평면 위의 점 3개의 x, y값이 주어집니다. 이때, 점 3개를 순서대로 이은 선분이 어떤 방향을 이루고 있는지 구하여 출력하는 문제입니다. 해당 문제는 점A, 점B, 점C 가 있을 때, C에서 B로가는 벡터, B에서 A로 가는 벡터의 외적곱을 통해 CCW값을 구할 수 있습니다. 벡터 CB는 (bx - cx, by - cy), 벡터 BA는 (ax - bx, ay - by) 로 정의되고, 이 두 벡터를 외적곱하면 CCW = (bx - cx)*(ay - by) - (by - cy)*(ax - bx) 가 됩니다. 이때, CCW 값이 .. 2023. 9. 20.
반응형