본문 바로가기

알고리즘204

[백준] 14889번 - 스타트와 링크 (Python) 문제 및 풀이 문제) 백준 - 완전 탐색 - 스타트와 링크 https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 최대 인원 수가 20명이므로 완전 탐색으로 해결할 수 있습니다. Python의 Combination을 활용하여 팀을 나눕니다. 나눈 팀의 능력치 차이의 최솟값을 구하여 해결할 수 있습니다. Python 소스코드) 2022. 4. 3.
[백준] 2250번 - 트리의 높이와 너비 (C++) 문제 및 풀이 문제) 백준 - 트리 - 트리의 높이와 너비 https://www.acmicpc.net/problem/2250 2250번: 트리의 높이와 너비 첫째 줄에 노드의 개수를 나타내는 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 각 줄마다 노드 번호와 해당 노드의 왼쪽 자식 노드와 오른쪽 자식 노드의 번호가 순서대로 주어진다. www.acmicpc.net 트리의 중위 선회를 통해 해방 레벨에서의 최소 idx와 최대 idx를 memo 합니다. 그 후, 1부터 N까지 너비의 최댓값을 찾아 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/2250_%ED%8A%B8%EB%A6%A.. 2022. 3. 18.
[백준] 13302번 - 리조트 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 리조트 https://www.acmicpc.net/problem/13302 13302번: 리조트 수영이는 여름방학을 맞이하여 많은 놀이 시설이 있는 KOI 리조트에 놀러가려고 한다. 리조트의 하루 이용권의 가격은 만원이다. 하지만 리조트의 규모는 상상을 초월하여 모든 시설을 충분히 www.acmicpc.net 날짜와 쿠폰의 개수를 memoization하여 문제를 해결합니다. 쿠폰, 하루권, 3일권, 5일권을 각각 사용할 경우의 최소비용을 구합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Solution/13302_%EB%A6%AC%EC%A1%B0%ED%8A%B8.cpp GitH.. 2022. 3. 18.
[백준] 2075번 - N번째 큰 수 (C++) 문제 및 풀이 문제) 백준 - 우선수위 큐 - N번째 큰 수 https://www.acmicpc.net/problem/2075 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net N * N개의 모든 수를 저장하고 정렬해서 N번째 큰 수를 구하기에는 메모리 제한이 12MB이기에 불가능합니다. 대부분의 정렬 문제는 우선순위 큐로 해결할 수 있습니다. 우선순위 큐를 최소 힙으로 사용하여 문제를 해결했습니다. Input을 최소 힙에 push 하면서 최소 힙이 N개가 되게 유지합니다. 그 후, top을 출력하면 해답을 구할 수 있습니다. C+.. 2022. 3. 17.
[백준] 9935번 - 문자열 폭발 (C++) 문제 및 풀이 문제) 백준 - 문자열 - 문자열 폭발 https://www.acmicpc.net/problem/9935 9935번: 문자열 폭발 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다. 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다. 두 문자열은 모 www.acmicpc.net ans에 문자열을 더하면서 폭발 문자열의 끝과 확인하여 만약 같을 경우 폭발 문자열 전체를 확인하여 같을 경우 pop 합니다. C++ 소스코드) 2022. 3. 17.
[백준] 1613번 - 역사 (C++) 문제 및 풀이 문제) 백준 - 플로이드 와샬 - 역사 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 전/후 관계가 있는 역사 사건들이 주어질 때, 임의의 두 사건의 전/후 관계를 구하는 문제였습니다. 사건의 개수가 최대 400이므로 플루이드 와샬 알고리즘(O(N^3))으로 해결할 수 있습니다. >, < 관계를 1, -1로 저장하여 같은 전/후 관계끼리만 비교가 가능하므로 update 합니다. C++ 소스코드) 2022. 3. 16.
[백준] 1963번 - 소수 경로 (C++) 문제 및 풀이 문제) 백준 - BFS - 소수 경로 https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 주어진 첫 소수의 한 자리를 바꾸어 두 번째 소수를 만들 수 있는 최소 변환 수를 구하는 문제였습니다. 에라토스테네스의 체를 활용하여 10000 이하에 대하여 소수 판별(isPrime)을 진행합니다. 그 후 주어진 수의 첫자리부터 4번째 자리까지 변환하면서 소수이면서 방문하지 않은 수에 대하여 queue에 push 하여 BFS를 진행합니다. C++ 소스 코드) Full.. 2022. 3. 16.
[백준] 1261번 - 알고스팟 (C++) 문제 및 풀이 문제) 백준 - 다익스트라 - 알고스팟 https://www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net 0 또는 1로 가중치가 있는 간선이 존재하기 때문에 다익스트라 알고리즘으로 해결했습니다. 간선과 좌표를 우선순위 큐에 push 하여 구현하며 가중치가 더 적을 간선이 들어올 경우 upadte 합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/S.. 2022. 3. 14.
[백준] 14620번 - 꽃길 (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 꽃길 https://www.acmicpc.net/problem/14620 14620번: 꽃길 2017년 4월 5일 식목일을 맞이한 진아는 나무를 심는 대신 하이테크관 앞 화단에 꽃을 심어 등교할 때 마다 꽃길을 걷고 싶었다. 진아가 가진 꽃의 씨앗은 꽃을 심고나면 정확히 1년후에 꽃이 피므 www.acmicpc.net 백트래킹으로 꽃을 심어가면서 최소 비용을 구합니다. C++ 소스코드) 2022. 3. 13.
반응형

티스토리툴바