본문 바로가기

PS(Problem Solving)/백준_BOJ201

[백준] 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.
[백준] 4779번 - 칸토어 집합 (C++) 문제 및 풀이 문제) 백준 - 분할 정복 - 칸토어 집합 https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 큰 문제를 작은 문제로 쪼갤 수 있는 분할 정복 문제입니다. n이 0일 때 "-"를 출력하고, 0보다 클 경우 3 등분으로 쪼개어 작은 문제로 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/4779_%EC%B9%B8%ED%86%A0%EC%.. 2022. 2. 27.
[백준] 14400번 - 편의점 2 (C++) 문제 및 풀이 문제) 백준 - 정렬 - 편의점 2 https://www.acmicpc.net/problem/14400 14400번: 편의점 2 영선이는 이번에 편의점으로 창업을 하려고 계획 중이다. 이번 창업을 위해 많은 준비를 하고 있는데, 아직 편의점을 세울 위치를 결정을 하지 못했다. 영선이는 미리 시장조사를 하여, 주요 고 www.acmicpc.net 거리의 최소를 구하는 문제였습니다. 거리의 최소는 x 좌표와 y좌표의 중간값을 고르면 구할 수 있습니다. C++ 소스 코드) 2022. 2. 26.
[백준] 10988번 - 팰린드롬인지 확인하기 (Python) 문제 및 풀이 문제) 백준 - 문자열 - 팰린드롬인지 확인하기 https://www.acmicpc.net/problem/10988 10988번: 팰린드롬인지 확인하기 첫째 줄에 단어가 주어진다. 단어의 길이는 1보다 크거나 같고, 100보다 작거나 같으며, 알파벳 소문자로만 이루어져 있다. www.acmicpc.net 문자열의 앞,뒤가 같은지(팰린드롬인지) 확인하는 문제였습니다. Python 소스코드) 2022. 2. 25.
[백준] 21758번 - 꿀 따기 (C++) 문제 및 풀이 문제) 백준 - 그리디 알고리즘 - 꿀 따기 https://www.acmicpc.net/problem/21758 21758번: 꿀 따기 첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다. www.acmicpc.net 벌과 꿀통의 위치에 따라 최대 꿀의 양을 구합니다. 각 벌과 꿀통은 양쪽 끝에 위치해야 꿀의 최대를 가질 수 있습니다. (벌 벌 꿀), (벌 꿀 벌), (꿀 벌 벌) 순서로 최대 꿀의 양을 계산하며 누적 합을 이용하여 빠르게 구할 수 있습니다. C++ 소스코드) 2022. 2. 24.
[백준] 11655번 - ROT13 (C++) 문제 및 풀이 문제) 백준 - 문자열 - ROT13 https://www.acmicpc.net/problem/11655 11655번: ROT13 첫째 줄에 알파벳 대문자, 소문자, 공백, 숫자로만 이루어진 문자열 S가 주어진다. S의 길이는 100을 넘지 않는다. www.acmicpc.net 문자열을 입력받아 하나씩 변환하여 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/11655_ROT13.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutions. Contribute to Chocochip101/BOJ_Solution developmen.. 2022. 2. 24.
[백준] 21317번 - 징검다리 건너기 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 징검다리 건너기 https://www.acmicpc.net/problem/21317 21317번: 징검다리 건너기 산삼을 얻기 위해 필요한 영재의 최소 에너지를 출력한다. www.acmicpc.net 전형적인 동적 계획법으로 쉽게 해결할 수 있는 문제였습니다. solve(i, usedMegajump)를 통해 i 번째 돌까지 갔을때 필요한 최소 에너지의 memoization을 통해 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/21317_%EC%A7%95%EA%B2%80%EB%8B%A4%EB%A6%AC%EA%B1%B4%EB%84%88%EA%B8%B0.cpp .. 2022. 2. 23.
[백준] 20495번 - 수열과 헌팅 (C++) 문제 및 풀이 문제) 백준 - 이분 탐색 - 수열과 헌팅 https://www.acmicpc.net/problem/20495 20495번: 수열과 헌팅 예제에서, 수열의 수들을 차례로 x1, x2, x3이라 하자. -10 ≤ x1 ≤ 30, 25 ≤ x2 ≤ 55, 55 ≤ x3 ≤ 85이다. 만약 (x1, x2, x3) = (28, 25, 70)이라면, x2가 첫번째, x1이 두번째, x3이 세 번째 수가 된다. 또, (x1, x2 www.acmicpc.net 최대, 최소를 배열과 벡터에 저장합니다. 배열에 있는 수는 탐색할 숫자이며 벡터에 있는 수는 정렬을 하여 탐색할 범위입니다. 최솟값을 최댓값이 정렬된 벡터의 lower_bound, 최댓값을 최솟값이 정렬된 벡터의 upper_bound를 통해 인덱스를 구합니다... 2022. 2. 23.
반응형

티스토리툴바