개발자 노트

문제설명 트라이로 접근하는 것. 전화번호 중 동일한 접두어가 존재하면 NO를, 존재하지 않으면 YES를 반환한다. 접근 TRI 이용 완전탐색으로 접근하지 않는 이유 완전탐색으로 접근하면 시간복잡도는 엄청나다. 매 테스터케이스마다 N개의 전화를 N!번 비교하여 min(P1,P2)만큼 비교해야 하므로 O(T*N*N!*P)이다. (T는 테스트케이스 수, N은 전화번호 수 P는 전화번호의 자리 수) 따라서 최악의 경우 연산량은 50*10000*10000!*10이 된다. tri접근시 공간복잡도 고려 0~9까지 10개의 수 표현을 10개 표현해야하므로 10^104byte(int선언 기준)가 된다. 256MB를 넘지만, 미리 10개를 다 선언하지 않고 있을 때마다 선언하면 공간복잡도는 많이 줄어든다. n이 10000..

문제설명 구현문제. rotate는 삼성 기출 중 톱니바퀴라는 문제가 있다. 이를 참고하면 좋을 듯. 총 문제 풀이시간은 2시간 10분으로 접근 방법 정하기 및 절차 작성 => 30분소요 구현 1시간 30분 소요 첫 코드 작성 40분소요 rotate 디버깅 30분 소요(;; 절망적.) 인접 부분 잘못 고려하여 20분 소요 접근 문제의 큰 틀 접근 자체는 크게 어렵지 않아 보였을 것이다. 그나마 포인트가 될 것은 다음과 같다. 1)인접하다 원형을 단순히 테이블로 변형하여 인접을 고려하는데 큰 어려움이 없을 것이다. 다음 부분만 제외하고. i번째 원을 기준으로 1번째의 왼쪽인 M번째 수. M번째의 오른쪽인 1번째 수. 이것이 인접하다는 것만 고려해주면 큰 문제는 없다. 2)원판에 동일한 수가 있다면 삭제하는 ..

문제설명 아주 기초적인 BFS문제. 최단거리를 찾아라. 접근 카카오2020 신입공채 블록이동하기 문제를 풀다가 아주 복잡하게 최단경로 문제를 풀고 있는 것 같아 이 문제를 살펴보았다. 접근1 개별의 이동에 대해 방문정보를 가지고 있어서 모두 탐색하도록 정했다. (1,1)에서 (2,1)이동가능하면 (2,1)노드와 함께 방문정보 (1,1),(2,1)을 que에 넣어준다. (1,1)에서 (1,2)이동가능하면 (2,2)노드와 함께 방문정보 (1,1),(1,2)를 que에 넣어준다. (2,1)과 (1,2)모두 (2,2)이동이 가능하므로 각각의 방문에 (1,1),(2,1),(2,2), (1,1),(1,2),(2,2)를 que에 넣어준다. 굵은 표시에 있는 내용을 보면 '최단거리'를 구하는 문제이므로 ..

문제설명 간단히 말하여 높이가 서로 다른 탑들이 주어졌을 때 탑 꼭대기 왼쪽방향에 해당 탑보다 큰 탑이 존재하면 해당 탑의 번호를(1부터 시작), 없으면 0을 출력한다. 문제를 이해하는데 있어 중요한 내용은 1.탑의 높이는 중복없음. 2.탑의 수는 50만이하 탑의 높이는 1억이하이다. 접근 아이디어가 곧바로 떠오르지 않아 예제를 통해 어떻게 접근할 지 결정하고자 했다. 예제 : 6 9 5 7 4 1.6기준 왼쪽에 탑이 없으므로 0출력 2.9기준 6은 낮으므로 또 0 출력 3.5기준 9가 높으므로 9의 번호인 2번 출력 4.7기준 왼쪽에 있는 5는 낮으나, 9가 만나 2추력 5.4기준 7을 만나 그 번호인 4출력. 위를 봤을 때 관심의 대상이 되는 빌딩기준 왼쪽에 더 큰 빌딩이 있는지 봐야하는데 단계가 지..