본문 바로가기

알고리즘/백준 문제 풀이

 (338)
[Python] 4349번 Blocks https://www.acmicpc.net/problem/4349 4349번: Blocks Donald wishes to send a gift to his new nephew, Fooey. Donald is a bit of a traditionalist, so he has chosen to send a set of N classic baby blocks. Each block is a cube, 1 inch by 1 inch by 1 inch. Donald wants to stack the blocks together into a rectangu www.acmicpc.net 22/09/24 브론즈 문제 치고는 살짝 당황하게 만드는 난이도를 가진 문제로, 애를 살짝 먹었다. 개인적으로는 브론즈 2가 아니라 ..
[Python] 1455번 뒤집기 II https://www.acmicpc.net/problem/1455 1455번: 뒤집기 II 세준이는 동전 뒤집기를 하려고 한다. 세준이는 동전을 N×M개 가지고 있다. 동전은 세로로 N개, 가로로 M개 크기의 직사각형에 차곡차곡 놓여져 있다. 동전의 앞면을 0이라고 하고 뒷면을 1이라고 www.acmicpc.net 22/09/23 전형적인 그리디 문제로, 문제 상황을 잘 시뮬레이션하면 되는 문제이다. 문제 접근 방식: 먼저, 문제 상황을 보자. 문제는 모든 동전을 뒤집어서 앞면으로 만들고자 하는 것이 목표이고, 그때의 뒤집는 횟수를 최소화하고 싶은 것이 최종적인 목표이다. 한 동전을 선택하면, 맨 위의 좌측 동전부터 선택한 동전까지, 그 직사각형에 해당하는 영역만큼의 동전이 모두 뒤집힌다는 사실을 보고,..
[Python] 10255번 교차점 https://www.acmicpc.net/problem/10255 10255번: 교차점 이제 사각형의 경계선과 선분의 교차점에 관한 간단한 기하 문제를 풀어볼 것이다. 매우 다행히도 사각형은 항상 축에 평행한 형태로만 놓여 있다. 어떤 사각형과 어떤 선분의 교차점은 항상 0 www.acmicpc.net 22/09/22 선분 교차 알고리즘을 조금 응용한 문제로, 약간의 아이디어가 있어야하는 문제이다. 문제 접근 방식: 무작정 선분 교차 알고리즘을 4번 적용하여 문제를 풀어버리면 조금 난감하다. 왜냐하면, 모서리에만 선이 닿는다고 했을 때, 실제로는 선분과 직사각형이 한 점에서만 만나지만, 선분 교차 알고리즘이 만나는 모서리를 포함하는 두 직선에 대해서 모두 실행되기 때문에 두 점에서 만나는 것으로 오해 ..
[Python] 20149번 선분 교차 3 (추후 보강 예정) https://www.acmicpc.net/problem/20149 20149번: 선분 교차 3 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. www.acmicpc.net 22/09/22 선분 교차 2 문제를 풀었다면 거기에 교점을 구하는 코드를 추가로 집어넣음으로써 문제를 풀 수 있다. 문제 접근 방식: 이 문제를 풀기 전에 선분 교차 2 문제를 풀기를 권장한다. 먼저 CCW알고리즘과 이를 응용한 선분 교차 알고리즘을 이해하고 있다는 가정 하에서 서술하겠다. 선분 교차 알고리즘에 관한 글을 추후에 작성한다면 여기에 글을 덧붙일 예정이다. 어떤 선분이 교차하는지 교차하지 않는지 판단을 했다면, 그 교점을 구해야 한다. 그러면..
[Python] 3108번 로고 https://www.acmicpc.net/problem/3108 3108번: 로고 로고는 주로 교육용에 쓰이는 프로그래밍 언어이다. 로고의 가장 큰 특징은 거북이 로봇인데, 사용자는 이 거북이 로봇을 움직이는 명령을 입력해 화면에 도형을 그릴 수 있다. 거북이는 위치와 www.acmicpc.net 22/09/22 유니온-파인드(분리 집합)와 두 직사각형이 만나는 함수를 섞으면 쉽게 풀 수 있는 문제이다. 유니온-파인드의 기본 난이도가 골드 5인데, 이 문제에서 유니온-파인드를 사용해야 된다는 점을 캐치하는 것, 그리고 두 직사각형이 만나는 함수를 구현하는 난이도, 그리고 약간의 예외처리를 고려하자면 저 난이도는 굉장히 적절한 난이도라고 생각한다. 문제 접근 방식: PU명령은 펜을 떼라는 명령이다. 이 ..
[Python] 10844번 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 22/09/22 전형적인 2차원 DP문제로, 그렇게 어렵진 않다. 푸는 유형만 알고 있다면 굉장히 쉽게 풀 수 있다. 문제 접근 방식: 비슷한 유형의 문제 중에서 오르막 수라는 문제가 있다. 이와 비슷하게 접근하면 되는데, 여기서 DP의 정의를 다음과 같이 정의하자. DP[i][j] = 자리가 i자리 숫자일 때, 숫자가 j로 끝나는 계단 수의 개수 그러면 계단수의 정의 상, 바로 이전의 숫자가 1만큼만 차이가 나야 하므로, DP[i][0] = DP[i-1][1] DP[i][1] = DP[i-1][0] + DP[..
[Python] 11053번 가장 긴 증가하는 부분 수열 https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 22/09/21 전형적인 유명한 DP문제. 그리고 그렇게 어렵지도 않은 DP문제이다. 문제 접근 방식: DP[i] = A[i]를 마지막 값으로 가지는 가장 긴 부분 수열의 길이라고 정의하자. 그러면 O(n^2)의 시간 복잡도로 우리는 이 문제를 해결할 수 있다. DP[i] = A[i] > A[j] (i > j)가 성립되..
[Python] 1629번 곱셈 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 22/09/21 파이썬의 강력함. 그 한 줄이면 충분하다. 문제 접근 방식: 파이썬의 기본 내장 함수 중 pow함수는 어떤 숫자를 거듭제곱한 것을 특정 숫자로 나누는 연산을 지원한다. 또한, 기본적으로 pow함수의 거듭제곱의 원리가 분할 정복을 이용한 거듭제곱이라 매우 빠르다. 제일 그 풀이가 간단해서 그 풀이로 문제를 풀었다. 이후에 만약 행렬 거듭제곱문제를 풀게 된다면 새롭게 함수를 구현해야 하긴 한다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드..

티스토리툴바