greedy3 [Greedy] 12940번 A와 B https://www.acmicpc.net/problem/12904 알고리즘 Greedy 풀이 포인트 문자열 S를 T로 만들기 위해서는 다양한 경로를 따져야 하지만, T에서 S를 만드는 경로는 하나라는 점. Greedy 이 문제를 처음 접했을 때, 가장 먼저 떠오른 풀이는 bfs이었다. 즉, 현재 상태에서 두 가지 선택권이 있고, 각 상태를 만들기 위한 최소 연산 수를 기록하며 bfs를 한다면, 문자열 T를 만들 수 있는지 여부를 구할 수 있다고 생각했다. 전형적인 bfs 문제라고 생각하고 아래와 같이 코드를 짰다. [Source Code] from collections import deque def func_1(x): return x+'A' def func_2(x): return x[::-1]+'B' .. 2022. 3. 17. [Greedy] 12931번 두 배 더하기 https://www.acmicpc.net/problem/15990 알고리즘 Greedy 풀이 포인트 BFS나 Brute Force 풀면 시간초과가 뜬다. greedy한 접근법을 통해 풀이 시간을 줄여야한다. BFS 딕셔너리 visited를 key 상태까지 도달하기 위한 최소 연산 횟수로 정의한다. 그리고 큐에서 현재 상태를 꺼낼 때마다, n개의 원소에 대해, i번째 원소에 1을 더한 a의 새로운 상태를 큐에 넣는다. 또한, 일괄적으로 2배를 한 a의 새로운 상태도 큐에 넣는다. 이 풀이의 시간 복잡도는 어떻게 될까? 최악의 경우, 길이가 50이면서 b의 모든 원소는 1000의 값을 가진다. 0에서 1000까지 1씩 더하면 1000번의 계산이 필요하므로, 대략 시간복잡도는 $O(50 \times 1000.. 2022. 2. 11. [BF] 16937번 두 스티커 https://www.acmicpc.net/problem/16937 알고리즘 Brute Force Greedy (?) 풀이 포인트 주어진 n개의 스티커 중 두 개의 스티커만 사용하여 최대 넓이를 구한다는 점 스티커를 회전할 수 있고 스티커끼리 접할 수 있다는 점 Brute Force 전형적인 brute force 문제이다. n개의 스티커 중 2개를 골라서 스티커를 붙여보면서 최대 넓이를 가지는 스티커 조합을 찾으면 된다. 여기서 고민되는 부분이 스티커를 붙이는 것을 어떻게 구현하는지였다. 가장 먼저 생각난 점은, $h \times w$ 넓이에 한칸 한칸 for문을 돌면서 스티커를 붙여보는 것이었다. 그런데 이렇게 하면, 스티커를 붙일 수 있는 격자판과 스티커 최대 넓이가 100이므로 시간 복잡도가 꽤 커.. 2022. 1. 9. 이전 1 다음
