알고리즘 검색 결과

해당 글 87건
실수 오차의 무서움과 가희와 방어율 무시

가희와 방어율 무시 문제는 상당히 쉬운 문제였습니다. 그럼에도 불구하고 정답률이 그렇게 높지 않았는데요. 실수 오차 때문에 고전하는 경우가 상당히 많이 있었습니다. 이와 비슷한 이슈가 있었던 문제 중 하나는 가희와 btd5가 있었습니다. 먼저, 오답 코드는 위와 같습니다. 물론, 백준 질문에도 올라왔던 코드입니다. 어느 케이스에서 틀렸을까요? 500 80에서 제대로 답을 출력하지 못합니다. 왜 그럴까요? 실수 오차 때문이다. 라는 것을 누구나 알 수 있습니다. 어떠한 과정에서 잘못된 결과가 나왔는지 하나씩 보겠습니다. 먼저 1, b/100, c에 대해서 bit 값을 출력해 보겠습니다. 저는 memcpy 등으로 변수를 배열에 복사한 뒤에, 저장되어 있는 값의 bit를 하나씩 꺼내왔습니다. 저는 b, b/1..
알고리즘/ps 2022. 9. 5. 01:00
가희와 프로세스 2 : 관점을 바꾸어서 이분 탐색을 적용해 봅시다.

안녕하세요. 팀 codingdog입니다. 1회에 출제된 문제 중 가장 어려웠던 문제는 가희와 프로세스 2 문제였는데요. 대회 당시에 단 2분만 푸셨을 정도로 쉽지 않은 문제였습니다. 어떤 점이 발목을 잡았는지, 그래서 어떻게 접근을 해야 했는지만 보겠습니다. 먼저 기본 아이디어는 가희와 프로세스 1 문제와 동일합니다. 나머지 프로세스의 우선순위가 1 상승하는 것을 상대적인 관점에서 생각한다. 즉, 현재 실행되고 있는 프로세스가 실행되면, 우선순위가 1 하락한다. 달라보이지만, '상대적'인 관점에서 생각하면 똑같은 말입니다. 어렵지 않죠? 문제를 요래 변형하는 게 첫 번째 포인트입니다. 이 부분은 2회의 가희와 거북이 인형 문제에서도 교과서에 나온 개념 그대로 연계해서 출제한 적이 있습니다. 예제 1번을 ..
알고리즘/ps 2022. 2. 21. 01:01
백준에서 자주 보이는 절대 오차 상대 오차에 대해 간단하게 알아봅시다.

이번 시간에는 백준에서 문제를 푸실 때 많이 보이는 절대오차, 상대오차에 대해서 간단하게 짚고 넘어가도록 하겠습니다. 먼저 모범 답안과의 절대 오차가 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가 된다고 되어 있는데 이것을 구현해 보라는 목적도 있었고요. 제한을 ..
알고리즘/ps 2022. 1. 28. 17:01
bfs나 dfs에서 component를 왜 구하는지 알아보고 응용해 봅시다.

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