알고리즘 검색 결과

해당 글 86건
가희와 프로세스 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
가희와 비행기 문제를 카탈란 수로 구해 봅시다.

안녕하세요. 오랫만입니다. 이번 시간에는 제가 출제한 가희와 비행기 문제를 보도록 하겠습니다. 문제를 다 이해하셨다면, 구하려고 하는 것은 그리 어렵지 않음을 알 수 있습니다. 김포 공항에서 김해 공항까지 수평 거리가 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가 아닐 때, ..
알고리즘/ps 2022. 1. 6. 23:15
반응형