안녕하세요. 팀 codingdog입니다. 1회에 출제된 문제 중 가장 어려웠던 문제는 가희와 프로세스 2 문제였는데요. 대회 당시에 단 2분만 푸셨을 정도로 쉽지 않은 문제였습니다. 어떤 점이 발목을 잡았는지, 그래서 어떻게 접근을 해야 했는지만 보겠습니다. 먼저 기본 아이디어는 가희와 프로세스 1 문제와 동일합니다. 나머지 프로세스의 우선순위가 1 상승하는 것을 상대적인 관점에서 생각한다. 즉, 현재 실행되고 있는 프로세스가 실행되면, 우선순위가 1 하락한다. 달라보이지만, '상대적'인 관점에서 생각하면 똑같은 말입니다. 어렵지 않죠? 문제를 요래 변형하는 게 첫 번째 포인트입니다. 이 부분은 2회의 가희와 거북이 인형 문제에서도 교과서에 나온 개념 그대로 연계해서 출제한 적이 있습니다. 예제 1번을 ..
ps 검색 결과
안녕하세요. 오랫만입니다. 이번 시간에는 제가 출제한 가희와 비행기 문제를 보도록 하겠습니다. 문제를 다 이해하셨다면, 구하려고 하는 것은 그리 어렵지 않음을 알 수 있습니다. 김포 공항에서 김해 공항까지 수평 거리가 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가 아닐 때, ..
가희배 코딩테스트 1회에서 나온 7번 문제는 가희와 프로세스 문제의 결과값이 주어졌을 때, 거꾸로 인풋 값을 만들어 보라는 문제였습니다. 항상 가능한 경우만 주었기 때문에 쉬울 거라고 생각했습니다. 그런데, 실제로 대회 때 문제를 푸신 분들은 그리 많지 않았고 골드 1로 평가되는 기염을 토하게 되었습니다. 사실 불가능한 경우까지 출력하라고 했는데, 진짜 그렇게 출제 했다면 100% 플레급으로 뛰었을 거라 생각합니다. 그러면 무엇이 이렇게 어렵게 만들었을까요? 문제에서 설명하는 알고리즘을 단순화 하는 것이 제일 어렵지 않았나 싶습니다. 게다가 실행 결과를 가지고 가능한 입력값을 만들라고 하니 당황할 수 밖에 없었을 겁니다. 사실 제가 맞닥트렸어도 매우 당황했을 겁니다. 일단, 가희와 프로세스의 나온 입력 ..
이번 시간에는 Longest Substring Without Repeating Characters 문제를 풀어보면서, 어떻게 시간 복잡도를 분석하는지 보도록 하겠습니다. 이 문제는 길이가 5만 이하인 문자열에서, 문자가 반복되지 않는 가장 긴 부분 문자열을 찾는 문제입니다. 문자열에 들어갈 수 있는 문자는 알파벳, 숫자, symbol, 그리고 space 문자입니다. 보통, 이렇게 주기 보다는 CodePoint는 아스키 코드 범위 내에 있다. 혹은 유니코드 범위 내에 있다. 이런 전제를 까는 게 더 좋기는 한데 넘어가 봅시다. 이모지 같은 것들 때문에 태클이 들어올 여지가 있습니다. 저 또한 문제 제작했을 때 간과했던 부분이기도 합니다. 문자열에 들어갈 수 있는 문자 집합이 작을 때에는 어떨까요? 놀랍게도..
얼마전에 추가된 tony님 문제를 풀었습니다. 필수 유형들과 어려운 유형들이 몇 개 있는데요. 알아가면 좋을 법한 트릭을 하나씩 소개해 드리겠습니다. 먼저 산책 시리즈입니다. large나 small이나 별 다른 건 없으니, 풀어보도록 합시다. 문제를 읽어보면, 제일 중요한 것은 딱 하나임을 알 수 있어요. S에서 E로 갈 때 최단 거리가 여러개 있다면 사전 순으로 가장 앞선 것을 택해라. k번째는 훨씬 어려워서, 사전순으로 가장 앞선 것을 택하라고 했을 겁니다. 그러면 어떤 정보가 필요할까요? 즉, 모든 i에 대해서, e까지의 최단 거리를 구해야 함을 알 수 있어요. 이런 그래프가 있고, s가 1, e가 4라고 해 봅시다. 처음에 우리는 1에서 4까지 가는 최단 경로 중에 사전순으로 앞선 경로를 구해야 ..
최근댓글