백준 검색 결과

해당 글 24건
백준에서 자주 보이는 절대 오차 상대 오차에 대해 간단하게 알아봅시다.

이번 시간에는 백준에서 문제를 푸실 때 많이 보이는 절대오차, 상대오차에 대해서 간단하게 짚고 넘어가도록 하겠습니다. 먼저 모범 답안과의 절대 오차가 x 이하이면 정답 처리한다는 말이 무슨 이야기일까요? 실제 정답이 a라고 하면 a-x를 출력해도 정답, a+x를 출력해도 정답이라는 의미입니다. 즉, 내가 출력한 답을 b라 하고, 실제 답을 a라 하면 abs(b-a)의 값이 x이면 정답이라는 의미입니다. 1008번 문제를 보도록 할게요. a/b를 출력하라고 하는데요. 절대 오차 또는 상대 오차가 10^(-9) 이하이면 정답이라고 해요. a = 4, b = 3을 입력받았어요. float로 받아서 float 형식으로 출력했어요. 1.3333333731이 출력되네요. 실제 답은 1.3333333333... 인데..
자료알고/알고리즘 2022. 1. 31. 22:16
롯데 자이언츠와 가희 : 벤다이어그램을 그려서 도식화 시켜 봅시다.

이번 시간에는 오랫만에 코딩 테스트가 아닌, 제가 출제한 문제에 대해서 간단하게 해설해 보겠습니다. 사실, 이 문제는 선린고 대회 문제로 출제하려고 했지만, 모종의 이유로 반려된 문제입니다. 그렇지만, 백준에 낼 가치는 충분히 있다고 판단되어 올리게 되었습니다.이 자리를 빌어, 제 문제를 검수해 주신 분들에게 감사드립니다. 아마, 이 블로그의 글들을 유심히 보셨던 분들이라면 제가 키움과 롯데 자이언츠 팬임은 아실 수 있을 겁니다. 이 문제에 나타난 7월 28일을 제가 굳이 언급한 이유는 쓰리런으로 끝내기를 치신 그 분 때문입니다. 각설하고 가희가 9회 말을 보기 위해 풀어야 하는 수학 문제를 보도록 합시다. n개의 수가 최소 공배수가 L이고, 최대 공약수가 G인 가짓수를 구해야 하는 게 목표입니다. 보기..
자료알고/알고리즘 2021. 11. 24. 23:39
트리 dp : 스크루지 민호 문제로 간단한 것만 풀어 봅시다.

tree dp는 최근에 코테에 나왔습니다. 그래서 트리 dp 2 문제를 준비해 보았습니다. 스크루지 민호 시리즈는 이들을 연습하기 좋은 셋트이기 때문입니다. 트리 탐색이나, dfs에 대한 기본적인 이해가 있다고 가정하고 진행하겠습니다. 먼저, 이 문제부터 보겠습니다. 왜 1부터 안 푸냐. 사실 해당 방법으로 풀기는 2가 1보다는 쉽기 때문입니다. 트리가 이렇게 있어요. 문제 조건을 잘 보시면, 양방향 간선에 연결되어 있는 도시 2개 중에 최소 하나 이상은 경찰서가 있어야 함을 알 수 있어요. 그러면 현재 cur에 경찰서를 세운 경우와 그렇지 않은 경우로 나눌 수 있음을 알 수 있어요. 먼저, cur에 경찰서를 세우지 않은 경우를 생각해 봅시다. 그러면, 자식 도시들은 모두 경찰서를 세워야 합니다. 만약에..
자료알고/알고리즘 2021. 4. 25. 20:24
백준 배열 돌리기 5 : 전략적인 브루트 포스로 풀어봅시다.

배열 돌리기 5는 solved 난이도로 골드 1인 문제입니다. 200만개의 쿼리를 브루트 포스하게 실행시키면, 시간초과가 나는 것은 당연해 보입니다. 높이가 100, 너비가 100인 배열을 어떻게 압축을 시키면 좋을까요? 문제가 되는 것은 5번, 6번임을 알 수 있습니다. 가로로 반, 세로로 반을 나눠서 처리해야 하기 때문입니다. 사실 그것만 없었다면, 그냥 시점만 이동해서 풀 수 있었을 겁니다. 일단, 제 풀이는 브루트 포스입니다. 그런데, 100 by 100 전체를 브루트 포스를 하지 않습니다. 데이터를 압축하는 것이 목표입니다. 어떻게 잘 압축을 할까요? 배열 S가 아래와 같이 있다고 해 보겠습니다. 5, 6번 연산 때문에 이렇게 나누었다는 것을 눈치채셨을 겁니다. 이 4개의 영역 중에, 모서리 부..
자료알고/알고리즘 2021. 4. 4. 03:29
펜윅 트리 (fenwick tree) : 구간합을 빠르게 구한다.

펜윅 트리는 구간합을 구할 때 상수를 줄이기 위해 이용할 수 있는 구조입니다. 유성 문제는 세그먼트 트리 대신에 펜윅을 써야 풀리는 문제로 유명한데요. 시간 복잡도의 특성상 상수를 줄여야 하는데, 레이지를 이용한 세그 트리는 느리기 때문입니다. 이게 어떤 식으로 동작하는지 보고, 간단하게 코드를 작성해 보도록 하겠습니다. 펜윅 트리는 다음과 같이 그릴 수 있습니다. 이들은 각각 [1], [3], [5], [7]을 담고 있는 노드입니다. 규칙을 찾아보면, 1, 3, 5, 7은 1의 배수이지만 2의 배수는 아닙니다. 다음에 1, 3, 5, 7과 비교했을 때 구간의 크기가 2배인 2와 6이 있습니다. 이들의 구간 크기는 2이고요. 각각 구간 [1, 2], [5, 6]을 담고 있습니다. 이 둘의 공통점은 2의 ..
자료알고/자료구조 2021. 3. 14. 00:37