알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 단속카메라

문제 : https://programmers.co.kr/learn/courses/30/lessons/42884 풀이 그리디 알고리즘을 이용하여야 한다. 여러 방법이 있겠으나 우선순위 큐를 이용하여 풀었다. routes를 첫항을 기준으로 오름차순 정렬하면 [[-20,15], [-18,-13], [-14,-5], [-5,-3]] 여기서 [-20,15], [-18,-13], [-14,-5]는 [-14,-13] 범위에서 중복된다. 그러므로 위 세개는 -14, -13 둘 중 하나에서 카메라를 설치하고 -5~-3의 범위에서 카메라를 또 하나 설치한다. 시간이 -30000부터 계속 증가하다가 -20이 되면 [-20, 15]를 만난다. 그럼 [-20, 15]를 우선순위 큐에 넣는다. 우선순위 큐는 현재 고속도로에 존재..

2019. 10. 27. 10:50
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 예산

문제 : https://programmers.co.kr/learn/courses/30/lessons/43237 서론 이진탐색 문제인데, 뭔가 M/budgets.size()를 이용해서 풀 수 있을것 같아서 먼저 시도했다가 실패하고 이진탐색으로 해결 풀이 1번 조건이 해당되는지 확인 후에 2번 조건은 이진탐색으로 해결한다. 이때 이진탐색할 배열은 [1,2,3,4,.....m-1,m]이다. 반복되는 이진탐색에서 mid의 값은 정수상한액이며 2번 조건에 따라 정수상한액으로 총 예산을 계산한다. long long cal(int mid, vector &budgets){ long long sum = 0; for(auto i : budgets){ if(mid

2019. 10. 26. 15:55
알고리즘/문제풀이 - 프로그래머스

프로그래머스 레벨3 섬 연결하기

문제 : https://programmers.co.kr/learn/courses/30/lessons/42861 서론 전형적인 MST문제. 크루스칼 알고리즘을 이용하여 풀이 구현 // c++ #include #include #include #include using namespace std; int parent[101]; bool compare(vectora, vectorb){ return a[2]b) parent[a] = b; else parent[b] = a; } return true; } int solution(int n, vector costs) { int answer = 0; for(int i=0;i

2019. 10. 25. 11:08
알고리즘/문제풀이 - 백준

백준 13458 시험 감독

문제 : https://www.acmicpc.net/problem/13458 서론 문제가 너무나 쉬웠다. 반면 정답비율은 낮아서 계속 의심을 하면서 풀었는데 역시나 채점 결과가 틀렸다. 틀린 이유는 출력결과가 int의 범위를 초과해서인데, 매우 의심한거 치고는 상당히 수월하게 끝냈다. 풀이 예제 1번의 결과로 총감독과 부감독 중 하나는 없을 수도 있는것을 알 수 있다. 예제 4번의 결과로 총감독은 반드시 방마다 한명이 있어야 함을 알 수 있다. 그럼 각 방마다 먼저 인원수에서 b를 감소시킨 후 출력값을 +1하고, 아직 방안에 인원이 남아있으면 남아있을때까지 c를 감소시키며 출력값을 늘려가면 된다. c를 감소시킬때는 아래와 같이 나누기와 나머지를 이용하면 반복문을 사용하지 않아도 된다. if (room[i..

2019. 10. 19. 13:23
알고리즘/문제풀이 - 백준

백준 14499 주사위 굴리기

문제 : https://www.acmicpc.net/problem/14499 서론 시뮬레이션 문제. 문제 이해가 필요하며 잘 읽어야한다. 주사위는 최초에 모든 면이 0이다. 전개도의 숫자가 아니다. 풀이 특정 방향으로 이동할때마다 전개도가 바뀌는데, 바뀐 전개도를 알면 나머지는 쉽게 구현 가능하다. 이동할때 바뀌는 전개도는 일일이 만들어가며 찾았다. 최초의 전개도 동 서 남 북 위 아래 3 4 2 5 1 6 각 방향으로 이동했을때 전개도 동 서 남 북 위 아래 최초 3 4 2 5 1 6 동 1 6 2 5 4 3 서 6 1 2 5 3 4 남 3 4 1 6 5 2 북 3 4 6 1 2 5 구현 // c++ #include #include using namespace std; int map[20][20]; i..

2019. 10. 19. 10:55
알고리즘/문제풀이 - 백준

백준 14500 테트로미노

문제 : https://www.acmicpc.net/problem/14500 서론 정사각형 4개가 가질 수 있는 모든 경우의 수를 찾기 위해 DFS를 이용했는데 보라색 사각형 모양이 DFS로는 안나온다. 이걸 구현한 후에야 알았다. 접근법이 틀렸다고 생각해서 이것저것 생각해봤는데 저 모양의 사각형들을 일일이 만들어야 하는것만 떠올랐다. 그리고 다른분의 풀이를 봤더니 보라색 사각형만 만들고 나머지는 DFS로 구현했다. 왜 이걸 생각하지 못했을까 풀이 보라색을 제외한 나머지는 DFS로 구현한다. DFS는 전형적인 DFS이며 깊이가 4가되면 탐색한 칸들의 합을 최대값과 비교하고 리턴한다. 탐색한 칸들의 합은 DFS의 인수에 더해주는 방식을 이용한다. void dfs(int y, int x, int sum) {..

2019. 10. 18. 23:06