알고리즘204 [백준] 14697번 - 방 배정하기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 방 배정하기 https://www.acmicpc.net/problem/14697 14697번: 방 배정하기 정보 초등학교 6학년 여학생들은 단체로 2박 3일 수학여행을 가기로 했다. 학생들이 묵을 숙소에는 방의 정원(방 안에 있는 침대 수)을 기준으로 세 종류의 방이 있으며, 같은 종류의 방들이 여러 www.acmicpc.net N이 최대 300이므로 A, B, C를 0~300까지 탐색하면 N이 만들어지는지 확인하면 됩니다. C++ 소스코드) 2022. 2. 9. [백준] 2304번 - 창고 다각형 (C++) 문제 및 풀이 문제) 백준 - 자료 구조 - 창고 다각형 https://www.acmicpc.net/problem/2304 2304번: 창고 다각형 첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 www.acmicpc.net 입력을 받을 때, 제일 긴 막대 기둥의 인덱스를 저장합니다. 먼저 오름차순(기둥이 길어지는 부분)을 계산합니다. 스택에 높이를 push 하여 다음 높이가 더 클 경우 push, 작을 경우 기존 스택에 가장 긴 높이의 넓이를 result에 더합니다. C++ 소스코드) Full Code) https://github.com/Chocochip10.. 2022. 2. 9. [백준] 22869번 - 징검다리 건너기 (small) (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 징검다리 건너기 (small) https://www.acmicpc.net/problem/22869 22869번: 징검다리 건너기 (small) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 0번째부터 오른쪽으로 출발하여 N-1번째까지 도착할 수 있는지 확인합니다. cache[idx]를 통해 idx번까지 도달 여부를 저장해 1일 경우 가능, -1일 경우 미방문, 0일 경우 불가능으로 판단합니다. C++ 소스코드) Full Code) https://github.co.. 2022. 2. 8. [백준] 6550번 - 부분 문자열 (C++) 문제 및 풀이 문제) 백준 - 문자열 - 부분 문자열 https://www.acmicpc.net/problem/6550 6550번: 부분 문자열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 문자열 s 와 t가 빈칸을 사이에 두고 들어온다. s와 t의 길이는 10만을 넘지 않는다. www.acmicpc.net 문자열 s가 문자열 t의 부분 문자열로 존재하는지 확인하는 문제였습니다. t의 문자열을 처음부터 탐색하면서 s와 같을 경우 idx를 1 증가시킵니다. 만약 idx가 s 문자열의 길이와 같을 경우 true를 return 합니다. C++ 소스코드) 2022. 2. 8. [백준] 2602번 - 돌다리 건너기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 돌다리 건너기 https://www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net 두루마리 문자열의 인덱스, 다리의 인덱스, 악마/천사 여부를 이용하여 현재 위치에서 돌다리를 건널 수 있는 모든 경우를 동적 계획법을 이용해 계산합니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/2602_%EB%8F%8C%EB%8B.. 2022. 2. 4. [백준] 18113번 - 그르다 김가놈 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 그르다 김가놈 https://www.acmicpc.net/problem/18113 18113번: 그르다 김가놈 첫 번째 줄에 손질해야 하는 김밥의 개수 N, 꼬다리의 길이 K, 김밥조각의 최소 개수 M이 주어진다. (1 ≤ N ≤ 106, 1 ≤ K, M ≤ 109, N, K, M은 정수) 두 번째 줄부터 김밥의 길이 L이 N개 주어진다. www.acmicpc.net N개의 김밥을 입력받아 꼬다리를 제외한 김밥 길이를 계산합니다. 김밥이 폐기되거나 길이가 0인 김밥은 필요가 없기 때문에 vector을 이용하여 김밥의 길이를 저장합니다. 이분 탐색을 이용하여 가능한 P의 최대를 계산합니다. C++ 소스 코드) 2022. 2. 4. [백준] 18513번 - 샘터 (C++) 문제 및 풀이 문제) 백준 - BFS - 샘터 https://www.acmicpc.net/problem/18513 18513번: 샘터 첫째 줄에 자연수 N과 K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N, K ≤ 100,000) 둘째 줄에 N개의 샘터의 위치가 공백을 기준으로 구분되어 정수 형태로 주어진다. (-100,000,000 ≤ 샘터의 위치 ≤ www.acmicpc.net BFS를 통해서 각 샘터를 기준으로 지을 수 있는 집의 최소 불행도를 구한다. 주언진 샘터의 좌표를 Queue에 push 하여 매번 Queue size마다 K개 집에 대하여 거리를 더해준다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Prob.. 2022. 2. 3. [백준] 11365번 - !밀비 급일 (C++) 문제 및 풀이 문제) 백준 - 문자열 - !밀비 급일 https://www.acmicpc.net/problem/11365 11365번: !밀비 급일 당신은 길을 가다가 이상한 쪽지를 발견했다. 그 쪽지에는 암호가 적혀 있었는데, 똑똑한 당신은 암호가 뒤집으면 해독된다는 것을 발견했다. 이 암호를 해독하는 프로그램을 작성하시오. www.acmicpc.net 문자열을 차례대로 입력 받아 역순으로 출력합니다. C++ 소스 코드) 2022. 2. 3. [백준] 7511번 - 소셜 네트워킹 어플리케이션 (C++) 문제 및 풀이 문제) 백준 - 분리 집합 - 소셜 네트워킹 어플리케이션 https://www.acmicpc.net/problem/7511 7511번: 소셜 네트워킹 어플리케이션 각 테스트 케이스마다 "Scenario i:"를 출력한다. i는 테스트 케이스 번호이며, 1부터 시작한다. 그 다음, 각각의 쌍마다 두 사람을 연결하는 경로가 있으면 1, 없으면 0을 출력한다. 각 테스트 케이스 www.acmicpc.net 친구 두 명이 주어질 때, 서로 친구인지 확인해야 됩니다. 쿼리 최대 개수가 10만이기에 각 쿼리를 O(1)의 시간 복잡도로 해결할 수 있는 분리 집합(Union-Find)을 활용하여 해결했습니다. Merge(Union)와 Find는 O(N)이므로 N이 100만이여도 해결할 수 있습니다. C++ 소스코드) .. 2022. 1. 30. 이전 1 ··· 5 6 7 8 9 10 11 ··· 23 다음 반응형
