꾸준함

문제 링크입니다: https://school.programmers.co.kr/learn/courses/30/lessons/142085 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr enemy 길이가 최대 백만이기 때문에 시간 복잡도 O(nlogn) 안에 풀어야 하는 것이 자명한 문제였습니다. O(nlogn)이라고 하면 제일 먼저 떠오르는 자료구조가 힙이였는데 다행히도 최소 힙으로 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 최소힙을 선언하고 enemy를 순서대로 넣어줍니다. 1.1 무적권은 k개이기 때문에 최소 힙의 크기는 k개 이하로 유..

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12920 코딩테스트 연습 - 선입 선출 스케줄링 처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니 programmers.co.kr 우선순위 큐를 이용하면 쉽게 풀 수 있을 것 같은 문제이지만 주어진 조건의 범위가 크기 때문에 힙을 이용할 경우 시간 초과가 발생하는 문제입니다. 해당 문제는 코어 당 작업을 처리하는 시간을 기준으로 최소 시간과 최대 시간을 구하여 해당 범위 내 파라메트릭 서치 기법을 이용하여 풀어야 시간제한 내 AC를 받을 수 있..

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12927 코딩테스트 연습 - 야근 지수 회사원 Demi는 가끔은 야근을 하는데요, 야근을 하면 야근 피로도가 쌓입니다. 야근 피로도는 야근을 시작한 시점에서 남은 일의 작업량을 제곱하여 더한 값입니다. Demi는 N시간 동안 야근 피로도 programmers.co.kr 최대 힙을 이용하여 쉽게 풀 수 있는 문제였습니다. 1. 최대 힙을 선언하고 모든 작업을 넣어줍니다 2. 반복문을 n번 돌리면서 제일 오래 걸리는 작업을 꺼내 시간을 1 감소시키고 다시 넣어줍니다. 2.1 시간이 0 미만으로 내려갈 수 없다는 점을 주의해야 합니다. 3. 힙에 있는 작업들을 모두 제곱한 결과를 반환합니다. 개발환경..

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42628 코딩테스트 연습 - 이중우선순위큐 programmers.co.kr 문제에서는 우선순위 큐 두 개를 사용하는 것을 원한 듯 하지만 set 자료구조를 이용하면 쉽게 풀 수 있는 문제였습니다. 알고리즘은 아래와 같습니다. 1. set을 생성하고 명령어가 I인 경우 set에 숫자를 삽입합니다. 2. 명령어가 D인 경우 아래와 같은 절차를 따릅니다. 2.1 최댓값을 삭제할 경우 set의 제일 뒤 숫자를 삭제하고 2.2 최솟값을 삭제할 경우 set의 제일 앞 숫자를 삭제합니다. 3. operations 벡터를 전부 순회할 동안 1번과 2번 과정을 반복하고 4. set이 비어있을 경우 {0, 0},..

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42627 코딩테스트 연습 - 디스크 컨트롤러 하드디스크는 한 번에 하나의 작업만 수행할 수 있습니다. 디스크 컨트롤러를 구현하는 방법은 여러 가지가 있습니다. 가장 일반적인 방법은 요청이 들어온 순서대로 처리하는 것입니다. 예를 programmers.co.kr 힙과 정렬을 이용하여 푸는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 작업을 시간순으로 정렬한 벡터를 생성해주고, 작업 소요시간이 짧은 순서가 우선순위를 갖는 힙을 생성해줍니다. 2. 초를 나타내는 sec 변수를 정의하고 0으로 초기화한 뒤, 2.1 1번에서 생성한 벡터 내 sec 이하인 작업들을 1번에서 생성한 pq에 넣어줍니다. ..

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/42626 코딩테스트 연습 - 더 맵게 매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같 programmers.co.kr 최소 힙을 이용하여 푸는 문제였습니다. 알고리즘은 아래와 같습니다. 1. 최소 힙을 생성해주고 scoville 벡터에 있는 값들을 전부 넣어줍니다. 이때, scoville 벡터에 있는 값들이 모두 K 이상일 경우 조건을 충족하므로 0을 반환해줍니다. 2. 문제 조건에 따라 음식을 섞어주고 음식을 섞은 뒤 모든 음식이 K 이상인지 확..

문제 링크입니다: https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1≤n≤50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 검은 방을 흰방으로 바꾼 횟수가 적을 수록 우선순위가 높은 우선순위 큐 자료구조를 활용하면 쉽게 풀 수 있는 문제였습니다. 일반적인 BFS 문제처럼 풀되 앞서 언급한 우선순위 큐로 BFS를 진행하시면 됩니다. 개발환경:Visual Studio 2019 지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

문제 링크입니다: https://www.acmicpc.net/problem/1261 우선순위 큐를 이용한 BFS(Breadth First Search) 알고리즘을 통해 푼 문제였습니다. 백준 13549번 숨바꼭질 3(http://jaimemin.tistory.com/583)과 유사한 문제였습니다.깨드린 블럭을 기준으로 우선순위 큐를 선언하여 BFS 알고리즘을 적용하면 쉽게 풀 수 있는 문제였습니다.*다익스트라 알고리즘을 통해서도 풀 수 있다고 합니다. #include #include #include #include #include #include using namespace std; const int MAX = 100; typedef struct { int y, x; }Dir; Dir moveDir[4]..

문제 링크입니다: https://www.acmicpc.net/problem/16466 우선순위 큐를 이용해서 간단히 풀 수 있는 문제라고 생각했지만 생각보다 함정이 많았던 문제였습니다. 알고리즘은 아래와 같습니다.1. 티켓팅 번호가 중복될 경우가 있으므로 map을 이용하여 중복해서 우선순위 큐에 넣어지지 않도록 합니다.2. 티켓 번호는 1부터 시작하므로 우선순위 큐의 root를 idx와 비교하고 idx와 root가 다를 경우 idx가 답이므로 출력하고 프로그램을 끝냅니다.3. 1~N까지 다 티켓팅이 완료되었을 경우 2번에서 값이 출력되지 않습니다. 따라서 2번에서 끝나지 않을 경우를 대비해 while문 밖에서 idx를 출력하는 문장을 추가해줍니다. #include #include #include #inc..

문제 링크입니다: https://www.acmicpc.net/problem/2917 조건이 많이 붙어있는 BFS(Breadth First Search) 알고리즘 문제였습니다.해당 문제를 풀기 위해서는 나무들로부터의 최소거리를 찾기 위해 queue 자료구조를 사용해야하고 경로를 찾기 위해서는 priority_queue를 사용해야합니다.나무들로부터의 최소거리를 찾는 것까지는 성공했으나 경로를 priority_queue를 이용해서 풀 생각을 못 했기 때문에 kdk8361님(http://organize-study.tistory.com/34) 포스팅을 참고해서 풀었습니다. 알고리즘은 아래와 같습니다.1. dist[][] 배열은 나무들로부터의 최소거리이기 때문에 나무들의 좌표를 queue에 넣고 dist[i][j]..