반응형 전체 글162 프로그래머스 - 파일명 정리 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/17686# 코딩테스트 연습 - [3차] 파일명 정렬 파일명 정렬 세 차례의 코딩 테스트와 두 차례의 면접이라는 기나긴 블라인드 공채를 무사히 통과해 카카오에 입사한 무지는 파일 저장소 서버 관리를 맡게 되었다. 저장소 서버에는 프로그램 programmers.co.kr 문제 풀이 각각의 파일을 돌며 숫자가 나오기 전까진 head, 숫자가 나온 뒤부터는 number로 넣어준다. 숫자의 크기는 최대 5이다. 모두 추출하였으면 pair형태의 string, int로 넣어주고 다시 pair를 선언하여 앞에는 인덱스를 붙여준다. 즉, pair의 형태가 된다. 다음으로, 정렬을 위한 compare 함수를 만들어준.. 2022. 3. 18. 다익스트라 알고리즘 다익스트라 알고리즘은 그래프에서 최단 경로 문제를 해결할 수 있는 알고리즘 중 하나이다. 최단 경로 문제이므로 각 간선에는 가중치(거리)가 존재하며, 가중치가 음수인 간선이 존재한다면 다익스트라 알고리즘을 사용할 수 없다. 이해를 위해 아래의 예시를 살펴보자 1번 노드부터 모든 경로의 최단거리를 구하려고 한다. 1번 노드에서 본인의 거리는 0이므로 0으로 업데이트한 뒤 나머지 노드까지의 거리는 무한대로 설정한다. 다음으로 1번과 연결된 노드들과의 거리를 업데이트해준다. 연결된 모든 노드들의 거리를 구했으면 가장 짧은 경로로 이동한다. 따라서 위의 예시에서는 5번 노드를 방문하여 다시 거리를 계산한다. 즉, 원래의 distance[4]는 9이지만 distance[5] = 1과 5에서 4로 이동하는 거리 2.. 2022. 3. 17. 프로그래머스 - 이중우선순위큐 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 풀이 그대로 구현하면 돼서 간단한 문제이지만 한 가지 문제가 있다. min heap과 max heap을 각각 선언하여 각각의 최솟값 최댓값을 pop하는 방식으로 구현했을 때 각 힙에 3을 넣고, -3을 넣은 뒤 최솟값 pop 최댓값 pop을 하게 되면 maxHeap에는 -3이 남아있을 것이고 minHeap에는 3이 남아있을 것이다. 하지만 원래는 모든 힙에는 원소가 없어야한다. 이를 방지하기 위해 카운트 변수를 생성하여 원소에 삽입할 때에는 증가, 삭제할 때에는 감소시켜준다. 따라서, 카운트가 0일 때에는 모든 큐가 비워지도.. 2022. 3. 16. 프로그래머스 - 디스크 컨트롤러 / C++ 문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/42627# 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 풀이 문제의 예시에서 평균 시간을 줄이는 법을 설명하였다. 간단히 요약하면 요청 순으로 수행하다가 소요 시간이 더 짧은 것이 들어오면 해당 작업을 다음으로 수행한다. 이 과정에서 우선순위 큐를 이용하면 된다. 먼저 요청 순으로 수행하기 위해 jobs 배열을 정렬한다. 다음으로 pair 형태를 가지는 우선순위 큐를 선언한다. 추후에 first.. 2022. 3. 15. 이전 1 ··· 11 12 13 14 15 16 17 ··· 41 다음 반응형
