본문 바로가기

Algorithm/그리디7

[백준] 2138번 : 전구와 스위치 https://www.acmicpc.net/problem/2138 2138번: 전구와 스위치 N개의 스위치와 N개의 전구가 있다. 각각의 전구는 켜져 있는 상태와 꺼져 있는 상태 중 하나의 상태를 가진다. i(1 < i < N)번 스위치를 누르면 i-1, i, i+1의 세 개의 전구의 상태가 바뀐다. 즉, 꺼져 www.acmicpc.net N=100000이기때문에 모든 전구에 대해서 스위치를 킬지 말지 고려하면 풀수 없다. O(n)만에 풀어야하는 문제다. 처음에 생각했던 로직은 메모리초과가 났고, 효율적인 로직이 생각나지 않아 결국 블로그(https://staticvoidlife.tistory.com/143)를 참고하여 풀었다. 이 문제는 2가지 케이스로 나누어 풀어야한다. 1. 0번째 전구를 키고 시작.. 2021. 11. 18.
[프로그래머스] 광고삽입 (C++) (2021 KAKAO BLIND RECRUITMENT) https://programmers.co.kr/learn/courses/30/lessons/72414?language=cpp 코딩테스트 연습 - 광고 삽입 시간을 나타내는 HH, H1, H2의 범위는 00~99, 분을 나타내는 MM, M1, M2의 범위는 00~59, 초를 나타내는 SS, S1, S2의 범위는 00~59까지 사용됩니다. 잘못된 시각은 입력으로 주어지지 않습니다. (예: 04:60:24, 11 programmers.co.kr 이 문제에서는 효율성을 고려해야하는 문제로 구간합과 투포인터 알고리즘을 사용하였다. 해당 알고리즘을 사용하기 전에 HH:MM:SS 초로 바꿔주는 두가지 함수를 구현하였다. 이후에는 구간합만 구하면 되는데, 이 부분이 핵심인 문제였다. 전체 구간 길이가 N이고 광고 길이.. 2021. 10. 2.
[백준] 1647번 : 도시 분할 계획 https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소비용 문제로 크루스칼 알고리즘을 사용하였다. 이 문제에서 주어진 추가적인 조건은 두개의 마을로 분할해서 최소비용을 구하는 것이었다. 따라서, 일반적인 크루스칼 알고리즘을 통해 모든 정점을 이어서 구할 수 있는 최소 비용을 구한 후 선택된 간선들 중 가장 큰 가중치값을 갖는 간선치를 빼주었다. 해당 마을을 분할해주면 되기 때문이다. 전체 코드는 다음과 같다... 2021. 9. 24.
[백준] 1920번 : 수 찾기 (C++) https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들 www.acmicpc.net 이분 탐색으로 구현하였다. 이분 탐색 시작 전, 배열을 오름차순 정렬하는 걸 잊지말자! #include #include #include using namespace std; int N, M; int n; int arr[100000]; int solve(int n) { int start = 0; int end = N-1; while (start > N.. 2021. 9. 21.
[백준] 1197번 : 최소 스패닝 트리 (C++) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 크루스칼 알고리즘으로 구현하였다. #include #include #include using namespace std; int V, E; int A, B, C; int getParent(int parent[], int x) { if (parent[x] == x) return x; return parent[x] = getParent(parent, par.. 2021. 9. 15.
[백준] 8980번 : 택배 (C++) https://www.acmicpc.net/problem/8980 8980번: 택배 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이 www.acmicpc.net 이 문제에서의 핵심은 택배를 올리면 무조건 목적지에서 내려지기 때문에 무게 맞게 올리는 경우만 고려하면된다. 따라서, 받는 마을과 보내는 마을의 차이가 작고, 택배를 빨리 내릴수록 효율적이기 때문에 받는 마을의 번호를 기준으로 오름차순 정렬한 후 탐색해야한다. 오랜만에 다시 본 문제였는데도 풀이방식이 제대로 생각나지 않았다... 몇번 더 풀어봐야 할 것같다! 문제 풀이 방식은 .. 2021. 9. 5.

티스토리툴바