자료구조3

• 

  백준 - 가운데를 말해요 문제 설명 숫자를 입력 받을 때마다 중앙에 위치한 값을 출력하는 문제이다. min, max Heap 을 이용한다. maxHeap에는 작은 수를 min힙에는 큰 수를 넣어준다. (이름과 반대로 된 value들을 집어넣어준다.) 이렇게 minHeap에는 큰 값이 뒤로 밀려나고 maxHeap에는 작은값이 뒤로 밀리게 되면서 중앙값을 minHeap의 머리 또는 maxHeap 머리에 위치하게 된다. 그러면 이제 두 힙중에 어떤게 중앙값인지 선별해야 한다. 두 heap size()를 고르게 분포하기 위해 같은 Heap 사이즈를 갇는다면 max힙으로 몰아준다.(min으로 몰아줘도 상관없음) maxHeap이 더많다면 minHeap으로 이동한다. 이렇게 되면 maxHeap으로 이동한 혹시모를 큰수가 maxHeap에 머리.. Algorithm/백준 2023. 4. 29.

• 

  프로그래머스 - 행렬과 연산 문제 설명 행렬이 주어진다. 주어진 연산에 의해 행렬이 이동하고 난 후 결과를 출력하는 단순한 문제이다. 하지만 이문제는 효율성 측정되는 문제라 최적화를 생각해야한다. shiftRow, rotate 두가지 명령만이 존재한다. 일반적인 시뮬레이션으로 구현하면 shiftrow는 최대 n *m 번의 연산이 필요하고 rotate는 n+m-2번이 필요하다. 그리고 명령어는 최대 10만이라 정확성은 통과할지라도 효율성은 당연히 실패한다. 최적화하기에 시도했던 방법은 연산의 일부를 합치면 최적화가 가능한가 그려봤다. 하지만 나오지 않았다. 2022 테크 여름인턴십 코딩테스트 해설 해당 내용을 참고하였더니 자료구조의 쓰임을 잘 알고있는지 체크하는 문제였다. 각각을 단순한 시물레이션이아닌 자료구조의 최적화를 유도했던 문.. Algorithm/프로그래머스 2023. 4. 8.

• Array vs Linked List Array 논리적 저장 순서와 물리적 저장 순서가 일치.(index를 활용하여 해당 element에 접근 할 수 있다.) 해당 원소에 인덱스를 알고 있으면 O(1)이라는 시간 복잡도를 갖는다. Random Access가 가능하다. 하지만 삭제 또는 삽입과정에서 비용이 많이 발생한다. 해당 원소의 삽입 과정에서 맨 뒤의 경우를 제외하고 원소들이 있는 처음 또는 중간에 넣게 된다면 삽입할 공간을 만들기 위해 해당 원소들이 뒤로 이동해야하는 비용이 발생한다. 해당 원소의 삭제 과정에서 해당 원소를 삭제 한 후 빈 공간이 생긴다. 이 빈 공간을 매우기 위해 빈 공간 다음으로 이어지는 원소들을 한 칸씩 앞으로 떙겨야 하므로 비용이 발생한다. 비용에 대한 시간 복잡도는 O(n) 이다. Linked List 배열에 .. CS/DataStructure 2021. 3. 30.