본문 바로가기
728x90
반응형

코딩/백준

알고리즘 - Python / 백준 - 2252번 : 줄 세우기 2252번: 줄 세우기 (acmicpc.net) 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 풀이 줄을 세울 때 , 어떤 사람이 어떤 사람 앞에 있어야 한다는 조건들을 가지고 줄을 세울 수 있는 경우를 출력하면 되는 문제다. 만약 4 2의 경우 4번 사람이 2번 사람 앞에 서야 한다는 이야기이다. 모든 조건을 배열에 저장하고 큐를 이용해 위상 정렬을 구현하였다. 1. 모든 노드를 검사해 그 노드의 진입 차수가 0이 라면 큐에 추가한다. ( 노드 간 간선 정보 , .. 더보기
알고리즘 - Python / 백준 - 6571번 : 피보나치 수의 개수 6571번: 피보나치 수의 개수 (acmicpc.net) 6571번: 피보나치 수의 개수 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 음이 아닌 두 정수 a와 b로 이루어져 있다. 입력의 마지막 줄에는 0이 두 개 주어진다. (a ≤ b ≤ 10100) 두 수 a와 b는 0으로 www.acmicpc.net 풀이 구간 내에 존재하는 피보나치 수의 개수를 찾는 문제다. 범위가 그리 크지 않아 전체 범위 안의 피보나치 수를 찾고 , 피보나치 수 배열을 통해 구간 내에 얼마나 존재하는지 확인하였다. import sys fibo = [1,1];t = 1 while fibo[-1] < 10**100: fibo.append(fibo[t]+fibo[t-1]) t += 1 while True: .. 더보기
알고리즘 - Python / 백준 - 1806번 : 부분합 1806번: 부분합 (acmicpc.net) 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 풀이 부분합과 투 포인터를 사용하는 기본적인 문제다. 부분합을 통해 배열의 일정 부분의 합을 쉽게 구할 수 있고 , 투 포인터를 활용해서 조건을 만족하는 구간의 길이를 찾으면 된다. 배열의 합이 일정 값 이상이 될 때 까지 뒤쪽 포인터를 전진시키고 해당 값이 만족되면 해당 값이 만족되지 않을 때까지 다시 앞쪽 포인터를 전진시킨다. 앞쪽 포인터가 전진하면서 다시 배열의 합이 일정 값 이하가 되면 다시 조건.. 더보기
알고리즘 - Python / 백준 - 17404번 : RGB거리 2 17404번: RGB거리 2 (acmicpc.net) 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 RGB 거리 1 문제에 1번째 집과 마지막 집의 색이 다르게 해야 한다는 조건만 추가된 문제다. RGB 문제 역시 점화식을 통해 DP로 해결가능한 문제이므로 DP로 접근해 문제를 풀었다. RGP 거리 1 문제와 다른점은 선택 가능한 마지막 집이 첫 번째 집과 색이 겹치지 않아야 한다는 것이다. 따라서 DP 배열을 3개 만들어 첫번째 집이 R , G , B 인 경우로 두고 모두 .. 더보기
알고리즘 - Python / 백준 - 11049번 : 행렬 곱셈 순서 11049번: 행렬 곱셈 순서 (acmicpc.net) 11049번: 행렬 곱셈 순서 첫째 줄에 입력으로 주어진 행렬을 곱하는데 필요한 곱셈 연산의 최솟값을 출력한다. 정답은 231-1 보다 작거나 같은 자연수이다. 또한, 최악의 순서로 연산해도 연산 횟수가 231-1보다 작거나 같 www.acmicpc.net 풀이 DP 문제 중 유명한 문제인 행렬 곱셈 순서 문제다. 행렬의 곱셈 순서 문제를 작은 문제 단위로 나누었을 때 , 이전 단계의 문제가 다음 문제를 푸는데 도움을 준다. 따라서 DP를 사용해 풀 수 있다. 예를 들어 M1 * M2 * M3 * M4의 경우 M1 * M2 / M2 * M3 / M3 * M4 곱을 먼저 구하였다면 , 이후 M1 * M2 * M3 / M2 * M3 * M4의 경우에도 .. 더보기
알고리즘 - Python / 백준 - 1011번 : Fly me to the Alpha Centauri 1011번: Fly me to the Alpha Centauri (acmicpc.net) 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 어느 구간을 우주선이 이동한다고 가정할 때 , 움직일 수 있는 거리는 이전 움직인 거리에 +1 , +0 , -1 한 경우이다. 출발과 도착 구간을 1만큼 움직이며 , 가장 적게 움직이는 횟수를 구하는 문제다. 어느 구간을 최소 횟수로 도달하는 가장 직관적인 방법은 1 , 2 , 3... k , k-1 , k-2... 2 , .. 더보기
알고리즘 - Python / 백준 - 1490번 : 자리수로 나누기 1490번: 자리수로 나누기 (acmicpc.net) 1490번: 자리수로 나누기 첫째 줄에 어떤 수 N이 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 어떤 수 N이 주어졌을 떄 , N으로 시작하면서 N의 모든 자리수로 나누어 떨어지는 수를 찾는 문제이다. 어떤 수 N의 모든 자리수로 나누어 진다는 것은 , N의 모든 자리수의 최소공배수로 나누어 떨어진다는 것을 의미한다. 따라서 LCM을 활용해 최소공배수를 구하여 활용하면 연산시간을 조금이나마 더 줄일 수 있다. 각 자리수에 대해 전체 최소공배수를 구한 후 , N 뒤쪽에 자리수를 늘려가며 숫자를 붙여 최소공배수로 나누어 떨어질 때 break 하도록 두었다. PyPy3 채점환경에는 아직 math... 더보기
알고리즘 - Python / 백준 - 1323번 : 숫자 연결하기 1323번: 숫자 연결하기 (acmicpc.net) 1323번: 숫자 연결하기 첫째 줄에 N과 K가 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. K는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 숫자를 연결하면서 k로 나누었을 때 나누어 떨어지는 수를 찾고 그때 몇번 이어붙여야 하는지 구하는 문제이다. 먼저 갈피를 잡아보기 위해 예제 케이스인 2 9를 실행하고 나오는 나머지들을 모두 확인하였다. 나열된 나머지들은 2 4 6 8 1 3 5 7 0 2 4 6 8 1 3 5 7 ... 로 확인한 결과, 패턴을 이루고 있었다. 2 9 의 경우는 2 4 6 8 1 3 5 7 0 이고 이때 처음으로 0이 나오는 9가 정답이 된다. 따라서 n % k 의 범위는.. 더보기
반응형

티스토리툴바