본문 바로가기

알고리즘/BaekJoon 문제풀이5

[백준] 오타 - 5875 문제링크 5875번: 오타 올바른 괄호쌍을 좋아하는 키파는 최근에 노트북을 샀다. 그런데 키보드의 크기가 너무 작았기 때문에, 키파는 혹시 여는 괄호와 닫는 괄호를 서로 잘못 입력하지 않았는지 걱정되었다. 키 www.acmicpc.net 최대 100,000개의 입력값이 주어지며 1초의 시간 안에 풀어야 하므로 log(n) ~ nlog(n) 안에 풀어야 합니다. 변경할 괄호의 위치를 순환하는 n은 필수적으로 소모되므로 변경된 문자열이 올바른 괄호쌍인지 판단하는데 소모되는 시간은 log(n) 보다 짧아야 합니다. 문제를 풀기 위해 누적합(prefix sum) 알고리즘을 사용했습니다. 해당 알고리즘은 n만큼의 시간을 소요하여 새로운 정보를 만든 후 해당 정보를 1만큼의 시간을 통해 가공하여 답을 찾습니다. 풀.. 2023. 12. 8.
[백준] 행렬 곱셈 순서 - 11049번 문제링크 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 재귀를 활용하여 모든 경우의 수를 확인해 보는 간단한 문제입니다. 하지만 시간제한에 걸리지 않기 위해서는 memoization과정을 사용해야만 합니다. 풀이 코드 #include #include #include using namespace std; vector matrix; vector dp; int getMinCnt(int st, int ed) { if (st == ed) { return 0; } if (dp[st][ed] != -1) { .. 2021. 11. 19.
[백준] 드래곤 커브 - 15685 문제를 풀기 위해서는 점회전에 대해 알고 있어야 합니다. 문제에서는 원점을 기준으로 시계방향으로 90도 회전하도록 되어있지만 주어진 그래프의 점들의 자표는 x축 대칭되어 있으므로 반시계방향으로 90도 회전한다 생각할 수 있습니다. 따라서 원점을 기준으로 90도 회전할 경우 아래와 같은 방법으로 값을 구할 수 있습니다. x' = 0 - y * Sin(90˚) y' = x * Sin(90˚) + 0 하지만 문제에서 원하는 회전은 원점이 아닌 끝 점을 통해 회전하기를 원하므로 x값과 y값에 해당 점만큼 원점을 향해 이동시켜 준 후 회전시켜야 합니다. 이후 다시 이동한 거리만큼 되돌려주는 방식을 통해 회전된 점의 위치를 구할 수 있습니다. 각 세대별 끝점은 이전 세대를 계산하는 과정에서 가장 먼저 생성된 점이 .. 2021. 2. 19.
[백준] Facebook - 20501 문제 링크 20501번: Facebook 예제에서, 1, 2번 사용자, 1, 3번 사용자, 2, 3번 사용자, 2, 4번 사용자는 서로 친구이다. 이 때, 2번 사용자, 4번 사용자와 동시에 친구인 사용자는 없다. 1번 사용자, 3번 사용자와 동시에 친구인 www.acmicpc.net 문제에서 요구되는 과정은 아래와 같습니다. 각 쿼리별 공통된 요소 검색 검색 결과로 나온 공통된 요소 개수 계산 비교를 요하는 쿼리수가 최대 500,000이므로 각각의 과정이 200 미만의 계산 횟수를 가져야 합니다. 쿼리별 공통 요소 검색 bit 연산을 활용한다면 O(1) 시간 안에 공통된 요소를 찾을 수 있습니다. 하지만 비교 대상의 수만큼 메모리를 사용하므로 연산 가능한 범위만큼 값이 주어지는지 확인해야 합니다. 이번.. 2021. 2. 19.

티스토리툴바