본문 바로가기

전체 글533

[알고리즘] 징검다리 건너기 (프로그래머스 Level3) 코딩테스트 연습 - 징검다리 건너기 [2, 4, 5, 3, 2, 1, 4, 2, 5, 1] 3 3 programmers.co.kr 우선 stones 배열의 최대 크기가 20만이기 때문에 O(N) 시간 만에 처리를 해야 한다. Solution 친구들이 뛰어넘을 수 있는 길이는 K만큼이라고 했으니 어느 구간이라도 연속 K개의 돌이 0이 되는 순간 친구들은 더 이상 다리를 건널 수 없다. 즉 배열에 존재하는 K 길이만큼의 구간들 중, 각 구간마다 포함하고 있는 돌의 최댓값이 모든 구간들 중 최솟값이 되는 경우를 찾아야 한다. 이게 무슨 말이냐면 위의 예시 문에서의 K는 3이다. 해당 배열에서 길이가 3인 구간은 총 8개가 나온다. Start Index Finish Index Max Value 0 2 5 1 3.. 2020. 9. 9.
[알고리즘] 이중우선순위큐 (프로그래머스 Level3) 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 기본적으로 우선순위큐는 Heap을 통해서 구현된다. 하지만 자바에는 기본적으로 PriorityQueue가 구현이 되어있으므로 우선순위큐 자체에는 신경쓸 필요가 없고, 이중우선순위큐라는 점에 주목해야한다. 이 말인 즉슨, 한 큐에서 최대값을 반환, 최소값을 반환하는 두 가지 작업이 동시에 가능해야된다는 점이다. Solution 우선 각각 최대값, 최소값을 반환하는 PriorityQueue 2개를 만들었다. 하지만 데이터를 삭제할 때, 2개의 큐를 모두 동기화시킬 필요가 있다. 때문에 HashMap을 사용했다. HashMap의 Key값은 삽입된 데이터, Value는 현재 큐에 들어있는 해당 데이터의 개수를 의미한다. 이 후에 삽입 때는 특별한.. 2020. 9. 8.
[자료구조] 이진 트리 (Binary Tree) 이진 트리 (Binary Tree) 모든 노드의 차수가 2 이하인 트리 ​ 이진 트리 종류 1. 포화 이진 트리 (Full Binary Tree) 모든 레벨의 노드가 꽉 차있는 이진 트리 n = 2 ^ h - 1 ( 높이가 h 인 이진 포화 트리의 노드 개수) ​ 2. 완전 이진 트리 (Complete Binary Tree) 높이가 h 일 때, 레벨1 ~ 레벨 h-1까지는 포화 이진트리처럼 꽉 채워져 있고 마지막 레벨 h(단말 노드) 에서는 중간에 빈 노드 없이 노드가 왼쪽부터 차례로 채워져 있어야함. n < 2 ^ h - 1 (높이가 h인 완전 이진 트리의 노드 개수) ​ 3. 편향 이진 트리 (Skewed Binary Tree) 같은 높이의 이진 트리 중에서 최소 개수의 노드 개수를 가지면서 왼쪽 혹.. 2020. 9. 8.
[안드로이드 이슈] AndroidX의 RecyclerView 사용 시 layoutManager를 무조건 설정 해줘야 정상적으로 표시됨 2020. 9. 8.

티스토리툴바