본문 바로가기

파이썬

 (320)
[Python] 2669번 직사각형 네개의 합집합의 면적 구하기 2669번: 직사각형 네개의 합집합의 면적 구하기 (acmicpc.net) 2669번: 직사각형 네개의 합집합의 면적 구하기 입력은 네 줄이며, 각 줄은 직사각형의 위치를 나타내는 네 개의 정수로 주어진다. 첫 번째와 두 번째의 정수는 사각형의 왼쪽 아래 꼭짓점의 x좌표, y좌표이고 세 번째와 네 번째의 정수는 사각 www.acmicpc.net 22/09/08 이 문제 또한 브론즈 문제 치고는 독특한 아이디어를 가지고 있다. 얼핏 봐서는 기하학 문제처럼 보이지만, 그렇게 풀면 정말 어렵고, 직접 그림을 그림으로써 해결하는 문제이다. 문제 접근 방식: 그냥 직접 그림을 스케치북에 그리듯이 그림으로써 해결한다. 좌표를 2차원좌표로 받고 거기에 해당하는 곳을 모두 1로 바꿔주면 구현 끝! 어렵게 생각하면 오히..
[Python] 1236번 성 지키기 1236번: 성 지키기 (acmicpc.net) 1236번: 성 지키기 첫째 줄에 성의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 성의 상태가 주어진다. 성의 상태는 .은 빈칸, X는 경비원이 있는 칸이다 www.acmicpc.net 22/09/08 그룹 채점 현황에서 무작위로 골라서 푼 문제로, 의외로 브론즈 문제 치고는 재미있는 아이디어를 가진 문제 같아서 흥미로웠다. 문제 접근 방식: 'X'표시가 되어있는 곳은 이미 경비원이 지키고 있는 줄이라는 뜻이다. 나는 성의 모습을 입력받고, 각 줄에 경비원이 있는지 확인하는 row_check, col_check 리스트를 1로 초기화하며 선언해주었다. 성의 모습을 확인하며, 만약 경비원이..
[Python] 11659번 구간 합 구하기 4 11659번: 구간 합 구하기 4 (acmicpc.net) 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 22/09/08 누적 합 알고리즘을 사용하여 해결할 수 있는 전형적인 문제로, 만약 이 문제를 해결하고 싶다면 누적 합 알고리즘에 관해서 조금 알아두는 것이 편할 것이다. 문제 접근 방식: 그냥 누적 합 알고리즘을 그대로 구현한 것이다. 누적 합 알고리즘은 위와 같은 상황처럼 부분 합을 구하는데 그 쿼리의 양이 감당할 수 없을 정도로 많을 때, 이를 쉽게 구하고자 고안된 알고리즘으로..
[Python] 1711번 직각삼각형 1711번: 직각삼각형 (acmicpc.net) 1711번: 직각삼각형 첫째 줄에 점의 개수 N(3 ≤ N ≤ 1,500)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 좌표값은 절댓값이 1,000,000,000을 넘지 않는 정수이며, 주 www.acmicpc.net 22/09/08 그룹 연습에서 풀다가 실패했던 문제로, 다시 풀어서 맞았습니다! 를 받은 문제이다. 단순한 브루트 포스이지만, 맞왜틀을 많이 당한 문제로, 지금 다시 보니 for문과 combinations의 차이점을 느낄 수 있었던 문제였던 것 같다. 문제 접근 방식: 단순 무식하게 그냥 세 점을 잡아서, 세 점의 길이 중 가장 긴 변의 제곱이 나머지 두 변의 길이의 제곱의 합과 같은지..
[Python] 15645번 내려가기 2 15645번: 내려가기 2 (acmicpc.net) 15645번: 내려가기 2 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 22/09/07 이전에 북마크 해놓았던 문제 중 하나로, 무난하게 풀 수 있었던 dp문제였다. 이전에 비슷한 문제를 풀어서 쉽게 풀 수 있었다. 문제 접근 방식: 사실 dp류의 문제는 아이디어만 알면 구현하는 것 자체는 그렇게 어렵지 않은 문제가 꽤 많다. 이것도 그러한데, 아이디어는 다음과 같다. 각각의 dp리스트를 정의해주었다. 총 6개가 존재하는데, 예를 들면 다음과 같다. first_line_min[N]은 내가 ..
[Python] 4470번 줄번호 / 23803번 골뱅이 찍기 - ㄴ / 23804번 골뱅이 찍기 - ㄷ 4470번: 줄번호 (acmicpc.net) 4470번: 줄번호 텍스트에서 줄을 입력받은 뒤, 줄 번호를 출력하는 프로그램을 작성하시오. www.acmicpc.net 23803번: 골뱅이 찍기 - ㄴ (acmicpc.net) 23803번: 골뱅이 찍기 - ㄴ 서준이는 아빠로부터 골뱅이가 들어 있는 상자를 생일 선물로 받았다. 상자 안에는 ㄴ자 모양의 골뱅이가 들어있다. ㄴ자 모양은 가로 및 세로로 각각 5개의 셀로 구성되어 있다. 상자에는 정사 www.acmicpc.net 23804번: 골뱅이 찍기 - ㄷ (acmicpc.net) 23804번: 골뱅이 찍기 - ㄷ 서준이는 아빠로부터 골뱅이가 들어 있는 상자를 생일 선물로 받았다. 상자 안에는 ㄷ자 모양의 골뱅이가 들어있다. ㄷ자 모양은 가로 및 세로로 ..
[Python] 7576번 토마토 7576번: 토마토 (acmicpc.net) 7576번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M,N ≤ 1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토 www.acmicpc.net 22/09/04 이 문제는 전형적인 BFS문제이고, 클래스에도 있는 전형적인 문제이다. 하지만 나는 이 문제에 대해서 특별한 추억을 가지고 있다. 때는 내가 BFS알고리즘을 배우지도 않은 PS 문제풀이 초반 시점에, 나는 호기롭게 이 문제에 도전했었다. 그냥 단순무식하게 깡 구현과 시뮬레이션으로 이 문제에 도전했었고, 당연히 실패했었다. 그리고 4달이 지난 후, BFS알고리즘을 배우고 나서 강해진 나는..
[Python] 2381번 최대 거리 2381번: 최대 거리 (acmicpc.net) 2381번: 최대 거리 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 각 좌표의 범위는 -1,000,000이상 1,000,000이하이다. www.acmicpc.net 22/09/03 그룹 연습에서 풀었던 문제이다. 이 문제는 애드혹 태그에 속하는데, 발상이 골드 3에 걸맞은 발상이라고 생각한다. 나 같은 경우 이 문제의 해답의 일부분을 어딘가에서 봤던 기억이 났기 때문에 풀 수 있었다. 문제 접근 방식: 이 문제의 시간제한은 1초이고, 파이썬 시간제한을 기준으로 하면 3초인데, 만약 그냥 두 점을 비교하는 방식으로 푼다면 입력의 크기가 50000*50000 = 25억이기 때문에 절대로 시간 내에 풀지 못한다. 따라서 시간 ..

티스토리툴바