반응형 Algorithm/Stack & Queue7 [스택/큐] 캐시 - 2018 KAKAO BLIND RECRUITMENT 이 문제는 LRU(Least Recently Used) 알고리즘을 구현하는 문제다. 해결 방법 LRU 알고리즘은 가장 오랫동안 사용되지 않은 요소를 제거하는 교체 알고리즘이며, 필자가 구현한 방법은 다음과 같다. 먼저, 큐에 있는 요소들을 pop해가며, cache hit이 발생한 요소를 제외하고 모두 임시 큐로 옮겨놨다가 다시 기존 큐로 옮긴다. cache hit이 발생했다면 cache hit이 발생한 요소는 큐의 맨 뒤에 push한다. 만약 cache hit이 발생하지 않았다면 새로운 요소를 큐에 넣어야 하는데, 그 전에 cacheSize를 따져서 큐가 모두 찼다면 가장 오래된 요소를 제거해두면 된다. 마지막으로 cache hit의 여부에 따라 cache hit이 발생했다면 answer에 1을 더하고,.. 2022. 7. 5. 삽입, 삭제 모두 O(logn)!! STL priority_queue 소개 priority_queue는 큐에 데이터가 삽입, 삭제 되어도 데이터들의 우선순위를 유지해주는 라이브러리이다. priority_queue는 힙 구조로 구현되므로 삽입과 삭제의 시간 복잡도는 O(logn) 밖에 되지 않는다. 프로그래머라면 O(n)과 O(logn)의 차이가 얼마나 큰지 알고 있을 것이다. 후자는 거의 상수 취급 하기도 할 정도로 시간복잡도를 매우 단축할 수 있다. 힙 구조에 대한 자세한 설명은 아래 링크를 보면 좋다. ko.wikipedia.org/wiki/%ED%9E%99_(%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0) 힙 (자료 구조) - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 1부터 100까지의 정수를 저.. 2020. 9. 16. 스택/큐 고득점 kit 풀이 완료, 후기 스택은 데이터를 후입선출(LIFO) 구조를 유지하는 자료구조, 큐는 데이터를 선입선출(FIFO) 구조를 유지하는 자료구조이다. 이를 물론 배열/벡터와 인덱스 변수만으로 구현 할 수도 있다. 그리고 C++에서는 라이브러리를 제공한다. 데이터는 push함수로 넣고 pop함수로 뺄 수 있다. 스택과 큐 라이브러리는 빈 상태(empty) 여부를 판단하는 empty함수도 제공하고 스택의 front 함수, 큐의 top 함수로 가장 앞에 있는 데이터도 확인 할 수 있다. 이 라이브러리를 사용하여 코드도 줄이고 가독성도 올리는 것을 추천한다. 고득점 kit에 있는 스택/큐 문제들도 해결하기 까지 어느정도 생각이 필요했지만 전반적으로 어렵지 않게 풀 수 있었다. 문제모음 [난이도 하] 주식 가격 kimcoder.tist.. 2020. 9. 16. [스택/큐, 난이도 하] 프로그래머즈, 주식가격 이 문제는 맞추고도 당황했다. prices의 길이는 최대 100000인데 prices의 길이에 대한 이중 반복문을 사용했는데 효율성까지도 만점을 받았다. 그래서 난이도를 '하' 로 정했다. 뒤의 요소들을 탐색하면서 시간을 계속 더해주되, 주식가격이 현재가격보다 아래가 되는 경우 바로 break를 해줘서 그런 것 같은데, 테스트 케이스들이 최악의 경우 까지는 고려를 안해서 그런 것 같다. prices의 길이가 100000이고, 주식 가격이 계속 오르기만 하는 경우에서 최악의 시간 복잡도가 나올 것이다. 현재의 주식 가격과 그 다음의 주식 가격의 관계만 신경 쓰면 되므로 이 문제에서 요구하는 것은 스택이라고 볼 수 있다. 벡터와 인덱스 변수만으로도 스택을 흉내낼 수 있기도 하고 벡터를 이용하는 것이 소스 코.. 2020. 9. 16. [스택/큐, 난이도 중하] 프로그래머즈, 기능개발 먼저 배포되어야 하는 작업의 순서가 정해져 있는 것을 보아 큐를 이용하여 푸는 문제임을 알 수 있었다. 이번엔 큐 라이브러리를 이용하지 않고 현재 작업중인 작업 번호 변수를 만들어 큐의 역할을 흉내냈다. 큐를 이용한다면 입력 vector의 요소들을 큐에 모두 넣는 작업이 필요한데 굳이 그럴 필요까진 없었기 때문이다. 앞에 있는 task의 진도율이 100이 아닌 경우, 100이 나올 때 까지 계속해서 현재 진도율에 speed값을 더해준다. 반복할때마다 날짜는 1씩 더해준다. 그리고 앞에 있는 task의 진도율이 100을 달성 했을 경우, 한번에 배포할 수 있는 작업수와 작업 번호를 모두 1씩 증가시켜주면 된다. 그 뒤에 있는 task들에도 날짜와 speed를 곱한 값을 더해보고 진도율이 100을 달성 했을.. 2020. 9. 15. [스택/큐, 난이도 중하] 프로그래머즈, 다리를 지나는 트럭 트럭은 1초에 최대 1번 다리에 들어올 수 있고, 최대 1번 나갈 수 있다. 즉 초를 세는 변수를 만들고, 반복문 안에 트럭이 다리에 들어오는 조건문과 나가는 조건문을 하나씩 세워주면 된다. 제일 앞에 있는 트럭의 입장 시각이 현재 시각에 다리의 길이를 뺀 값이 되면, 누적 무게에서 이 트럭의 무게를 빼고 queue에서 pop시켜주고 누적 무게에 가장 앞에 대기중인 트럭의 무게를 더해봐서, 제한 무게를 넘어가지 않는다면 queue에 push 해주면 된다. queue 안에 들어있는 pair 정보는 트럭의 무게와 입장 시각이다. 테스트 케이스 14개 모두 통과 #include #include using namespace std; int solution(int bridge_length, int weight, .. 2020. 9. 14. [스택/큐, 난이도 중하] 프로그래머즈, 프린터 문제의 조건을 보고 스택,큐중 어느 것을 요구하는지 파악해보자. 1. 인쇄 대기목록의 가장 앞에 있는 문서(J)를 대기목록에서 꺼냅니다. 2. 나머지 인쇄 대기목록에서 J보다 중요도가 높은 문서가 한 개라도 존재하면 J를 대기목록의 가장 마지막에 넣습니다. 3. 그렇지 않으면 J를 인쇄합니다. '앞', '마지막' 이라는 단어가 나오는 것을 보아 큐 문제임을 알 수 있다. 그리고 둘 이상의 문서끼리 중요도가 같을 수 있고, 문서의 인덱스까지 신경써줘야 하는 문제이다. 그래서 큐에 문서의 중요도, 인덱스 두 정보를 pair을 이용해 정리했다. 문서는 최대 100개 있고, 중요도는 1~9의 정수로 표현할 수 있다. J보다 중요도가 높은 문서를 찾기 위해 큐에 있는 모든 요소를 확인하는 것 보다는, 중요도별로 .. 2020. 9. 9. 이전 1 다음
