본문 바로가기
728x90
반응형

BOJ71

[BOJ] 11779번 최소비용 구하기 2 / 사용언어 : 파이썬(python) ※ 문제링크 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 해당 문제는 가중치가 있는 최단거리경로를 구하는 것과 관련된 문제로 가중치에 음수가 없으므로 다익스트라 알고리즘을 활용하여 해결할 수 있는 문제였다. 다만 경유하는 도시들의 숫자와 도시들을 같이 출력해줘야하는 것이 문제조건이기에 해당 부분만 추가하면 생각보다 쉽게 해결할 수 있는 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 바탕으로 리스트를 활용하여 그래프를 구현해준다. 2. heapq와 .. 2022. 2. 12.
[BOJ] 2075번 N번째 큰 수 / 사용언어 : 파이썬(python) ※ 문제링크 2075번: N번째 큰 수 첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다. www.acmicpc.net 해당문제는 우선순위큐 자료구조를 통해 값을 저장하고 정렬하여야 풀 수 있는 문제였다. 파이썬에서는 heapq로 해당 자료구조를 지원해주고 있기에 활용하여 해결하였다. 주의해야할 점은 문제의 메모리제한이 상당하기 때문에 입력값을 모두 저장한 후 정렬후 값을 꺼내서 출력하면 안된다는 점이다. 문제의 조건에 의하면 n번째로 입력받은 값들 중 1개값은 무조건 n-1번째로 입력받은 값들 보다 크다는 점을 이용하여 문제를 해결하였다. 자세한 문제풀이방법과 코드는 아래.. 2022. 2. 10.
[BOJ] 1238번 파티 / 사용언어 : 파이썬(python) ※ 문제링크 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net ※ 관련 개념 23. 다익스트라(Dijkstra) 알고리즘 다익스트라(Dijkstra) 알고리즘은 다이나믹 프로그래밍을 활용한 대표적인 최단 경로(Shortest Path) 탐... blog.naver.com 해당문제는 가중치가 있는 단방향 그래프에서 최단거리를 구하는 것과 관련된 문제로 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 다익스트라 알고리즘에 대해 잘 설명해준 사이트를 참조사이트로 걸어놓았으니 개념이.. 2022. 2. 9.
[BOJ] 2644번 촌수계산 / 사용언어 : 파이썬(python) ※ 문제링크 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1 ≤ n ≤ 100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어 www.acmicpc.net 해당문제는 그래프 탐색과 관련된 문제로 BFS, DFS로 해결할 수 있는 문제였다. DFS는 재귀한계를 따로 수정해주지 않으면, recursion 에러가 발생하기에 추가적인 설정을 할 필요가 없는 BFS로 문제를 해결하였다. BFS를 작성하기 위해 파이썬의 deque를 사용하여 문제를 해결하였다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 2차원 리스트를 활용하여 그래프형태로 구현해준다.(문제에서 각각의 간선.. 2022. 2. 8.
[BOJ] 11057번 오르막수 / 사용언어 : 파이썬(python) ※ 문제링크 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 해당 문제는 동적프로그래밍과 관련된 문제로 단순 반복문으로도 답을 구할 수 있지만 메모리와 속도를 문제의 조건에 맞게 하기 위해서는 메모이제이션을 활용해야하는 문제였다. 모든 동적프로그래밍의 문제가 그렇듯 점화식이 존재한다고 가정하고, n = 1부터 4까지의 값들을 보며 규칙을 찾아보았다. 확인결과 발견한 규칙은 아래와 같다. 0__ 1__ 2__ 3__ 4__ 5__ 6__ 7__ 8__ 9__ 1 1 1 1 1 .. 2022. 2. 7.
[BOJ] 11726번 2xn 타일링 / 사용언어 : 파이썬(python) ※ 문제링크 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 해당 문제는 메모이제이션 개념과 피보나치 수열의 개념을 이해하면 풀 수 있는 문제였다. 점화식 도출을 위해 간단하게 n = 1부터 n = 5까지 결과값을 생각해봤다. 각각의 n의 값이 1, 2, 3, 4, 5일때 결과값은 1, 2, 3, 5, 8이 도출되는 것을 확인하였고, n이3이상일때부터는 f(n) = f(n-1) + f(n-2)인것을 추론하여 문제에 대입해보았더니 해결이 되었다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력값을 바탕으로 메모이제이션을 적용하여 결.. 2022. 2. 1.
[BOJ] 10282번 해킹 / 사용언어 : 파이썬(python) ※ 문제링크 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 해당문제는 다익스트라 알고리즘을 활용하여 풀 수 있는 문제였다. 입력받은 값들로 그래프를 구현하고 다익스트라로 최단거리를 구해준 후 이어져 있는 컴퓨터의 수와 최대 시간만 출력해주면 되었기에 생각보다 쉽게 해결할 수 있었다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들과 2차원 리스트를 활용하여 그래프를 구현해준다. 2. 각각의 컴퓨터들로 갈 수 있는 최단시간을 구하기 위한 다익스트라 함수를 작성해준다. 3. 입력받은 값들로 결과값을 출력해.. 2022. 1. 30.
[BOJ] 1854번 K번째 최단경로 찾기 / 사용언어 : 파이썬(python) ※ 문제링크 1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 해당문제는 다익스트라를 활용하여 풀 수 있는 문제였다. 가중치가 있는 최단경로를 구하는 문제에서 조금 더 나아간 문제로, 간선으로 이어져있는 도시들을 k번째 수가 구해질때까지만 반복시키는 것이 핵심인 문제였다. 해당 부분은 메모이제이션과 정렬을 반복함으로써 해결하였으며, 테스트 결과 정상적으로 작동하는 것으로 확인했다. 다만, sys를 사용하고도 3528ms가 걸리는 것으로 확인했기에 sys를.. 2022. 1. 30.
[BOJ] 2665번 미로만들기 / 사용언어 : 파이썬(python) ※ 문제링크 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 해당문제는 우선순위큐 자료구조와 BFS를 활용하여 풀 수 있는 문제였다. 최단거리를 구하는 것이 아닌 최대한 적게 방을 바꾸는 길을찾는 것이 문제의 조건이었기에 최소힙을 활용하여 문제를 해결하였다. 문제풀이방법에 대해 간단하게 설명하면, BFS함수를 통해 4방위를 탐색하고, 탐색할때마다 가중치도 함께 저장하여, 가장 작은 가중치부터 꺼내는 방식으로 길을 찾아서 배열의 마지막 지점에 도달하면 탐색을 종료하고, 결과값을 출력하면 문제를 해결할 수 있었다.. 2022. 1. 30.
728x90
반응형

티스토리툴바