Programming/BOJ18 [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. [누적합] 2015번 수들의 합 4 https://www.acmicpc.net/problem/2015 알고리즘 누적합 (구현) 풀이 포인트 누적합의 개념을 알고 있어야 하고 코딩할수 있어야 한다. key-value 개념을 통해, 이전에 누적합이 i인 것의 개수를 저장한다. 누적합 누적합을 통해 주어진 수열의 부분합을 $O(n)$으로 구할 수 있다. 하지만 이 문제는 부분합이 $k$인 구간이 몇 개 있는지 구해야한다. 수열의 부분합을 구하고 ($O(n)$) $n$개 중 2개를 뽑아서 ($O(n^2))$ 그 부분합이 $k$인지 확인 ($O$(1))하면 된다. 즉, 시간 복잡도는 $O(n^2)$이며, 문제의 $n$의 범위로 보아, 시간 초과가 뜰 것이다. 따라서 이 문제는 시간 복잡도를 $O(n)$ 또는 $O(nlogn)$으로 줄여야 정답 판정.. 2022. 3. 9. [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. [DP] 2578번 계단 오르기 https://www.acmicpc.net/problem/2578 알고리즘 Dynamic Programming 풀이 포인트 bottom-up 구현 세 계단을 연속적으로 오르지 못하는 제한 조건을 활용하여 점화식 변형 Dynamic Programming 전형적인 dp 문제로, i번째 계단을 방문했을 때, 그 상태를 기반으로 i+1번째 계단, i+2번재 계단을 방문할 때의 점수 상태를 업데이트하면 된다. 이때, 연속적으로 3개의 계단을 방문하면 안되므로, i번째 계단 방문 상태가 이미 연속 두 계단을 방문한 상태라면 i+1번째 계단은 방문 못하고 i+2번째 계단만 방문할 수 있다. 만약, 연속 두 계단이 아닌, 연속 하나의 계단만 방문한 상태라면 i+1,i+2 계단 모두 방문할 수 있다. 우선 2차원 dp .. 2022. 1. 29. [BFS] 15558번 점프 게임 https://www.acmicpc.net/problem/15558 알고리즘 BFS 풀이 포인트 하나의 상태를 나타내는 조건을 그대로 옮기면 메모리 초과가 난다는 점 BFS 처음에 이 문제를 접했을 때 하나의 상태를 나타내는 조건이 여러개인, 전형적인 조금 어려운 BFS문제라고 생각했다. 그 조건은 아래와 같다. x,y 좌표 몇초가 지났는지 따라서 처음에 3차원 visited 배열을 아래와 같이 정의했다. visited = [[[-1]*n for _ in range(n)] for _ in range(2)] 이렇게 하니 메모리 초과가 발생했다. 문제의 제한 조건을 잘보면, $1 2022. 1. 13. [BFS] 1175번 배달 https://www.acmicpc.net/problem/1175 알고리즘 BFS 풀이 포인트 하나의 state을 나타내는 조건들이 여러개라는 점 BFS 문제에서 주어진 조건들이 여러개라 이를 state로 연관하고 그에 맞게 프로그래밍을 하는게 약간 어려운 문제이다. 먼저 주의해야하는 조건을 정리해보자. 선물이 2개이고 이를 모두 배달하기 전까지 배달은 끝나지 않는다. 두 개의 선물을 각각 A,B라고 할 때, 아래 네 개의 상태가 존재한다. A만 배달한 상태 B만 배달한 상태 두 개 모두 배달하지 않은 상태 둘 모두 배달한 상태 같은 방향으로 두 번 연속 이동할 수 없다. 따라서 (i,j)를 방문했을 때, 어느 방향을 보고 있는지에 따라서 동,서,남,북 네 개의 상태가 존재한다. 이런 문제 의식을 가지고.. 2022. 1. 13. 이전 1 2 3 다음
