백준30 [백준/C++] #11000 강의실 배정 (Greedy) 문제https://www.acmicpc.net/problem/11000 구상가장 처음에 왼쪽 그림처럼 2차원 배열을 만들어서 1번 강의실부터 시간들 채워나가며 몇번 강의실까지 사용하는지 알고자 했는데, S와 T의 범위가 10^9로 굉장히 커서 시간 복잡도에서 문제가 생겼다. 그래서 오른쪽 그림과 같은 구상을 했는데, 먼저, 주어진 S와 T를 배열에 넣고, S(시작 시간)기준으로 정렬한다. 그리고, 끝시간은 최소힙에 하나씩 넣고 시작시간과 비교해 시작시간이 최소힙에 있는 끝시간보다 같거나 크면 힙의 top값을 pop하고, 현재 강의 시간의 끝 시간을 최소힙에 넣는다. 남아있는 강의들 중에서 시작 시간이 가장 빠른 강의가 이미 배정된 강의 중에서 가장 끝시간이 빠른 강의 뒤에 올 수 있는지 판단하는 것이.. 2024. 7. 15. [백준/C++] #2529 부등호 (Back Tracking) 문제https://www.acmicpc.net/problem/2529 구상주어진 부등호 사이사이에 0~9 범위의 숫자를 넣어야했다. 즉, 부등호 조건에 맞는 0~9로 이루어진 순열을 만들어야 했다. 근데, sign 배열의 크기도 작고, 숫자의 범위로 0~9로 작기에 순열을 만들때 완전탐색으로 backtraking하면 될 것 이라 판단했다. 풀이 + 코드backtracking의 일반적인 기본 구조는 재귀 함수 안의 if-for문이다. for문 안에서 특정 횟수만큼의 답을 구하거나 답을 구할 수 있도록 반복하는데, for문 안에서 재귀호출을 하며 가능한 경우를 전부 따진다. if문에서는 답이 될 수 있는 조건을 충족하면 답을 따로 저장한다. 세세한 조건은 if문을 사용하는데, for문에서 재귀 돌기 전에.. 2024. 7. 7. [백준/C++] #15686 치킨 배달 (Brute Force) 문제https://www.acmicpc.net/problem/15686 구상처음에는 어떤 치킨집을 폐업시켜야 할까? 라는 고민을 통해 아래 처럼 풀이를 구상했었다. 1. bfs로 각각의 집들에서 가장 가까운 치킨집 방문, 치킨거리 갱신 2. 가장 방문이 많은 치킨집 순으로 최대 m개를 고르고 3. 나머지 치킨집이랑 가까웠던 집들은 다시 거리 계산해야 한다. -> 하지만, 방문이 많은 m개 집 고른다 해도 해당 집들이 최소 도시 치킨 거리를 만든다고 장담할 수 없다. 수정 후 풀이는 다음과 같았다. Brute force! 1. 치킨집 조합 만들기 -> next_permutation 이용!! 2. 각각의 치킨집에 대해 집들의 거리 구하기 3. 거리를 다 합친 도시 치킨 거리들 중 최소값 구하고 출력 next.. 2024. 7. 6. [백준/C++] #9251 LCS (DP/LCS) 문제https://www.acmicpc.net/problem/9251 구상사실.. 문제 이름 자체가 LCS여서... 바로 LCS 대입해서 풀었다. 알고리즘: LCS (Longest Common Subsequence) 두 수열이나 문자열에서 공통되는 가장 긴 부분수열 혹인 부분 문자열 중요한건, 공통되는 문자열이 연속적일 필요는 없다! LCS는 2차원 DP 배열을 통해 구할 수 있다. 풀이 + 코드if (현재 비교하는 문자가 서로 다르다면) 왼쪽, 위쪽 두 개의 값 중 큰 값 저장else 왼쪽 위 대각선의 값 + 1 저장 #include #include using namespace std;string s1, s2;vector> dp;/*9251 LCS*/int main() { cin >> s1 >> .. 2024. 7. 5. 이전 1 ··· 3 4 5 6 7 8 다음
