본문 바로가기

백준 문제 풀이

 (134)
백준 2457번 공주님의 정원 (C++) https://www.acmicpc.net/problem/2457 2457번: 공주님의 정원 첫째 줄에는 꽃들의 총 개수 N (1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 각 꽃이 피는 날짜와 지는 날짜가 주어진다. 하나의 날짜는 월과 일을 나타내는 두 숫자로 표현된다. 예를 들어서, www.acmicpc.net 처음 문제를 보고 투포인터 이분탐색이 생각났다. 처음 꽃은 반드시 3월 1일 이하부터 피어야하고 마지막 꽃은 12월 1일 이하에 져야한다. 그러므로 각 포인터들을 이동시켜서 최적의 조건을 만든 후 checking 절차를 하면 된다고 생각했다. 결론적으로 말하면 위 방법이 완전히 틀린 것은 아니지만 이렇게할 필요도 없고 문제의도와 맞지 않다. 이 문제의 의도는 Greedy 이다...
백준 9251번 LCS(C++) https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 최장 공통 수열이란 ABCDE BCFZ E 두개가 있으면 BCE가 공통 수열이다. 즉 이어져있지 않아도 순서만 맞으면 된다는 뜻이다. 이 문제는 DP분류이지만 LCS알고리즘이라는 말이 따로 있을 정도라 카테코리로 분류해도 된다고 생각이 든다. 처음에는 2 x N 배열로 문제를 해결하려 했는데 사실 알고보니 두 문자열의 길이가 다를수도 있어서 될수가 없는..
백준 15683번 - 감시(C++) https://www.acmicpc.net/problem/15683 15683번: 감시 스타트링크의 사무실은 1×1크기의 정사각형으로 나누어져 있는 N×M 크기의 직사각형으로 나타낼 수 있다. 사무실에는 총 K개의 CCTV가 설치되어져 있는데, CCTV는 5가지 종류가 있다. 각 CCTV가 감 www.acmicpc.net 삼성 SW 역량 기출 문제 답게 상당한 구현을 요구하는 문제이다. 접근법 - 먼저 이 문제는 CCTV들이 4방향이 가능하고 총 5가지 종류가 있다. 모든 CCTV의 상태 별 감시 위치를 확인해야하기 때문에 이 문제는 BRUTEFORCE 완전 탐색 문제이다. 그러나 브루트포스하게 몇 중 반복문으로 해결하기는 힘들다. CCTV의 숫자가 정해져있지 않기 때문이다. 내가 선택한 방법은 DFS ..
백준 1759번 암호 만들기 https://www.acmicpc.net/problem/1759 1759번: 암호 만들기 첫째 줄에 두 정수 L, C가 주어진다. (3 ≤ L ≤ C ≤ 15) 다음 줄에는 C개의 문자들이 공백으로 구분되어 주어진다. 주어지는 문자들은 알파벳 소문자이며, 중복되는 것은 없다. www.acmicpc.net 전형적인 순열 구하기 문제이다. dfs 백트래킹으로 검사하고 주의할 것은 자음의 수가 2개 이상이라는 것만 체크하면 된다. 그런데 난 모음의 요소를 저렇게 검사했는데 맞는지 모르겠다. 시간 복잡도는 O(조합 * N) 으로 빠른시간에 해결 가능했다. N이 높지 않은 탓이다. 문제를 보고 바로 파악할 수 있었다. 코테에서도 이래야할탠데... #include #include #include using nam..
백준 9465번 - 스티커(C++) https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 2차원 DP문제이다. 이 문제를 지난학기에는 풀지 못했었는데 이번에 풀게 되어 기쁘다. 놀기만 한 건 아니라는 거지.. 아무튼, 2차원 dp배열을 선언하고 풀이하면 된다. 이 문제는 bottom up 방식으로 먼저 왼쪽부터 오른쪽으로 진행하며 풀이를 했다. 오른쪽에서 왼쪽으로 가도 상관은 없다. - 접근법 이 문제를 재귀나 분기로 풀면 어떻게 될까. 만약 0,0 을 선택했을 때 다음으로..
백준 3079번 입국심사(C++) https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 처음 문제를 봤을 때 우선순위큐 문제라고 생각했다. 그러나 몇 초 쉬고 다른 심사대로 이동하는 것을 생각해보면 아무래도 우선순위 큐로는 풀어낼 수 없다. 그러다가 분류를 보니 이분탐색 파라메트리 서치가 보였다. ? 아니 이걸 어떻게 파라메트리로 ? 라고 생각해서 기다렸다가 가는 시간초를 파라메트릭으로 판단하나? 생각했는데 그걸리가 없지. 파라메트릭은 보통 "정답" 을 반환한다. an..
백준 23843번 콘센트 (C++) https://www.acmicpc.net/problem/23843 23843번: 콘센트 광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다. 전자기기들은 한 www.acmicpc.net - 접근법 - 먼저 콘센트의 개수가 최대 10개이기 때문에 시간복잡도에 큰 영향을 받지 않는 문제이다. 중요한 것은 콘센트들에 기기가 충전중 일 때 가장 오래걸리는 것을 꽂아놔야한다는 것이다. 만약 작은것 부터 꽂았다면 예제 1 1 4 4 8 에서 콘센트 1 - 1 4 콘센트 2 - 1 4 이런식으로 꽂히게 될 것이고 이후 8이 들어오면 답이 아니다. 그러므로 먼저 큰 놈이 들어와서 자리를 잡아야한다. 그..
백준 1339번 단어 수학 (C++) https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net ------------- 접근법 처음 보면 Backtracking 인가? 최적의 해를 어떻게 구할 수 있지? 라는 고민을 먼저 하게 된다. PS를 하면서 느끼는 건 "이렇게 하면 답이 나오는데 증명이 안됐다" 라는 해는 사용하면 안된다 맞는 경우도 있겠지만 매우 위험하다. 이 문제도 마찬가지다. ABCDE FCG 에서 AB까지는 9 8 을 하고 나머지는 번갈아가며 7 6 5 4.. 를 주니 ..

티스토리툴바