전체 글105 [segment tree] 11505번 구간 곱 구하기 https://www.acmicpc.net/problem/11505 자료구조 segment tree 풀이 포인트 segment tree 자료구조를 이용해서 $O(logn)$ 시간 복잡도로 문제 풀기 (segment tree 자료구조 설명) modular 연산에 유의하여 update 함수 변경하기 segment tree update 함수 기존의 누적 합 문제에서는 새로 바꿀 수와 기존의 수와의 차이 (diff)를 구하고, 해당 인덱스가 포함되는 노드에 diff를 더해주는 식으로 update 함수가 작동했다. 하지만 이 문제에서는 누적 곱을 구하는 문제이고 중간에 modular 연산이 들어가기 때문에 이런 방식으로 할 수가 없다. 만약에 누적합 문제와 유사하게 누적곱의 update 함수를 구성하면 아래와 같.. 2022. 3. 20. Segment Tree Motivation segment tree 자료구조는 아래의 문제를 해결하는데 사용된다. 1. 1차원 배열의 i번째 수부터 j번째 수까지의 연속 합을 구해야할 때 (총 $m$번) 2. 배열의 i번째 수가 변경되는 쿼리를 같이 처리해야할 때 (총 $k$번) 1번의 문제만 해결해야한다면, 부분 합 (Prefix Sum) 문제로 치환하여, $O(n+m)$의 시간 복잡도로 해결할 수 있다. 하지만, 2번의 문제까지 추가가 된다면 상황이 복잡해진다. 부분 합을 이미 구해 놓은 상태에서, i번째 수가 변경된다면 부분 합을 다시 업데이트해야한다. 즉, $k$번만큼 배열의 수가 변경될때마다 부분 합을 업데이트해야하므로 여기서 $O(nk)$의 시간 복잡도가 발생한다. 여기에 m개의 연속 합을 구해야하므로 최종 시간 복잡.. 2022. 3. 19. [구현] 2174번 로봇 시뮬레이션 https://www.acmicpc.net/problem/2174 알고리즘 구현, 시뮬레이션 풀이 포인트 파이썬 class를 이용해서 구현하기 구현, 시뮬레이션 로봇의 위치, 방향, 번호의 정보를 가지는 robot class를 만든다. $B \times A$ 크기의 land 2차원 배열을 선언하고, $(x,y)$ 좌표에 로봇이 있을 경우, 해당 위치에 로봇 클래스를 추가한다. 로봇의 개수만큼의 크기를 가지는 robot_info 1차원 배열을 선언하고 i번째 위치에 i번 로봇 클래스를 추가한다. 문제의 명령을 그대로 수행한다. 벽에 만나거나, 다른 로봇을 만나면 경고문과 함께 프로그램을 종료하고 그렇지 않다면 land 배열에서 로봇을 옮기거나 로봇 클래스의 방향을 수정해준다. [Source Code] a,.. 2022. 3. 17. [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. 이전 1 ··· 13 14 15 16 17 18 다음
