C++33 [C/C++] 백준 11725: 트리의 부모 찾기(vector 이용) https://www.acmicpc.net/problem/11725 11725번: 트리의 부모 찾기 루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오. www.acmicpc.net 맨 처음에 문제에서 트리의 루트를 1로 둔다는 조건을 확인 못해서 맨 처음에 해맸다.. 구현!! 사실 간단하게 풀이가 가능하다. 이차원 백터 vectorv1[100001]를 선언하여 각 노드와 연결되어 있는 노드를 뒤에 추가해주면 된다. 이때 무엇이 부모이고 자식 노드인지 모르기 때문에 v1[tmp1].push_back(tmp2); v1[tmp2].push_back(tmp1); 두번 다 해줘야한다. 그 다음에는 queue를 이용하여 push와 pop을 해주면 .. 2023. 9. 17. [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++] 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. [C/C++] 백준 1916: 최소비용 구하기 (다익스트라 구현하기!) https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 이번에 드디어 다익스트라 알고리즘을 배워서 실제 문제 풀이에 적용하였다. 알고리즘 문제해결 전략에 나와있는 것을 응용하여 해결했다. 1. 준비작업 1-1. vector adj_list[100001] 먼저 각 노드들의 인접리스트를 만들 이차원 백터 vector adj_list[100001]을 선언해주었다. 이 백터의 역할은 a번째 노드와 연결되어 있는 b번째 노드까.. 2023. 9. 13. 이전 1 2 3 4 5 6 7 8 9 다음
