코딩테스트 검색 결과

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

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

제가 개최한 코딩테스트 2회의 2번 문제는 가희와 키워드 문제였습니다. 메모장에 있었던 키워드는 해당 키워드에 대한 글을 쓰고 나면 지워지게 되는데요. 문제는 블로그에 글을 쓰고 난 후, 메모장에 남은 키워드는 몇 개인지를 묻는 것입니다. 이 문제의 원래 출제 의도는 string의 길이 제한을 잘 보고 압축을 해서, 문자열 비교하는 복잡도를 떨궈낼 수 있는 가였습니다. 문제 제한을 더 자세히 보겠습니다. 문제에서 등장하는 키워드의 총 개수는 200만개 이하입니다. 200만개에 대해서 메모장에 키워드가 있는지를 검사하면 되므로, treemap을 써도 괜찮아 보이긴 합니다. O(200만log50만)면 괜찮지 않을까요? 여기서 문제. treemap을 쓰면 문자열의 compareTo 함수는 얼마나 호출이 될까요..
구현 2022. 2. 25. 16:52
가희와 프로세스 2 : 관점을 바꾸어서 이분 탐색을 적용해 봅시다.

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

제가 개최한 1회 코딩테스트는 총 8문제가 있었습니다. 2, 3회에 비해 상대적으로 어렵지 않았는데요. 어디까지나 제가 개최한 코딩테스트 기준일 뿐이니 너무 자신감을 잃지 않으셔도 됩니다. 대회 당시에 맞은 분들 수를 보면, 4번부터 통곡의 벽처럼 다가오셨을 거 같습니다. 이 삼형제 중에 두 문제는 이미 풀이를 마쳤고요. 나머지 한 녀석이 가희와 자원 놀이라는 문제입니다. 세팅하는 데 1달이 넘게 걸렸습니다. 이 문제를 출제하기 위해 턴제 게임의 시스템도 다른 분들이 이해하실 수 있게 서술하기 위해 공부해야 했습니다. 제너레이터 몇 번 다시 재작업 하면서 겨우 출제했던 기억이 나네요. 이 자리를 빌어 검수진 분들에게 다시 한 번 감사 말씀을 올립니다. 이제, 이 문제를 풀기 위해서 어떻게 생각하셔야 하는..
구현 2022. 2. 14. 19:19
가희와 쓰레기 놀이 : 메타 정보를 잘 저장해서 효율적으로 구현해 봅시다.

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