728x90 반응형 개발공부74 [BOJ] 2003번 수들의 합 2 / 사용언어 : 파이썬(python) ※ 문제링크 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net ※ 관련개념 [Algorithm] 투포인터(Two Pointer) 알고리즘 알고리즘 문제를 풀다보면 종종 나오는 투포인터 알고리즘! 막 꼬여가지고 ㅋㅋㅋ 저도 중간에 제대로 못짜고 그러는 경우가 많은데요, 많은 코딩테스트 문제에 등장하는 것은 아니지만 잊을만 butter-shower.tistory.com 해당 문제는 투 포인터 알고리즘을 활용하면 해결할 수 있는 문제였다. 문제를 풀기전 해당 알고리즘의 원리를.. 2022. 2. 16. [BOJ] 1182번 부분수열의 합 / 사용언어 : 파이썬(python) ※ 문제링크 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 해당 문제는 DFS와 백트래킹을 활용하여 모든 경우의 수를 탐색하여 풀 수 있는 문제였다. 기본적인 풀이원리는 입력받은 값들을 바탕으로 길이가 1인 행렬부터 길이가 N인 행렬까지 가능한 모든 경우의 수를 탐색하고 그 합이 요구치와 같으면 값을 더하는 방식으로, 브루스포트 알고리즘과 DFS를 이해하고 있으면 비교적 쉽게 해결할 수 있는 문제였다. 자세한 풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 저장하고,.. 2022. 2. 15. [BOJ] 5014번 스타트링크 / 사용언어 : 파이썬(python) ※ 문제링크 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net 해당 문제는 BFS를 활용하여 해결할 수 있는 문제였다. 주의해야할 점은 건물의 최소 층수가 1층이라는 점과 출발층과 목표층이 같을수 있다는 점이었다. 그 이외에는 BFS와 queuq자료구조를 활용하면 비교적 쉽게 해결할 수 있는 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다. 1. 입력받은 값들을 따로 숫자형태로 저장해준다. 2. 한번에 움직일 수 있는 경우의 수들을 확인하고, 조건에 맞으면 queue자료구조에 넣고 추출하여 방문여부를 확인하는 방식으로 .. 2022. 2. 14. [BOJ] 1715번 카드 정렬하기 / 사용언어 : 파이썬(python) ※ 문제링크 1715번: 카드 정렬하기 정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장 www.acmicpc.net 해당 문제는 우선순위큐 자료구조를 활용해서 풀 수 있는 문제였다. Python에서는 heapq라이브러리를 통해 최소힙을 사용할 수 있기에 해당 라이브러리를 사용해서 문제를 해결했다. 간단하게 풀이방법을 설명하면 자료구조에서 작은 값부터 2번씩 뽑고, 1번째 뽑을때는 단순히 기록만하고, 2번째 뽑을 때는 기록 후 다시 힙 자료구조에 넣어주어 힙 자료구조가 빌 때까지 반복해주면 되는 문제였다. 자세한 문제풀이방법과 코드는 아래와 같다. 1.. 2022. 2. 13. [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. 이전 1 2 3 4 5 6 7 ··· 9 다음 728x90 반응형
