개발일지

https://programmers.co.kr/learn/courses/30/lessons/68937 코딩테스트 연습 - 트리 트리오 중간값 5 [[1,5],[2,5],[3,5],[4,5]] 2 programmers.co.kr 접근 1. 트리의 지름을 구할 수 있는 임의의 정점을 찾고 해당 정점과 다른 정점들 사이의 거리 중 2번째로 큰 값을 반환했다. => 12번 테스트 케이스에서 오답. 1번의 반례 위와 같은 그래프는 A-B를 통해 트리의 지금을 구할 수 있다. 해당 경우 A와 다른 정점들 사이의 거리 중 2번째로 큰 값을 반환한 값보다 (A, B, C)의 중간값이 더 크다. => 트리의 지름을 d라고 할 때 정점들 사이의 거리 중 d가 2개 이상 나올 수 있는 경우를 놓쳤기 때문에 1번 풀이법은 옳..

https://programmers.co.kr/learn/courses/30/lessons/1838 코딩테스트 연습 - 몸짱 트레이너 라이언의 고민 4 5 [[1140,1200],[1150,1200],[1100,1200],[1210,1300],[1220,1280]] 4 programmers.co.kr 접근 그리디하게 최대로 사람이 몰리는 시점에 사람이 몇명인지 파악하고 격자판에 그 사람을 배치하면 된다. => 사람이 많은 시점이 사람이 적은 시점보다 거리가 멀기 때문 1) 규칙성 격자판으로 채울 경우((n*n + 1)/2 == people)인 경우) 거리가 2, 그 이상은 거리가 1이라고 할 수 있다. 그 외에 경우 규칙성을 찾으려 했지만 실패 2) 분할정복 & DP people이 1이면 0 (문제 조건..

개념 위 그림은 911, 91125, 97625 저장했을 때 트리의 예시이다. 트라이는 문자열을 효율적으로 관리하기 위한 트리구조이다. 접두사를 노드에 하나씩 저장하고 접두사를 제외한 문자열을 자식 노드에 저장하는 트리구조이다. (접두사를 저장한다고 해서 Prefix Tree라고도 불림) 작동원리 문자열의 앞부터 차근차근 트리를 탐색하여 문자를 찾기 때문에 검색 속도는 빠르지만 각 노드별로 모든 문자를 저장할 배열이 필요하기 때문에 메모리가 많이 든다. * 메모리 크기 : 포인터 크기 * 배열의 길이(저장하는 문자의 수) * 총 노드의 개수 시간 복잡도 저장 : O(L) 검색 : O(L) 문제 www.acmicpc.net/problem/5052 5052번: 전화번호 목록 첫째 줄에 테스트 케이스의 개수 ..