자료알고 검색 결과

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

이번 시간에는 백준에서 문제를 푸실 때 많이 보이는 절대오차, 상대오차에 대해서 간단하게 짚고 넘어가도록 하겠습니다. 먼저 모범 답안과의 절대 오차가 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
가희와 쓰레기 놀이 : 메타 정보를 잘 저장해서 효율적으로 구현해 봅시다.

이번 3회 코테에서도 어김없이 3번 문제에는 cs가 나왔습니다. 그런데, 기존 3번 문제는 골드 5로 평가되었던데 비해, 3회 3번은 얘네들보다 난이도가 높았습니다. 가희와 쓰레기 놀이는 어떤 문제였는지, 출제 목적이 무엇이였는지부터 상세하게 설명을 하면서 풀이를 작성하도록 하겠습니다. 먼저, 이 문제를 가져오게 된 계기는 그리 어렵지는 않았습니다. 이 글에서도 간접적으로 볼 수 있긴 하지만, 결정적인 계기는 logback의 MDC를 보다가 threadLocal을 보게 되었고, 그 안에 있는 WeakReference를 보게 된 것이 결정타였습니다. gc가 약하게 도달 가능한 객체들을 모두 지워야 겠다는 판단을 했을 때, finalize가 된다고 되어 있는데 이것을 구현해 보라는 목적도 있었고요. 제한을 ..
자료알고/알고리즘 2022. 1. 28. 17:01
bfs나 dfs에서 component를 왜 구하는지 알아보고 응용해 봅시다.

오랫만입니다. 가희와 함께 하는 3회 코딩 테스트 때문에 작년 연말부터 글이 꽤 뜸하게 올라왔습니다. 이것이 어제 끝났으니, 문제들을 하나 하나씩 리뷰해 보도록 하겠습니다. bfs나 dfs를 배우다 보면, 방향성이 없는 (다시 말해서, 양방향 간선만 있는) 그래프에서Component 라는 것이 나오게 됩니다. 이 문제가 대표적인 예입니다. 이것을 bfs나 dfs로 찾을 수 있다고 하는데요. 이것을 왜 찾을까, 찾아서 어디에 써 먹을 건지. 이 두 가지 의문에서 나온 것이 제가 출제한 가희와 베개 문제입니다. 아래 그림을 보면 Component는 2개가 있어요. 여기에 있는 간선들은 양방향으로 연결된 친구들입니다. 1번에서 bfs를 돌려 봅시다. 1번을 큐에 넣어볼까요? 그러면 큐에는 1만 들어가 있을 거..
자료알고/알고리즘 2022. 1. 24. 16:10
가희와 비행기 문제를 카탈란 수로 구해 봅시다.

안녕하세요. 오랫만입니다. 이번 시간에는 제가 출제한 가희와 비행기 문제를 보도록 하겠습니다. 문제를 다 이해하셨다면, 구하려고 하는 것은 그리 어렵지 않음을 알 수 있습니다. 김포 공항에서 김해 공항까지 수평 거리가 d일 때, 조건에 맞게 비행할 수 있는 가짓수를 구하는 것인데요. x인 지점에서 비행기의 고도가 h라고 해 보겠습니다. 그러면 x-1인 지점에서부터 고도가 1만큼 하강하거나, 혹은 고도가 1만큼 상승하는 이 두 가지 경우밖에 없습니다. 그래서, dp[x][h]를 x인 지점에서 고도가 h인 경우라고 정의하면, dp[x][h]는 dp[x][h-1] + dp[x][h+1]이 됩니다. 그런데, 예외가 있습니다. 중간에 착륙하는 경우는 없다고 했어요. 그렇기 때문에, x가 0이거나 d가 아닐 때, ..
자료알고/알고리즘 2022. 1. 6. 23:15
롯데 자이언츠와 가희 : 벤다이어그램을 그려서 도식화 시켜 봅시다.

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