알고리즘 문제풀이/백준134 [백준 11652] 카드 www.acmicpc.net/problem/11652 11652번: 카드 준규는 숫자 카드 N장을 가지고 있다. 숫자 카드에는 정수가 하나 적혀있는데, 적혀있는 수는 -262보다 크거나 같고, 262보다 작거나 같다. 준규가 가지고 있는 카드가 주어졌을 때, 가장 많이 가지 www.acmicpc.net 숫자의 범위가 -2^62~2^62이므로 long long을 사용해야 한다. 1. map을 사용한 방법 map에 넣은 후 sort해주는 간단한 방법으로 풀 수 있다. map을 소팅하는 방법은 pair형 벡터로 선언해준 후 벡터를 정렬하는 방법이다. 메모리를 많이 사용한다. #include #include #include #include using namespace std; map mp; bool cmp(co.. 2021. 2. 25. [백준 148990] 경사로 www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 구현문제 실전에서 나오면 백퍼 틀림 ㅋㅎㅋㅎ 괜히 골3이 아녔다. 알고리즘은 없고 구현 조건이 까다롭다. 처음에 row, col따로 함수를 만들었는데 그러지 않고 transpose를 해서 함수 하나로 돌리는게 낫다. for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { scanf("%d", &arr[i][j]); } } for (int i = 0; i < n; i++) { for .. 2021. 2. 25. [백준 15591] Moo Tube www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net 문제대로 풀면 TLE 발생 처음 접근 방법: 플로이드 와샬 알고리즘처럼 모든 경로에서의 최단 거리를 구하려했다. TLE 발생 -> 개선: BFS 사용. 모든 경로에서의 최단 거리를 구할 필요가 없다. 조건이 있는 BFS 문제였다. 문제의 목적은 start노드에서 USADO가 K이상인 노드 수를 세는 게 목적이다. i->a의 USADO는 min(i->j, j->.. 2021. 2. 17. [백준 1339] 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 백트래킹 문제여서 백트래킹으로 풀었더니 답은 맞았지만 엄청나게 시간이 오래 걸렸다. 아래 제출한 기록이 백트래킹으로 풀었을 때 걸리는 시간이다. 백트래킹 로직은 1. 사용된 모든 알파벳을 담은 후 2. 각 알파벳에 숫자를 매칭시켜서 (백트래킹) 3. 최댓값을 구한 것이다. #include #include #include #include using namespace std; vector v(11); int .. 2021. 2. 9. 이전 1 2 3 4 5 6 7 ··· 34 다음
