C++156 [백준] 14863번 - 서울에서 경산까지 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 서울에서 경산까지 https://www.acmicpc.net/problem/14863 14863번: 서울에서 경산까지 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 두 자연수 N과 K가 공백으로 분리되어 주어진다(3 ≤ N ≤ 100, 0 < K ≤ 100,000). 두 번째 줄에는 구간 1을 도보로 이동할 때 걸리는 시간(분), 이 www.acmicpc.net 도보로 이동하거나 자전거를 이용하는 방법을 택하여 제한 시간 이내에 얻을 수 있는 최대 모금액을 구하는 문제였습니다. 동적 계획법을 통해 해당 구간과 제한 시간을 memoization 하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_So.. 2022. 3. 8. [백준] 9024번 - 두 수의 합 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 두 수의 합 https://www.acmicpc.net/problem/9024 9024번: 두 수의 합 프로그램은 표준입력으로 입력을 받는다. 프로그램 입력은 t 개의 테스트 케이스로 구성된다. 입력의 첫 번째 줄에 테스트 케이스의 개수를 나타내는 정수 t 가 주어진다. 두 번째 줄부터 두 줄 www.acmicpc.net 주어진 숫자 배열에서 두 개의 수를 뽑았을 때, K에 가장 가까운 쌍의 개수를 찾는 문제였습니다. N이 최대 100만이기에 O(NlogN)의 시간 복잡도로 해결할 수 있어야 합니다. 정렬 + 이분 탐색으로 K에 가장 가까운 수의 합을 탐색하며 갱신하면 해결할 수 있습니다. C++ 소스코드) 2022. 3. 7. [백준] 18405번 - 경제적 전염 (C++) 문제 및 풀이 문제) 백준 - BFS - 경제적 전염 https://www.acmicpc.net/problem/18405 18405번: 경쟁적 전염 첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치 www.acmicpc.net BFS를 통해 바이러스를 전염시킵니다. 매 초마다 전염을 하는데 1번부터 K번 순서대로 전염시켜야 되기 때문에 각 초마다 q_size의 좌표를 벡터에 넣어 정렬을 진행합니다. 정렬을 했다면 BFS를 진행하여 바이러스를 퍼트립니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BO.. 2022. 3. 2. [백준] 17609번 - 회문 (C++) 문제 및 풀이 문제) 백준 - 구현 - 회문 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 글자의 앞과 뒤를 비교하여 회문 여부를 판단합니다. 만약 앞(l), 뒤(r) 글자가 같지 않으면 회문이 아니므로 유사 회문 판단을 진행합니다. 유사 회문 판단은 l+1번째 글자부터 r번째 글자의 회문 여부와 l 번째 글자부터 r - 1번째 글자의 회문 여부를 판단합니다. 전자는 l번째 글자를 제외할 경우의 유사 회문 판단이고 후자는 r번째 글자를 제외할 경우의 유사회문 판단입니다. C++ 소스코드.. 2022. 3. 1. [백준] 9242번 - 폭탄 해체 (C++) 문제 및 풀이 문제) 백준 - 구현 - 폭탄 해체 https://www.acmicpc.net/problem/9242 9242번: 폭탄 해체 입력으로 폭탄의 코드가 주어진다. 코드는 2자리 이상, 8자리 이하이고, 각 자리는 5행 3열의 문자로 주어진다. 문자는 공백과 별표('*') 중 하나이다. 또, 각 숫자를 구분하기 위해 숫자 사이에는 www.acmicpc.net C++ 소스코드) 2022. 3. 1. [백준] 12851번 - 숨바꼭질 2 (C++) 문제 및 풀이 문제) 백준 - BFS - 숨바꼭질 2 https://www.acmicpc.net/problem/12851 12851번: 숨바꼭질 2 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/12851_%EC%88%A8%EB%B0%94%EA%BC%AD%EC%A7%882.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutio.. 2022. 3. 1. [백준] 15486번 - 퇴사 2 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 퇴사 2 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net N이 150만이기에 동적 계획법으로 해결이 안 될 줄 알았는데 생각보다 넉넉한 시간에 통과해서 의외였습니다. solve(now)를 통해 해당 날짜에서 얻을 수 있는 최대 수익을 계산합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/S.. 2022. 2. 28. [백준] 13418번 - 학교 탐방하기 (C++) 문제 및 풀이 문제) 백준 - 최소 스패닝 트리 - 학교 탐방하기 https://www.acmicpc.net/problem/13418 13418번: 학교 탐방하기 입력 데이터는 표준 입력을 사용한다. 입력은 1개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 건물의 개수 N(1≤N≤1,000)과 도로의 개수 M(1≤M≤n*(n-1)/2) 이 주어진다. 입력의 두 번째 줄 www.acmicpc.net 내리막길로 갈 수 있는 최대 간선과 오르막길로 갈 수 있는 최대 간선의 차를 구하는 문제입니다. 모든 점을 잇는 간선을 뽑아야하므로 최소 스패닝 트리를 이용하여 간선을 선택합니다. 최대 간선은 정렬을 반대로 하여 Kruskal 알고리즘을 진행합니다. C++ 소스코드) Full Code) https://github.co.. 2022. 2. 27. [백준] 18243번 - Small World Network (C++) 문제 및 풀이 문제) 백준 - BFS - Small World Network https://www.acmicpc.net/problem/18243 18243번: Small World Network 첫 번째 줄에 지구에 있는 사람의 수 N과 친구 관계의 개수 K가 주어진다. 모든 사람은 1부터 N까지 번호가 매겨져 있다. (1 ≤ N ≤ 100, 0 ≤ K ≤ N×(N-1)/2) 두 번째 줄부터 K+1번째 줄까지 친구 www.acmicpc.net 1부터 N까지 시작하여 각 사람마다 거리를 구하여 6번 안에 이어져있는지 확인합니다. 가중치가 없는 간선으로 이어져 있으므로 BFS를 활용합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/mai.. 2022. 2. 27. 이전 1 2 3 4 5 ··· 18 다음 반응형
