본문 바로가기

알고리즘/백준42

[백준] 11404 플로이드 C++ 플로이드 워셜 알고리즘 : 모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구하는 알고리즘 풀이 a->b로 갈때 1~n 사이의 임의의 정수인 k를 들렸다 가는 경우 중에 최솟값으로 비용을 정한다. 주의 길이 없는 경우를 990만 보다 (99X100000) (99개의 노드를 다 들리고 각 간선 간 비용이 최대값일 경우) 작게 잡으면 안된다. (자연수로 설정할 때) * 그리고 출력할때 한 칸 씩 띄어 출력하라는 말이 없었는데 붙여서 썼더니 틀렸다 1. 길이 없는 경우를 1000000000으로 표현 #include #include using namespace std; int city[101][101]; int n, m; int main() { cin >> n; cin >> m; //입력 a->b로 가는 버.. 2023. 3. 24.
[백준] 1715 카드 정렬하기 c++ https://www.acmicpc.net/problem/1715 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 내 풀이 두 수를 더하고 다음 수에 대해 무언가를 해야한다고 생각해서 해맸다. (a, b, c, d .. 오름 차순으로 있다면 a + b 하고 c에 대해 해야한다고 ) 또한 수를 a, b, c, d, e, f 로 두고 대수적으로 풀려고 해서 꼬였다. 흔적.. 그래서 힌트를 봤는데 우선순위큐가 있었다. .. 제일 작은 두 수를 더한다. 그 다음은? 이라고 생각했는데 제일 작은 두수를 .. 2023. 1. 28.
[백준] 3078 좋은 친구 c++ https://www.acmicpc.net/problem/3078 3078번: 좋은 친구 첫째 줄에 N과 K가 주어진다. (3 ≤ N ≤ 300,000, 1 ≤ K ≤ N) 다음 N개 줄에는 상근이네 반 학생의 이름이 성적순으로 주어진다. 이름은 알파벳 대문자로 이루어져 있고, 2글자 ~ 20글자이다. www.acmicpc.net 정답률 29%인데 한번에 맞춰서 기분이 너무 너무 좋았다 💞 💞 💞 💞 💞 💞 💞 💞 💞 처음에 문제 봤을때 떠오른 생각은 뒤에 있는 k명하고 길이를 비교하는 것을 생각했는데 골드 4가 그렇게 쉬울리가 없고 정답률이 낮아서 그 방법은 아닐 것 같았다. 시간제한 1초이기도 했고. 풀이 *큐에는 k+1개를 담을 수 있다. 비교할 등수 범위를 정해준다. *배열 nameLength에는.. 2023. 1. 7.
[백준] 3980 선발 명단 c++ https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 브루트포스 알고리즘이 떠올랐는데 시간초과가 날까 걱정했다. 계산 횟수가 많을 것 같아서 고민해서 태그를 봤는데 브루트 포스 알고리즘이였다. 계산량 계산하는 것이 아직 어려웠다. 풀이 백트래킹을 통해서 선수들이 포지션을 가질 수 있는 모든 경우의 수를 계산한다. 주의 해야될 점은 아래 사진처럼 (0,0) , (1,1) , (2 , 2) 를 선택하고 3번째 선수로 넘어갈때 2번째 포지션은 이미 2번 째 선수가 가져가서 3번째 선.. 2023. 1. 7.

티스토리툴바