전체 글102 [C++] 모듈러 사칙 연산 (BOJ 1629: 곱셈) 백준 1629: 곱셈 문제를 풀다가 자꾸 시간초과가 나오다보니 결국 하는 방법을 찾게 되었는데 모듈러 계산에 대해서 공부할 필요성을 느끼게 되었다. 앞으로 모듈러 연산이 나올 때마다 여기다가 다시 정리를 해야겠다. 모듈러 사칙 연산 덧셈, 뺄셈, 곱셈에 대해서는 다음 식이 항상 성립한다. (이부분에서는 mod M을 % M이라고 표현) 덧셈 : (a+b) % M = ((a % M) + (b % M)) % M 뺄셈 : (a-b) % M = ((a%M) - (a%M)) % M 곱셈 : (a*b) % M = ((a%M) * (b%M)) % M 나눗셈 : 모듈로 연산에서 나눗셈은 곱셈 역원(multiplicative inverse)을 곱하는 방식으로 이루어진다. 모듈로 곱셈 역원은 항상 존재하는 것이 아니라, b.. 2023. 9. 15. [C/C++] 백준 1167: 트리의 지름 (다익스트라 풀이) https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 풀이 방법?? 문제 자체가 트리의 지름을 구하라고 하는데 이때 트리의 지름이란 임의의 두 점 사이의 거리 중 가장 긴 것을 의미한다. 그렇기 때문에 모든 노드에서 DFS 혹은 다익스트라 알고리즘을 통해 가장 긴 거리를 구하려는 것이 첫번째 생각일 것이다. 하지만 이렇게 할 경우 각 정점마다 (V) 트리를 모두 순회하며 (V) 최댓값을 구해야하기 때문에 O(V^2)의 시간이 걸려 시.. 2023. 9. 15. [C/C++] 백준 11660 구간 합 구하기 5 (이차원 구간 합) https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 풀이 방법? 가장 먼저 드는 생각은 합을 구해야하는 횟수마다 저장되어 있는 2차원 배열에서 이중 for문을 통해 구간 합을 각각 구하는 방법인데 이 방법으로 할 경우 최악의 경우에는 100,000*1024*1024 의 경우를 모두 확인해야하므로 시간 초과가 발생한다. 그렇기 때문에 여기서 제목에 있는 힌트를 빌려 풀이 방법을 생각해보자면 현재 있는 위치까.. 2023. 9. 15. [C++] Map을 이용한 tree 구현 (BOJ 1991: 트리순회) https://www.acmicpc.net/problem/1991 1991번: 트리 순회 첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파 www.acmicpc.net 이 문제를 직접 tree를 구현하여 풀지 않고 map을 이용하여 구현하였다. Map이란? map은 각 노드가 key와 value가 쌍을 이루고 있는 트리로 pair 객체로 저장되기 때문에 first-key로 second-value를 저장한다. 중복을 허락하지 않으며 기본 형태는 map m; 으로 key를 통해 value를 찾기 용이하게 되어있다. 그래서 map은 pair로 이루어진 se.. 2023. 9. 14. 이전 1 ··· 4 5 6 7 8 9 10 ··· 26 다음
